[개념 정리/운영체제] CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

CPU가 어떤 프로세스를 선택할 것인지는 스케줄링 알고리즘을 통해 선택되며,

효율적으로 선택하는 것이 중요하다.

 

효율적이란, 아래 세 가지 사항을 만족시키는 것을 말한다.

 

1. CPU 사용률이 높은가?
2. 단위 시간당 작업을 마친 프로세스의 수(처리량)이 높은가?
3. 작업을 요청한 프로세스가 작업을 시작하기 전 대기하는 시간이 짧은가?

CPU 스케줄링 방식은 비선점형과 선점형으로 나뉜다.

 

비선점형 방식(non-preemptive)

비선점형 방식에는 FCFS, SJF, 우선순위 방식 세 가지가 있다.

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며,

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

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

 

FCFS(First Come, First Served)

FCFS는 먼저 온 것을 가장 먼저 처리하는 알고리즘이다.

길게 수행되는 프로세스 때문에

준비 큐에서 대기가 길어지는 현상(convoy effect)이 발생한다는 단점이 있다.

 

SJF(Shortest Job First)

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

긴 실행 시간을 가진 프로세스가 실행되지 않는 starvation 현상이 발생할 수 있다.

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

실제로는, 실행 시간을 정확히 알기 어려워 과거의 실행 시간을 토대로 추측한 값을 사용한다.

 

우선순위 + SJF

기존 SJF 스케줄링의 경우, 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다.

이를 오래된 작업일수록 우선순위를 높이는 방법(aging)을 통해 단점을 보완한 알고리즘이다.

 

여기서 우선순위는

작업의 시간, 프로세스의 메모리 요구 사항, 열린 파일 수, 평균 CPU 사용량 등을 고려하여 설정된다.

 

참고로, 우선순위 알고리즘은 우선순위 + SJF 외에도,

우선순위 + FCFS, 혹은 선점형, 비선점형 우선순위 스케줄링 알고리즘을 말하기도 한다.

 

선점형 방식(preemptive)

선점형 방식은 현대 운영체제가 사용하는 방식으로 

사용하고 있는 프로세스를 알고리즘에 의해 중단시키고

강제로 다른 프로세스에 CPU 소유권을 할당할 수 있는 알고리즘이다.

 

선점형 방식에는 라운드 로빈, SRF, 다단계 큐가 있다.

 

라운드 로빈(RR, Round Robin)

라운드 로빈은 현대 컴퓨터가 사용하는 스케줄링 방법으로,

단순한 선점형 알고리즘이다.

각 프로세스는 동일한 시간을 할당 받아, 그 시간에 안에 끝나지 않으면

다시 준비 큐(ready queue)의 뒤로 들어가는 알고리즘이다.

 

예를 들어, q만큼의 할당 시간이 부여되고,

N개의 프로세스가 운영된다고 하면 

(N - 1) * q 시간이 지나면 자신의 차례가 온다.

 

할당 시간이 너무 크면 FCFS가 되고,

너무 짧으면 스위칭이 잦아져 오버헤드가 발생하며 비용이 커진다.

 

일반적으로 전체 작업 시간은 길어지지만

평균 응답 시간은 짧아진다는 특징이 있다.

이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.

 

SRF(Shortest Remaining Time First, SRTF)

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 

기존 작업을 모두 수행 후 그 다음 짧은 작업을 이어나가지만,

SRF는 중간에 더 짧은 작업이 들어오면 수행 중이던 프로세스를 중지하고

해당 프로세스를 수행하는 알고리즘이다.

 

다단계 큐

다단계 큐는 우선순위에 따른 준비 큐를 여러개 사용하고,

큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다.

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

유연성이 떨어지는 특징이 있다.

우선순위가 높은 큐부터 처리되기 때문에 

낮은 큐의 프로세스가 처리되지 않는 기아현상(starvation)이 발생할 수 있다.

다단계 큐

비선점형 알고리즘으로만 이루어진 다단계 큐 스케줄링 알고리즘도 있다.

 

참고: inflearn 강의 'CS 지식의 정석 - 큰돌'