스케쥴링
스레드를 지원하는 운영체제에서는 실질적으로 프로세스를 스케쥴링하는 것이 아니라 커널 쓰레드를 스케쥴한다. 이러한 차이점을 무시하고 이번 게시물에서는 커널 쓰레드를 프로세스라고 언급하며, 유저 쓰레드를 쓰레드라고 언급할 것이다.
스케쥴링은 Ready Queue에 있는 프로세스들 중 어떤 프로세스를 CPU에게 할당해야 하는지를 결정하는 일이다. 스케쥴링이 필요한 이유는 CPU 이용율(CPU Utilization)을 최대화 하기 위해서이다. 만약 하나의 프로세스가 CPU를 점유하여 실행(CPU Burst)하다가 특정 I/O처리를 기다려야 한다면, 이 프로세스는 Device Queue에 머무르게 되고 I/O처리를 하는 시간(I/O Burst)동안 CPU는 쉬게 될 것이다. 이는 CPU 이용율을 떨어뜨리게 된다. 따라서 적절한 스케쥴링 방법을 사용하여 CPU Burst Time을 최대로 하는 것이 스케쥴링의 목적이다.
선점, 비선점 스케쥴링 ( Preemptive and Non-Preemptive Scheduling)
스케쥴링이 일어나는 시점은 프로세스의 상태 변화에 따라 크게 네 가지로 분류할 수 있다.
1.Running 상태의 프로세스가 Wait 상태로 변화할 때. 예를 들어 I/O Request가 발생하거나 생성한 자식 프로세스의 종료를 기다릴 때.
2.Running 상태의 프로세스가 Ready 상태로 변화할 때. 예를 들어 Interrupt가 발생할 때.
3.Wait 상태의 프로세스가 Ready 상태로 변화할 때. 예를 들어 I/O Request의 처리가 완료되거나 생성한 자식 프로세스가 종료되었을 때.
4.프로세스가 종료될 때.
만약 스케쥴링에 1번과 4번 방식만 채택한다면, 이것을 비선점 스케쥴링 방식(Non-Preemptive Scheduling)이라고 한다.
2번과 3번 방식이 채택된다면, 이것을 선점 스케쥴링 방식(Preemptive Scheduling)이라고 한다.
비선점 스케쥴링에서는 하나의 프로세스가 실행중이라면 실행도중 I/O 요청이 들어오더라도 다른 프로세스에 의해 선점되지 않고 요청에 대한 처리가 끝날때까지 기다리게 되며, 결국 해당 프로세스가 끝날때까지 CPU는 해당 프로세스만이 차지하고 있게 된다.
선점 스케쥴링에서는 하나의 프로세스가 실행중이더라도 다른 프로세스에 의해 선점될 수 있다.
Preemptive Scheduling 방식에서는 Critical Section에 대한 Competition을 초래할 수 있다. 공유 자원에 대해서 프로세스들 간에 경쟁해야 하는 것이다. 적절한 경쟁 조건이 갖춰져 있다면 문제가 발생하지 않겠지만, 경쟁 조건이 갖춰져 있지 않다면 데이터의 일관성이 깨지는것과 같은 문제가 발생할 것이다.
디스패처 ( Dispatcher )
스케쥴링이 일어날 때, CPU에서 동작중인 프로세스를 Ready Queue에 있는 다른 프로세스로 교체할 때 CPU와 Ready Queue 사이에서 다음과 같은 일들을 수행하는 모듈을 Dispatcher라고 한다.
1. 문맥 교환을 수행 (Context Switching)
2. 유저 모드로 전환
3. 유저 프로그램을 이전에 중지되었던 위치부터 다시 시작하기 위해 적절한 위치로 jump
위와 같은 일들을 수행하는데 필요한 시간을 Dispatch Latency라고 한다.
스케쥴링 기준 ( Scheduling Criteria )
스케쥴링은 어떤 프로세스를 CPU에게 할당할지의 문제이고, 이러한 문제를 해결하기 위한 여러가지의 방법인 스케쥴링 알고리즘이 존재하기 마련이다. 각각의 시스템에 최적화된 스케쥴링 알고리즘이 존재하고, 이러한 스케쥴링 알고리즘을 평가하기 위한 여러가지 기준들이 존재한다.
- CPU Utilization : CPU Burst Time / 전체 실행 시간 * 100
- Throughput : 단위 시간에 처리된 프로세스의 개수
- Turnaround Time : 하나의 프로세스를 실행하는 데에 걸린 시간. 하나의 프로세스가 차지하는 CPU Burst Time이 아니라, 해당 프로세스가 제출되고 완료되기까지의 시간이다. 즉 프로세스가 wait 상태에 있는 시간도 포함된다.
- Waiting Time : 프로세스가 Ready Queue에 존재하는 시간의 합
- Response Time : 프로세스가 응답하는 데까지 걸리는 시간
CPU Utilization과 Throughput이 높을수록, Turnaround Time, Waiting Time, Response Time이 낮을수록 좋은 스케쥴링이라고 할 수 있다.
스케쥴링 알고리즘 ( Scheduling Algorithm )
Ready Queue에 있는 어떤 프로세스에게 CPU를 할당할지 결정하는 알고리즘에는 여러가지가 있다.
- First-Come, First-Served Scheduling
먼저 Ready Queue에 들어온 프로세스에게 CPU를 할당하는 방식이다. 프로세스의 처리시간에 따라서 스케쥴링 기준 중 하나인 waiting time에 대한 평가가 달라지는데, 짧은 프로세스가 앞쪽에 올수록 (Ready Queue에 먼저 들어갈수록) 평균 Waiting Time이 줄어들고, 긴 프로세스가 앞쪽에 올수록 평균 Waiting Time이 길어진다.
- Shortest-Job-First Scheduling
Ready Queue에 있는 프로세스들 중 CPU burst의 길이가 가장 짧은 프로세스에게 CPU를 할당하는 방식이다. 하지만 이 방식에서의 문제점은 환경에 따라 가변적인 CPU burst time을 어떻게 결정하는지에 대한 것이다. 이는 이전 실행에서 해당 프로세스의 CPU Burst time을 측정함으로써 해결할 수 있다.
- Shortest-Remaining-Time-First Scheduling
Ready Queue에 있는 프로세스들 중 남은 Burst Time이 가장 짧은 프로세스에게 Preemption을 일으키는 방식이다. 만약 CPU burst time이 5ms인 프로세스 P1이 실행을 시작하고 1ms 후에 cpu burst time이 3ms인 프로세스 P2가 Ready Queue에 들어온다면, 남은 CPU Burst Time을 비교했을 때 P1은 4ms, P2는 3ms이므로 CPU는 P2에게 선점된다.
- Priority Scheduling
프로세스들마다 우선순위(Priority)를 부여하여 Ready Queue에서 가장 높은 우선순위가 높은 프로세스에게 CPU를 할당 하는 스케쥴링 방식이다. Preemptive방식일수도 있고, Non-Preemptive방식일수도 있다. Priority Scheduling 방식에서의 문제점은 낮은 우선순위를 가진 프로세스는 CPU를 할당받지 못하는 현상인 Starvation이다. 이는 우선순위가 낮고 오래된 프로세스의 우선순위를 높이는 Aging기법을 활용하여 해결할 수 있다.
- Round Robin Scheduling
프로세스들에게 일정한 시간 할당량(Time Quanta)를 부여하여 circular queue형태의 ready queue에 존재하는 프로세스들을 번갈아가며 실행시키는 스케쥴링 기법이다. 만약 time quanta가 프로세스의 cpu burst time보다 크다면, 선입선출 스케쥴링 방식과 동일하게 동작할 것이다. 하지만 time quanta가 프로세스의 cpu burst time보다 작다면, 어떤 프로세스의 실행중에 다음 번 실행이 예정된 프로세스에게 선점되어 circular queue의 마지막 프로세스의 time quanta가 지나고 나서야 선점을 당한(밀려난) 프로세스의 나머지 cpu burst가 마저 소진될 것이다. 이는 불필요한 Context Switcing에 소모되는 오버헤드의 발생을 야기할 수 있다.
- Multilevel Queue Scheduling
Ready Queue를 여러 개의 Queue로 분류하고, 각각의 Queue 내에 독립적인 스케쥴링 기법을 적용시키고, 각각의 Queue사이에도 별도의 스케쥴링 기법이 존재하는 스케쥴링 방식이다. 큐 사이의 스케쥴링 기법으로는 Priority 기법을 적용할수도, Time Slice 방식을 적용할수도 있다.
- Multilevel Feedback Queue Scheduling
Multilevel Queue Scheduling 기법은 근간으로 하여, 여러개의 큐들 중 특정 큐에 들어있는 프로세스가 다른 큐로의 이동을 허용하는 스케쥴링 방식이다. 만약 큐 사이의 스케쥴링 기법으로 Priority Scheduling을 사용한다면 Starvation이 발생할 수 있는데, Starvation이 발생한 프로세스를 더 높은 우선순위를 가지는 Queue로 이동함으로써 Aging기법을 구현할 수 있다.
쓰레드 스케쥴링 ( Thread Scheduling )
쓰레드 스케쥴링을 언급하기에 앞서 경쟁범위(Contention Scope)에 대해서 알아보자.
프로세스 경쟁 범위 ( Process-Contention-Scope ) : 프로세스 내에서 유저 쓰레드들 간의 경쟁 범위. 즉, 하나의 커널 쓰레드를 두고 여러개의 유저 쓰레드가 경쟁을 하는 것이다.
시스템 경쟁 범위 ( System-Contention-Scope ) : 시스템 내에서 커널 쓰레드들 간의 경쟁 범위. 즉, 하나의 CPU를 두고 여러개의 커널 쓰레드가 경쟁을 하는 것이다.
쓰레드 스케쥴링에서 쓰레드의 의미는 유저 쓰레드를 의미한다. 즉, 실제로 CPU에서 실행되고 있는 커널 쓰레드는 변하지 않지만, 해당 커널 쓰레드 위에서 LWP(Light Weight Process)에 의해 실행되고 있는 유저 쓰레드의 전환을 어떻게 할지에 대한 문제를 다루는것이 Thread Scheduling을 의미한다.
멀티프로세서 스케쥴링 ( Multiple-Processor Scheduling )
프로세서 또는 코어가 여러개인 경우 여러개의 CPU에 대하여 스케쥴링을 해주어야 한다.
- Asymmetric Multiprocessing : 오직 하나의 프로세스만 시스템 자료구조에 접근한다.
- Symmetric Multiprocessing : 각각의 프로세스는 고유의 레디 큐가 있거나 공유하는 레디 큐가 있고, 스스로 스케쥴링한다.
프로세서가 여러개인 경우 어떤 프로세스는 특정 프로세서에게 프로세서 친화성(Processor Affinity)을 가진다. 이는 만약 프로세스가 친하지 않은 프로세서에게 할당될 경우 관련 데이터 메모리를 모두 이동해야 하기 때문이다.
Non-Uniform Memory Access(NUMA, 메모리 접근 시간이 일정하지 않은 구조)를 예로 들어보자. 만약 해당 프로세스와 관련있는 데이터를 가지고 있는 특정 프로세서 내의 메모리가 있다면, 이 프로세서에 해당 프로세스를 연관시키는 것이 메모리 접근 속도에 있어서 손해를 보지 않을것이다.
Symmetric Multiprocessing에서는 CPU 부하를 균등하게 분배할 필요가 있는데, 이를 Load Balancing이라고 한다.
Load Balancing을 구현하기 위한 두가지의 방법이 있다.
- Push Migration : CPU부하를 관리하는 특정 태스크가 각각 프로세서의 부하를 측정하고 과부하된 프로세서의 태스크를 비교적 부하가 적은 태스크로 밀어넣는 이주(Migration)방식.
- Pull Migration : idle 상태인 프로세서가 과부화된 프로세서로부터 태스크를 끌어들이는 방식.
Push Migration은 특정 Task가 주관하고, Pull Migration은 프로세서가 주관한다.
실시간 운영체제 CPU 스케쥴링 ( Real-Time OS CPU Scheduling )
자동차의 브레이킹 시스템과 같은 임베디드 컴퓨터에서는 실시간 운영체제가 사용된다. 이러한 환경에서는 위에서 살펴본 Scheduling Criteria중 Response Time이 절대적으로 중요한 기준이다. 이러한 Response Time은 아래의 그림과 같이 구성된다.
Response Time을 줄이기 위해서는 지연 시간(latency)를 줄이는것이 중요한데, 반응시간에 포함되는 지연시간은 두 가지 종류가 있다.
- Interrupt Latency : CPU에 인터럽트가 발생한 시점부터 해당 ISR(Interrupt Service Routine)이 시작하기까지의 시간
- Dispatch Latency : Dispatcher가 Context Switching, Changing to User Mode, Jumping to previous state를 처리하는 데 걸리는 시간
실시간 운영체제에서는 각각의 프로세스가 일정한 주기(Deadline)를 가지고 각각의 프로세스가 자신의 주기에 도달할 때 우선순위에 따라 선점(Preemtion)이 일어나게 된다. 이러한 환경에서 자주 사용되는 스케쥴링 방식을 살펴보자.
- Rate Monotonic Scheduling : 프로세스의 실행주기에 따라 스케쥴링 하는 방식.
짧은 주기를 가지는 프로세스에게는 높은 우선순위를, 긴 주기를 가지는 프로세스에게는 낮은 우선순위를 부여한다. 이러한 스케쥴링 방식을 사용하는 이유는 긴 주기의 프로세스를 먼저 실행시킨다면 이후에 실행되는 짧은 프로세스는 자신의 실행주기를 맞추지 못할가능성이 크기 때문이다. 하지만 주기가 짧은 프로세스를 먼저 실행시키더라도 주기가 꼬이게 되면 실행주기를 맞추지 못할수도 있다.
- Earliest Deadline First Scheduling : 실시간으로 데드라인을 계산하고 동적으로 우선순위를 다르게 하는 스케쥴링 방식.
실시간으로 계산한 데드라인이 빨리 도달하는 프로세스에게 높은 우선순위를 동적으로 배당한다. 이 방식은 위의 Rate Monotonic Scheduling방식을 보완한다.
- Proportional Share Scheduling : CPU Time을 비율로 분할하여 프로세스에게 배당하는 방식
알고리즘 평가 ( Algorithm Evaluation )
스케쥴링 알고리즘을 평가하는 모델에 대해서 알아보자.
- Deterministic Modeling
어떤 특정 기준을 선정하고 각각의 알고리즘마다 해당 기준의 퍼포먼스를 결정하는 방식. 예를 들어 first-come-first-served, shortest-job-first, round-robin 알고리즘에 대하여 프로세스들의 평균 Waiting Time을 결정하고 비교할 수 있을것이다.
- Queueing Modeling
CPU와 I/O burst 분포를 추정하거나 근사값으로 계산하여 각 스케쥴링 알고리즘을 평가하는 모델.
- Simulation
모의실험을 통해 스케쥴링 알고리즘을 평가해 보는 것이다.
참조
ABRAHAM SILBERSCHATZ, PETER BAER GALVIN, GREG GAGNE / 운영체제 / (주)교보문고 / 2018년