[CS/운영체제] CPU 스케줄링

CPU 스케줄링 알고리즘

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

프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, Ready Queue에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.

 

1. 비선점형 방식(=비전형 방식)

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서 프로세스 종료나 I/O 등의 이벤트가 발생할 때까지 실행을 보장하며, Context Switching으로 인한 부하가 적다.

 

(1) FCFS(First Come First Serve)

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

길게 수행되는 프로세스 때문에 Ready Queue에서 오래 기다리는 현상(convoy effect)이 발생한다는 단점이 있다.

 

(2) SJF(Shortest Job First)

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

해당 방식은 긴 시간을 가진 프로세스가 실행되지 않는 기아 상태(Starvation)가 발생한다는 단점이 있지만, 평균 대기 시간이 가장 짧다는 특징이 있다.

하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용한다.

 

(3) 우선순위

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 기아 상태가 발생한다.

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

이러한 우선순위는 앞서 설명한 SJF와 우선순위를 말하는 것 뿐만 아니라 FCFS를 활용하여 만들기도 하며 선점형, 비선점형적인 우선순위 스케줄링 알고리즘을 말하기도 한다.

 

2. 선점형 방식

선점형 방식은 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식이다.

(1) 라운드 로빈

라운드 로빈은 현대 컴퓨터가 쓰는 선점형 알고리즘 스케줄링 방법으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 Ready Queue의 뒤로 가는 알고리즘이다.

 

예를 들어 q만큼의 할당 시간이 부여되었고 N개의 프로세스가 운영된다고 하면 (N - 1) * q 시간이 지나면 자기 차례가 오게 된다. 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져 오버헤드, 즉 비용이 커진다.

 

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

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

 

(2) SRTF(Shortest Remaining Time First)

비선점형 방식 중 SJF 방식은 중간에 실행 시간이 더 짧은 작업이 들어와도 기존의 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나가는데, SRTF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

 

(3) 다단계 큐(Multi-level queue)

우선순위 별로 Ready Queue를 여러 개 사용하는 방식

• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
• 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리

다단계 큐는 기본적으로 큐 간의 이동이 불가능하다.

이로 인해 우선 순위가 낮은 프로세스는 계속해서 실행이 연기될 수 있음에 따라 기아 현상이 발생할 수 있다.

 

(4) 다단계 피드백 큐 스케줄링(Multi-level feedback queue)

큐 간의 이동이 불가능했던 다단계 큐 스케줄링의 단점을 보완한 방식이다. 다단계 피드백 큐 스케줄링을 통해 큐 간의 이동이 가능하다는 특징이 있다.

즉, 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식이다.