> Basic Process Scheduling의 한계는 프로세스의 구체적인 실행 정보를 요구하는데 현실에서는 프로세스의 총 실행 시간이나 연산 및 입출력을 많이 하는지, I/O 요청은 언제하는지, 장치는 언제 그 요청을 처리해서 알려줄 것인지와 같은 정보들이 명확히 주어지지 않는게 다반사다.
1. Multi-Level Queue (MLQ) 방식
우선 순위별로 Ready Queue를 스케줄링 목적에 따라 여러 개 사용하는 스케줄링 방식이다. 우선 순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선 순위 큐에 있는 프로세스들을 처리한다.
그림과 같이 큐를 여러 개 두면 프로세스 유형별로 우선 순위를 구분하여 실행하는 것이 편리하다. 그리고 각 큐마다 독자적인 스케줄링 알고리즘이 존재할 수 있다. 예를 들어, Foreground(Interactive) 프로세스와 Background(Batch) 프로세스를 구분해보자.
이 두 가지 유형의 프로세스는 응답 시간 요구 사항이 다르므로 스케줄링 요구 사항이 다를 수 있다. 또한 Foreground 프로세스는 Background 프로세스보다 우선순위를 가질 수 있고, 각각 별도의 큐가 사용될 수 있으며 자체 스케줄링 알고리즘이 있을 수 있다. 예를 들어, Background Queue는 FCFS 스케줄링 방식, Foreground Queue는 RR 스케줄링 방식으로 스케줄될 수 있다. 추가적으로, 큐와 큐 사이에 스케줄링도 반드시 있어야 하며, 일반적으로 고정된 우선 순위의 선점형 스케줄링으로 구현된다.
각 큐는 낮은 우선 순위의 큐보다 절대적인 우선순위를 가진다. 예를 들어, System process, Interactive process, interactive editing process를 위한 큐들이 모두 비어 있지 않다면, Batch Queue에 있는 프로세스는 실행될 수 없다. Batch process가 실행되고 있는데, Interactive process가 Ready Queue에 들어간다면 Batch process는 순서를 빼앗길 것이다. 한편으론, 큐들 사이에 시간을 나누어 사용할 수도 있다.
각 큐는 CPU 시간의 일정량을 받아서 자신의 큐에 있는 다양한 프로세스들을 스케줄할 수 있다. 예를 들어, Foreground-Background Queue에서 전자는 자신의 프로세스들 사이에서 RR 스케줄링을 위해 CPU 시간의 80%가 주어지고, 후자는 CPU 시간의 20%를 받아 자신의 프로세스들에 FCFS 방식으로 처리할 수 있다.
But... MLQ 스케줄링 방식의 문제점도 명확해보인다.
MLQ 방식의 문제점
위 그림처럼 우선 순위가 높은 A와 B 프로세스는 문제가 없을 테지만, 만일 5번, 6번, 7번 Queue에 누군가 끼어든다면 C와 D는 다른 녀석들이 끝날 때까지 CPU를 할당받지 못한다. 따라서 그 대안으로 Multi-Level Feedback Queue (MLFQ) 스케줄링 방식이 제시되었다.
2. Multi-Level Feedback Queue (MLFQ) 방식
MLFQ 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.프로세스들을 CPU 버스트 성격에 따라 구분한다. Interactive Process처럼 키보드를 입력할 때 마다 기다리면서 잠시 CPU를 놓는 프로세스의 경우에는 높은 우선순위의 큐로 이동되고, CPU Intensive Process처럼 오랜 시간 CPU를 너무 많이 사용하는 프로세스의 경우에는 낮은 우선 순위 큐로 이동된다.
MLFQ가 고민하는 문제는 Turnaround Time을 최적화하고, Response Time을 최소화하는 두 마리 토끼를 동시에 잡는 것 이다. 알다시피 앞서 살펴봤던 스케줄링 방식들은 하나만을 목표로 설정했었다. 아무튼 두 가지 목표를 달성하기 위해 해결해야 하는 것은 프로세스의 작업 길이 등의 작업 정보를 어떻게 알아내느냐다. 짧은 길이의 CPU 실행 시간을 가지는 Interactive Process와 장기간 수행하는 CPU-bound process가 혼재한 작업을 가정하고 몇 가지 조건들을 상정하여 목표에 접근해보자.
1. 우선 순위가 높은 작업을 먼저 실행한다.
2. 같은 우선 순위를 가지는 작업은 RR 알고리즘을 적용한다.
3. 작업이 생성되면 가장 높은 우선 순위를 부여한다. (최상단 큐에 배치)
4. 작업이 주어진 Time slice를 소진하면 우선권을 내린다. (하위 큐로 이동)
5. 작업이 Time slice를 소진하지 못하고 포기하면 우선권을 유지한다. (해당 큐 유지)
첫 번째 그림에서는 처음 프로세스가 생성될 당시, 규칙 3번에 의해 가장 높은 큐인 Q2에 배치된다. 10ms의 Time slice 소모 후, 규칙 4번에 의해 낮은 우선순위인 Q1, Q0로 각각 이동한다. 두 번째 그림에서는 만약 긴 실행 시간을 가진 A가 실행되고 있을 때 20ms의 실행 시간을 가지는 B 프로세스가 100ms인 순간에 생성되었다고 하면, B 프로세스가 생성되면 규칙 3에 의해 Q2에 적재되고 Time slice 10ms를 소진하고 규칙 4에 의해 Q1에 적재된다. 그 후, 아직까지 B의 우선순위가 A보다 높으므로 B가 실행된다. B가 실행이 완료되었으니 그리고 나서 Q0의 A가 재실행된다. 이번엔 I/O가 추가된 예시도 생각해보자.
Time slice는 동일하게 10ms로 가정하자. 처음 프로세스가 생성되면 규칙 3에 의해 가장 높은 큐인 Q2에 적재한다. Time slice 소모 이전에 I/O 발생으로 1ms만 실행 후 CPU를 포기하면 규칙 5에 의해 우선순위 큐가 유지된다. CPU를 포기한 시간 동안 우선 순위가 낮은 Q0에 있던 프로세스가 실행된다(I/O Overlap). 다시 Time slice 소모 후, 우선순위가 높은 Q2 프로세스가 규칙 5에 의해 실행된다. 이처럼 CPU 소모가 적은 Interactive Process의 경우에 빠른 실행과 응답성을 보장한다.
MLFQ는 Long-running process와 Short-running or I/O Interactive process에 효과적이다. 반면, 문제점은 없을까?
MLFQ 방식의 문제점
Starvation(기아 상태) : 너무 많은 Interactive process들이 최상단 큐에 있으면, 하단 큐에 있는 긴 실행 시간을 가진 프로세스들은 CPU를 할당받지 못한다.
CPU Monopolize(CPU 독점) : 사용자가 의도적으로 공평한 스케줄링을 방해할 수 있다. 예를 들어, 충분히 CPU를 사용하고 Time slice가 끝나기 직전 I/O를 요청하여 CPU를 포기한다면 해당 우선 순위 큐에 계속 유지될 것이다. (완전 양아치...)
실제 프로그램은 CPU-bound, I/O Interactive로 딱 나뉘지 않는다. 하나의 프로그램이지만 시간에 따라서, 혹은 단계별로 혼재되어 있을 수 있다.
이런 문제점을 개선하기 위해 규칙을 추가해보자. 바로 "일정 시간이 지나면 모든 작업에 최상위 우선권을 부여(Priority boost)" 하는 것 이다. 다시 말해, 주기적으로 모든 작업의 우선 순위를 뻥튀기시켜 Starvation 문제를 해결한다는 것이다. 가장 높은 큐에 배치되면 RR 방식으로 실행하고, CPU-bound process가 Interactive process 작업으로 바뀐다면 Priority boost 이후에 빠르게 처리가 가능해진다.
Boost 주기를 잘 정해주는 것이 중요하다. 주기가 너무 길면 Long-running process가 손해고, 주기가 너무 짧으면 Interactive process가 손해다.
다음 개선 방법으로는 MLFQ의 각 레벨마다 실제 사용되는 CPU 시간을 추적 및 계산하는 방법 이 있다. 각 프로세스가 사용한 Time slice에 집중할 것이 아니라, 프로세스가 할당된 큐에서 사용한 CPU 시간에 집중하는 것이다. 아까 규칙 4와 5를 개선하여 "CPU를 포기한 횟수에 상관없이 프로세스가 큐에 할당된 CPU 시간(Time allotment)을 소진하면, 우선권을 낮추는 것" 이다. 쉽게 말해, "너 순수하게 CPU 시간 얼마나 썼냐? 많이 썼지? 그럼 내려가라" 라고 말하는 것이다. 아래 왼쪽 그림처럼 원래는 양아치처럼 CPU를 독점할 수 있었지만, 오른쪽 그림을 보다시피 이젠 Time slice가 끝나기 직전 CPU를 포기해도 얄짤없다.
하지만 아직 몇 가지 더 고려해야 할 문제들이 있다. 큐를 몇 개나 배치할 것인지, 큐마다 Time slice는 얼마로 할 것인지, 얼마나 자주 Boost를 해줄지와 같은 문제들이 있다.
