[OSTEP] CPU 가상화 : MLFQ 스케줄러
1. MLFQ 기본 컨셉
(1) 해결하고자 하는 과제
MLFQ가 해결하고자 하는 것은 반환 시간과 응답 시간을 최적화 하는 것이다. 반환 시간 최적화는 짧은 작업을 먼저 실행하여 전체 반환 시간을 줄이는 문제이다. 앞서 살핀 SJF나 STCF와 같이 작업의 실행 시간을 미리 알고 있다면 짧은 작업을 먼저 처리할 수 있지만, 운영체제는 이러한 정보를 사전에 알 수 없다. 따라서 마지막 가정을 완화하고, 작업의 실행 시간을 간접적으로 추정하여 최적화하는 방법을 모색해야 한다.
응답 시간 최적화는 신속한 응답을 제공하여 시스템이 빠르게 반응하는 것처럼 보이게 하는 문제이다. RR과 같은 스케줄링 기법은 응답 시간을 단축시킬 수 있지만 반환 시간에서 약점이 있었다. 결국 이 두 요소간의 균형을 맞추는 것이 관건이 된다.
(2) 기본 규칙
멀티 레벨 피드백 큐 (Multi Level Feedback Queue)는 다른 우선순위가 배정된 여러 개의 큐로 구성된다. 우선순위가 다르다면 더 높은 우선순위의 작업이 먼저 실행되고, 같은 우선순위를 갖는 같은 큐 내부의 작업들 사이에서는 RR스케줄링 알고리즘이 사용된다.
MLFQ의 핵심은 우선순위를 정하는 방식이다. MLFQ는 각 작업의 특성에 따라 동적으로 우선순위를 부여한다. 예를 들어, 대화형 프로세스에서 나타나는 패턴에는 키보드 입력을 기다리며 반복적으로 CPU를 양보하는 특성이 있다. 이러한 특성의 작업의 경우 MLFQ는 해당 작업의 우선순위를 높게 유지한다. MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.
2. 우선순위 변경 알고리즘
MLFQ는 작업의 특성에 따라 동적으로 우선순위를 부여한다고 하였다. 즉 MLFQ는 작업의 우선순위를 틈틈이 변경한다는 의미이고, 우선순위를 변경하는 것은 작업이 존재할 큐를 결정한다는 의미이다. 이 우선순위를 변경하는 알고리즘을 살펴보자.
우선 앞서 살펴본 두 가지 기본 규칙은 다음과 같다.
- 1) 우선순위가 다른 경우 더 높은 우선순위의 작업을 먼저 실행한다.
- 2) 동일한 우선순위를 갖는 같은 큐 내부의 작업들 사이에서는 RR 스케줄링 알고리즘이 적용된다.
여기에 우선순위 조정을 위한 다음 두 가지 규칙을 추가적으로 생각할 수 있다.
- 3) 작업이 시스템에 진입하면 가장 높은 우선순위를 갖는 맨 위의 큐에 놓인다.
- 4) 주어진 타임 슬라이스를 모두 사용하면 우선순위가 낮아져 한 단계 아래의 큐로 이동하고, 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
운영체제는 각 작업의 실행시간을 (이제는) 모르고 있다는 점을 상기하자. 3번 규칙에서, 스케줄러는 작업이 긴 작업인지 짧은 작업인지 알 수 없기 때문에 일단 짧은 작업이라고 가정하여 가장 높은 우선순위를 부여하는 것이다. 해당 작업이 정말 짧은 작업이었다면 빠르게 실행된 뒤 종료될 것이다. 해당 작업이 긴 작업이라면, 4번 규칙에 의해 천천히 아래 큐로 이동하게 된다. 결국 SJF와 근사한 동작을 수행하게 된다. 4번 규칙의 후단부는 대화형 작업과 같이 입출력 작업을 자주 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도할 것이기 때문에, 이러한 경우 동일한 우선순위를 유지하게 하는 것이다
3. 문제점과 해결방안
위 알고리즘에는 다음과 같은 문제점이 존재한다.
- 시스템에 너무 많은 대화형 작업이 존재하면 이들이 모든 CPU 시간을 소모하게 되어 긴 실행 시간을 갖는 작업은 CPU 시간을 할당받지 못하게 된다. (기아 상태)
- 작업이 타임 슬라이스가 끝나기 전에 CPU를 양보하도록 프로그램을 의도적으로 작성하여 스케줄러를 유리하게 동작시키게 할 수 있다.
- 프로그램은 시간 흐름에 따라 특성이 변할 수 있는데, CPU 위주 작업이 대화형 작업으로 바뀌는 경우를 적절하게 반영하지 못한다. 즉, 이 경우 다른 대화형 작업들과 같은 대우를 받지 못한다.
첫 번째 문제점인 기아 문제를 방지하려면 CPU 위주의 작업이 조금이라도 진행하는 것을 보장할 필요가 있다. 이를 위해 다음과 같은 5번째 추가 규칙을 생각할 수 있다.
- 5) 일정 시간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동시킨다.
이를 적용하면 최상위 큐에 존재하는동안에는 RR 방식에 의해 CPU를 이용할 수 있게 된다. 이를 통해 첫 번째 문제와 세 번째 문제를 동시에 해결할 수 있게 된다.구체적으로는 아래 그림과 같이 변화하게 된다.
두 번째 문제점은 4번 규칙을 다음과 같이 재정의함으로써 해결할 수 있다.
- 4) 주어진 단계에서 시간 할당량을 소진하면 CPU 양도와 관계없이 아래 큐로 이동한다.
스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장하여, 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등시키는 것이다. 아래 그림을 참고하자.
