[OS] CPU 스케줄링(CPU Scheduling)

CPU 스케줄링의 필요성

프로세스는 CPU burst와 I/O burst 두 가지 상태로 순환하면서 작동한다.

CPU burst : CPU 명령을 실행하는 것

I/O burst : I/O 입력을 대기하는 것

참고로 CPU burst가 큰 프로세스를 CPU bound process, I/O burst가 큰 프로세스를 I/O bound process라 한다.

프로세스는 위 사이클처럼 CPU burst와 I/O burst로 상태를 바꾸면서 동작하게 된다.

하지만 대부분의 프로세스는 CPU burst보다 I/O burst가 큰 I/O bound process이다.

I/O burst 상태인 프로세스는 사용자의 입력이 있을 때까지 대기하기 때문에 CPU는 그동안 다른 일을 할 수 없게 된다. 

이때 CPU를 할당하고 있는 프로세스 대신 다른 프로세스를 실행하게 하는 것이 CPU 스케줄러이다.

 

CPU 스케줄러

CPU 스케줄러는 메모리 안에 있는 실행될 준비가 된 프로세스를 선택하여 CPU에 할당한다.

CPU 스케줄링은 다음과 같은 상황에서 발생할 수 있다.

1. 프로세스가 running state에서 waiting state로 변경될 때
2. 프로세스가 running state에서 ready state로 변경될 때
3. 프로세스가 waiting state에서 ready state로 변경될 때
4. 프로세스가 종료될 때

 

디스패처(Dispather)

디스패처는 CPU 스케줄러가 선택한 프로세스에게 CPU를 점유할 수 있는 권한을 준다.

또한 디스패처는 다음과 같은 일을 수행한다.

• 문맥 교환
• 사용자 모드로 전환
• 프로그램을 다시 시작하기 위해 적절한 위치로 프로그램 이동

 

스케줄링 기준

• CPU 이용률 : CPU를 가능한 얼마나 바쁘게 유지하는지
• 처리량 : 단위 시간당 실행이 완료된 프로세스의 수
• 총 처리 시간 : 특정 프로세스가 실행되는데 필요한 총 시간
• 대기 시간 : 프로세스가 ready queue에서 기다리는데 소요된 시간
• 응답 시간 : request가 제출되고 첫 response가 생성되는 데 걸리는 시간

 

스케줄링 알고리즘

FCFS(First-Come, First-Served)

FCFS 알고리즘은 CPU에 먼저 요청한 프로세스가 먼저 CPU를 할당받는 식으로 동작한다.

P1, P2, P3가 있을 때 각각 Burst time이 24, 3, 3이라고 하겠다.

 

P1, P2, P3 순서로 요청

이때 프로세스마다의 waiting time은 P1 = 0, P2 = 24, P3 = 27이다

평균 waiting time은 (0 + 24 + 27) / 3 = 17이다.

 

P2, P3, P1 순서로 요청

이때 프로세스마다의 waiting time은 P1 = 6, P2 = 0, P3 = 3이다

평균 waiting time은 (6 + 0 + 3) / 3 = 3이다.

문제점

하나의 프로세스가 CPU를 독점할 수 있다.

해결책

프로세스가 CPU를 점유할 수 있는 최대 제한 시간을 정한다.

 

SJF(Shortest Job First)

SJF 알고리즘은 가장 Burst Time이 작은 프로세스를 CPU에 할당한다.

 

Non-premitive 한 경우

P1, P2, P3, P4가 있을 때 각각 Burst time이 6, 8, 7, 3이라고 하겠다.

Burst time이 작은 순서대로 P4, P1, P3, P2가 CPU에 차례로 할당된다.

 

이때 프로세스마다의 waiting time은 P1 = 3, P2 = 16, P3 = 9, P4 = 0이다

평균 waiting time은 (3 + 16 + 9 + 0) / 4 = 7이다.

 

Premitive 한 경우

Premitive 하게 SJF 알고리즘이 동작할 경우 SRTF(Shortest Remaining Time First)라고 부른다.

P1, P2, P3, P4가 있을 때 각각 Burst time이 8, 4, 9, 5이고 Arrived Time이 0, 1, 2, 3이라고 하겠다.

새로운 도착할 때마다 최소 burst time인 프로세스를 선택하게 된다.

평균 waiting time은 ((10 - 1) + (1 - 1) + (17 - 2)  +  (5 - 3)) / 4 = 6.5이다.

문제점

얼핏 봤을 때는 평균 waiting time을 줄여주는 가장 효율적인 알고리즘으로 볼 수 있지만, 실제 CPU burst time을 예측하는 것은 쉽지 않기 때문에 실제로 적용하기에는 어려움이 있다.

 

Round Robin

각각의 프로세스에게 작은 단위의 CPU 할당 시간을 동일하게 주는 알고리즘이다.

CPU 스케줄러는 ready queue에 맨 앞에 있는 프로세스에게 일정한 time quantum만큼의 CPU 시간을 준다.

주어진 시간이 끝나기 전에 프로세스가 종료되면 다른 프로세스를 차례로 할당시키고, 시간이 끝났을 때 프로세스가 할 일을 모두 마치지 못한 경우에는 ready queue에 맨 뒤에 push 하고 다른 프로세스로 context switch가 일어난다.

P1, P2, P3가 있을 때 각각 Burst time이 24, 3, 3이라고 하겠다.

time quantum이 4일 때 Round Robin을 사용하면 다음과 같은 순서로 프로세스가 실행된다.

문제점

Round Robin 알고리즘의 성능 time quantum의 크기에 따라 달라질 수 있다.

Time quantum이 매우 큰 경우에는 FCFS와 동일하게 작동하게 되고, 매우 작은 경우에는 수많은 context switch로 인해 성능저하가 일어날 수 있다.

 

Priority Scheduling

프로세스마다 우선순위 값을 받아 우선순위가 높은 순서대로 프로세스를 실행하는 알고리즘이다.

우선순위가 같은 프로세스는 FCFS와 동일한 방식으로 작동한다.

P1, P2, P3, P4, P5가 있을 때 각각 Burst time이 10, 1, 2, 1, 5이고 우선순위가 3, 1, 4, 5, 2라고 하겠다.

프로세스들 중 우선순위가 높은 P2가 먼저 시작하고, 우선순위에 따라 프로세스들이 차례로 실행되는 것을 볼 수 있다.

문제점

우선순위가 낮은 프로세스가 있을 때, 이 프로세스보다 우선순위가 높은 프로세스들이 계속 들어오게 되면 우선순위가 낮은 프로세스는 영원히 실행될 수 없다.

이를 해결하기 위해 프로세스가 대기했던 시간에 따라 우선순위를 높이는 방법을 선택할 수 있다.