[OS] 스케줄링 알고리즘

First Come First Served (FCFS)

비선점형 스케줄링으로 단순한 방식이다. 즉 먼저 도착한 프로세스 순서대로 처리를 한다.

빠른 응답을 요구하는 대화식 시스템에서는 적절하지 못한 스케줄링 방식이다. 

FCFS에서는 프로세스들의 실행 시간에 따라 평균 반환시간과 대기시간의 차이가 크다. 

또한 프로세서를 오래동안 차지하는 프로세스가 먼저 도착하게 되면 뒤에 도착한 프로세스들은 그만큼 기다려야 하는데

이를 Convoy Effect라고 한다. 즉 CPU이용률이 현저하게 낮아진다.

 

FCFS는 구현이 단순하고, 모든 프로세스는 결국 실행이 되기 때문에 공정하다고 할 수 있지만 현대의 시스템에는 맞지 않는 방식이다

 

Shortest Job First (SJF)

SJF는 실행시간이 가장 짧은 프로세스에게 우선권을 주어서 실행하는 방법이다.

같은 실행 시간을 가진 프로세스가 있다면 선입선출의 방식을 적용하게 된다.

 

SJF는 선점과 비선점이 가능하지만 시분할 시스템에서는 비선점형으로 사용하기에는 무리가 있다. 

선점형에서는 문맥교환의 시간비용이 있고 현재 실행 중인 프로세스보다 짧은 프로세스가 끼어들 수 있기 때문에 

Shortest Remaining Time First (SRTF) 스케줄링이라고도 한다.

 

이러한 이유 때문에 특정 프로세스는 자신의 차례가 오지 않고 계속해서 뒤로 밀려나가 프로세서를 얻지 못하는 Starvation 현상이 나타날 수 있다.

또한 항상 짧은 작업을 우선적으로 하기 때문에 FCFS와 다르게 공정하지 못하다 할 수 있고 실행 시간을 정확히 예측하는 것은 어려운 일이기 때문에 실용성에서 떨어진다.

 

Priority Scheduling (우선순위 스케줄링)

우선순위 스케줄링은 준비큐에 도착한 프로세스와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 더 높은 프로세스에게 CPU를 할당하는 방식이다. 

우선순위는 내부 또는 외부적으로 정의가 가능한데, 내부적으로는 제한시간, 평균 프로세스 버스트, 사용 파일 수 등으로 가능하다.

 

우선순위 스케줄링의 특수 케이스를 SJF라고 볼 수 있다.

근본적으로 우선순위 알고리즘에서는 기아(Starvation)문제와 무한 정지 문제가 있다.

그 이유는 실행준비는 되어있지만 계속해서 높은 우선순위를 갖은 프로세스들이 들어오면 자신은 CPU를 할당받지 못하는 상태가 오기 때문이다.

그렇게 된다면 무한정으로 기다리기만 해야된다.

 

이를 해결하기 위한 것이 Aging 기법이다.

오래 기다린 프로세스에 대해서 점진적으로 우선순위를 증가시켜 시간이 지날수록 우선순위가 높아지게 하는 것이다.

 

Round Robin (라운드 로빈)

라운드 로빈은 Time Quantum or Time Slice를 통해서 시간 단위를 규정한다.

그리고 각 프로세스는 해당 시간만큼 프로세서를 얻어서 실행하고 스케줄러는 준비큐를 돌면서 다음 프로세스를 실행한다.

여기서 준비큐는 Circular Queue로 설계 되어서 자신의 시간을 다 실행한 프로세스는 준비 큐의 맨 뒤에 다시 붙어서 자신의 차례를 기다리게 된다.

 

스케줄러가 준비 큐의 첫번째 프로세스를 실행하면 두가지 상황이 발생한다.

1. 규정 시간안에 작업이 끝나서 다음 프로세스로 넘어간다.

2. 규정 시간보다 남은 실행 시간이 있기 때문에 운영체제가 인터럽트를 걸어서 우선 프로세스를 중단시키고 PCB에 저장을 하고 준비 큐 맨 뒤로 보낸다. 이후 다음 프로세스를 실행한다.

 

RR은 규정시간량의 크기에 따라 성능의 차이가 있다.

우선 준비 큐에 n개의 프로세스, 규정시간량은 q이면 각 프로세스는 (n-1) * q 시간 이상을 대기 하지 않는다.

또한 각 프로세스는 최대로 q시간마다 1/n의 시간을 얻게 된다.

 

그렇다면 규정시간을 매우 크게 한다면 어떻게 될까?

이렇게 된다면 선입선출의 방식과 유사하게 작동된다.

각 프로세스는 자신의 작업을 한번에 완료할 시간을 갖기 때문이다. 그런 이유로 짧은 작업 시간을 가진 프로세스들은 오래 기다려야한다.

 

규정시간량이 매우 짧다면 RR을 Processor Sharing이라고 하며 n개의 프로세스가 실제 프로세서의 속도의 1/n처럼 수행되는것 처럼 보이게 된다.

 

하지만 RR에서는 규정시간량 외에 다른 프로세스로 넘어갈 때 발생하는 오버헤드가 존재한다. 다른 프로세스로 넘어가기 전에 PCB에 상태를 저장해야하기 때문이다. 

규정 시간량이 짧으면 문맥 교환의 횟수가 증가하게 되기 때문에 규정 시간량을 충분하게 해야된다.

 

MultiLevel Queue (다단계 큐)

다단계 큐는 작업을 묶음 단위로 분류 할 수 있을 때 사용된다.

준비 큐를 하나가 아닌 종류별로 여러개로 분할을 하여 작업의 특징에 따라 특정 준비 큐에 할당하게 된다.

또한 각 준비 큐는 자신만의 독자적인 스케줄링 알고리즘을 갖는다. 그리고 준비 큐 사이에서도 우선순위가 있다.

 

큐에도 우선순위가 있기 때문에 우선순위가 높은 큐가 먼저 실행이 된다. 즉 낮은 큐는 자신보다 우선순위가 높은 큐가 있다면 기다려야한다. 이 알고리즘에서도 SJF처럼 낮은 우선순위 큐는 무한정 기다리는 기아현상이 발생할 수 있다.

 

MultiLevel Feedback Queue (MLFQ)

MLFQ는 MLQ와 다르게 프로세스는 큐를 옮겨 다닐 수 있다. 보통 작업의 실행 시간이 길면 낮은 단계의 큐로 이동을 하고 결국 FCFS 알고리즘으로 작동하는 큐로 이동을 하게 된다.

 

예를 들어 Q1, Q2, Q3, Q4가 있다면 Q1에는 시간 할당을 2만큼, Q2는 4, Q3는 16 그리고 Q4는 FCFS로 했다면 스케줄러는 우선 Q1에 있는 작업을 수행하고 이후 Q2에 있는 작업들을 수행할 것이다. 즉 우선순위가 높이 있는 큐가 비어 있어야 다음 큐에 있는 작업들이 시작이 된다. 이때 역시 기아 현상이 발생하기 때문에 에이징 방법을 활용한다.

 

이 알고리즘의 특징으로는 우선 시간 할당량이 짧은 큐부터 실행하기 때문에 짧은 시간만을 필요로 하는 작업들은 큐에서 빠르게 처리가 되는 장점이 있다. 시간이 더 필요한 작업이면 하위 큐로 점점 내려가게 되는 것이다.

 

그렇기 때문에 MLFQ를 구현할 때 고려해야하는 점은 큐의 수, 각 큐에 대한 스케줄링, 언제 우선순위가 높은 큐로 이동시킬지 등 정의해야할 사항이 많다.