운영체제 | CPU 스케줄링 알고리즘 | MLFQ

멀티 레벨 피드백 큐(MLFQ, Multi-level Feedback Queue)

우선순위 스케줄러의 발전된 형태 중 하나이며, Windows에서도 일부 채택되는 방식이다. 

(Linux는 현재 RB 트리를 활용하는 CFS(Completelty Fair Scheduler)를 사용한다고 한다.)

 

MLFQ의 목표 두 가지

1. 반환 시간 최적화: 짧은 작업을 먼저 실행시킨다

2. 응답 시간 최적화: 대화형 사용자에게 응답이 빠른 시스템이라는 느낌 주기

 

근데 시스템은 작업의 실행 시간을 미리 알 수 없다. 

따라서 핵심적인 질문은 다음과 같다: 작업의 실행 시간에 대한 선행 정보 없이 어떻게 위 목표를 달성할 수 있는가?

 

MLFQ의 규칙

MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위(Priority level)가 배정된다.

그리고 각각의 큐에는 둘 이상의 작업이 존재할 수 있다. (이 둘은 같은 우선순위)

 

MLFQ에서는 두 개의 작업 A, B에 대해 다음과 같은 규칙들이 적용된다. 

 

규칙 1. Priority(A) > Priority(B) 이면, A가 실행된다. 

• A가 B보다 더 높은 우선순위의 큐에 속한 경우

규칙 2. Priority(A) = Priority(B) 이면, A와 B는 라운드로빈(RR) 방식으로 실행된다. 

• A와 B가 같은 우선순위의 큐에 속한 경우

규칙 3. 새로운 작업이 시스템에 진입하면, 가장 높은 우선순위(맨 위의 큐)에 배치된다.

규칙 4. 시간 할당량을 소진하면, 우선순위는 낮아진다. CPU 양보 여부와 횟수는 고려하지 않는다.

1. 해당 작업이 현 우선순위 단계에서 CPU를 얼마나 사용했는지(CPU 사용시간)를 기록한다.
2. 중간에 CPU를 양보했다면, 다음 차례때는 기록된 CPU 사용시간부터 이어서 측정한다.
3. CPU 사용시간이 시간 할당량(= 타임 슬라이스)에 도달하면, 현재 실행이 타임 슬라이스에 도달하지 않아도 즉시 우선순위를 낮춘다. 

규칙 5. 상향 조정(Boost): 일정 기간(S)이 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다. 

 

 

각 규칙에 대해서 조금 더 자세히 살펴보자. 

---

MLFQ의 규칙은 어떻게 세워졌을까?

MLFQ의 기본 규칙

규칙 1. Priority(A) > Priority(B) 이면, A가 실행된다. 

• A가 B보다 더 높은 우선순위의 큐에 속한 경우

규칙 2. Priority(A) = Priority(B) 이면, A와 B는 라운드로빈(RR) 방식으로 실행된다. 

• A와 B가 같은 우선순위의 큐에 속한 경우

그러나 이 규칙들만으로는 낮은 우선순위의 큐에 있는 작업들이 영영 실행되지 못한다. 

따라서 큐들의 우선순위를 적절히 바꿔주는 동적인 메커니즘이 더해져야 한다. 

 

규칙 3. 새로운 작업이 시스템에 진입하면, 가장 높은 우선순위(맨 위의 큐)에 배치된다.

규칙 4-1(임시). 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.

• 즉, RR 방식으로 실행을 하되, 정상적으로 타임 슬라이스만큼의 실행시간을 채우면 우선순위를 낮춘다.  

규칙 4-2(임시). 타임 슬라이스를 소진하기 전에 CPU를 양보하면 같은 우선순위를 유지한다. 

• 만일 인터럽트가 발생했거나, Sleep 상태로 전환되는 등 타임 슬라이스를 소진하지 않고 CPU를 양보하면 큐를 이동하지 않는다. (후에 나오겠지만, 이러한 경우 CPU를 얼마나 사용했는지를 기록해둔다.)
• 이 조치를 통해 I/O 작업을 자주 수행하는 (예를 들어 키보드 입력을 자주 받는 프로세스) 작업의 경우 높은 우선순위를 장기간 유지할 수 있게 되어, 사용자에게 더 빠른 응답 시간 경험을 제공한다. 

그림 11.3은 그림 11.2 이후의 상황에 Interactive형 작업이 들어온 경우라고 생각해도 된다

 

 

그림 11.2는 타임 슬라이스가 10ms 정도인 경우, 새로운 작업이 들어왔을 때의 우선순위 변화를 나타낸다. 

그림 11.3은 전부터 실행 중이던 작업이 있는 와중에 새로운 Interactive 작업(실행 시간이 10ms로 매우 짧은)이 들어왔을 때의 상황이다. 

(대화형 작업으로 번역되어있는데, 원문인 Interactive의 의미는 상호작용형에 더 가까운 것 같다.)

 

스케줄러는 작업의 실행 시간을 알 수 없기 때문에, 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다.

진짜 짧은 작업이면 빨리 실행되고 바로 종료할 것이다. 짧은 작업이 아니라면 천천히 아래 큐로 이동하게 되고, 스스로 긴 Batch형 작업(Batch job, 사용자의 상호작용 없이 연속적으로 실행되는 작업)이라는 것을 증명하게 된다. 

 

 

 

아예 I/O 집중 작업이라면? 타임 슬라이스를 다 소진하지 않은 상태에서 CPU를 양도하게 되고, 장기간 높은 우선순위를 유지할 것이다. 

이를 통해 키보드를 한번 입력하고 장시간 기다려야 하는 등의 상황을 방지할 수 있다. 

 

 

MLFQ 기본 규칙의 한계

위 기본 규칙을 따르는 MLFQ는 그 자체로 꽤 합리적으로 보이나, 특정 상황에서는 문제점을 가질 수 있다. 

 

1. 기아(Starvation) 상태 발생

• 시스템에 너무 많은 interactive 작업이 존재할 경우, Batch형 작업이 CPU를 할당받지 못하고 굶는다.

 

2. 의도적인 CPU 양보에 취약

• 누군가 의도적으로 타임 슬라이스 전에 CPU를 양보하도록(예를 들어, 타임 슬라이스 직전에 아무 파일을 대상으로 I/O 요청을 내리는 등) 작업을 설계한다면, 해당 작업이 CPU를 거의 독점하도록 만들 수 있다. 

 

3. 프로세스의 특성 변화를 반영하지 못함

• CPU 집중형 프로세스가 언제까지나 CPU 집중형인게 아니고, I/O 집중형도 언제까지나 I/O 집중형이란 법은 없다. 하나의 프로세스여도 시간 흐름에 따라 사용자 입력을 자주 받다가, 혼자 작업을 처리하다가 할 수가 있다.
• 기본 규칙 상에서는, 초기에 Batch형 작업이어서 우선순위가 낮아졌다면 이후에 I/O 집중형으로 바뀌었을 때 매우 비효율적인 응답시간을 갖게된다. 

 

한계 보완을 위한 MLFQ의 추가 규칙

 

규칙 5. 상향 조정(Boost): 일정 기간(S)이 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다. 

 

매우 간단하지만, 위에서 말한 한계들 중 2가지를 효과적으로 해결하는 방안이다. 

1. 기아 상태를 확실히 방지한다.
   • 일정 시간마다 CPU 할당을 보장받기 때문
2. 프로세스의 특성 변화를 반영할 수 있게 된다. 
   • CPU 위주 작업이 I/O 위주 작업으로 변했다고 해도, Boost up 된다면 I/O 위주 작업 특성에 맞게 스케줄링이 적용된다. 

 

[S는 어떻게 정하지?]
최적의 S값은 어떻게 결정할까? 이러한 종류의 변수는 부두 상수(Voo-doo Constants)라고 불린다. 왜냐하면 상황에 따라 정확하게 최적값을 아는 건 흑마술의 영역으로 느껴질 만큼 어려워서..  (OSTEP p.88)

[Tip: 부두 상수는 가능한 피하자 (Ousterhout's Law)]
가능하다면 부두 상수를 피하는 것이 좋은 생각이다. 그러나 MLFQ의 예처럼 피할 수 없는 경우가 더 잦다. default 값으로 가득찬 설정 파일들이 그 예시이다. 이 값들은 풍부한 경험의 관리자가 조정 가능하다. 그러나 최적값을 증명하기엔 매우 어렵거나 불가하고, 그저 현장에서 문제없기를 바랄뿐이다... (OSTEP p.90)

 

 

그럼 나머지 하나의 한계점(의도적인 CPU 양보에 취약)은 어떻게 해결할까?

규칙 4-1, 4-2를 보완함으로써 이는 이룰 수 있다. 그래서 등장한게 규칙 4번이다.

 

규칙 4. 시간 할당량을 소진하면, 우선순위는 낮아진다. CPU 양보 여부와 횟수는 고려하지 않는다.

1. 해당 작업이 현 우선순위 단계에서 CPU를 얼마나 사용했는지(CPU 사용시간)를 기록한다.
2. 중간에 CPU를 양보했다면, 다음 차례때는 기록된 CPU 사용시간부터 이어서 측정한다.
3. CPU 사용시간이 시간 할당량(= 타임 슬라이스)에 도달하면, 현재 실행이 타임 슬라이스에 도달하지 않아도 즉시 우선순위를 낮춘다. 

 

 

 

타임 슬라이스의 크기는 얼마로 해야 하는가?

이 또한 Boost를 위한 기간 S의 결정처럼 쉽지 않은 문제이다. 

 

대부분의 MLFQ 기법들은 각 우선순위 별로 다른 타임 슬라이스를 적용한다. 

• 일반적으로, 우선순위가 높은 큐는 짧은 타임 슬라이스(10ms 이하)를 지정한다.
  • 왜냐하면 I/O 집중형 작업 비중이 높을 것이고, 따라서 빠르게 교체해주는 것이 의미있기 때문이다. 
• 우선순위가 낮은 큐는 긴 타임 슬라이스(수백 ms)를 지정한다.
  • 왜냐하면 낮게 가라앉은 CPU 집중형 작업들이 많을 것이기 때문이다. 

 

대략 이런 모양이 될 것이다.