스케줄링: 멀티 레벨 피드백 큐[1]

멀티 레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ) 스케줄러는 1962년 Corbato 등에 의해 CTSS(Compatible Time-Sharing System)에 처음 도입되었습니다. Corbato는 이 연구와 Multics에 대한 후속 연구로 최고 권위의 튜링상을 수상했죠. 이후 MLFQ는 수년에 걸쳐 발전을 거듭하며 오늘날의 몇몇 현대 시스템에까지 이르게 되었습니다.

MLFQ가 해결하고자 하는 핵심 문제는 두 가지입니다.

1. 짧은 작업을 우선 처리하여 반환 시간(turnaround time)을 최적화하는 것입니다. SJF나 STCF 같은 알고리즘은 이를 위해 각 작업의 실행 시간 정보를 필요로 하지만, 안타깝게도 운영체제는 이 정보를 사전에 알 수 없습니다.

2. 사용자와 상호작용하는 프로세스, 즉 사용자가 화면 앞에서 응답을 기다리는 프로세스의 응답 시간(response time)을 최소화하는 것입니다. RR 같은 알고리즘은 응답 시간을 어느 정도 단축시키지만, 반환 시간 측면에서는 거의 최악에 가까운 성능을 보입니다.

Note

라운드 로빈(Round Robin, RR)은 프로세스들에게 CPU 사용 시간을 공평하게 분배하는 스케줄링 알고리즘입니다.

RR에서는 각 프로세스가 동일한 시간 할당량(타임 슬라이스)을 받습니다. 할당된 시간이 끝나면 프로세스는 선점(preemption)되고, 준비 큐(ready queue)의 맨 뒤로 보내집니다. 그러면 큐의 다음 프로세스가 CPU를 받아 실행되는 식이죠.

이런 방식으로 모든 프로세스가 돌아가면서 CPU를 사용하게 됩니다. 마치 원탁에 앉은 사람들이 돌아가며 말하는 것과 비슷하다고 해서 ‘라운드 로빈’이라는 이름이 붙었습니다.

RR의 주요 특징은 다음과 같습니다.

1. 모든 프로세스는 동일한 타임 슬라이스를 할당받습니다.

2. CPU 버스트가 타임 슬라이스보다 짧으면 프로세스는 자발적으로 CPU를 양보합니다.

3. CPU 버스트가 타임 슬라이스보다 길면 타임 슬라이스가 끝난 후 프로세스는 선점됩니다.

4. 선점된 프로세스는 준비 큐의 맨 뒤로 가서 다시 CPU를 기다립니다.

RR은 대화형 시스템에서 응답 시간을 줄이는 데 효과적입니다. 모든 프로세스가 CPU를 조금씩 나눠 쓰기 때문에 어느 한 프로세스가 지나치게 오래 기다리는 일이 없거든요.하지만 문맥 교환(context switch) 오버헤드가 있고, 타임 슬라이스가너무 작으면 오히려 성능이 저하될 수 있다는 단점도 있습니다.

여기서 우리가 마주하는 질문은 이렇습니다.

• 개별 프로세스에 대한 사전 정보가 전혀 없는 상황에서 이런 스케줄러를 어떻게 만들 수 있을까요?

• 프로세스가 실행되는 동안 그 특성을 파악하고, 이를 토대로 더 나은 스케줄링 결정을 내리려면 어떤 방법을 사용할 수 있을까요?

핵심 질문: 정보 없이 스케줄링하는 방법은?

프로세스의 실행 시간을 미리 알 수 없는 상황에서, 대화형 프로세스의 응답 시간을 최소화하면서 동시에 전체 반환 시간도 최소화할 수 있는 스케줄러를 어떻게 설계할 수 있을까요?

MLFQ는 바로 이 문제에 도전하기 위해 고안된 스케줄링 기법입니다. 프로세스의 실행 특성을 관찰하고 그에 따라 동적으로 우선순위를 조정함으로써, 사전 정보 없이도 최적에 가까운 스케줄링을 달성하고자 하는 것이죠.

MLFQ: 기본 규칙

멀티 레벨 피드백 큐(MLFQ)의 기본 알고리즘은 다음과 같습니다. 세부 사항에서는 차이가 있을 수 있지만, 대부분의 MLFQ 구현체는 이와 유사한 원리를 따릅니다.

MLFQ는 여러 개의 큐로 이루어져 있으며, 각 큐는 서로 다른 우선순위(priority level)를 갖습니다. 실행 가능한 모든 프로세스는 이 큐들 중 하나에 위치하게 됩니다. MLFQ는 우선순위에 따라 다음에 실행할 프로세스를 선택하는데, 보다 높은 우선순위의 큐에 있는 프로세스가 우선적으로 선택됩니다.

팁: 과거에서 배우다

MLFQ는 과거의 행동 패턴을 토대로 미래를 예측하는 좋은 예시입니다. 이런 접근법은 운영체제를 비롯한 컴퓨터 과학의 여러 분야(하드웨어의 분기 예측이나 캐시 알고리즘 등)에서 자주 사용됩니다. 이 방식은 작업의 진행 양상이 단계적이고 예측 가능할 때 효과적입니다. 다만 주의해서 사용해야 합니다. 잘못 적용하면 오히려 예측 정보가 없을 때보다 더 안 좋은 결정을 내릴 수 있기 때문이죠.

한 큐에는 여러 프로세스가 존재할 수 있는데, 이들은 모두 동일한 우선순위를 갖습니다. 같은 큐 내의 프로세스들에 대해서는 라운드 로빈(Round-Robin, RR) 스케줄링이 적용됩니다.

MLFQ의 핵심은 바로 이 우선순위를 결정하는 방식에 있습니다. MLFQ는 각 프로세스에 고정된 우선순위를 부여하지 않고, 프로세스의 실행 특성에 따라 동적으로 우선순위를 조정합니다.

예를 들어, 어떤 프로세스가 키보드 입력을 기다리며 반복적으로 CPU를 양보한다면 MLFQ는 그 프로세스의 우선순위를 높게 유지합니다. 이는 대화형 프로세스의 전형적인 행동 양식이기 때문이죠. 반대로 어떤 프로세스가 장시간 CPU를 독점한다면 MLFQ는 그 프로세스의 우선순위를 점차 낮춰갑니다.

이렇게 MLFQ는 프로세스의 실행 도중 그 특성을 파악하고, 이를 토대로 향후 행동을 예측하는 것입니다.

MLFQ의 두 가지 기본 규칙은 다음과 같습니다.

• 규칙 1: Priority(A) > Priority(B) 이면, B는 실행되지 않고 A가 실행됩니다.

• 규칙 2: Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행됩니다.

시도 1: 우선순위의 변경

MLFQ는 프로세스의 우선순위를 어떻게 조정할 것인지 결정해야 합니다. 프로세스의 우선순위를 변경한다는 것은 곧 그 프로세스가 위치할 큐를 결정하는 것과 같습니다. 이를 위해서는 시스템의 워크로드 특성을 반영해야 합니다. 일반적으로 워크로드는 짧은 CPU 버스트를 가지며 자주 I/O를 수행하는 대화형 작업과, CPU 시간을 많이 필요로 하지만 응답 시간은 상대적으로 덜 중요한 긴 CPU 버스트의 계산 집약적 작업이 섞여 있습니다.

우선순위 조정을 위한 첫 번째 시도는 다음과 같습니다.

어떤 한 시점에서 큐의 상태는 그림 11.1과 같을 수 있습니다. 프로세스 A와 B는 가장 높은 우선순위 큐에, C는 중간 큐에, D는 가장 낮은 우선순위 큐에 있습니다. 우리가 알고 있는 MLFQ의 동작 방식에 따르면, 스케줄러는 최상위 큐에 있는 A와 B를 RR 방식으로 번갈아 실행할 것입니다. 다만 이런 정적인 스냅샷만으로는 MLFQ의 실제 동작을 완전히 파악할 수 없습니다.

프로세스의 우선순위가 시간에 따라 어떻게 변화하는지 살펴보겠습니다.

• 규칙 3: 새로운 프로세스가 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 배치된다.

• 규칙 4a: 할당된 타임 슬라이스를 모두 소진하면 해당 프로세스의 우선순위가 한 단계 낮아진다. 즉, 바로 아래 큐로 이동한다.

• 규칙 4b: 타임 슬라이스가 끝나기 전에 스스로 CPU를 양보(yield)하면 같은 우선순위를 유지한다.

여기서 타임 슬라이스(time slice)란 각 프로세스에 할당되는 CPU 사용 시간의 단위를 말합니다. 프로세스가 이 시간을 모두 쓰면 선점(preemption)되고, 자발적으로 양보하면 우선순위가 유지되는 거죠.

이러한 규칙을 통해 MLFQ는 프로세스의 실행 특성에 따라 동적으로 우선순위를 조정합니다. I/O를 많이 수행하는 프로세스는 높은 우선순위를 유지하는 반면, CPU를 오래 사용하는 프로세스는 점차 낮은 우선순위로 이동하게 됩니다.

예제 1: 긴 CPU 버스트를 가진 프로세스

이제 몇 가지 예시를 통해 MLFQ가 어떻게 동작하는지 살펴보겠습니다. 먼저, CPU를 오랫동안 사용하는 프로세스가 시스템에 들어왔을 때 어떤 일이 벌어지는지 알아봅시다. 그림 11.2는 3개의 큐로 구성된 MLFQ 스케줄러에서 시간이 지남에 따라 이 프로세스의 우선순위가 어떻게 변화하는지 보여줍니다.

예시에서 볼 수 있듯이, 프로세스는 처음에 최상위 큐인 Q2에 위치합니다(규칙 3). 10ms의 타임 슬라이스를 모두 소진하면, 스케줄러는 이 프로세스의 우선순위를 한 단계 낮춰 Q1으로 이동시킵니다(규칙 4a).

Q1에서도 마찬가지로 타임 슬라이스를 다 쓰면 프로세스는 최하위 큐인 Q0으로 내려갑니다. 이후로는 계속 Q0에 남아있게 되는 거죠.

여기서 주목할 점은 다음과 같습니다.

1. 프로세스는 가장 높은 우선순위에서 시작합니다.

2. 할당된 타임 슬라이스를 모두 쓰면 우선순위가 단계적으로 낮아집니다.

3. 최하위 큐에 도달하면 우선순위의 변동이 없습니다.

이를 통해 우리는 CPU를 많이 사용하는 프로세스가 MLFQ에서 어떻게 처리되는지 알 수 있습니다. 초기에는 높은 우선순위를 받지만, CPU를 계속 점유하면 점차 낮은 큐로 이동하다가 결국 최하위 큐에 머무르게 되는 것이죠. 이렇게 MLFQ는 프로세스의 실행 패턴에 따라 동적으로 우선순위를 조정합니다.

예제 2: 짧은 프로세스와 함께

이번에는 좀 더 복잡한 시나리오를 살펴보겠습니다. 이를 통해 MLFQ가 어떻게 SJF(Shortest Job First)와 유사하게 동작할 수 있는지 이해할 수 있을 것입니다.

이 예시에서는 두 개의 프로세스가 등장합니다. 프로세스 A는 CPU를 오랫동안 사용하는 계산 집약적인 작업이고, 프로세스 B는 실행 시간이 짧은 대화형 작업입니다. A는 이미 어느 정도 실행된 상태이고, B는 방금 시스템에 도착했다고 가정해 봅시다. 이때 MLFQ는 어떻게 동작할까요? B를 우선적으로 처리함으로써 SJF와 비슷한 결과를 낼 수 있을까요?

그림 11.3은 이 시나리오의 결과를 보여줍니다. 다른 CPU 집약적 프로세스와 마찬가지로, A(검은색)는 최하위 큐에서 실행 중입니다. B(회색)는 시간 100에 시스템에 진입하면서 최상위 큐에 배치됩니다(규칙 3). B의 실행 시간은 20ms로 매우 짧기 때문에, 두 번의 타임 슬라이스 안에 실행을 마칩니다. 즉, 최하위 큐까지 내려가기 전에 종료되는 거죠. B가 끝난 후에야 A가 하위 큐에서 실행을 재개합니다.

이 예제는 MLFQ 알고리즘의 주된 목표를 잘 보여줍니다. 스케줄러는 각 프로세스의 실행 시간을 미리 알 수 없으므로, 일단 모든 프로세스를 “짧은 작업”으로 간주하고 높은 우선순위를 부여하는 것입니다.

만약 정말 짧은 작업이라면 금방 실행을 마치고 종료될 것입니다. 그렇지 않고 긴 작업이라면 점차 아래 큐로 내려가면서 스스로 CPU 집약적 작업임을 드러내게 됩니다. 이런 방식으로 MLFQ는 SJF와 유사한 효과를 달성할 수 있습니다.

예제 3: I/O 집약적 프로세스

이번에는 I/O 작업이 많은 프로세스의 경우를 살펴보겠습니다. 앞서 언급한 규칙 4b에 따르면, 프로세스가 할당된 타임 슬라이스를 다 쓰기 전에 CPU를 양보(yield)하면 현재의 우선순위를 유지하게 됩니다.

이 규칙의 의도는 다음과 같습니다. 대화형 프로세스는 사용자의 키보드나 마우스 입력을 기다리면서 빈번히 I/O 작업을 수행하게 됩니다. 이 때문에 타임 슬라이스가 끝나기 전에 CPU를 양보하는 일이 잦을 거라고 예상할 수 있죠. 이런 경우에는 프로세스의 우선순위를 그대로 유지함으로써 대화형 작업의 응답성을 높이고자 하는 것입니다.

그림 11.4는 이 규칙이 어떻게 적용되는지 보여줍니다. 프로세스 B(회색)는 대화형 프로세스로, I/O 요청을 하기 전에 CPU를 1ms 동안만 사용합니다. 반면 프로세스 A(검정색)는 CPU를 오래 점유하는 배치(batch) 프로세스입니다. 이 둘은 CPU 사용을 두고 경쟁하는 관계에 있습니다.

B는 I/O 작업 때문에 반복적으로 CPU를 양보하게 됩니다. 따라서 MLFQ는 규칙 4b에 의해 B를 가장 높은 우선순위에 머물게 합니다. 만약 B가 정말 대화형 프로세스라면, 이는 MLFQ가 대화형 작업의 응답 시간을 최소화하려는 목표에 부합하는 것이라 할 수 있습니다.

이 예제를 통해, MLFQ가 프로세스의 I/O 행동을 고려하여 우선순위를 동적으로 조정함으로써 시스템의 응답성을 개선하려 한다는 점을 알 수 있습니다. I/O를 많이 하는 프로세스에게는 높은 우선순위를 부여하고, CPU를 오래 쓰는 프로세스는 점차 낮은 우선순위로 내리는 것이죠.

현재 MLFQ의 문제점

지금까지 살펴본 MLFQ는 비교적 단순한 알고리즘입니다. CPU를 긴 작업과 짧은 작업 사이에 적절히 분배하고, I/O 집약적인 대화형 작업의 응답 시간을 최소화하는 등 나름 잘 동작하는 것처럼 보입니다. 그러나 이 기법에는 몇 가지 심각한 결함이 있습니다.

1. 기아 상태(starvation)의 가능성: 만약 시스템에 대화형 작업이 너무 많이 존재한다면, 이들이 대부분의 CPU 시간을 차지하게 될 것입니다. 그 결과 CPU를 오래 사용하는 배치 작업들은 제대로 된 CPU 시간을 할당받지 못하게 됩니다. 이런 시나리오에서도 긴 작업들이 어느 정도 진행될 수 있도록 보장하는 것이 바람직할 것입니다.

2. 스케줄러 악용의 위험: 영리한 사용자라면 스케줄러를 자신에게 유리하게 작동하도록 프로그램을 조작할 수 있습니다. 일반적으로 이는 스케줄러를 속여 정해진 것보다 더 많은 CPU 시간을 할당받는 것을 의미합니다. 현재의 MLFQ 알고리즘은 이런 공격에 취약합니다. 예를 들어, 프로세스가 타임 슬라이스가 끝나기 직전에 불필요한 I/O 요청을 내려 CPU를 양보한다면, 계속해서 높은 우선순위 큐에 머물 수 있습니다. 이 트릭을 잘 활용하면, 예컨대 타임 슬라이스의 99%를 쓰고 CPU를 양보하는 식으로, 사실상 CPU를 독점할 수도 있는 것이죠.

3. 시간에 따른 프로세스 특성 변화: 프로그램의 행동 양식은 시간이 지남에 따라 달라질 수 있습니다. CPU 집약적 작업이 어느 순간 대화형 작업으로 바뀔 수도 있는 거죠. 그러나 현재의 MLFQ로는 이런 작업이 다른 대화형 작업과 동등한 취급을 받기 어렵습니다.

이상의 문제들은 MLFQ가 프로세스의 실행 이력에만 의존한다는 점에서 비롯됩니다. 기아 상태, 악용 가능성, 동적 특성 변화 등의 이슈를 해결하려면 보다 정교한 기법이 필요해 보입니다.

시도 2: 우선순위의 상향 조정

이제 MLFQ의 규칙을 보완하여 기아 문제를 해결할 수 있는 방법을 살펴보겠습니다. CPU 집약적인 작업도 어느 정도 진행될 수 있도록 보장하려면 어떻게 해야 할까요?

한 가지 간단한 아이디어는 주기적으로 모든 작업의 우선순위를 상향 조정(boost)하는 것입니다. 여러 방법이 있겠지만, 가장 단순한 방식은 모든 프로세스를 최상위 큐로 이동시키는 것입니다. 이를 반영한 새로운 규칙은 다음과 같습니다.

• 규칙 5: 일정 시간 S가 경과할 때마다, 시스템의 모든 프로세스를 최상위 큐로 이동시킨다.

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

1. 모든 프로세스가 기아 상태에 빠지지 않음을 보장합니다. 최상위 큐에 있는 동안에는 다른 우선순위 높은 프로세스들과 라운드 로빈 방식으로 CPU를 나눠 쓰게 되므로, 어느 정도의 CPU 시간을 할당받을 수 있습니다.

2. CPU 집약적 작업이 대화형 작업으로 특성이 바뀌더라도, 우선순위 상향을 통해 스케줄러가 이 변화를 감지하고 적절히 대응할 수 있게 됩니다.

예를 들어, 그림 11.5는 CPU를 오래 사용하는 한 프로세스와 짧은 대화형 프로세스 두 개가 경쟁하는 시나리오를 보여줍니다. 왼쪽 그래프는 우선순위 상향이 없는 경우인데, 긴 작업이 짧은 작업들이 도착한 이후로는 계속 기아 상태에 빠져 있습니다. 반면 오른쪽 그래프는 50ms마다 우선순위 상향이 일어나는 모습입니다(예시를 위해 짧은 주기를 사용했습니다). 이 경우 긴 작업도 주기적으로 실행 기회를 얻어 꾸준히 진행됨을 알 수 있습니다.

물론 주기 S를 얼마로 정할 것인지가 중요한 문제입니다. 존경받는 시스템 연구자 John Ousterhout는 이런 종류의 값을 “부두(voodoo) 상수”라고 불렀는데, 마치 이 값을 정하려면 흑마술이라도 써야 할 것 같다는 뜻입니다. 안타깝게도 S가 바로 그런 변수입니다. S를 너무 크게 잡으면 긴 작업이 여전히 기아 상태에 빠질 수 있고, 너무 작게 잡으면 대화형 작업이 충분한 CPU 시간을 받지 못할 수 있습니다. 적절한 균형점을 찾는 것이 중요한 과제입니다.

시도 3: 더 정확한 시간 측정

MLFQ에는 해결해야 할 또 다른 문제가 있습니다. 바로 사용자가 스케줄러를 조작하여 자신에게 유리하게 만드는 것을 막는 것입니다. 이런 일이 가능했던 것은 규칙 4a와 4b 때문입니다. 이 규칙들은 프로세스가 타임 슬라이스를 다 쓰기 전에 CPU를 양보함으로써 현재 우선순위를 유지할 수 있도록 허용했습니다. 이를 막기 위해서는 어떻게 해야 할까요?

해법은 MLFQ의 각 단계에서 프로세스가 실제로 CPU를 사용한 누적 시간을 측정하는 것입니다. 스케줄러는 현재 단계에서 각 프로세스의 CPU 사용 시간을 기록합니다. 프로세스가 해당 단계의 타임 슬라이스를 모두 소진하면, 그 횟수에 관계없이 다음 우선순위 큐로 내려가게 됩니다. 타임 슬라이스를 한 번에 다 쓰든, 짧게 여러 번 나눠 쓰든 상관없이 누적 사용 시간만 고려하는 것이죠. 이를 반영하여 규칙 4a와 4b를 하나의 규칙으로 통합해 보겠습니다.

• 규칙 4: 프로세스가 현재 단계에서 CPU를 양보한 횟수와 무관하게, 정해진 시간 할당량을 모두 소진하면 우선순위가 낮아집니다. (즉, 한 단계 아래 큐로 이동합니다.)

그림 11.6은 이 아이디어를 잘 보여줍니다. 왼쪽은 프로세스가 규칙 4a와 4b를 악용하여 스케줄러를 조작하는 모습인데, 타임 슬라이스가 거의 끝나갈 때마다 I/O 요청을 내려 계속 높은 우선순위에 머물러 있습니다.

반면 오른쪽은 새로운 규칙 4를 적용한 모습입니다. 이제는 프로세스의 I/O 행동과 무관하게 정해진 CPU 시간을 다 쓰면 하위 큐로 내려가게 되므로, 더 이상 CPU를 불공정하게 많이 쓸 수 없게 됩니다.

이처럼 MLFQ에서 프로세스의 CPU 사용 시간을 정확히 측정하고 누적하는 것은 스케줄러 조작을 방지하고 공정성을 높이는 데 있어 매우 중요한 아이디어라고 할 수 있습니다.

MLFQ의 조정과 기타 이슈

MLFQ 스케줄링에는 여러 가지 추가적인 고려 사항이 있습니다. 스케줄러가 사용하는 각종 변수들을 어떻게 설정할 것인가도 중요한 문제입니다. 예를 들어, 몇 개의 큐를 사용할 것인지, 각 큐의 타임 슬라이스는 얼마로 할 것인지, 기아 상태를 방지하고 프로세스의 행동 변화를 반영하기 위해 얼마나 자주 우선순위를 조정할 것인지 등이 그런 문제들입니다. 이에 대한 명확한 답을 찾기는 쉽지 않습니다. 실제 워크로드를 관찰하고 경험을 쌓아가며 최적점을 찾아야 할 것입니다.

실제로 많은 MLFQ 구현체들은 각 큐마다 서로 다른 타임 슬라이스를 사용합니다. 일반적으로 높은 우선순위 큐는 짧은 타임 슬라이스를 할당받습니다. 이 큐에는 주로 대화형 프로세스들이 위치하므로, 이들을 빠르게 교체하는 것이 응답성 향상에 도움이 되기 때문입니다(예: 10ms 이하). 반대로 낮은 우선순위 큐는 주로 CPU 집약적인 장기 실행 프로세스들을 포함하므로, 상대적으로 긴 타임 슬라이스를 부여받습니다(예: 수백 ms).

그림 11.7은 최상위 큐는 10ms, 중간 큐는 20ms, 최하위 큐는 40ms의 타임 슬라이스를 갖는 스케줄러에서 두 프로세스가 실행되는 모습을 보여줍니다.

팁: 부두 상수를 피하라 (Ousterhout’s Law)

가능하다면 ‘부두(voodoo) 상수’의 사용을 피하는 것이 좋습니다. 하지만 현실적으로는 앞서 본 것처럼 이를 완전히 배제하기 어려운 경우가 많습니다. 최적값을 찾는 일도 쉽지 않죠.

흔히 이런 상황에서는 온갖 기본값들로 가득 찬 설정 파일이 등장합니다. 뭔가 잘 동작하지 않을 때 경험 많은 관리자가 이 값들을 수정할 수 있도록 하는 거죠. 하지만 대부분의 경우 이 기본값들이 그대로 사용되며, 현장에서 잘 먹혀 들기를 바랄 뿐입니다.

이런 통찰을 널리 알린 운영체제 교수 John Ousterhout의 이름을 따 ‘Ousterhout’s Law’라고도 부릅니다.

이처럼 MLFQ는 매우 유연하고 강력한 스케줄링 기법이지만, 최적으로 운용하기 위해서는 여러 변수들에 대한 세심한 조정이 필요합니다. 실제 시스템의 특성과 요구 사항을 잘 파악하여 적절한 균형점을 찾아가는 것이 중요한 과제라 하겠습니다.

Solaris 운영체제의 MLFQ 구현체인 ‘시분할 스케줄링 클래스(Time Sharing Scheduling Class, TS)’는 설정이 특히 간편합니다. Solaris는 프로세스의 수명 주기 동안 우선순위의 변화 패턴, 각 큐의 타임 슬라이스 길이, 그리고 우선순위 상향 조정(priority boost)의 주기 등을 결정하는 테이블을 제공합니다. 시스템 관리자는 이 테이블을 수정함으로써 스케줄러의 동작을 조정할 수 있죠. 기본 설정은 60개의 큐, 최상위 큐의 타임 슬라이스는 20ms에서 시작해 최하위 큐에서는 수백 ms까지 점진적으로 증가, 그리고 약 1초마다 우선순위 상향 조정이 일어나는 식입니다.

하지만 모든 MLFQ 스케줄러가 이런 테이블이나 이 장에서 언급한 규칙들을 그대로 사용하는 것은 아닙니다. 어떤 경우에는 수학 공식을 활용해 우선순위를 조절하기도 합니다. 가령 FreeBSD 4.3 버전의 스케줄러는 프로세스의 누적 CPU 사용량을 기준으로 현재 우선순위를 계산하는 공식을 사용합니다. 이때 CPU 사용량은 시간이 지나면서 서서히 감쇄(decay)되는데, 이를 통해 우선순위 상향 조정을 간접적으로 구현하는 셈이죠. 이런 유형의 ‘감쇄 사용량(decay-usage)’ 알고리즘과 그 특성에 대해서는 Epema의 논문에 잘 정리되어 있습니다.

그 외에도 스케줄러들은 다양한 부가 기능을 제공하곤 합니다. 예컨대 일부 스케줄러는 최상위 우선순위 큐를 운영체제 프로세스를 위해 예약해 두기도 합니다. 이 경우 일반 사용자 프로세스는 절대 최고 우선순위를 얻지 못하게 되죠. 또 어떤 시스템들은 사용자가 직접 우선순위를 조정할 수 있는 방법을 제공하기도 합니다. 리눅스의 ‘nice’ 명령어가 대표적인데, 이를 통해 프로세스의 우선순위를 높이거나 낮출 수 있습니다(자세한 사용법은 매뉴얼 페이지 참조).

팁: 가능하다면 힌트를 활용하라

운영체제가 모든 프로세스에게 최선의 처우가 무엇인지 알기는 어렵습니다. 따라서 사용자나 관리자가 시스템에 힌트를 제공할 수 있는 인터페이스를 마련해 두면 도움이 됩니다. 이런 힌트를 ‘조언(advice)’이라고 부르기도 하는데, 운영체제가 반드시 이를 따라야 하는 것은 아니지만 보다 현명한 판단을 내리는 데 참고할 수 있습니다.

스케줄러(‘nice’), 메모리 관리자(‘madvise’), 파일 시스템(정보 제공에 기반한 프리페칭, 캐싱 등) 등 운영체제의 다양한 영역에서 이런 조언 메커니즘이 유용하게 활용될 수 있습니다.

MLFQ: 요약

이 장에서는 ‘멀티 레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ)’라고 불리는 스케줄링 기법에 대해 알아보았습니다. 이제 왜 이런 이름이 붙었는지 이해할 수 있을 것입니다. MLFQ는 여러 개의 우선순위 큐를 사용하며, 각 프로세스의 우선순위를 결정하기 위해 과거 실행 이력을 피드백으로 활용합니다. 즉, 프로세스가 지금까지 어떻게 행동했는지가 앞으로의 우선순위를 정하는 기준이 되는 것이죠. 따라서 MLFQ에서는 프로세스의 시간에 따른 행동 변화와 그에 대한 적절한 대응이 매우 중요합니다.

이해를 돕기 위해 이 장에서 다룬 MLFQ의 주요 규칙들을 다시 정리해 보겠습니다.

• 규칙 1: 프로세스 A의 우선순위가 B보다 높으면, A는 실행되고 B는 실행되지 않는다.

• 규칙 2: 프로세스 A와 B의 우선순위가 같으면, A와 B는 라운드 로빈 방식으로 실행된다.

• 규칙 3: 새로운 프로세스가 시스템에 진입하면 최상위 큐에 배치된다.

• 규칙 4: 프로세스가 현재 단계에서 받은 시간을 모두 소진하면, CPU를 양보한 횟수와 관계없이 한 단계 아래 큐로 이동한다.

• 규칙 5: 주기 S마다 시스템의 모든 프로세스를 최상위 큐로 이동시킨다.

MLFQ는 여러모로 흥미로운 스케줄러입니다. 프로세스의 특성을 사전에 알지 못해도, 실행 과정을 관찰하여 그에 맞게 우선순위를 부여할 수 있습니다. 또한 반환 시간(turnaround time)과 응답 시간(response time)을 동시에 최적화하려 노력합니다.

MLFQ는 실행 시간이 짧은 대화형 프로세스에게는 SJF/STCF와 유사한 수준의 성능을 제공하며, 실행 시간이 긴 CPU 집약적 프로세스에 대해서도 어느 정도 공정성을 보장하여 조금씩이라도 진전을 이룰 수 있게 해줍니다.

이러한 장점 때문에 BSD 유닉스 및 그 파생 운영체제들[Lef+89; Bac86], Solaris[McD06], 윈도우 NT 및 후속 윈도우 시리즈[CS97] 등 많은 시스템들이 MLFQ를 기본 스케줄러로 채택하고 있습니다.

---

[1]

조세현