Multi-Level Feedback Queue (MLFQ)

Multi-Level Feedback Queue

지난 글에서는 CPU Scheduler의 여러가지 알고리즘들과 각각을 비교해보았었다. 이번 글에서는 Multi-Level Feedback Queue가 어떤식으로 동작하고, 어떠한 문제들을 해결하는지 살펴보겠다.

우리의 목표는 세가지이다.

1. Response time 최소화
2. Turnaround time 최소화
3. Job의 수행시간을 모르는 상태에서 Scheduling

(Response time, Turnaround time에 대한 설명)

Multi-Level Feedback Queue는 이름에서 알 수 있듯이 Multiple Queue를 갖고 있다. 각각의 큐는 서로 다른 priority를 가지고 있고, A job의 priority가 B job의 priority 보다 높다면 A job을 선택한다. 만약 두 job의 priority가 같다면 Round-Robin 알고리즘으로 job들을 수행한다.

다음과 같은 예시를 보자.

A,B가 RR 방식으로 수행되고, C, D가 실행될 것이다. 하지만 이 때 문제점은 A, B가 완료되거나 I/O 작업으로 block되기 전까지 C와 D는 CPU 자원을 받을 수 없다는 것이다.

이때문에 우리는 job들의 priority를 고정된 값으로 두는 것이 아니라, 동적으로 바꿔줄 필요가 있다. MLFQ는 job들의 과거 행적을 보고 priority를 조정한다. 만약 job이 CPU자원을 많이 요구하는 탐욕적인 job이라면 priority를 낮추고, I/O 작업을 많이하여 CPU자원을 자주 양보하는 job이라면 priority를 높게유지한다.

• I/O - bound jobs
  • Interactive and short-running 우선 순위 높게!
• CPU-bound jobs
  • Compute intensive and longer-running 우선 순위 낮게!

모든 job은 MLFQ에 들어올때 가장 높은 priority를 갖고 시작한다.

이때 job이 CPU 자원을 사용하면 Priority가 낮아져 다른 job이 들어왔을때 그 job을 수행할 수 있다.

이렇게하면 response time과 turnaround time 모두 좋게 만들 수 있다.

만약 job이 I/O 작업을 수행한다면 Priority가 낮아지지 않고 그대로 유지된다.

완벽해 보이는 현재 방식에도 아직 다음의 세가지 문제점이 존재한다.

Problems

1. Starvation

   만약 I/O 작업을 수행하는 job들이 매우많아진다면 낮은 Priority에 있는 CPU job들이 오랜시간 자원을 할당받지 못하는 현상이 발생한다.

   

2. Gaming the scheduler

   일종의 해킹처럼, 똑똑한 사용자는 자신의 프로그램이 CPU 자원을 계속 사용하다가, time slice가 소진될 시점에 I/O 작업을 수행해 scheduler가 마치 I/O - bound job인 것처럼 착각하게 만들어 CPU를 독점하게 프로그램을 만들수 있다. 이렇게 되면 나머지 프로세스들은 자원을 받지 못한다.

   

3. Changing behavior

   CPU - bound job이 계속 CPU를 사용해 Priority가 낮아진 상태에서, I/O - bound job으로 바뀌어도 이미 낮아진 Priority를 회복하는것이 불가능할 수 있다.

해당 세가지 문제점을 해결하기 위한 방법으로 우선 Priority Boost를 이용한다. Priority Boost는 일정 시간마다 모든 job들의 Priority를 큐의 최상단으로 동일하게 끌어올리는 것이다. 이렇게 하면 상기한 1번 문제와 3번 문제를 해결할 수 있다.

2번째 문제는 time slice 당시 수행하는 job의 operation을 Priority 조정의 판단기준으로 삼는 것이 아니라, time slice 동안의 CPU 사용시간을 기준으로 Priority를 조정하면 문제를 해결할 수 있다.

추가로, Response time을 최소화하기 위해 높은 Priority 큐에서는 짧은 time slice를 이용하고 낮은 Priority 큐에서는 Turnaround time을 최소화하기 위해 긴 time slice를 이용한다.

지금까지 여러 Scheduling 알고리즘들의 장단점, 문제점들과 각 문제점들의 해결과정을 알아보았다. 현존하는 상용 운영체제들은 이밖에도 여러 알고리즘들을 함께 사용하고 있다. 여러 알고리즘들에 대해 확실하게 공부하고 복습할 필요가 있겠다.