[OS] MLFQ

스케줄링 기법 중 멀티 레벨 피드백 큐 (MLFQ) 스케줄링 기법에 대해 공부하였다.

MLFQ가 해결하고자 하는 기본적인 문제는 다음과 같다.
- 짧은 작업을 먼저 실행시켜 반환 시간을 최적화
- 응답이 빠른 시스템이라는 느낌을 주기 위한 응답 시간 최적화

운영체제가 프로세스에 대한 정보를 가지고 있지 않은데 어떻게 이러한 스케줄러를 만들 수 있을까 ?

MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위가 배정된다. 실행 준비가 된 프로세스는 이중 하나의 큐에 존재한다.

한 큐에는 둘 이상의 작업이 존재할 수 있으며, 이들은 모두 같은 우선순위를 가진다.
이 작업들 사이에는 타임슬라이싱 스케줄링이 사용된다.

MLFQ 스케줄링의 핵심은 작업의 우선순위를 정하는 방식이며, 작업의 특성에 따라 동적으로 우선순위를 부여한다.

이를테면 대화형 프로세스같은 작업의 경우, 짧고 빈번하게 CPU를 사용하므로, MLFQ는 해당 작업의 우선순위를 높게 유지한다.

MLFQ가 우선순위를 변경하는 방법에 대해 자세히 알아보자.
작업의 우선순위를 변경한다는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지이다.

기본적으로 처음 작업이 시스템에 진입하면, 가장 높은 우선순위의 큐에 놓인다. 이 작업들은 다음과 같은 규칙을 따른다.
- 만약 이 작업이 주어진 타임슬라이스를 모두 소모하는 경우 우선순위가 낮아진다.
- 만약 이 작업이 타임슬라이스를 소모하기 전에 CPU를 양도하면 우선순위가 유지된다.

 

타임슬라이스를 소모하기 전 CPU를 양도하는 경우만 봐도, 짧고 빈번한 작업에 대해 높은 우선순위를 유지하려고 하는게 보인다.

예시를 통해 더 자세히 알아보자.

 

한 개의 긴 시간을 가지는 작업

위 세 개의 큐로 이루어진 스케줄러에서 긴 시간을 가지는 작업의 우선순위가 어떤 식으로 변하는지 알아보겠다.

작업은 최고 우선순위로 진입해서, 10msec의 타임 슬라이스를 모두 소모한다.

이 과정을 반복하며 가장 낮은 우선순위를 가지는 큐인 Q0로 이동하게 되며, 이후 계속 머무르게 된다.

아주 간단하다.

 

짧은 작업과 함께

 

짧은 작업의 경우도 살펴보자. 처음에 말했다시피, MLFQ는 짧은 작업을 우선 실행하길 원한다. (SJF에 근접하길 원함)

예시에는 2 개의 작업이 존재하는데, A는 오래 실행되는 CPU 위주 작업, B는 짧은 대화형 작업이다.

오래 실행되는 작업 A는 이미 시스템에 도착해 실행해온 상태, B는 이제 도착한 상태를 가정해보자.

과연 MLFQ는 SJF처럼 짧은 동작 B를 선호할까? 그림을 분석해보자.

 

작업 B는 T=100에 시스템에 도착해 가장 높은 우선순위 큐로 들어간다.

실행시간이 20msec인 B는 한 번만 타임슬라이스를 전부 소모하고, Q0에 도착하기 전에 종료된다.

이후 A는 낮은 우선순위에서 실행을 재개한다.

 

이 예에서 MLFQ 알고리즘의 주요 목표를 알 수 있다.

위에도 말했듯이 스케줄러는 들어온 작업이 짧은지 긴지 작업에 대한 정보가 없다. 따라서 일단 짧은 작업이라고 가정하고 높은 우선순위를 부여한다.

만약 그 작업이 진짜 짧은 작업이라면 빨리 실행되고 종료될 것이고, 짧은 작업이 아니였다면 자연스레 우선순위가 낮은 큐로 이동하면서 스스로가 작업시간이 긴 작업이라는 것을 증명할 것이다.

 

입출력 작업에 대해서는 어떻게?

다음은 입출력 작업을 수행하는 예를 살펴보자.

상기했듯이 MLFQ는 프로세스가 타임 슬라이스를 소진하기 전 CPU를 양도하면 같은 우선순위를 유지하는데, 이 규칙의 의도는 간단하다.

만약 대화형 작업이 사용자 입력을 대기하며 자주 입출력을 수행하면, 타임 슬라이스가 종료되기 전 CPU를 양도할텐데, 이 경우 동일한 우선순위를 유지하게 하는 것이다.

 

입출력 작업과 CPU 집중적인 작업이 혼합된 경우의 예를 보자

회색 작업은 대화형 작업으로, 입출력을 수행하기 전 1msec만 실행되고, A는 긴 작업으로, B와 CPU를 차지하기 위해 경쟁한다.

회색 작업은 CPU를 계속 양도하기 때문에 가장 높은 우선순위를 계속 유지할 것이고, 이는 MLFQ의 목표에 근접한다.

 

현재 MLFQ의 문제점

현재까지 본 MLFQ는 간단한 원리로 스케줄링을 잘 해주는 것 같지만, 심각한 결점을 가진다.

 

먼저, 기아 상태가 발생할 수 있다.

시스템에 너무 많은 대화형 작업이 존재한다면, 결국 실행시간이 긴 작업들은 CPU를 할당받지 못할 것이다.

 

또한, 스케줄러를 자신에게 유리하게 동작하도록 사용자가 프로그램을 다시 작성할 수도 있다.

한마디로 스케줄러를 속이는 것인데, 일부러 타임슬라이스가 끝나기 전 CPU를 양도해 우선순위를 유지시켜 CPU를 독점할 수 있다.

 

마지막으로는, 시간이 지나면서 프로그램의 특성이 변한다.

CPU 위주 작업이 대화형 작업으로 바뀔지는 아무도 모르는데, 현재까지 본 방식으로는 그런 작업을 대우해줄 순 없다.

 

 

우선순위의 상향 조정

규칙을 보완하여 기아 문제를 방지할 수 있는지 살펴보자.

간단한 아이디어는, 주기적으로 모든 작업의 우선순위를 상향 조정하는 것이다. 

 

일정 기간이 지나면 모든 작업을 최상위 큐로 보내는 규칙을 추가해보자.

이 규칙은 프로세스는 굶지 않는다는것을 보장해주고, 작업의 특성이 변할 경우 변경된 특성을 새로 적용할 수 있게 해준다.

 

예를 들어 긴 실행시간을 가진 작업이 두 개의 대화형 작업과 CPU를 경쟁한다고 해보자.

우선순위 상향이 없는 왼쪽의 경우, 긴 실행시간을 가진 작업은 굶게 된다.

50msec마다 우선순위 상향이 일어나는 오른쪽의 경우를 보면, 긴 작업도 꾸준히 진행되는 것을 보장할 수 있다.

 

물론 S값(우선순위 상향 주기)의 결정이 불가피하다. S가 너무 크면 긴 작업이 굶고, 너무 짧으면 대화형 작업이 CPU를 사용할 수 없게 되므로 적절한 시간 설정이 필요하다.

 

더 나은 시간 측정

아직 해결하지 못한 문제로, 스케줄러를 자신에게 유리하게 동작하도록 속이는 경우가 있다.

이 문제의 원인은, 타임슬라이스가 끝나기 전 CPU를 양도 시 우선순위가 유지된다는 규칙이다.

 

여기서의 해결책은, MLFQ의 각 단계에서 CPU 총 사용시간을 측정하는 것이다.

스케줄러는 현재 단계의 프로세스가 소진한 CPU 사용시간을 저장하고, 타임 슬라이스에 해당하는 시간을 모두 소진하면 강등된다.

즉 타임 슬라이스를 한 번에 다 쓰든 여러번 쪼개쓰든 상관없이 타임슬라이스를 다 쓰면 강등되는 규칙을 추가한다.

 

 

왼쪽 그림은 사용자가 자신에게 유리하게 스케줄러를 조작하였지만, 오른쪽 그림을 보면 새로운 규칙을 추가해 프로세스의 입출력 행동같이 CPU 양보와 무관하게 CPU독점을 방지할 수 있게 되었다.

 

 

나머지 쟁점들

MLFQ 스케줄링에는 상기한 쟁점들 외에도 다양한 쟁점들이 존재한다.

필요한 변수들 (큐의 개수, 타임슬라이스의 크기, 우선순위 상향의 주기)들을 어떻게 설정하는지가 이에 해당하며,  

계속 조정해나가면서 균형점을 찾아야한다.