2021. 9. 5. 15:38ㆍ운영체제
CPU Scheduling이란?
Process에게 CPU 사용을 분배하는 것을 말한다. CPU를 최대로 활용하여 idle을 최소화하는 것이 CPU 스케줄링의 목표이다. CPU scheduling은 I/O를 하거나 (상태 변화 running -> waiting) timer 인터럽트가 발생하는 경우 (상태 변화 running -> ready) 이루어진다.
스케줄링의 종류
- 비선점형 스케줄링 (Non-preemptive Scheduling)
- I/O 수행 시 이루어지는 스케줄링이다.
- OS가 강제로 CPU 사용을 중단시키지 않는다.
- 멀티프로그래밍의 기본 스케줄링이다. - 선점형 스케줄링 (Preemptive Scheduling)
- 타임퀀텀을 소진한 상황에서 선점형 스케줄링이 이뤄진다.
- OS가 현재 CPU를 사용하고 있는 프로세스의 수행을 강제적으로 정지할 수 있다.
스케줄러를 디자인 할 때의 고려 사항
이상적인 스케줄러는 최대의 CPU 사용률, 최대의 처리량, 최대의 응답시간, 최대의 대기시간을 보여줘야한다.
그러나 위와 같이 완벽한 스케줄러를 만드는 것은 현실적으로 불가능하기 때문에 시스템의 용도에 따라 요구사항을 고려해 스케줄러를 디자인하면 된다.
EX) 슈퍼 컴퓨터는 CPU 사용률을, 개인용 컴퓨터는 응답시간을, 워크 스테이션은 처리량을 고려하여 디자인한다.
* CPU 활용률 (CPU utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
CPU 전체 사용 시간-idle time / CPU 전체 사용 시간
* 처리량 (Throughput) : CPU가 단위 시간 당 처리하는 프로세스의 개수, 완료된 프로세스의 갯수만 해당
* 응답 시간 (Response time) : 프로세스가 입출력을 시작해서 첫 결과가 나오는데까지 걸리는 시간
* 대기 시간 (Waiting time) : 프로세스가 Ready Queue 내에서 대기하는 시간의 총합
프로세스 수행은 보통 CPU burst, I/O burst를 번갈아 가며 수행된다
CPU-bound 프로세스는 긴 CPU burst를 가지고, I/O-bound 프로세스는 짧은 CPU burst를 가진다.
위의 두개의 프로세스 중 어떤 프로세스가 많은 지에 따라 스케줄링 기법의 효율성이 달라진다.
Scheduling Algorithms
1. FCFS(First-Come, First-Served) Scheduling
Ready 큐에 있는 순서대로 CPU를 할당한다.
| Process | Burst Time |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
만약 위와 같은 프로세스가 P1, P2, P3 순서대로 ready queue에 들어온다면 CPU 할당은 다음과 같다.
위와 같은 순서로 CPU를 할당할 경우, 평균 대기 시간은 (0+24+27)/2 = 17이다.
만약 순서를 P2, P3, P1으로 바꿀 경우 (0+3+6)/3=3으로 위의 경우보다 더 짧은 대기 시간을 가진다. 이처럼 작업의 수행 순서에 따라 대기 시간이 변할 수 있다.
2. SJF(Shortest Job First) Scheduling
최소의 평균 대기 시간을 제공하기 위해 CPU burst 시간이 가장 짧은 프로세스에 CPU를 먼저 할당한다. 여기서는 선점형 방식과 비선점형 방식으로 나뉘는데 선점형 방식은 타임퀀텀마다 CPU burst 시간이 가장 짧은 프로세스를 선택한다. 비선점형 방식은 자발적 양보 시점에 다음 프로세스를 선택하여 수행한다.
| Process | Arrival Time | Burst Time |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
이와 같은 프로세스를 선점형과 비선점형 방식으로 나뉘어서 보자.
(1) Preemprive SJF Scheduling
① 0초에 P1이 먼저 들어간다.
② 2초에 P2가 들어가는데, 이 때 P1의 남은 burst time(5) > P2 burst time(4)이므로 P2가 CPU를 선점한다.
③ 4초에 P3이 들어가는데, 이 때 P2의 남은 burst time(2) > P3 burst time(1)이므로 P3가 CPU를 선점한다.
④ P3의 burst time이 1초이므로 5초에 P3이 완전히 종료되고, P4가 들어간다.
그러나 이 때, P4 burst time(4) > P2 남은 burst time (2) 이므로 P2가 CPU를 선점한다.
⑤ 7초에 P2가 완전히 종료되고, ready queue에 있는 process 중 제일 burst time이 제일 적은 P4가 CPU를 선점한다.
⑥ 11초에 P4가 완전히 종료되고, ready queue에 유일하게 남아 있는 P1이 들어간다.
⑦ 16초에 P1이 완전히 종료된다.
평균 대기 시간 : (9+1+0+2)/4 = 3
(2) Non-preemptive SJF Scheduling
① 0초에 P1이 들어간다. P1이 실행되는 사이에 P2, P3, P4가 순서대로 ready queue에 들어간다.
② 7초에 P1이 종료되고, ready queue에 있는 process 중 burst time이 제일 적은 P3이 들어간다.
③ P3이 종료되고, ready queue에 있는 process 중 burst time이 제일 적은 P2가 들어간다.
④ P2가 종료되고, ready qeueu에 유일하게 남는 P4가 들어간다.
⑤ P4가 종료된다.
평균 대기 시간 : (0+6+3+7)/4 = 4
3. Priority Scheduling
Priority에 따라 CPU를 할당하며, Priority Scheduling도 비선점형과 선점형으로 나뉜다.
- 선점형 : 타임퀀텀마다 현재 실행되는 프로세습돠 높은 priority를 가지고 있는 프로세스를 먼저 수행한다.
- 비선점형 : 현재 수행중인 process가 자발적 양보를 할 때 우선순위에 따라 프로세스를 선택한다.
그러나 priority 스케줄링은 사용하게 되면 낮은 priority를 가진 프로세스는 전혀 수행되지 않을 수 있기 때문에 기아 상태가 발생할 수도 있다. 이러한 문제는 기다리는 시간에 따라 프로세스 priority를 증가시켜주는 againg 방법을 사용하면 해결된다.
| Process | Burst Time | Priority | Arrival Time |
| P0 | 10 | 3 | 0 |
| P1 | 6 | 2 | 3 |
| P2 | 4 | 1 | 1 |
(1) Preemptive Priority Scheduling
① 0초에 P0가 들어간다.
② 1초에 들어온 P1이 실행 중인 P0보다 우선 순위가 높기 때문에 P1이 CPU를 선점한다.
③ 3초에 P1이 들어오지만 실행 중인 P2의 우선 순위가 더 높기 때문에 그대로 P2가 CPU 연산을 실행한다.
④ P2가 종료되고, ready queue에 있는 process 중 우선 순위가 제일 높은 P1의 CPU 연산이 실행된다.
⑤ P1이 종료되고, ready queue에 있는 유일한 프로세스인 P0이 CPU 연산을 실행한다.
⑥ P0이 종료된다.
(2) Non-Preemptive Priority Scheduling
① 0초에 P0가 들어간다. P0이 실행되는 사이에 P1과 P2가 들어오지만 비선점형이기 때문에 그대로 P0가 CPU 연산을 실행한다.
② P0가 종료되고, 남아있는 프로세스 중 우선 순위가 제일 높은 P2가 CPU를 선점한다.
③ P2가 종료되고, 유일하게 남은 P1이 CPU 연산을 실행한다.
④ P1이 종료된다.
4. Round Robin Scheduling
선점형 스케줄링 방식으로, CPU를 시간 단위(time quantum)로 할당한다.보통의 타임 퀀텀은 1~100ms이며 time quantum을 수행한 프로세스는 ready queue의 끝으로 들어가 다시 할당을 기다린다.
time quantum = 20
| Process | Burst Time |
| P1 | 53 |
| P2 | 17 |
| P3 | 68 |
| P4 | 24 |
위의 Process들에 대한 CPU 연산 수행은 다음과 같다.
다음의 그림처럼 Round Robin Scheduling은 respone time이 짧아 interactive 프로세스에 필요하다.
5. Multilevel Queue Scheduling
Multilevel Queue Scheduling은 Ready 큐를 여러개 만들어 각각에 대해 다른 우선순위와 스케줄링 알고리즘을 사용하는 기법이다. 예를 들어 foreground 큐는 interactive한 동작이 필요한 프로세스를 위한 큐이므로, round robin 기법을 사용하고, backgound 큐는 cpu 연산 작업을 주로 수행하는 프로세스를 위한 큐이므로 FCFS 기법을 사용한다.
Multilevel Queue Scheduling은 상위 큐에 프로세스가 계속 있으면 하위 큐에 기아 현상이 발생한다는 문제점이 있다.
6. Multilevel Feedback Queue Scheduling
Multilevel Queue Scheduling의 기아 현상을 해결하기 위한 방법으로, Multilevel Queue에서 프로세스들이 다른 큐로 이동할 수 있도록 한 스케줄링 기법이다.
만약 새로운 프로세스가 들어오면 Q0에서 8ms동안 수행된다. Q0에서 종료되지 않았다면 Q1으로 이동 후 16ms 동안 수행된다. Q2에서도 종료되지 않다면 Q2로 이동해 FCFS로 수행한다.
7. Multi core scheduling
여러 개의 코어를 사용하는 시스템은 스케줄링은 더욱 복잡해진다. 요즘은 멀티프로세서 연구가 한계에 봉착해 CPU 내에 코어를 늘리는 추세이다. 또한 GPU를 AI에 사용하기도 한다.
- Load Balancing
- 코어마다 각각 ready 큐를 둘 경우 일부 코어에 프로세스가 집중되지 않도록 하기 때문에 scalability 측면에서 유리하다.
- 코어 전체에 하나의 ready 큐를 둘 경우 사용 가능한 코어에 차례대로 프로세스를 할당한다.