CPU 스케줄링: Chapter 5. CPU Scheduling (Part 2)
on OS
[공룡책 정리] CPU 스케줄링: Chapter 5. CPU Scheduling (Part 1)
CPU 스케줄링 알고리즘
선입 선처리 스케줄링(First-Come, First-Served Scheduling)
비선점 스케줄링 방식으로 CPU를 먼저 요청하는 프로세스를 우선적으로 할당하는 방식이다. FIFO 큐를 사용해 쉽게 관리할 수 있다. 가장 간단한 CPU 스케줄링 기법이지만 현재에는 거의 사용되지 않는 스케줄링 기법이다.
| Process | Burst time | Turnaround time | Waiting time |
|---|---|---|---|
| P1 | 24 | 24 | 0 |
| P2 | 3 | 27 | 24 |
| P3 | 3 | 30 | 27 |
총 대기시간 : ( 0 + 24 + 27 ) = 51 평균 대기시간 : 51 / 3 =17
모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.
최단 작업 우선 스케줄링 (Shortest-Job-First Scheduling)
CPU burst 길이가 짧은 순서대로 할당하는 방식이다. 최적의 알고리즘이지만 다음 CPU burst 길이를 알 수 있는 방법이 없어 근사적인 값을 활용해 구현한다. (앞서 처리한 프로세스들의 기록을 보고 추측한다.)
SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 Ready Queue에 도착하면 선택이 발생한다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU burst를 가질 수 있다. 선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고 반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다. 선점형 SJF 알고리즘은 최소 잔여 시간 우선 스케줄링(shortest remaining time first)이라고 불립니다.
비선점형일 경우 CPU burst 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
| Process | Burst time | Turnaround time | Waiting time |
|---|---|---|---|
| P1 | 6 | 9 | 3 |
| P2 | 8 | 24 | 16 |
| P3 | 7 | 16 | 9 |
| P4 | 3 | 3 | 0 |
총 대기시간 : ( 3 + 16 + 9 + 0 ) = 28 평균 대기시간 : 28 / 4 =7
최소 잔여 시간 우선 스케줄링(shortest remaining time first)
프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당하는 방식으로, 수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.
평균대기 시간이 가장 짧은 알고리즘이지만 기본적으로 선점형 방식이기 때문에 잦은 문맥 교환이 일어나고 그에 따른 오버헤드가 커질 수 있다.
| Process | Arrival time | Burst time | Turnaround time | Waiting time |
|---|---|---|---|---|
| P1 | 0 | 8 | 17 | 9 ( 10 - 1 ) |
| P2 | 1 | 4 | 4 | 0 ( 1 - 1 ) |
| P3 | 2 | 9 | 26 | 15 ( 17 - 2 ) |
| P4 | 3 | 5 | 7 | 2 ( 5 - 3 ) |
총 대기시간 : ( 9 + 0 + 15 + 2 ) = 26 평균 대기시간 : 26 / 4 =6.5 ( * 똑같은 데이터로 SJF 스케줄링 수행 시 7.75)
라운드 로빈 스케줄링( Round - Roubin Scheduling )
프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 이 시간 동안만 CPU를 할당한다. 선점형 방식을 사용해 할당 시간 동안 처리를 다 하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘긴다. 주로 원형 큐를 이용해 구현하고 빼앗긴 프로세스는 준비 큐의 맨 뒤로 간다.
따로 CPU 처리 시간을 계산하지 않아도 돼서 선점형 방식의 가장 단순하고 대표적인 방법이다. 우선순위도 없기 때문에 매우 공평하다.
라운드 로빈 알고리즘의 경우, 만약 할당 시간이 q고 대기 중인 프로세스가 n개라면 어떤 프로세스도 (n-1)q 이상을 기다리지 않아도 된다. 이는 곧 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 큰 장점을 가지게 된다.
타임 퀀텀을 얼마로 설정하냐에 따라 OS의 스케줄링 성능이 좌지우지된다.
| Process | Burst time | Turnaround time | Waiting time |
|---|---|---|---|
| P1 | 24 | 30 | 6 ( 10 - 4 ) |
| P2 | 3 | 7 | 4 |
| P3 | 3 | 10 | 7 |
timequantum : 4
총 대기시간 : ( 6 + 4 + 7 ) = 17 평균 대기시간 : 17 / 3 = 5.66
라운드 로빈방식만 사용하면 대기시간이 길어질 수 있지만 후에 이를 SJF와 함께 사용하면 유용학게 사용할 수 있다.
우선순위 스케줄링( Priority Scheduling )
특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다. 우선순위를 정하는 기준으로는 위에서 언급한 SJF, SRTF 알고리즘 등이 있고, 우선순위가 같은 프로세스들은 FCFS 순서로 스케줄 된다.
프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식을 사용해 기아 문제를 어느 정도 해결할 수 있다.
| Process | Priority | Burst time | Turnaround time | Waiting time |
|---|---|---|---|---|
| P1 | 3 | 10 | 16 | 6 |
| P2 | 1 | 1 | 1 | 0 |
| P3 | 4 | 2 | 18 | 16 |
| P4 | 5 | 1 | 19 | 18 |
| P5 | 2 | 5 | 6 | 1 |
총 대기시간 : ( 6 + 0 + 16 + 18 + 1 ) = 41 평균 대기시간 : 17 / 3 = 8.2
다단계 큐 스케줄링( Multilevel Queue Scheduling )
다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 당연히 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되야 다음 우선순위 큐가 실행될 수 있다. 만약 우선순위가 낮은 큐에서 작업을 실행 중일 때 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링 방식을 사용한다. 한 번 우선순위가 매겨져 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다. 각 큐는 라운드 로빈이나 FCFS등 독자적 스케줄링 사용이 가능하다.
큐들 간의 프로세스 이동을 허락하지 않아 우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아 현상이 발생할 수도 있다
다단계 피드백 큐 스케줄링( Multilevel Feedback Queue Scheduling )
다단계 큐의 공평성 문제를 완화하고 기아문제를 해결하기 큐 사이의 이동을 허용한 알고리즘이다.
한 번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아진다. 따라서 더 낮은 큐로 이동하게 된다. 낮은 큐에서 너무 오래 대기하면 다시 상위 큐로 이동 할 수 있다.(에이징 기법을 통한 기아상태 예방)
그리고 더 보완하기 위해 우선순위가 높은 큐보다 우선순위가 낮은 큐에 타임 슬라이스 크기를 크게 준다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용하게 해주기 위함이다.
