CPU 스케줄링 알고리즘

CPU 스케줄링이란?

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

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

CPU자원을 가지고 있다가 빼앗길수 있는 상황은 아래와 같다.

• 실행(Running)상태에서 대기(Waiting)상태로 전환될 때 (예, 입출력 요청) – Non Preemptive(비선점)
• 실행(Running)상태에서 준비(Ready)상태로 전환될 때 (예, 인터럽트 발생할 때) – Preemptive(선점)
• 대기(Waiting)상태에서 준비(Ready)상태로 전환될 때 (예, 입출력이 종료될 때) - Preemptive(선점)
• 종료될 때(Terminated) - Non Preemptive(비선점)

선점과 비선점의 차이는 기존에 CPU를 사용하던 프로세스가 계속 프로세스를 사용할 수 있는데도 불구하고 자원을 빼앗는지에 대한 여부이다. 대기상태로 전환되거나 종료된 경우에는 CPU사용을 멈춘 상태이므로 다른 CPU자원이 다른 프로세스에 할당 되는 것이 당연하나 준비 상태일 때는 CPU 계속 사용이 가능한 상태이므로 CPU자원이 다른 프로세스로 이동하는 것은 CPU자원을 빼앗긴 것이다.

※ Running 상태의 CPU를 빼앗는 경우는 없다. CPU자원을 잃을 수 있는 경우 = Waiting, Ready, Terminated

선점(preemptive) 스케줄링

한 프로세스가 CPU를 차지하고 있을 때, 다른 프로세스가 현재의 프로세스를 중지시키고, CPU를 차지할 수 있도록 하는 방법

긴급을 요하는 우선순위를 갖는 시분할 처리, 실시간 처리에 유용

비선점(Non-Preemptive) 스케줄링

일단 CPU가 한 process에 할당되면, process가 종료하던가, 또는 대기상태로 전환해 CPU를 해제할 때까지 CPU를 점유하는 방법

모든 process에 대해서 공정한 처리가 가능하지만 긴급 응답을 요하는 작업에는 좋지 못하다. 짧은 작업이 긴 작업이 끝날 때까지 기다리는 문제점(Convoy Effect)가 생길 수 있다.

FCFS(First-Come, First-served) 스케줄링

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

• 장점 : 구현이 가장 간단하고 처리 순서가 명확하다.
• 단점 : Convoy Effect가 생길 수 있다.

Convoy Effect

하나의 큰 프로세스가 자원을 오랫동안 독점 하는 동안 작은 프로세스들이 자원을 할당받지 못한다. 같은 중요도라 가정했을때 작은 프로세스들이 자원을 먼저 사용하고 큰 프로세스가 사용 하는 것이 성능상 유리하다.

SJF(Shortest Job First) 스케줄링

Ready Queue에 있는 작업 중 작은 프로세스(처리 시간이 짧은 프로세스) 부터 자원을 할당받는다. 선점형과 비선점형으로 나뉜다.

비선점형은 할당받을 당시에 Ready Queue에 있는 프로세스 중 처리시간(Burst)이 가장 작은 프로세스가 자원을 할당 받고 이 프로세스가 모두 끝난 후에 다른 프로세스에게 자원을 할당 하는 것이다.

선점형은 할당받을 당시엔 Burst가 가장 작은 프로세스라 자원을 할당 받았지만, 작업중에 Ready Queue에 들어온 프로세스가 남은 Burst보다 더 작은 Burst를 가진다면  자원을 빼앗아 그 짧은 작업부터 처리하는 방식이다. Average Waiting Time이 줄어든다.

비선점형은 Non Preemptive SJF라고도 불리나 SRF(Shortest Remaining Time First) 스케줄링이라고 다른 이름을 사용하기도 한다.

• 장점 : 최소의 Average Waiting Time을 실현할 수 있다.
• 단점 : Starvation이 생길 수 있다.
• 해결법 : Aging
• 현실적 문제점 : 처리 시간은 실제로 프로세스를 돌려봐야 정확히 알 수 있다.

Starvation

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

Aging

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

HRN(Highest Response ratio Next) 스케줄링

SJF의 단점을 보완한 스케줄링 알고리즘으로, 처리시간과 대기시간을 모두 고려하여 우선순위를 정한다. 긴 작업과 짧은 작업간의 지나친 불편들을 해결하기 위해 처리시간과 대기시간을 고려한 공식을 적용한다. 선점형과 비선점형으로 모두 구현할 수 있지만 일반적으로 비선점형으로 분류된다.

Waiting Time + Burst / 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를 비선점형으로 운용하는 알고리즘이다.

개념 이해 확인

1. 선점형과 비선점형의 개념 차이를 설명할 수 있는가?
2. HRN 스케줄링의 우선순위를 계산하는 공식을 말할 수 있는가?
3. Convoy Effect는 어떤 스케줄링 알고리즘에서 발생할 수 있는 문제인가?
4. Starvation과 그에 대한 해결방법에 대해 설명할 수 있는가?
5. SJF와 SRF의 차이에 대해 설명 할 수 있는가?
6. MLQ와 MFQ의 차이에 대해 설명 할 수 있는가?
7. FCFS, SJF, SRF, HRN알고리즘의 Waiting Time과 Turnaround Time을 계산할 있는가?