[CS] 운영체제 CPU 스케줄링 알고리즘

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

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을

스레드 단위로 CPU에 할당한다

 

프로그램이 실행될 때는 CPU 스케줄링 알고리즘이

어떤 CPU 소유권을 줄것인지 결정한다

 

이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게,

준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는것을 목표로 한다

 

2. 비선점형 방식 (Non-Preemptive)

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

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

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

 

FCFS (First Come First Served)

- 비선점 방법이자 스케줄링 알고리즘 중 가장 간단한 기법이다

 

- 프로세스는 준비 큐에서 도착순서에 따라 디스패치되며

일단 한 프로세스가 CPU를 차지하면 그 프로세스의 수행이 완료된 후에

그 다음 프로세스가 CPU 차지하고 수행된다

 

- 겉보기에는 공정하지만, 짧은 작업이 긴 작업을 기다리게 되기도 하고

중요한 프로세스가 나중에 수행될 수 있는 불합리함이 있어 대화식 시스템에 부적합하다

 

- 최근 시스템에서 FCFS 스케줄링은 주요 방법이 아니라 다른 방법과 결합하여 쓰이고 있다

 

 

예제

4개의 프로세스가 다음과 같은 실행시간을 가지고 있다고 가정해보자

4개의 프로세스 A, B, C, D가 거의 동시에 입력되었다면

FCFS 스케줄링 알고리즘의 수행결과는 다음과 같다

 

 

SJF (Shortest Job First)

- 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상된 것을 먼저 디스패치하여

실행하는 비선점 스케줄링 알고리즘이다

 

- 일괄처리 환경에서 구현이 쉽고 알고리즘으로 실행할 프로세스의 CPU 소요시간이 미리 주어진다

 

예제 1

4개의 프로세스가 동시에 입려되어 모두 준비 큐에 들어 있고

예상한 프로세스 각각의 실행시간은 다음과 같다

 

 

예제 2

이번에는 4개의 프로세스가 1단위의 CPU 사이클 시간의 차이를 두고

연속적으로 입력되는 경우를 가정해본다

 

 

우선순위

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

 

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

 

3. 선점형 (Preemptive)

선점형 방식은 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를

알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을

할당하는 방식을 말한다

 

RR (Round Robin)

- 대화형 시스템에서 사용되는 선점 스케줄링 방식이다

 

- 프로세스가 도착한 순서대로 프로세스를 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한한다

 

- 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료하지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU 독접하지 않고 공평하게 이용이 가능하다

 

 

예제

다음과 같이 4개의 프로세스가 주어지고 시간 할당량은 3이라고 가장하자

 

 

SRT(Shortest Remaining Time)

- SJF 알고리즘의 선점(preemptive) 알고리즘 버전으로,

새로 들어오는 프로세스를 포함하여 실행이 끝날때까지

남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치하여 실행한다

 

- 대화형 운영체제에 유용하다

 

- SRT가 SJF보다 평균 대기시간이나 평균 반환시간에서 효율적이다

 

- SRT는 실행되는 각 작업의 실행시간을 추적하여 각

프로세스가 서비스를 받은 시간이 기록되어야 하며

때로는 선점을 위한 문맥 교환되 해야 하므로 SJF보다 오버헤드가 더 크다

 

- SRT는 빠르지만 일반적인 운영체제에서는 그러한 장점이 문맥교환에

요구되는 시간을 고려하여 평가되어야 한다

 

 

다단계 큐 ( MLQ, MultiLevel Queue)

- 우선순위마다 준비 큐 형성

 

- 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당 (우선순위가 낮은 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링)

 

- 각 큐는 라운드 로빈이나 FCFS등 독자적 스케줄링 사용 가능

 

- 대화형, 배치(Background)등의 프로세스 성격에 따라 우선순위 부여

 

- 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어짐

 

- 우선순위가 낮은 프로세스가 오랬동안 CPU 할당을 기다리는 기아 현상이 발생할 수도 있음