[운영체제] cpu 스케쥴링 알고리즘

CPU 스케쥴링

메모리에 있는 준비(READY)상태의 프로세스 중 하나를 선택해 CPU자원을 할당하는 것

CPU 스케쥴링이 일어나는 시점

기존에 CPU를 사용하던 프로세스가 계속 프로세스를 사용할 수 있는데도 불구하고 자원을 빼앗는지에 대한 여부로 비선점/선점으로 나눈다.

Non Preemptive (비선점)	일단 CPU가 프로세스에 할당되면, 프로세스가 종료하던가 또는 대기상태로 전환해 CPU를 해제할 때까지 CPU를 점유하는 방법. 모든 프로세스에 대해서 공정한 처리가 가능하지만 긴급 응답을 요하는 작업에는 좋지 못하다. 짧은 작업이 긴 작업이 끝날 때까지 기다리는 문제점이 생길 수 있다.
	- 실행상태 → 대기상태 : 입출력 요청 - 종료될 때
	예) FCFS, SJF, HRN
Preemptive (선점)	한 프로세스가 CPU를 차지하고 있을 때, 다른 프로세스가 현재의 프로세스를 중지시키고, CPU를 차지할 수 있도록 하는 방법. 긴급을 요하는 우선순위를 갖는 시분할 처리로 실시간 처리에 유용하다.
	- 실행상태 → 준비상태 : 인터럽트 발생할 때 - 대기상태 → 준비상태 : 입출력이 종료될 때
	예) RR, MLQ, MFQ

Running 상태의 CPU를 빼앗는 경우는 없다. CPU자원을 잃는 경우는 대기, 준비, 종료 상태이다.

CPU 스케쥴링 종류

FCFS(First-Come, First-Served) 스케쥴링

Ready Queue에 들어온 순서대로 CPU를 할당한다. 

먼저 들어온 프로세스가 CPU자원을 모두 사용한 뒤 다음 프로세스에 할당하므로 비선점형 스케쥴링에 해당한다.

- 장점 : 구현이 가장 간단하고 처리 순서가 명확하다.

- 단점 : convoy effect가 생길 수 있다.

SJF(Shortest Job First) 스케쥴링

Ready Queue에 있는 작업 중 작은 프로세스(처리시간이 짧은 프로세스)부터 자원을 할당한다. 

선점형으로는 할당받을 당시엔 Burst(처리시간)가 가장 작은 프로세스라 자원을 할당 받았지만, 작업 중에 Ready Queue에 들어온 프로세스가

남은 Burst보다 더 작은 Burst를 가진다면 자원을 빼앗아 그 짧은 작업부터 처리하는 방식이다. Average Waiting Time이 줄어든다.

비선점형은 할당받을 당신에 Ready Queue에 있는 프로세스 중 Burst가 가장 작은 프로세스가 자원을 할당 받고 

이 프로세스가 모두 끝난 후에 다른 프로세스에게 자원을 할당하는 것이다. 

Non Preemptive SJF라고도 불리나 SRF(Shortest Remaining Time First)스케쥴링이라고도 한다.

- 장점 : 최소의 Average Waiting Time을 실현할 수 있다.

- 단점 : Starvation이 생길 수 있다.

- 해결법 : Aging

RR(Round Robin) 스케쥴링

프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간 단위로 CPU를 할당하는 방식이고 선점형으로 분류된다.

- 장점 : 응답시간이 짧아지므로 실시간 시스템에 유리하다.

- 단점 : context switch의 오버헤드가 크다.

HRN(Highest Response ratio Next) 스케쥴링

SJF의 단점을 보완한 스케쥴링 알고리즘으로, 처리시간과 대기시간을 모두 고려하여 우선순위를 정한다.

긴작업과 짧은작업간의 지나친 불편들을 해결하기 위해 처리시간과 대기시간을 고려한 공식을 적용한다. 선점형과 비선점형으로 모두 구현할 수 있지만 일반적으로 비선점형으로 분류된다.

처리시간에 비해 기다린 시간이 크다면 우선순위를 가질 수 있다.

Waiting Time + Burst / Burst

MLQ(Multi Level Queue) 스케쥴링

작업들이 여러 종류의 Ready Queue로 구분하여 스케쥴링하는 기법으로 각 Ready Queue 마다 독자적인 스케줄링 알고리즘을 사용하여 CPU를 할당한다. 모든 프로세스가 단순히 작업시간이나 대기시간만으로 우선순위를 정할 만큼 동일한 중요도를 가지는 것은 아니다. MLQ알고리즘은 작업시간과 대기시간만을 고려한 단순한 우선순위 할당보다 작업 자체의 우선순위를 고려하는 더 고도화된 스케쥴링 기법이다.

일반적으로 5개의 Ready Queue로 구분되며 각각 시스템 작업, 대화형 작업, 편집 작업, 일괄 처리형 작업, 학생 작업 순서대로 우선순위를 가진다. 상위 Ready Queue에 작업이 들어오면 하위 Ready Queue의 작업이 수행중이더라도 자운을 빼앗아 선점하므로 선점형으로 분류된다.

MFQ(Multilevel Feedback Queue) 스케쥴링

MLQ스케줄링 보다 좀 더 고도화된 알고리즘으로, 정확한 개념은 아니지만 쉽게 설명하자면 MLQ에서 생길 수 있는 Starvation을 보완한 스케쥴링 기법이다. MLQ처럼 중요 작업을 무조건 높은 우선순위로 분류할 경우 덜 중요한 작업들은 작업시간이 짧든 길든 CPU작업을 오랫동안 할당받지 못하는 문제가 생길 수 있다. SJF에서 작업시간이 긴 프로세스가 자원을 할당받지 못하는 문제와 같은 맥락이다.

이를 해결하기 위해 중요도 별로 여러 Ready Queue를 두되 각 Ready Queue마다 할당 시간을 부여하여 Ready Queue를 비선점형으로 운용하는 알고리즘이다.

참고

convoy effect

하나의 큰 프로세스가 자원을 오랫동안 독점하는 동안 작은 프로세스들이 자원을 할당받지 못한다.

같은 중요도라 가정했을 때, 작은 프로세스들이 자원을 먼저 사용하고 큰 프로세스가 사용하는 것이 성능상 유리하다.

Starvation

우선순위가 가장 작거나 처리시간이 긴 프로세스가 자원을 계속 할당받지 못하는 문제로 SJF, SRF에선 처리시간이 짧은 프로세스가 먼저 자원을 할당받으므로 처리시간이 작은 프로세스가 계속 Ready Queue에 들어올 경우 처리시간이 긴 프로세스는 오랫동안 대기했음에도 불구하고 계속 자원을 할당받지 못하는 문제가 생긴다.

Aging

Ready Queue에 있는 프로세스에 나이를 부여하는 방법이다. 

얼마나 오래기다렸는가를 고려하여 처리시간이 긴 프로세스임에도 기다린 시간이 길다면 자원을 할당해준다.