Dev.log

MLFQ에서 다루고자 하는 근본적인 문제는 두 가지이다.

첫 번째는 짧은 작업을 먼저 실행하여 turnaround time을 최적화(optimize)하는 것이다. 문제는, SJF(또는 STCF)와 같은 알고리즘이 필요로하는 정보인 작업의 실행 시간을 모른다는 것이다.

두 번째로, 시스템이 대화형 사용자(interactive user)에 반응하도록 하여 응답 시간을 최소화하는 것이다. 저번에 배웠던 Round Robin 알고리즘은 response time(응답 시간)은 짧지만 turnaround time이 길다.

우리가 프로세스에 대해서 아는 정보가 없을 때 어떻게 이러한 목표를 달성하기 위한 스케줄러를 만들 수 있을까? 스케줄러가 시스템이 실행될 때 실행 중인 작업의 특성을 학습하여 더 나은 스케줄링 결정을 내릴 수 있는 방법은 무엇일까?

MLFQ : Basic Rules

MLFQ에서  각기 다른 Priority Level(우선 순위 레벨)을 할당한 여러 개의 고유한 queue(대기열)을 가지고 있다. 언제든지 실행 가능한 작업은 단일 대기열에 존재한다. MLFQ는 우선 순위를 사용하여 주어진 시간에 실행할 작업을 결정한다. 우선 순위가 높은 작업이 실행되도록 선택된다. 둘 이상의 작업들이 지정된 대기열에 있을 경우 우선 순위가 같고, 이럴 땐 이들은 라운드 로빈 스케줄링을 사용한다.

따라서 MLFQ의 두 가지 규칙을 말할 수 있다.

규칙 1. 작업 A, B에 대해서 우선순위가 A > B이면 A가 실행된다.

규칙 2. 우선순위가 같은 작업들에 대해서는 라운드 로빈 스케줄링을 실행한다.

MLFQ 스케줄링의 핵심은 스케줄러가 우선순위를 설정하는 방법인데, MLFQ는 각 작업에 대해 고정된 우선순위를 부여하기보다는 관찰된 동작에 따라 우선순위를 변화시킨다. 예를 들어, 작업이 키보드 입력을 기다리는 동안 CPU를 반복적으로 포기하면 MLFQ는 interactive process의 행동이라고 판단하여 우선순위를 높게 유지시킨다. 대신 작업이 CPU를 장시간 집중적으로 사용하는 경우 MLFQ는 우선순위를 줄인다. 이처럼, MLFQ는 프로세스를 실행하며 프로세스에 대해 배우고, 작업의 이력(history)을 사용하여 작업의 미래 동작을 예측한다.

그러나, 때로는 우선 순위가 낮은 작업이 우선 순위가 높은 작업들에 의해 아예 실행이 되지 못하는 상황이 생기는 것을 막기 위해 우선순위가 낮은 작업의 순위를 올리는 판단도 필요하다. 이처럼, MLFQ 스케줄러가 작업의 우선순위를 어떻게 변화하는지를 아는 것이 핵심이다. 이에 대해서 배워보자. 

Attempt #1: How To Change Priority

이제, 작업의 생명주기동안 MLFQ가 우선 순위 레벨을 어떻게 변경할 것인지를 결정해야 한다. 이 때, 짧은 실행(키보드나 마우스에서 사용자 입력을 기다리며 많은 I/O를 수행하며 CPU를 자주 포기하는 경우)을 하는 대화형 작업과, 많은 CPU 시간이 필요하지만 반응 시간이 중요하지 않은 오래 실행하는 CPU-bound 작업이 혼합되어 있다는 점을 명심해야 한다.

규칙 3. 시스템에 들어가면 작업은 가장 높은 우선 순위에 배정된다.

규칙 4a. 작업을 실행하는 동안 전체 time slice를 모두 사용하는 경우 우선 순위 레벨이 감소한다.(대기열 하나 아래로 이동)

규칙 4b. 작업이 time slice를 전부 사용하기 전에 CPU를 포기하면 동일한 우선 순위 레벨을 유지한다.

Problems With Our Current MLFQ

문제점 1. 시스템에 너무 많은 대화형 작업이 있을 경우 그들이 모든 CPU time을 소모하므로 장기간 실행되는 작업은 CPU time을 전혀 할당받지 못하는 Starvation 문제가 발생할 수 있다.

문제점 2. 사용자가 그들의 프로그램을 재작성하여 공정한 시스템 리소스 점유율 그 이상을 할당받도록 스케줄러를 속일 수 있다. 즉, time slice가 끝나기 전에 I/O 작업을 실행하여 고의적으로 CPU를 포기하며 동일한 대기열에 남아 더 많은 CPU time을 확보할 수 있다. 예를 들어, time slice의 99%만큼 작업을 실행하고 포기하는 방식이 있다. 이를 통해 CPU를 독점할 수 있다는 문제가 생긴다.

문제점 3. 프로그램이 시간이 지남에 따라 동작을 변경할 수 있다. 작업의 동작 Phase가 CPU-bound -> Interactive로 전환되었을 때 현재의 접근 방식에서는 해당 작업은 시스템에서 다른 대화형 작업들처럼 다루어지지 않을 것이다.

Attempt #2: The Priority Boost

starvation 문제를 피하기 위해 새로운 규칙을 추가하자. 시스템 내 모든 작업의 우선 순위를 주기적으로 향상시킨다.

규칙 5. 일정 시간이 지나면(일정 주기마다) 시스템의 모든 작업을 대기열의 맨 위로 이동한다.

새 규칙은 두 가지 문제를 동시에 해결한다. 첫째, 프로세스가 중단되지 않도록 보장된다다(starvation 해결). 즉, 맨 위 대기열로 이동하여 CPU를 다른 우선 순위가 높은 작업과 라운드 로빈 방식으로 공유하여 결국 서비스를 받게 된다. 둘째, CPU-bound 작업이 대화형 작업이 된 경우 우선 순위 부스트를 받은 후 스케줄러가 해당 작업을 적절하게 처리한다.
 

Attempt #3: Better Accounting

고의적으로 time slice가 만료되기 전에 CPU를 포기하여 작업의 우선 순위를 유지하는 프로그램의 스케줄러 악용으로부터의 문제를 해결하기 위해 규칙 4를 수정한다. 이를 위해 스케줄러는 지정된 우선 순위 레벨에서 프로세스가 사용한 시간 할당의 양을 추적한다.

규칙 4: CPU를 포기한 횟수와 상관없이 해당 우선 순위 레벨에서 주어진 시간 할당을 모두 사용하면 우선 순위가 감소한다.

이를 통해 프로세스의 CPU 부당 점유를 막는다.

Tuning MLFQ And Other Issues

MLFQ 스케줄링에서 아직 몇 가지 다른 이슈가 존재한다. 한 가지 큰 이슈는 위에서 고려한 스케줄러를 어떻게 매개 변수화하느냐이다. 예를 들어 대기열이 몇 개여야 하는지, 대기열당 time slice가 얼마나 커야 하는지, starvation을 피하고 작업의 동작 변화(cpu-bound -> interactive)를 고려하기 위해 우선 순위를 얼마나 자주 올려야 하는지 등이다. 이러한 질문에 쉽게 대답할 수 없기 때문에 workload 기반 경험과 이후의 스케줄러 튜닝만이 만족스러운 균형을 이룰 수 있다.

마지막으로, 많은 스케줄러에는 사용자가 사용할 수 있는 몇 가지 다른 기능이 있다. 예를 들어 일부 스케줄러는 운영 체제 작업에 대해 가장 높은 우선 순위 수준을 예약하므로 일반적인 사용자 작업은 시스템에서 가장 높은 우선 순위를 얻을 수 없다. 또한 일부 시스템은 우선 순위를 설정하는 데 사용자의 개입을 허용하기도 한다. 예를 들어 명령줄 인터페이스를 사용하면 작업의 우선 순위를 늘리거나 줄일 수 있으므로 특정 시간에 작업이 실행될 가능성을 늘리거나 줄일 수 있다. 자세한 내용은 man 페이지를 참조하도록 하자.

MLFQ: Summary

• 규칙 1: 우선 순위(A) > 우선 순위(B)이면 A가 실행된다(B는 실행하지 않는다).
• 규칙 2: 우선 순위(A) = 우선 순위(B)인 경우, A와 B는 주어진 대기열의 Time slice를 사용하여 Round Robin 방식으로 실행된다.
• 규칙 3: 작업이 시스템에 진입할 때 가장 높은 우선 순위(맨 위 대기열)에 배치된다.
• 규칙 4: 주어진 우선 순위 수준에서 시간 할당을 모두 사용하면(CPU를 포기한 횟수에 관계없이), 우선 순위가 감소한다(즉, 대기열 하나 아래로 이동).
• 규칙 5: 일정 시간이 지나면 시스템의 모든 작업을 맨 위 대기열로 이동한다.

출처 : pages.cs.wisc.edu/~remzi/OSTEP/