CPU 스케줄링
1.
CPU-I/O 버스트 사이클
•
프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성되는데, 프로세스들은 이 두 상태를 주기적으로 반복한다.
•
프로세스가 실행되면 연산과 작업의 처리 위주의 CPU 버스트가 시작되고, 입출력 장치를 사용하게되면 I/O 버스트가 발생하고, 다시 CPU 버스트가 발생하고의 반복이다.
•
여러 프로세스들의 CPU 버스트의 지속 시간과 발생빈도를 측정해보면 아래와 같은 초지수형(hyperexponential) 그래프로 나타난다. I/O 위주의 프로그램은 CPU 버스트 시간이 짧고 자주 발생하고 이를 I/O bounded 프로그램이라 부른다. 반대로 CPU 연산 위주의 프로그램은 긴 CPU들이 적은 빈도로 발생하고 이를 CPU bounded 프로그램이라 부른다.
•
이러한 프로그램의 특성은 CPU 스케줄링 알고리즘을 선택하고 구현할 때 중요한 지표가 될 수 있다.
2.
CPU 스케줄러
•
CPU가 유휴 상태가 될 때마다 운영체제는 준비 큐에 있는 프로세스들 중에 하나의 프로세스를 선택하여 실행되는데, 프로세스 선택은 CPU 스케줄러에 의해 수행된다.
•
준비 큐는 선입선출 방식의 큐일수도 있고 우선순위 큐 혹은 트리나 연결 리스트로 구현될 수 있다. 준비 큐에는 일반적으로 프로세스의 프로세스 제어 블록(PCB)가 들어가 있다.
3.
선점 및 비선점 스케줄링
•
CPU 스케줄링이 발생하는 상황은 다음과 같다.
◦
실행 중인 프로세스가 I/O 요청이나 wait()과 같은 시스템 콜을 받아 대기 상태로 전환될 때
◦
인터럽트가 발생하여 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때
◦
I/O 작업의 완료로 인해 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때
◦
실행 중인 프로세스가 작업을 완료하여 종료될 때
•
비선점형(nonpreemptive) 스케줄링 혹은 협조적(cooperative) 스케줄링은 위의 상황 중 1번과 4번처럼 실행 중인 프로세스가 자발적으로 대기 상태로 전환되는 경우에만 스케줄링이 발생하는 스케줄링 방법이다.
•
선점형(preemptive) 스케줄링은 실행 중인 프로세스가 자발적으로 대기 상태가 전환되지 않더라도 특정 조건이 되면 강제로 대기 상태로 전환되고 다른 프로세스를 실행시키는 스케줄링 방법이다. 최신의 거의 모든 운영체제는 선점형 스케줄링 방식을 사용한다.
4.
디스패처
•
디스패처(dispatcher)는 다음 실행할 프로세스나 스레드를 선택하고, 선택한 프로세스나 스레드에 CPU의 제어를 넘겨주는 모듈로, 스케줄러의 하위 구성요소이며 프로세스와 스레드의 실행을 조정하는 역할을 하는 커널의 일부분이다.
•
디스패치가 하는 역할은 다음과 같다.
◦
디스패처는 스케줄링 알고리즘에 따라 다음에 어떤 프로세스나 스레드를 실행할지 선택한다.
◦
디스패처는 선택된 프로세스나 스레드에 CPU를 할당하기 전에, 이전에 실행하던 프로세스나 스레드의 상태를 저장하고 선택된 프로세스나 스레드의 상태를 복원하는 문맥 교환 작업을 수행한다.
◦
디스패처는 선택된 프로세스나 스레드에 메모리나 입출력 장치 등 필요한 자원과 함께 CPU를 할당한다.
•
디스패치는 문맥 교환 시마다 호출되는데, 디스패처가 하나의 프로세스를 정지하고 다음 프로세스를 실행하기까지 소요되는 시간을 디스패치 지연(dispatch latency)이라 한다.
스케줄링 기준
•
CPU 스케줄링 알고리즘의 특성을 잘 고려하여 선택하기 위해 스케줄링 알고리즘의 몇 가지 기준이 있다.
◦
CPU 이용률(utilization)
◦
처리량(throughput)
◦
총처리 시간(turnaround time)
◦
대기 시간(waiting time)
◦
응답 시간(response time)
스케줄링 알고리즘
1.
선입 선처리(FCFS, First-Come First-Served) 스케줄링
•
가장 간단한 스케줄링 알고리즘으로, CPU에 먼저 요청한 프로세스가 먼저 CPU를 할당받는 방법이다.
•
비선점형 스케줄링 방식
•
선입선출(FIFO) 큐를 통해 쉽게 관리할 수 있다.
•
평균 대기시간이 매우 길어지는 경우가 발생할 수 있다.
◦
프로세스 P1은 24 ms, P2는 3 ms, P3가 3 ms의 버스트 시간을 가지고 1, 2, 3의 순으로 CPU 요청한 상황이다.
◦
FCFS 스케줄링 방식으로 스케줄링한다면 위 그림과 같은 Gantt 차트를 얻을 수 있는데, 프로세스의 평균 대기시간은 (0 + 24 + 27) / 3 = 17ms이다.
◦
하지만 순서를 조금만 바꿔 위와 같이 스케줄링한다면 (6 + 0 + 3) / 3 = 3ms의 평균 대기시간을 가진다.
◦
이처럼 하나의 긴 처리 시간을 가진 프로세스가 CPU를 먼저 차지하게 되면 다른 모든 프로세스들이 오랜 시간 기다려야해서 전체적인 시스템 성능이 저하된다. 이런 현상을 호위 현상(convey effect)라 부른다.
2.
최단 작업 우선(SJF, Shortest Job First) 스케줄링
•
대기 중인 프로세스들의 다음 CPU 버스트의 길이를 예측하여, 그 중 가장 짧은 CPU 버스트를 가진 프로세스를 할당하는 방법이다.
•
비선점형 스케줄링 방식
•
최소의 평균 대기 시간을 가진다.
•
CPU 버스트의 길이를 정확하게 알아낼 방법이 없기 때문에, 이전 CPU 버스트들의 길이들의 지수 평균으로 예측 값을 사용한다.
•
짧은 CPU 버스트 타임을 가진 프로세스들이 연속적으로 CPU를 차지하면, CPU 버스트가 긴 프로세스에 차례가 돌아오지 않는 기아(Starvation)가 발생할 수 있다.
•
CPU의 대기시간에 따른 우선 순위를 두어 기아 현상을 개선하려는 HRN(Highest Response Ratio Next) 방식이 있으나, 여전히 공평성이 낮아 잘 사용되지 않는다.
3.
라운드 로빈(RR, Round-Robin) 스케줄링
•
시간 할당량(time quantum) 혹은 타임 슬라이스(time slice)라고 불리는 작은 시간 단위를 기준으로, 선입선처리 방식에서 하나의 프로세스가 한 번의 타임 슬라이스만큼 CPU를 점유하고 다시 준비 큐로 돌아가는 방법이다. 일반적으로 한번의 타임 슬라이스는 10 ~ 100ms정도를 가진다.
•
선점형 스케줄링 방식
•
타임 슬라이스가 줄어들수록 잦은 문맥교환이 발생하여 그로 인한 오버헤드가 발생한다. 반대로 타임 슬라이스가 너무 크다면 FCFS 스케줄링 방식의 단점을 그대로 가져오게 된다.
4.
우선순위(Priority) 스케줄링
•
CPU를 우선순위가 높은 프로세스부터 할당하는 방식으로, 우선순위가 같다면 FCFS 순서로 스케줄링 하는 방법이다.
•
일반적으로 선점형 스케줄링 방식을 말하지만, 선점형과 비선점형 둘 다의 방식으로 구현 가능하다.
•
SJF 방식은 CPU 버스트 시간을 기준으로 우선순위를 정한 일종의 우선순의 알고리즘이다.
•
우선순위의 기준은 설계 방식에 따라 다르지만 주로 시간 제한이나 메모리 요구, 열린 파일의 수, 평균 I/O 버스트, 평균 CPU 버스트 등의 지표가 사용된다.
•
우선순위 스케줄링도 우선순위가 낮은 프로세스가 무한히 CPU 점유를 못하게 되는 기아(Starvation) 현상이 발생한다. 이에 대한 해결책으로 대기 시간이 길어질수록 우선 순위가 높아지는 노화(aging) 방식이 있다.
5.
다단계 큐(Multi-Level Queue) 스케줄링
•
스케줄링 큐를 단일 큐에 두고 그 중 검색이나 선택을 하는 것이 아니라, 우선순위가 다른 여러 개의 큐를 단계적으로 두고 남은 프로세스 중 우선순위가 가장 높은 큐에서만 꺼내서 사용하는 방법이다. 같은 큐 내에서는 라운드-로빈 방식으로 동작한다.
•
일반적으로 선점형 스케줄링 방식을 말하지만, 선점형과 비선점형 둘 다의 방식으로 구현 가능하다.
•
다단계 큐 스케줄링도 우선순위가 낮은 큐에 대기하는 프로세스가 무한히 CPU 점유를 못하게 되는 기아(Starvation) 현상이 발생할 수 있다.
6.
다단계 피드백 큐(Multi-Level Feedback Queue) 스케줄링
•
다단계 큐 스케줄링 방식에서 CPU를 차지한 프로세스가 다시 대기 큐로 돌아갈 때 우선순위를 낮춰서 돌아가는 방식이다.
•
선점형 스케줄링 방식
•
다단계 피드백 큐 스케줄링도 다단계 큐와 마찬가지로 기아(Starvation) 현상이 발생할 수 있다. 하지만 다단계 피드백 큐에서는 큐 간의 이동하는 것을 허용하기 때문에, 대기 시간이 길어질수록 우선 순위가 높이는 노화(aging) 방식으로 해결할 수 있다.
스레드 스케줄링
•
대부분의 최신 운영체제에서는 스케줄링을 프로세스 기준으로하는게 아닌 커널 스레드를 대상으로 하고, 사용자 스레드는 스레드 라이브러리에 의해 관리된다.
1.
경쟁 범위
•
다대일과 다대다 모델을 가지는 시스템에서는 스레드 라이브러리를 통해 사용자 스레드를 LWP 상에서 스케줄링한다. 이 방식은 동일한 프로세스에 속한 스레드끼리 CPU를 경쟁하기 때문에 프로세스-경쟁-범위(PCS, Process-Contetion Scope)이다.
•
CPU 상에 커널 스레드를 스케줄링하는 것은 시스템-경쟁-범위(SCS, System-Contetion Scope)이다.
2.
Pthread 스케줄링
•
PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용하여 스레드를 스케줄하고, PTHREAD_SCOPE_SYSTEM은 SCS 스케줄링을 사용하여 스레드를 스케줄한다.
다중 처리기(Multi-Processor) 스케줄링
1.
다중 처리기 스케줄링에 대한 접근 방법
•
다중 처리기 시스템에서 마스터 서버(master server)라는 하나의 처리기가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 결정하고 다른 처리기들은 코드의 실행만 하는 방식을 비대칭 다중 처리(asymmetric multiprocessing)라 한다.
•
비대칭 다중 처리 방식은 하나의 코어만 시스템 자료구조에 접근하기 때문에 간단하다는 장점이 있지만, 마스터 서버가 시스템 성능을 저하할 수 있는 병목 현상이 발생할 수 있다.
•
대칭 다중 처리(SMP, symmetric multiprocessing)는 각 프로세서가 스스로 스케줄링하는 방식이다.
•
대칭 다중 처리 방식에서 스레드의 대기 큐는 하나의 큐를 통해 관리하는 방법과 각 프로세서마다 큐를 가지고 관리하는 방법이 있다.
•
하나의 대기 큐를 통해 관리하는 방법에서는 두 개의 프로세서가 동일한 스레드를 스케줄링하는 경쟁 조건이 발생할 수 있기 때문에 락킹 기법과 같이 경쟁 조건을 해결할 수 있는 방법을 사용해야하지만, 락킹 기법을 적용하면 공유 큐에 액세스 할 때마다 락을 얻어야하므로 병목 현상이 발생할 수 있다.
•
각 코어마다 대기 큐를 두어 관리하는 방법에서는 위와 같은 문제가 없기 때문에 실행 큐와 관련된 성능 문제가 발생하지 않는다. 큐마다 부하의 양이 다를 수 있어, 균형 알고리즘을 사용하여 모든 프로세서 간에 부하를 균등하게 만들어줄 필요가 있다.
2.
다중 코어 프로세서
•
프로세서는 메모리보다 훨씬 빠른 속도로 동작하기 때문에, 프로세서가 메모리에 접근할 때 데이터를 읽기 위해 기다리는 상황인 메모리 스톨(memory stall)이 자주 발생한다.
•
이런 상황을 해결하기 위해, 하나의 코어에 2개 이상의 하드웨어 스레드를 할당하여 메모리를 기다리는 동안 코어가 다른 하드웨어 스레드로 전환한다.
•
칩 다중 스레딩(CMT, Chip Multi-Threading)으로 알려진 이 기술은, 4개의 컴퓨팅 코어가 있다면 각 코어에 2개의 하드웨어 스레드가 있어 운영체제에서 볼 때 8개의 논리적 CPU가 있는 것으로 보인다.
•
Intel 프로세서에서는 단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 하이퍼-스레딩(동시 다중 스레딩)이라 불린다.
•
프로세서를 다중 스레드화 하는 방법에는 거친(coarse-grained) 다중 스레딩과 세밀한(find-grained) 다중 스레딩이 있다.
◦
거친 다중 스레딩 방식은 하나의 코어에서 작업을 수행하다 메모리 스톨과 같은 긴 지연시간을 가진 큰 이벤트가 발생할 때 다른 스레드로 바꾸어 작업을 수행하는 방법이다.
◦
switching 시 명령어 파이프라인을 완전히 정리해야하고, 스택에 레지스터를 저장하는 thread context switching이 발생하여 오버헤드가 존재한다.
◦
세밀한 다중 스레딩 방식은 작업을 세분화하여 쪼개서 매 사이클마다 스레드를 바꿔가며 작업을 수행하는 방법이다.
◦
거친 다중 스레딩 방식에 비해 구현하기 쉽고 멀티 스레딩을 위한 하드웨어를 따로 사용하기 때문에 switching 오버헤드가 없다는 장점이 있다. 하지만 이를 구현하기 위한 하드웨어가 복잡해지고 단일 스레드일 때 성능이 저하된다는 단점이 있다.
•
물리적인 처리 코어는 한 번에 하나의 하드웨어 스레드만 실행할 수 있기 때문에, 실질적으로 다중 스레드 다중 코어 프로세서는 2단계 스케줄링이 필요하다.
◦
단계 1에서는 운영체제가 하드웨어 스레드에서 실행시킬 소프트웨어 스레드를 스케줄한다.
◦
단계 2에서는 각 코어가 실행할 하드웨어 스레드를 결정한다.
3.
부하 균등화
•
대칭 다중 처리(SMP) 시스템에서 부하를 모든 프로세서에 균등하게 배분하기 위해, 부하 균등화(load balancing)가 필요하다.
•
push migration과 pull migration의 두 가지 접근방법이 있다.
◦
push migration은 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 과부화인 프로세서에서 덜 바쁜 프로세서로 스레드를 이동 시키는 방식이다.
◦
pull migration은 쉬고 있는 프로세서에서 바쁜 프로세서에 대기 중에 있는 스레드를 가져오는 방식이다.
•
push와 pull migration은 상호 배타적일 필요 없이 병렬적으로 구성하여도 된다.
4.
프로세서 선호도
•
프로세서에서 스레드를 실행하면 스레드에서 접근한 최근의 데이터를 캐시에 저장한다. 이렇게 저장된 캐시를 사용하여 빠르게 데이터를 접근할 수 있는 상황을 warm cache라 부르는데, 해당 스레드를 다른 프로세서에서 부르게 된다면 기존 캐시에서 데이터를 지우는 작업과 새로운 캐시에 데이터를 저장하는 작업이 필요하다.
•
이러한 이유로 SMP를 지원하는 대부분의 운영체제는 스레드를 가급적 다른 프로세서로 이주시키지 않고 같은 프로세서에서 실행시켜 warm cache를 이용하려 하는데, 이를 프로세서 선호도라고 부른다.
•
운영체제에서 동일한 프로세서에서 스레드를 실행시키려 노력은 하지만 보장은 하지 않는 경우에 약한 선호도(soft affinity)를 가진다고 표현한다.
•
반면, 강한 선호도(hard affinity)를 지원하는 시스템 콜을 사용하면 프로세스는 자신이 실행될 프로세서의 집합을 명시할 수 있다.
•
부하 균등화 때문에 프로세서 선호도의 이점을 잃어버릴 수 있다.
5.
이기종 다중 처리
•
이기종 다중 처리(HMP, Heterogeneous Multi-Processing)는 여러 개의 프로세서의 아키텍처, 속도, 전력 소비와 같은 특성이 각기 다를 때 사용되는 병렬 프로세싱 방법이다. HMP의 목적은 작업의 특성과 요구에 따라 알맞는 코어에 작업을 할당하여 작업을 효율적으로 수행하는 것이다.
•
예를 들면, CPU의 경우에는 일련의 작업을 처리하는데 특화되어 있고 GPU의 경우에는 대규모 데이터 병렬처리에 특화되어 있다. 이런 경우에 HMP를 적용하여 작업의 특성에 맞게 프로세서에 작업을 배치한다.
실시간 CPU 스케줄링
1.
지연시간(latency)
•
이벤트 지연시간 : 이벤트가 발생한 시점부터 해당 이벤트에 맞는 서비스 루틴이 실행되기까지의 시간
•
인터럽트 지연시간 : 인터럽트가 CPU에 발생한 시점부터 해당 인터럽트 서비스 루틴이 시작되기까지의 시간
•
디스패치 지연시간 : 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 실행시키기까지 걸리는 시간
2.
RealTime 스케줄링
•
우선순위 기반 스케줄링 : 프로세서의 주기, 마감시간, 수행 시간 사이의 관계를 이용하여 프로세스의 실행 빈도를 구하고 그를 통해 우선순위를 정한다.
•
Rate-Monotonic 스케줄링 : 주기에 따라 우선순위를 정하는 방법으로, 주기가 짧으면 높은 우선순위로 주기가 길면 낮은 우선순위를 배정한다.
•
Earliest-Deadline-First 스케줄링 : 마감시간에 따라 우선순위를 동적으로 부여하는 방법으로, 마감시간이 빠를수록 우선순위가 높고 늦을수록 낮아진다.
•
proportional share 스케줄링 : 모든 어플리케이션에 T개의 시간 몫을 나누어 할당하는 방식으로, 하나의 어플리케이션이 N 만큼의 시간 몫을 받으면 해당 어플리케이션은 전체 시간 중 N / T 만큼의 시간을 할당받는다.