CPU 스케줄링 알고리즘 요약정리

교니·2023년 2월 16일

MegabyteSchool cs공부 개발자취업부트캠프 국비지원교육 내일배움카드 메가바이트스쿨 패스트캠퍼스

CS 공부

목록 보기

10/12

CPU 스케줄링 알고리즘이란?

CPU core가 하나라면 한 번에 하나의 프로세스만 실행 가능할 것이다. 이때 필요한 것이 CPU 스케줄링이다.

즉, CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다.


** CPU 스케줄러는 언제 스케줄링을 결정하는가?

1) 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때

2) 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 

3) 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때

4) 종료(Terminated)될 때

-> 1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고 한다. 이외의 모든 스케줄링은 선점형(preemptive) 스케줄링이라고 한다.

비선점형 스케줄링

어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식. 강제로 프로세스를 중지하지 않는다. 따라서 문맥 교환(Context Switching)으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 나게 된다.

비선점형 스케줄링의 종류

FCFS (First Come, First Served)

가장 먼저 요청한 프로세스에 CPU를 할당해주는 선착순 방식이다.
Convoy Effect(호위 효과)가 발생할 수 있다. Convoy 효과란 몇 개의 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 현상을 말한다.

SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘이다. 하지만 실제로는 프로세스의 CPU 실행 시간을 예측하는 것이 어렵다는 문제가 존재한다. 또한 긴 시간을 필요로 하는 프로세스가 우선순위가 계속 밀려 실행되지 못하고 무기한으로 대기하게 되는 기아(Starvation) 현상이 일어날 수 있다.

우선순위 (Priority)

각각의 프로세스에 우선순위 넘버가 있는 알고리즘. 예를 들어 SJF 알고리즘의 경우, 낮은 우선 순위의 프로세스가 절대 실행되지 않는 기아(Starvation) 문제가 발생할 수 있는데 이를 해결하기 위해서 노화(aging)를 사용할 수 있다. 오래된 작업의 우선순위를 높여주는 식.

선점형 스케줄링

현대 운영체제가 사용하고 있는 방식으로, 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식. 알고리즘에 따라 강제로 중단시키고 다른 프로세스에 CPU를 할당하는 방식이다.
처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드(Overhead)가 커질 수 있다.

선점형 스케줄링의 종류

라운드 로빈 (RR, Round Robin)

현대 컴퓨터가 사용하는 우선순위 스케줄링이다. 각각의 프로세스에 동일한 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다. 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어가므로 선점형 방식이다.

응답 시간을 빠르게 할 수 있다는 장점이 있지만 할당 시간이 길면 FCFS처럼 작동하고, 반대로 할당 시간이 너무 짧으면 process sharing이라고 부른다. 이것은 n개의 프로세스가 프로세서 속도의 1/n 씩으로 작동함을 의미한다.

SRF

실행되고 있는 프로세스는 중단 없이 끝까지 실행하는 비선점형 SJF와는 다르게, 선점형 SRJ에서는 현재 실행되고 있는 프로세스의 남은 시간보다 더 빨리 끝날 수 있는 짧은 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 짧은 프로세스를 실행하도록 바꾸게 된다. SRTF(Shortest Remaining Time First)라고도 부른다.
이 스케줄링은 평균 대기 시간을 줄일 수 있지만 역시 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다는 문제가 존재한다.

다단계 큐 (Multilevel Queue)

우선순위에 따른 준비 큐가 여러 개의 큐들로 나뉘고 각각의 큐는 각자의 스케줄링 알고리즘을 가지고 있다. 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아(Starvation)현상이 나타날 수도 있으며, 각 큐 사이에서 프로세스들이 이동할 수 없어서 유연성이 떨어지는 특징이 있다.