[Operating System] CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

출처 : 면접을 위한 CS 전공지식 노트(2022)

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야하는 일을 스레드 단위로 CPU에 할당한다.

프로그램이 실행될 때 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 지 결정한다.

 

CPU 스케줄링 알고리즘은 CPU 이용률은 높게,

주어진 시간에 많은 일을 하게,

준비 큐(ready queue)에 있는 프로세스는 적게,

응답 시간은 짧게 설정하는 것을 목표로 한다.

 

비선점형 방식(non-preemtive)

프로세스가 스스로 CPU 소유권을 포기하는 방식이다.

강제로 프로세스를 중지하지 않는다.

따라서 컨텍스트 스위칭으로 인한 부하가 적다.

 

다만 CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 좋지 않다.

 

FCFS(First Come, First Served)

준비 큐에 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘.

한 번 실행되면 그 프로세스가 끝나야지 다음 프로세스를 실행할 수 있다.

 

Process	실행시간
P1	24
P2	3
P3	3

위와 같이 프로세스와 실행시간이 있고 CPU 스케줄러가 FCFS에 따라 일을 처리한다고 가정하면 다음과 같은 실행 순서를 갖게 된다.

 

출처 : Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 5

프로세스가 도착하는 순서는 P1, P2, P3이라고 하면

가장 실행 시간이 긴 P1이 먼저 실행되고 P2, P3이 실행된다.

 

이때 P1처럼 실행 시간이 긴 프로세스가 먼저 오게되면 다른 프로세스들이 준비 큐에서 오래 기다리게 된다.

이와 같은 현상을 convoy effect라고 한다.

 

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘.

 

Process	실행시간
P1	6
P2	8
P3	7
P4	3

위와 같이 프로세스와 실행시간이 있고 CPU 스케줄러가 SJF에 따라 일을 처리한다고 가정하면 다음과 같은 실행 순서를 갖게 된다.

 

출처 : Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 5

 

가장 실행 시간이 짧은 P4가 실행되고 그 다음 순으로 P1, P3, P2가 실행된다.

(실제로는 실행 시간을 알 수 없으므로 과거의 실행 시간을 토대로 추측해서 사용하는 경우가 있다)

 

이때 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어난다.

평균 대기 시간이 가장 짧다.

 

우선순위

우선순위를 높이는 방법(aging)을 사용한다.

프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정한다.

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 문제가 있었지만 우선순위 방식은 이를 보완한 것이다.

 

선점형 방식(preemptive)

지금 사용하고 있는 프로세스는 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식이다.

현대 운영체제가 쓰는 방식이다.

 

라운드 로빈(RR, Round Robin)

각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘이다.

현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링(priority scheduling)의 일종이다.

 

Process	실행 시간
P1	24
P2	3
P3	3

위와 같이 프로세스와 실행시간이 있고 CPU 스케줄러가 RR에 따라 일을 처리한다고 가정하면 다음과 같은 실행 순서를 갖게 된다.

 

출처 : Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 5

만약 할당 시간이 4ms라고 하면 위 그림과 같이 프로세스가 실행된다.

P1의 실행 시간은 24인데 4ms 사용할 수 있으므로 실행하다가 쫓겨난다.

P2는 실행 시간이 3이라서 할당 시간 내에 다 실행되므로 계속 실행되고 종료될 수 있다.

P3의 경우도 P2와 마찬가지라서 실행된 후 종료까지 된다.

 

P1의 경우는 P2, P3가 종료까지 되고 나서도 계속 실행 시간이 남아있어서 4ms 실행되고 끝난다.

 

할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져 오버헤드가 커진다.

일반적으로 전체 작업 시간은 길어지지만, 평균 응답 시간은 짧아진다는 특징이 있다.

 

로드밸런서에서 트래픽 분산 알고리즘으로 사용된다.

 

SRF(Shortest Remaining Time First)

중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

SJF는 중간에 더 짧은 작업이 들어와도 기존의 작업을 모두 수행하고 다음 짧은 작업으로 넘어간다.

 

Process	도착 시간	실행 시간
P1	0	8
P2	1	4
P3	2	9
P4	3	5

위와 같이 프로세스와 실행시간이 있고 CPU 스케줄러가 SRF에 따라 일을 처리한다고 가정하면 다음과 같은 실행 순서를 갖게 된다.

 

출처 : Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 5

제일 빨리 들어온 것은 P1 이었지만 P1의 실행 시간인 8보다 짧은 P2가 중간에 들어와서 중간에 P2를 실행한다.

P2를 실행하던 중에 P3이 들어오지만 P2보다는 실행 시간(9)이 길어서 P2는 계속 실행된다.

그리고 P4도 들어오지만 P2보다 실행 시간이 길어서(P2 = 4, P4 = 5) P2가 다 끝나야 P4가 실행된다.

P4가 다 실행되고 중간에 하다가 만 P1의 남은 실행 시간이 P3보다 짧아서(P1 = 7, P3 = 9) P1부터 실행하고 P3를 실행한다.

 

 

다단계 큐

출처 : 면접을 위한 CS 전공지식 노트(2022)

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것이다.

상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

 

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만

유연성이 좋지 않다.

 

참조

• 주홍철, 면접을 위한 CS 전공지식 노트, 길벗(2022)
• 조성호, 쉽게 배우는 운영체제, 한빛아카데미(2018)
• Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 5