[OSTEP] 스터디 4주차 - 스케줄링 2 : Part.1 - MLFQ

멀티 레벨 피드백 큐(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 같은 알고리즘은 응답 시간을 어느 정도 단축시키지만, 반환 시간 측면에서는 거의 최악에 가까운 성능을 보인다.

---

MLFQ : 기본 규칙

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

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

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 버스트의 계산 집약적 작업이 섞여 있다.

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

프로세스 A와 B는 가장 높은 우선순위 큐에, C는 중간 큐에, D는 가장 낮은 우선순위 큐에 있다. 우리가 알고 있는 MLFQ의 동작 방식에 따르면, 스케줄러는 최상위 큐에 있는 A와 B를 RR방식으로 번갈아 실행할 것이다.

우선순위 조정 알고리즘을 위한 첫 번째 시도는 다음과 같다.

• 규칙 3: 새로운 프로세스가 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 배치된다.
• 규칙 4a: 할당된 타임 슬라이스를 모두 소진하면 해당 프로세스의 우선순위가 한 단계 낮아진다. 즉, 바로 아래 큐로 이동한다.
• 규칙 4b: 타임 슬라이스가 끝나기 전에 스스로 CPU를 양보(yield)하면 같은 우선순위를 유지한다.

---

예 1: 한 개의 긴 실행 시간을 가진 작업

몇 가지 예시를 통해 알아보자. 먼저 CPU를 오랫동안 사용하는 프로세스가 시스템에 들어왔을 때 어떤 일이 벌어지는지 알아보겠다. 

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

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

---

예 2: 짧은 작업과 함께

좀 더 복잡한 예를 살펴보겠다. 이를 통해 MLFQ가 어떻게 SJF 와 유사하게 동작할. 수 있는지 이해할 수 있을 것이다.

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

다른 CPU 집약적 프로세스와 마찬가지로 A는 최하위 큐에서 실행 중이다. B는 시간 100에 시스템에 진입하면서 최상위 큐에 배치된다(규칙 3). B의 실행 시간은 20ms로 매우 짧기 때문에, 두번의 타입 슬라이스 안에 실행을 마친다. 즉 최하위 큐까지 내려가기 전에 종료된다. B가 끝난 후에 A가 하위 큐에서 실행을 재개한다.

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

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

---

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

다음으로 입출력 작업을 수행하는 예를 살펴보겠다. 앞서 언급한 규칙 4b에 따르면, 프로세스가 할당된 타임 슬라이스를 다 쓰기 전에 CPU를 양보하면 현재의 우선순위를 유지하게 된다.

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

프로세스 B(회색) 대회형 프로세스로 입출력 요청을 하기 전에 CPU를 1ms 동안만 사용한다. 반면 프로세스 A는 CPU를 오래 점유하는 배치 프로세스이다. 이 둘은 CPU 사용을 두고 경쟁한다.

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

---

현재 MLFQ의 문제점

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

1. 기아 상태(starvation)의 가능성: 만약 시스템에 대화형 작업이 너무 많이 존재한다면, 이들이 대부분의 CPU 시간을 차지하게 될 것이다. 그 결과 CPU를 오래 사용하는 배치 작업들은 제대로 된 CPU 시간을 할당받지 못하게 된다. 이런 시나리오에서도 긴 작업들이 어느 정도 진행될 수 있도록 보장하는 것이 바람직할 것이다.
2. 스케줄러 악용의 위험: 영리한 사용자라면 스케줄러를 자신에게 유리하게 작동하도록 프로그램을 조작할 수 있다. 일반적으로 이는 스케줄러를 속여 정해진 것보다 더 많은 CPU 시간을 할당받는 것을 의미한다. 현재의 MLFQ 알고리즘은 이런 공격에 취약하다. 예를 들어, 프로세스가 타임 슬라이스가 끝나기 직전에 불필요한 I/O 요청을 내려 CPU를 양보한다면, 계속해서 높은 우선순위 큐에 머물 수 있다. 이 트릭을 잘 활용하면, 예컨대 타임 슬라이스의 99%를 쓰고 CPU를 양보하는 식으로, 사실상 CPU를 독점할 수도 있다.
3. 시간에 따른 프로세스 특성 변화: 프로그램의 행동 양식은 시간이 지남에 따라 달라질 수 있다. CPU 집약적 작업이 어느 순간 대화형 작업으로 바뀔 수도 있다. 그러나 현재의 MLFQ로는 이런 작업이 다른 대화형 작업과 동등한 취급을 받기 어렵다.

---

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

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

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

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

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

1. 모든 프로세스가 기아 상태에 빠지지 않음을 보장한다. 최상위 큐에 있는 동안에는 다른 우선순위 높은 프로세스들과 라운드 로빈 방식으로 CPU를 나눠 쓰게 되므로, 어느 정도의 CPU 시간을 할당받을 수 있다.
2. CPU 집약적 작업이 대화형 작업으로 특성이 바뀌더라도, 우선순위 상향을 통해 스케줄러가 이 변화를 감지하고 적절히 대응할 수 있게 된다.

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

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

---

시도 3: 더 나은 시간 측정

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

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

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

왼쪽은 프로세스가 규칙 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 명령어가 대표적인데, 이를 통해 프로세스의 우선순위를 높이거나 낮출 수 있다.

---

요약

멀티 레벨 피드백 큐(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를 기본 스케줄러로 채택하고 있다.