CPU Scheduling - Scheduling Algorithm_5

Multilevel Queue(이하 MQ) Scheduling Algorithm, 멀티레벨 스케쥴링 알고리즘

MQ 알고리즘은 Process를 종류별로 구분하여 그룹으로 만들고 그 그룹별로 Queue를 제공한다. 그리고 그 그룹별로 별도의

Priority를 주어 Process를 수행하는 방식이다. 즉, 별도의 Priority를 가진 Ready Queue를 여러개로 나눈 알고리즘이다.

 

MQ 알고리즘에서 각각의 Queue들은 별도의 스케쥴링 알고리즘을 가지고 있다. Process들은 영구적으로 한 Queue에 소속되어

수행되는데 각 Qeueu별로 우선순위를 가지고 있기 때문에 각각 다른 수행 시간을 가지게 된다.

하지만 이런 알고리즘의 가장 큰 문제점은 Starvation이다. 때문에 Aging기법이 필요하게 되는데 이때 문제가 발생한다.

Priority방식 같은 경우에는 어차피 Queue가 하나기 때문에 Priority값만 변경 시켜주면 되었지만 MQ방식에서는 Process가 Priority를

가지고 있는게 아니라 각각의 Queue들이 Priority를 가지고 있기 때문에 Process가 Queue사이를 이동할 수 있어야 한다.

이렇게 Aging기법을 사용하기 위하여 Process가 Queue간의 이동이 가능한 MQ알고리즘을

Mulitilevel Feedback Queue Scheduling(이하 MFQ)라고 한다.

예를 들어 3개의 Queue를 가지고 있는 MFQ Scheduler를 살펴보자.

 

위에서부터 각각 Queue0, Queue1, Queue2라고 하자.

Queue0의 Process의 수행이 모두 종류되어야 Queue1의 Process가 수행될 수 있다. 만일 Queue1에서 Process가 수행 중일때

Queue0에 Process가 등록이 된다면 Preemption이 일어난다. 각각의 Queue들은 별도의 Time Quantum을 가지고 있다. 마지막

Queue인 Queue2는 FCFS방식으로 스케쥴링 되어있다. 만일 Queue0의 Time Quantum인 8milliseconds내로 Process가

수행완료 되지 않았다면 해당  Process는 Queue1으로 이동한다. 같은 방식으로 Queue1에서 Queue2로 Process가 이동한다.

때문에 CPU-Bounded Process의 경우에는 Queue2에, I/O-Bounded Process의 경우에는 Queue0에 많이 존재하게 된다.