Process Scheduling
이화여자대학교 반효경 교수님의 2014년 Operating System 강의를 시청한 후 정리한 내용이다.
http://kocw.net/home/cview.do?cid=3646706b4347ef09
CPU & I/O Burst in Program Execution
프로세스에서 CPU 연산을 진행하는 것을 CPU burst, I/O 연산을 진행하는 것을 I/O burst라고 한다. 프로세스는 CPU burst와 I/O burst를 번갈아 실행하며, CPU burst가 큰 경우에는 CPU bound process, I/O burst가 큰 경우에는 I/O bound process라고 부른다. 대게 사용자와 상호작용을 많이 하는 프로세스는 I/O bound process이다.
Need of CPU Scheduling
위 그래프는 프로세스가 실행하면서 CPU를 사용하는 경향을 표현한 것이다. 가로 축은 CPU burst duration, 세로 축은 CPU burst의 발생 빈도이다. 왼쪽 burst duration이 작고 frequency가 큰 구역은 I/O bound process로 볼 수 있다. I/O bound process의 CPU burst duration이 짧은 이유는 실행 중간에 I/O burst가 발생하기 때문인데, 그 대신 CPU burst의 발생 빈도가 빈번함을 알 수 있다. 이와 반대로, 그래프의 오른쪽 구역으로 갈 수록 CPU bound process임을 이해할 수 있다.
해당 그래프를 바탕으로 만약 CPU bound process가 많고 I/O bound process가 적다면, CPU bound process들이 CPU를 점유하는 시간이 많아져 I/O bound process가 진행하지 못하는 상황이 발생한다. 특히 실시간으로 상호작용하는 I/O bound process에게는 이 문제가 치명적이므로, 각 프로세스마다 CPU 할당 시간을 적절히 분배하는 CPU Scheduling Algorithm이 필요하다.
CPU Scheduler & Dispatcher
- CPU Scheduler: ready 상태의 process 중 CPU 제어권을 할당할 process를 선택하는 커널 코드
- Preemptive(선점형): CPU 제어권을 강제로 빼앗는 스케줄링. timer interrupt 등의 경우가 있다.
- Nonpreemptive(비선점형): CPU 제어권을 강제로 빼앗지 않고, 자진 반납하는 스케줄링. I/O event, 종료 등의 경우가 있다.
- Dispatcher: CPU Scheduler가 선택한 process에게 CPU 제어권을 할당하는 커널 코드. Context Switching을 담당한다.
Scheduling Criteria (= Performance Index)
- CPU Utilization (System): CPU 이용률. 최대한 CPU를 쉬지 않고 일하게 할수록 성능 척도에 좋은 영향을 준다.
- Throughput (System): CPU의 일 처리량
- Turnaround Time (Process): 새로 생성되어 ready상태가 된 프로세스가 실행 후 종료되기까지의 시간
- Waiting Time (Process): 프로세스가 Ready Queue에 기다린 총 시간
- Response Time (Process): 프로세스가 Ready Queue에서 CPU를 기다리는데 걸린 시간. Time-Sharing 환경에서 매우 중요하다.
FCFS(First-Come First-Served)
먼저 도착한 프로세스가 CPU 제어권을 먼저 할당받는다.
위와 같이 3개의 프로세스가 존재한다고 가정하자. P1의 실행 시간은 24ms, P2와 P3의 실행 시간은 3ms이다.
만약 P1, P2, P3 순으로 Ready Queue에 도착했다면 P1이 먼저 실행된다. 이 상황에서 평균 대기 시간은 (0 + 24 + 27) / 3 = 16.6ms이다. 그러나 평균 대기 시간을 더 줄이는 상황이 존재한다.
P2, P3, P1 순으로 도착한 상황을 가정하면, 평균 waiting time은 (0 + 3 + 6) / 3 = 3ms가 된다. 이는 실행 시간이 짧은 프로세스가 먼저 도착하여 실행되었으므로 첫 번째 상황보다 평균 대기 시간을 줄여졌다. 따라서 FCFS는 최악의 경우 평균 대기 시간을 불필요하게 늘릴 수 있음을 파악할 수 있다.
Convoy-Effect: 뒤에 있는 프로세스가 CPU를 먼저 점유한 프로세스가 종료될 때까지 기다리는 현상
SJF (Shortest-Job First) Scheduling
Ready Queue에 있는 프로세스 중, 다음 CPU burst Time이 짧은 프로세스가 먼저 실행된다.
위 Process들이 Ready Queue에 있다고 가정할 때 SJF는 아래와 같은 Scheduling을 할 것이다.
이 경우는 FCFS에서 두 번째 상황과 같은, 평균 대기 시간이 가장 짧은 케이스로, SJF는 FCFS와 달리 optimal average waiting time을 만족한다. 구현에 따라서 Preemptive, Nonpreemptive SJF가 있다.
- Nonpreemptive_SJF(Shortest-Job First): Ready Queue에 있는 프로세스 중 남은 CPU burst Time이 가장 짧은 프로세스부터 CPU 제어권을 할당받는다.
- Preemptive_SRTF(Shortest-Remaining-Time First): 실행 중인 프로세스의 남은 CPU Burst Time보다 짧은 CPU burst Time을 갖는 프로세스가 Ready Queue에 있다면, 현재 실행중인 프로세스의 CPU 제어권을 빼앗아 선택한 프로세스에게 넘긴다.
SJF은 다음 두 가지 문제점을 갖고 있다.
- Starvation: 실행되기를 기다리는 프로세스가 자신보다 CPU burst Time이 짧은 프로세스들로 인해 CPU 제어권을 얻지 못하는 현상
- 예측하기 어려운 CPU Burst Time (SRTF)
Exponential Averaging으로 CPU Burst Time을 예측할 수 있다.
Priority Scheduling
Ready Queue에 존재하는 프로세스 중 우선순위가 가장 높은 프로세스가 CPU 제어권을 얻는 스케줄링 방식이다. 리눅스에서는 프로세스마다 우선 순위를 나타내는 정수를 할당하는데, 해당 값이 작을수록 우선순위가 높도록 구현되어 있다. SJF은 burst time을 기준으로 우선순위를 가리므로, Priority Scheduling이라 볼 수 있다. 해당 스케줄러도 선점/비선점형 방식이 있다.
- Preemptive: 현재 실행되는 프로세스보다 Ready Queue에 있는 프로세스의 우선순위가 더 높다면, 현재 CPU를 점유하는 프로세스의 제어권을 빼앗아 Scheduler가 선택한 프로세스에게 넘긴다.
- Nonpreemptive: 현재 CPU를 점유하는 프로세스의 burst time이 끝날 때까지 기다리다가, Ready Queue에 있는 프로세스를 선택하여 제어권을 넘긴다.
이 스케줄링을 사용할 경우, 우선순위가 낮은 프로세스가 오랫동안 CPU 제어권을 얻지 못하는 Startvation이 발생할 수 있다. 따라서 해당 프로세스가 오래 기다릴수록 우선순위를 높여주는 Aging 기법을 통해 이 문제를 해결할 수 있다.
Round Robin (RR) Scheduling
현대 운영체제에서 사용되는 스케줄링 방식으로, 모든 프로세스에게 사용 시간을 할당한다. 따라서 짧은 실행 시간을 갖는 프로세스는 할당 시간 이내에 실행을 마치고 종료할 수 있지만, 실행 시간이 긴 프로세스는 제어권을 받고 Ready Queue에 들어가는 것을 여러 번 반복하여 실행된다.
프로세스가 n개이고 time quantum이 q라면, 최대 (n-1)xq만큼 기다리게 되므로 프로세스의 응답이 빨라진다는 장점이 있다. 이때 q가 클수록 FCFS 스케줄링에 가깝고, q가 작을수록 context switching의 오버헤드가 증가하므로 적절한 q값을 정해야 한다.
위와 같이 3개의 프로세스가 Ready Queue에 존재할 때 RR의 스케줄링 순서는 이러하다.
time quantum을 4ms로 잡았을 때, 제일 먼저 들어온 P1이 실행되었지만 할당 시간 내에 연산을 마치지 못했다. 그러나 P2와 P3은 실행 시간이 3ms이므로 할당 시간 내에 종료되었고, 나머지는 P1이 계속 CPU 제어권을 받아 4ms마다 실행하는 것을 볼 수 있다.
Multilevel Queue
Ready Queue를 여러 개 만들어 프로세스들을 용도와 우선순위에 따라 각 Queue에 넣는다. 이 Queue들은 우선 순위를 가지며, 우선 순위가 가장 높은 Queue에 프로세스들이 먼저 CPU 제어권을 얻고, 해당 Queue 내에 프로세스가 없다면 다음 우선순위의 Queue 내의 프로세스를 스케줄링하는 방식이다.
이 스케줄링 방식은 순위가 낮은 Queue 내에 프로세스들이 CPU 제어권을 얻지 못하는 Starvation 현상이 나타난다는 것이 단점이다. 이 문제는 다음 방법들로 해결 가능하다.
- Ready Queue를, 상호작용하는 Foreground Process용과 그렇지 않은 Background Process용으로 나눈다.
- 응답 시간이 중요한 Foreground Queue에는 RR 스케줄링을, 응답 시간이 중요하지 않는 Background Queue에는 Context Switching 오버헤드를 줄이기 위해 FCFS 스케줄링을 적용한다.
- Queue에 대한 스케줄링을 할 때, Foreground Queue에 있는 모든 프로세스를 실행한 후 Background Queue에 있는 프로세스를 실행하도록 스케줄링하는 것은 Starvation이 발생할 수 있다. 따라서 각 Queue마다 CPU Time을 적절한 비율로 할당한다.
Multilevel Feedback Queue
Multilevel Feedback Queue는 Multilevel Queue처럼 여러 Queue를 사용하여 스케줄링하지만, 프로세스가 하나의 Queue에만 머무는 것이 아니라, 실행될수록 우선순위가 더 낮거나 높은 Queue로 이동한다는 것이 특징이다.
Multilevel Feedback Queue의 스케줄링 방식을 정의할 때 다음 기준을 정해야 한다.
- Queue의 개수
- 각 큐의 Scheduling Algorithm
- Process를 상위/하위 순서의 Queue로 보내는 기준
- 프로세스가 들어갈 Queue를 결정하는 기준
위 그림은 Multilevel Feedback Queue의 일반적인 동작을 표현한 그림이다. 먼저 프로세스는 상위 순서의 Queue에 들어간다. 해당 Queue는 Time Quantum이 8ms인 RR Scheduling 방식을 운용하는데, 프로세스가 이 Queue에서 실행을 마치고 종료하지 못한다면, 하위 순서의 Queue로 들어간다. 이 Queue도 마찬가지로 RR Scheduling 방식을 이용하지만, Time Quantum이 16으로 늘어났다는 것이 차이점이다. 그러나 프로세스가 해당 Queue에서도 실행을 마치지 못한다면 FCFS 방식으로 스케줄링하는 Queue에 들어가 CPU 제어권을 기다리게 된다. 이 Queue들의 스케줄링 방식은, 상위의 Queue가 비어 있으면 하위의 Queue 내의 프로세스들에게 제어권을 할당하는 방식이다.
Multiple-Processor Scheduling
CPU가 여러 개일 경우 스케줄링 방법은 아래와 같다.
- Homogeneous Processor인 경우: 하나의 Queue에 프로세스들을 스케줄링하는 방식. 만약 어떤 프로세스가 특정 프로세서 내에서만 실행되어야만 한다면 이 방식은 부적합하다.
- Load Sharing: 어느 프로세서에게 job이 몰리지 않도록 프로세스들을 분산하는 스케줄링 방식. Queue를 여러 개 사용하는 방법과 공동 Queue를 사용하는 방법이 있다.
- Symmetric Multiprocessing (SMP): 각각의 프로세서가 스케줄링하는 방식
- Asymmetric Multiprocessing: 하나의 프로세서가 데이터 접근을 관리하고, 나머지 프로세서들은 관리에 따라서 동작
Real-Time Scheduling
Real-Time job은 정해진 시간 내에 처리해야 하는, 빠른 응답을 요구하는 프로세스이다. 따라서 Real-Time 프로세스들을 위한 스케줄링 방식이 존재한다.
- Hard Real-Time Systems: 반드시 정해진 시간 내에 job을 끝낼 수 있도록 프로세스를 적절히 배치하는 시스템
- Soft Real-Time Computing: 무조건 DeadLine을 지키지 않는 대신, 다른 프로세스보다 높은 우선 순위를 갖는다.
Thread Scheduling
Thread를 스케줄링할 때는 사용자 수준인지, 커널 수준인지에 따라 방식이 다르다.
- Local Scheduling: User Level Thread 대상으로, Thread Library에 의해 사용자 수준 내에서 프로세스가 스케줄링
- Global Scheduling: Kernel Level Thread 대상으로, 커널이 일반 프로세스처럼 스케줄링
Algorithm Evaluation
스케줄링 알고리즘이 기대에 미치는 성능을 가지는지 평가하는 방법은 아래와 같다.
- Queueing Models: 프로세스가 Ready Queue에 도착하는 확률과 CPU가 프로세스를 처리하는 확률 분포를 얻어 성능 척도를 계산하는 방법. 이 방법보다 실제 시스템에서 테스트하여 도출한 결과를 유의미있게 본다.
- Implementation & Measurement: 실제 시스템에서 해당 알고리즘을 동작시켜 성능 측정
- Simulation: 알고리즘을 프로그램으로 시뮬레이션하여 성능 측정
