[OS] Multi Level Feedback Queue (MLFQ)

 

---

이전 글에서 프로그램을 실행해보기도 이전에 프로그램의 실행 시간을 아는 것은 현실적으로 불가능한 이야기이므로 SJF와 STCF같은 정책들이 Optimal하지만 다른 방법을 탐색했어야했습니다. 

따라서 "실행 시간을 몰라도 SJF/STCF처럼 효율적이고, Round Robin처럼 공정한 스케줄링 정책은 없는 걸까 "라는 의문을 남긴채 글을 마무리했었습니다. 

 

그 의문을 해소하고자 Multi-Level Feedback Queue(MLFQ)가 등장하게 됩니다.

MLFQ의 목적은 두가지입니다.

• turnaround time(반환 시간)의 최적화 like SJF(or STCF)
• response time(반응 시간)의 최적화 like RR

즉, 반환시간과 반응시간 두가지의 성능 지표 모두를 노려보는 방법입니다.

 

---

MLFQ: Basic Rules

Rule 1. 작업 A의 우선 순위가 작업 B보다 높다면, 작업 A를 실행한다. (B는 실행하지 않는다.)
Rule 2. 작업 A와 B의 우선 순위가 같다면, A와 B는 RR 방식으로 실행된다.

 

 

이 그림을 예시로 보면 A와 B가 가장 우선순위가 높은 큐에 배치되어있기 때문에 A와 B가 우선적으로 RR방식(time sharing)으로 실행되게 됩니다(fairness). 하지만 위 두가지 규칙만 가진다면 우선순위가 변동될 일이 없어 C와 D는 전혀 실행될 수가 없습니다.

 

그렇다면 우선순위가 변동되기 위한 규칙들을 살펴봅시다.

Rule 3. 작업이 시스템에 도착하면, 가장 높은 우선 순위(최상위 큐)로 배정된다.
Rule 4a. 작업이 실행되는 동안 주어진 time slice를 모두 사용한다면, 우선 순위가 강등된다. (바로 아래 큐로 이동된다)
Rule 4b. 작업이 time slice가 끝나기 전에 CPU를 포기한다면, 동일한 우선 순위를 유지한다.

 

SJF와 STCF같은 정책들이 성능으로서 이미 최적의 정책임을 확인했습니다. 그런데 이 둘이 현실적으로 불가능한 이유는 바로 프로그램의 실행시간을 미리 알고 있어야 가능하다는 점 때문입니다. MLFQ에서는 프로그램의 실행 시간을 미리 알 수는 없지만, 그 작업들의 동작에 대해 학습하여 이 프로그램이 "짧은지, 긴지"를 어느정도 유추하게 됩니다.

 

time sharing방식으로 RR이 실행되다가 time out까지 가게 되었다면, 어느정도 이 프로그램의 실행시간은 좀 더 길구나 하고 우선순위를 내리는 판단을 합니다. 그에 반해 미리 CPU를 포기한다면(I/O 요청) 이 프로그램은 짧구나 로 인식하고 우선순위를 유지시켜줍니다.

 

이 때 처음에는 작업에 대한 어떠한 정보도 없으니 일단 모든 작업들은 최상위 큐, 가장 높은 우선 순위를 배정하여 실행시키는 것입니다.

일단 실행시키고 보는 것이기 때문에 response time이 빨라지는 효과가 있습니다.

 

이 규칙들을 가지고 실행시킨다면 long job같은 경우는 결국 low priority 큐로 가게 될테고, short job은 high priority큐쪽에 남게 될 것 입니다.

 

예제들과 좀 더 살펴보겠습니다.

---

Example 1. A Single Long-Running Job

시스템에 장시간 실행되는 작업이 있는 경우, time slice가 10ms인 상태를 살펴보겠습니다.
이 예시에서 보듯이, 작업은 가장 높은 우선순위인 Q2에 들어옵니다. 10ms의 time slice을 모두 써서 time out이 되면, 스케줄러는 작업의 우선 순위를 하나 낮추어 Q1로 이동시킵니다. Q1에서 또 한 번의 time slice를 실행한 후 time out이 되면, 작업은 마침내 시스템에서 가장 낮은 우선순위인 Q0으로 내려가게 되며, 거기에 계속 남게 됩니다.

 

Example 2. Along Came A Short Job & Example 3. I/O

이제 좀 더 복잡한 예시를 살펴보겠습니다. 이 예시에서는 두 가지 작업이 있습니다: CPU 집중적인 장기 실행 작업인 A와 짧은 대화형 작업인 B입니다. A가 어느 정도 실행된 후 B가 도착한다고 가정해보겠습니다.

 

이때 어떻게 될까요? MLFQ는 B에 대해 SJF(Shortest Job First, 가장 짧은 작업 우선)의 기능처럼 동작하게 할 수 있을까요?

작업 A(검정색으로 표시됨)는 가장 낮은 우선순위 큐에서 계속 실행됩니다 (장기 실행되는, CPU 집중적인 작업들은 일반적으로 이러한 위치에 있게 됩니다). 그리고 시간 T = 100에 작업 B(회색으로 표시됨)가 도착하여 가장 높은 큐에 삽입됩니다. B는 짧은 시간(20ms)동안만 실행되기 때문에, 두 번의 타임 슬라이스만으로도 가장 낮은 큐에 도달하기 전에 작업이 완료됩니다. 그 후 A가 다시 실행을 재개합니다(낮은 우선순위에서).

 

오른쪽 예시는 대화형이기 때문에 작업 B는 주어진 time slice를 다 쓰기도 이전에 IO요청을 보내기 때문에 CPU를 계속해서 포기함으로써 같은 우선순위에 머물게 됩니다(강등 X). IO 요청이 처리되는 동안에는 다른 작업이 실행되기 때문에, 작업 A가 사이사이에 실행되는 모습을 볼 수 있습니다.

이 예시들을 통해 알고리즘의 주요 목표 중 하나를 이해할 수 있습니다:

알고리즘이 어떤 작업이 짧은 작업인지 아니면 장기 실행 작업인지 모르기 때문에, 우선 작업이 짧은 작업일 수 있다고 가정하고 그에 대해 높은 우선순위를 부여합니다. 만약 실제로 짧은 작업이라면, 빨리 실행되고 완료될 것입니다. 그러나 만약 짧은 작업이 아니라면, 큐를 천천히 내려가며 자신이 장기 실행과 같은 일괄 처리형 프로세스임을 증명하게 됩니다. 이러한 방식으로 MLFQ는 SJF를 근사화합니다.

---

Problem With Our Current MLFQ

이제 우리는 MLFQ를 통해서 CPU를 오래 사용해야 하는 작업과 IO가 빈번하게 일어나는 대화형 작업 둘다 공정하고 빠른 성능으로 잘 동작하게 할 수 있게 되었습니다. 하지만 아직 치명적인 결함이 남아있습니다.

 

첫번째로 Starvation(기아, 굶주림) 문제가 있습니다.

시스템에 "너무 많은" 대화형 작업이 있다면, 이들이 결합하여 모든 CPU 시간을 소비하게 되어 우선 순위가 낮은 큐에 배치된 장기 실행되는 작업이 CPU 시간을 전혀 받지 못할 수 있습니다(굶주림 상태가 됨). 이러한 상황에서도 이러한 작업들에 대해 어느 정도의 진전을 이루고자 합니다.

 

둘째로, 똑똑한 사용자는 자신의 프로그램을 재작성하여 스케줄러를 속일 수 있습니다(Gaming System). 

스케줄러를 속이는 것은 일반적으로 스케줄러를 속여서 공정하지 않은 비율로 리소스를 더 얻으려는 개념을 의미합니다. 지금까지 설명을 기반으로 한 우리의 MLFQ는 다음과 같은 공격에 취약합니다.

할당량을 모두 사용하기 전에 I/O 작업(예: 파일 작업)을 의도적으로 요청하여 CPU를 양보합니다. 이렇게 하면 동일한 큐에 남아 있게 되어 더 많은 CPU 시간을 얻을 수 있습니다. 제대로 실행하면 (예: CPU를 양보하기 전에 할당량의 99%를 실행), 해당 작업은 CPU를 거의 독점할 수 있게 됩니다.

 

마지막으로, 프로그램은 시간이 지남에 따라 동작을 변경할 수 있습니다.

CPU 집중적인 작업이 대화형 작업 단계로 전환될 수 있습니다. 근데 지금의 방법으로써는 우선순위가 강등이 되고나면 다시 올라갈 방법이 없기 때문에, 이런 작업들은 대화형 작업으로 바뀌었지만, 취급이 바뀌지 않았기 때문에 좀 억울할 수 있다.

 

Starvation(기아) 문제를 막아보자: The Priority Boost

Rule 5. 일정 주기 S마다, 시스템의 모든 작업들을 최상위 큐로 옮긴다.

 

이 새로운 규칙은 동시에 두 가지 문제를 해결합니다. 

첫번째로, 우선 프로세스가 굶주리는 문제를 해결합니다. 가장 높은 우선순위 큐에 위치함으로써 작업은 RR 방식으로 CPU를 공유하게 되어 결국 서비스를 받게 될 것입니다.

둘째, CPU 집중적인 작업이 대화형으로 전환되었을 경우에도 스케줄러는 Priority Boost를 받게 되면, 그 이후 작업을 올바르게 다루게 됩니다.

위 사진에서의 예제를 살펴보겠습니다. 이 시나리오에서는 CPU를 두 개의 짧게 실행되는 대화형 작업과 경쟁하는 장기 실행 작업의 동작을 보여줍니다. 왼쪽은 Priority Boost가 없는 상황이고, 따라서 두 개의 대화형 짧은 작업이 도착하면 장기 실행 작업은 계속 굶주리게 됩니다.

오른쪽은 100ms마다 우선순위 부스트가 있는 경우입니다. 따라서 장기 실행되는 작업이 적어도 약 100ms마다 가장 높은 우선순위로 부스트되어 주기적으로 실행되도록 보장됩니다.

 

사실 이론적으로는 너무 좋은데, 일정 주기 S를 어떻게 설정하는지가 사실 매우 어렵습니다.

S를 너무 길게 줘버리면 우선순위가 낮은 작업들이 그 만큼 오래 굶게 될 것이고, 그렇다고 작게 줘버리면 대화형 작업이 적절한 CPU할당을받지 못할 수도 있습니다. 따라서, '적절한' 값을 줘야하는데, 이 적절하다라는 것을 판단하기가 굉장히 곤란한 것 입니다.

 

Gaming을 막아보자: Better Accounting

Rule 3. 작업이 시스템에 도착하면, 가장 높은 우선 순위(최상위 큐)로 배정된다.
Rule 4a. 작업이 실행되는 동안 주어진 time slice를 모두 사용한다면, 우선 순위가 강등된다. (바로 아래 큐로 이동된다)
Rule 4b. 작업이 time slice가 끝나기 전에 CPU를 포기한다면, 동일한 우선 순위를 유지한다.

 

남은 Gaming 문제를 어떻게 막을 수 있을까요?? 사실 진짜 문제는 Rule 4a와 4b입니다. 이들 규칙은 작업이 할당량이 끝나기 전에 CPU를 양보함으로써 작업이 우선순위를 유지하도록 허용합니다. 규칙의 변경이 필요해보입니다.

 

이 문제를 해결하기 위한 해결책은 MLFQ 각 수준에서 CPU 시간을 더 잘 회계하는 것입니다.

이 문제를 해결하기 위해서는 MLFQ가 각각의 time slice를 매번 새로 할당하는 것이 아닌, 이 상태를 기억하고 있다가 남은 시간이 얼마나 남았는지를 계속 추적해야합니다. state를 기억하고 있어야한다는 뜻 입니다. 

 

즉, time slice가 아닌 time allotment(할당량)을 활용해서 RR을 수행해야하고, 우선순위가 강등되는 조건이 time slice를 다 써서 time oout될 때가 아닌 CPU를 양보하든 말든 time allotment를 다 썼는지 안썼는지가 됩니다.

 

이제 문제의 4a와 4b 규칙을 아래 규칙으로 바꿔봅시다.

Rule 4. 작업이 특정 수준에서 할당량을 모두 사용하면(얼마나 많이 CPU를 양보했는지에 상관없이), 해당 작업의 우선순위가 감소됩니다(다음 큐로 이동).

 

예제와 함께 더 살펴봅시다.

 

 

왼쪽이 이제 Gaming문제에 대한 예시입니다. time slice를 다 소진하기 직전에 의도적으로 IO요청을 보냄으로써 CPU를 양보하여 우선순윅의 강등을 막고 있습니다. time slice가 매번 새로 할당되는 것이 문제입니다.

 

오른쪽 예시는 time allotment를 활용하여 Gaming문제를 해결한 예시입니다. 

이제 우선 순위가 강등되는 조건은 '자신에게 부여된 할당량을 다 썼는지(CPU양보와 상관없이)'입니다.

예를 들어 time allotment가 10ms라면, 9ms 때 IO요청을 보내고 다시 돌아왔을 때 기존의 방법대로였다면 다시 10ms의 time slice를 받지만, 여기서는 이전에 사용하고 남은 1ms(10 - 9)만큼만 작업을 더 이어서 할 수 있습니다. 이 방식대로 진행되다보면 결국 Q0의 큐에서 두 작업 모두 동일하게 배치되고 RR방식으로 균등하게 CPU를 할당받을 수 있게 됩니다.

 

MLFQ의 또 다른 이슈들: 튜닝하기가 쉽지 않다...

MLFQ 스케줄링에는 몇 가지 다른 문제가 있습니다. 그 중 하나는 이러한 스케줄러의 "매개변수를 어떻게 설정해야 하는가" 하는 문제입니다. 예를 들어,

• "큐는 몇 개나 있어야 할까요?"
• "각 큐마다 시간 슬라이스는 얼마나 길어야 할까요?"
• "할당량은 얼마나 되어야 할까요?"
• "굶주림을 피하고 동작 변화를 고려하기 위해 우선순위를 얼마나 자주 부스팅해야 할까요?"

이러한 질문들에 딱 정해진 답이 없기 때문에 워크로드에 대한 경험을 통해서 스케줄러를 조정하는 수 밖에 없습니다.

예를 들어, 다양한 우선 순위 큐 간에 time slice의 길이를 다르게 설정할 수 있습니다. 보통 High priority 큐에는 짧은 시간 슬라이스가 할당됩니다. 이 큐들은 주로 대화형 작업으로 구성되어 있으므로 빠르게 번갈아가며 실행하는 것이 유리합니다(10ms 이하). 반면에 Low priority 큐에는 CPU를 많이 사용하는 장기 실행 작업들이 포함되어 있으므로, 더 긴 time slice를 사용합니다.(수백 ms).

아래 예시 그림은 두 작업이 가장 높은 큐에서 10ms time slice, 중간에서는 20ms time slice, 그리고 가장 낮은 우선순위 큐에서 40ms time slice 동안 실행되는 예시를 보여줍니다.

 

Wrap up

문제점을 해결한 MLFQ의 최종 규칙은 아래와 같습니다.

Rule 1. 작업 A의 우선 순위가 작업 B보다 높다면, 작업 A를 실행한다. (B는 실행하지 않는다.)
Rule 2. 작업 A와 B의 우선 순위가 같다면, A와 B는 RR 방식으로 실행된다.
Rule 3. 작업이 시스템에 도착하면, 가장 높은 우선 순위(최상위 큐)로 배정된다.
Rule 4. 작업이 속해 있는 우선 순위 수준 안에서의 주어진 시간 할당량(time allotment)을 모두 사용하면, (얼만큼 CPU 사용을 포기했는지와는 상관 없이) 우선 순위가 강등된다. (그 아래의 큐로 이동된다.)
Rule 5. 일정 주기 S마다, 시스템의 모든 작업들을 최상위 큐로 옮긴다. (Boosting)

 

MLFQ는 다음과 같은 이유로 흥미로운데, 작업의 본질에 대한 사전 지식을 요구하는 대신 작업의 실행을 관찰하고 그에 따라 우선순위를 결정합니다. 이 방식으로 MLFQ는 두 마리 토끼를 모두 잡을 수 있습니다: 짧은 대화형 작업에 대해서는 최적의 성능을 제공할 수 있으며(SJF/STCF와 유사), 장기 실행 CPU 집중 작업에 대해서도 공정하게 진행할 수 있습니다(RR)