이번 장에서는 Multi-Level Feedback Queue(MLFQ)라는 유명한 스케줄링 방법에 대해 배울 것이다.
MLFQ는 두 가지 문제를 해결하는데 집중한다.
첫 번째는 이전 장에서 살펴본 turnaround time의 최적화의 문제이다. 이전 장에서 강조했듯 일반적으로 작업이 완료될 때까지 얼만큼 시간이 소요될지 알 수 없기 때문에, SJF나 STCF를 현실의 OS에서 적용하기는 매우 힘들거나 불가능하다.
두 번째는 response time의 최소화 문제이다. RR 등의 알고리즘을 스케줄링에 사용할 경우 turnaround time이 과도하게 증가해 사용자가 프로세스를 실행 시킨 후의 중간 결과를 보기까지의 시간이 너무 오래 걸린다.
즉, MLFQ는 프로세스에 대한 사전 정보가 없는 상태에서 turnaround time과 response time을 최적화하기 위한 스케줄링 기법이라고 할 수 있다. 어떻게 생겼는지 한 번 천천히 뜯어보자!
8.1. MLFQ: Basic Rules
MLFQ의 구현체마다 약간씩은 다르지만, 그 기본이 되는 알고리즘을 살펴보자.
MLFQ는 각기 다른 Priority level(우선 순위)가 부여된 각기 다른 몇 개의 Queue로 구성되는데, 실행될 준비가 된 작업은 이 큐들 중 하나에 반드시 소속된다.
MLFQ는 이 우선 순위를 실행할 작업을 선택하는데 사용하는데, 여러 개의 작업 중 높은 우선 순위를 가지는 작업, 즉 더 상위의 큐에 있는 작업이 스케줄러로부터 선택받아 실행된다.
우선 순위가 부여되는 것이 작업이 아닌 큐이므로, 같은 큐에 속해 있는 작업들은 같은 우선 순위를 가지기 때문에 이때는 Round-Robin 방법으로 작업을 실행시켜 준다. (즉, 큐에 들어 있는 작업들을 정해진 시간 동안만 돌아가며 순서대로 실행시켜 준다.)
이를 아래와 같은 기본 규칙으로 정리할 수 있다.
Rule 1. 작업 A의 우선 순위가 작업 B보다 높다면, 작업 A를 실행한다. (B는 실행하지 않는다.)
Rule 2. 작업 A와 B의 우선 순위가 같다면, A와 B는 RR 방식으로 실행된다.
따라서 MLFQ 스케줄링의 핵심은 우선 순위를 정하는 것이라 할 수 있다.
즉, 이전의 FIFO, SJF, STCF, RR와 같이 경직된 규칙으로 우선 순위를 정하는게 아니라, 각 작업의 특성에 따라 동적으로 우선 순위를 부여한다는 점이 다르다.
좀 더 자세히 말하자면, CPU를 알차게 다 쓰는 작업은 우선 순위를 낮춰 다른 작업에게 CPU를 양보하도록 강제하고, 반대로 CPU의 사용량이 적은 작업은 우선 순위를 높게 유지시킴으로써 CPU가 필요해질 때 쓸만큼 쓸 수 있도록 해줄 수 있도록 한다.
엇 근데,,? 위 규칙대로라면 우선 순위가 가장 높은 Q8에 속해 있는 A, B만 RR 방식으로 계속 번갈아가며 실행되고, C는 A, B가 Q4까지 떨어질 때까지, D는 A, B, C가 Q1까지 떨어질 때까지 절대 실행되지 않을 것이다. 어쩌다 보니 C나 D가 CPU를 딱 한 번 앞에서 열심히 쓰고 뒤쪽에선 I/O만 주구장창 발생한다면 C, D 입장에선 좀 억울하지 않을까? 하나씩 해결해보자.
8.2. Attempt #1: How to Change Priority
아까 'CPU를 알차게 쓰는 작업은 우선 순위를 낮추고 그렇지 않은 작업은 우선 순위를 유지시켜준다' 정도로 뭉뚱그려서 생각해봤는데, Priority를 정하는 이 정책을 좀 더 정교하게 다듬어보자.
Rule 3. 작업이 시스템에 도착하면, 가장 높은 우선 순위(최상위 큐)로 배정된다.
Rule 4a. 작업이 실행되는 동안 주어진 time slice를 모두 사용한다면, 우선 순위가 강등된다. (바로 아래의 큐로 이동된다.)
Rule 4b. 작업이 time slice가 끝나기 전에 CPU를 포기한다면, 동일한 우선 순위를 유지한다.
Example 1: A Single Long-Runnig Job
우선 긴 실행 시간을 필요로 하는 작업부터 살펴보자. 아래 예시는 3개의 큐가 있는 스케줄러에서 시간이 지남에 따라 작업이 어떻게 진행되는지를 나타낸다.
보다시피, 작업이 시스템에 도착하면 일단 가장 우선 순위가 높은 Q2로 배정된다(Rule 3). 그 다음으로 Rule 4a에 의해 작업에게 주어진 10ms간의 time slice 동안 CPU를 열심히 쓰고 나면 Q1, Q0의 순서대로 한 단계씩 우선 순위가 강등되고, Q0로 떨어진 이후로는 더 이상 우선 순위가 떨어질 곳도 없고, 같은 큐에 속한 다른 작업 역시 없기 때문에 Q0에서 이어서 계속 실행된다.
Example 2: Along Came A Short Job
그럼 이번엔 CPU를 오래 사용하는 작업 A와, CPU를 적게 사용하는 대화형 작업(사용자의 입력을 기다리는 시간이 많은) B가 있다고 가정해보자. 아래 예시는 A가 먼저 도착해 Q2에 배정되고, Q0까지 주어진 time slice를 모두 소비하며 계속 강등되다가 100ms에 작업 B가 시스템에 도착한 상황을 보여주고 있다.
작업 B는 CPU 사용량이 많지 않은 작업이기 때문에 Q2에서 Q1에 머물러 있는 동안만 CPU를 필요로 하므로(=그보다 낮은 큐에 있는 Q0보다 우선 순위가 높음이 20ms동안 보장되므로) SJF에 근사한 성능을 낼 수 있다.
좀 더 다듬어서 얘기해보자면, 작업이 시스템에 도착했을 때 일단 우선 순위가 가장 높은 큐에 배정하는 것은 해당 작업이 CPU를 적게 사용하는, 짧은 작업이라고 가정하는 것과 같다. 진짜 빨리 끝날 작업이었다면 낮은 우선 순위의 작업과 같은 우선 순위에 도달하기 전에 작업을 마칠 것이고, 그렇지 않다면 우선 순위를 조금씩 낮추어 다른 작업들과 경쟁하도록 조정하는 것이라 할 수 있겠다.
Example 3: What about I/O?
위의 두 예시는 CPU만 사용하는 작업이었고, I/O가 발생하는 경우에는 어떤 일이 일어날까?
Rule 4b에 의하면, time slice를 모두 사용하기 전에 작업이 CPU 사용을 포기하면 해당 작업의 우선 순위는 그대로 유지된다. 이는 I/O 작업이 잦은 대화형 작업이 사용자 입력을 기다리는 것은 CPU를 사용하는 것이 아니므로, CPU가 정말 필요하게 되었을 때 높은 우선 순위에서 시작 할 수 있도록 해주기 위함이다.
앞쪽까지는 예시 1과 같고, 회색 작업(B)이 50ms쯤 시스템에 도착해 매우 짧은 시간 동안(1ms)만 CPU를 사용하고 CPU 사용을 스스로 포기(blocked)했기 때문에 Q2가 비어 그 아래의 비어 있지 않은 큐인 Q0의 A가 time slice 동안, 그리고 B가 다시 Q2에 ready 상태로 enque 되기 전까지 열심히 실행하다가 다시 B에게 1ms 동안 CPU를 다시 빼앗기는 모습이다.
이 특성이 통해 CPU는 짧게 사용하지만 I/O가 빈번한 작업이 빠르게 실행될 수 있도록 만들었다.
Problems With Our Current MLFQ
좋다. MLFQ!
MLFQ를 통해 CPU를 오래 사용해야 하는 작업과 I/O가 빈번한 대화형 작업 둘 다 어느정도 공정하게 CPU를 사용할 수 있게 되었다. 그런데 아직 다루지 않은 치명적인 결함이 있다. 뭘까?
책 중간 중간에 자꾸 생각해보고 넘기라고 하는데 마음이 급해서 한 3분 생각하고 그냥 넘기는 중
첫째로, Starvation(기아)가 발생할 수 있다.
참 직관적인 용어라고 생각하는데, 만약 "너무 많은" 대화형 작업들이 시스템에 있는 경우, 이 작업들은 계속해서 상위 큐에 머물러 있기 때문에 그 아래에 있는 CPU를 오래 사용해야 하는 작업들은 평생 CPU를 사용할 수 없을지도 모른다. 굶는거지!
둘째로, 어떤 얌체같은 프로그래머가 트릭을 써서 내가 작성한 프로그램이 CPU를 계속 사용할 수 있도록, 다시 말하자면 높은 큐에 남아 있을 수 있도록 프로그램을 재작성할 수도 있다.
예를 들어 time slice가 끝나기 직전에 앞에서 배운 yield System call이라던지, 의미 없는 아주 짧은 I/O를 적절히 사용해서 일부러 CPU를 내려 놓는다면? 지금까지의 규칙에 의하면 일단은 time slice를 모두 사용한 것이 아니기 때문에 우선 순위가 강등되지 않을 것이다.
마지막으로, 작업의 성격이 바뀌었을 때 이를 반영할 방법이 없다.
예를 들어 CPU를 초반에 많이 사용하던 작업이 나중엔 CPU를 적게 사용하는, 대화형 작업이 된다면? 이런 작업들 입장에선 좀 억울할 것이다. 우선 순위의 강등이나 유지만 있지, 다시 올려 보내는 규칙이 없기 때문에!
8.3. Attempt #2: The Priority Boost
일단 기아 상태를 해결할 수 있도록 규칙을 좀 바꿔보려고 한다. 우선 순위가 높은 I/O 위주의 작업들이 있더라도, 아주 쪼금이라도 CPU 사용량이 많아 우선 순위가 낮은 작업들이 실행될 수 있도록 하려면 어떻게 하는 것이 좋을까?
더 정교한 규칙을 세우려면 세울 수도 있겠지만, 주기적으로 모든 작업들을 가장 위에 있는 큐, 그러니까 가장 높은 우선 순위로 다시 배정(boost)해주는 방법이 가장 간단하다.
Rule 5. 일정 주기 S마다, 시스템의 모든 작업들을 최상위 큐로 옮긴다.
이 새 규칙이 도입된다면, 주기적으로 대화형 작업이든, CPU 작업이든 최상위 큐로 올라가 RR 방식으로 번갈아가며 CPU를 번갈아 사용하다가 대화형 작업은 상위 큐로, CPU 사용량이 많은 작업은 하위 큐로 이동되기 때문에 특정 작업이 기아 상태에 머물러 있는 문제가 해결될 수 있다.
말고도 처음에만 CPU를 많이 사용하고, 나중에 대화형으로 전환되는 작업 역시 훨씬 덜 억울할 것이다. 주기 S마다 항상 최상위 큐로 끌어 올려지니까! 당연히 나중에 다시 CPU를 많이 사용하는 phase로 전환된다고 해도, MLFQ의 기본적인 특성에 의해 다시 하위 수준의 큐로 내려갈테니 이 역시 문제 없다.
좀 극단적인 상황이기는 한데, 위 왼쪽 예시는 작업 A가 100ms까진 문제 없이 계속 실행되다가 짧은 I/O가 잦은 두 작업이 Q2에 계속 머물러 있어 기아 상태에 놓인 상황을 보여주고 있다.
이에 오른쪽 예시에서는 Rule 5, Boost를 추가함으로써 boosting 주기인 50ms마다 모든 작업들을 최상위 큐로 끌어 올려 작업 A가 조금이라도(최소 50ms마다) 계속 실행될 수 있도록 한 모습을 보여주고 있다.
Boost를 통해 주기적으로 기아 상태에 빠진 작업들을 위로 끌어 올려주는 것은 좋은데, 그럼 이 boosting 주기 S는 어느 정도로 길게 설정하는 것이 좋을까?
이 값이 너무 크면 CPU 사용이 잦아 우선 순위가 강등된 작업들은 더 오래 굶게 될 것이고, 너무 작으면 I/O가 잦은 대화형 작업들이 CPU 사용량에 있어서 손해를 볼 수밖에 없다.
이런 값들을 Voo-doo Constants라 하는데, 현실적으로 이런 딜레마를 '적절하게' 해결하기 위해 부두 상수를 결정하는건,, 말도 안되는 일이기 때문이다.
음 근데, 여기서 뭔가 설명이 살짝 부족한(?) 점이 있어서 짚고 넘어가려고 한다.
-
Rule 5의 '최상위 큐'(topmost)는 '모든 작업들이 속해 있는 모든 큐들 중 가장 우선순위가 높은 큐'를 의미하는 것 같다.
그도 그럴것이 starvation이 발생하는 것은 상위 큐의 작업들과 하위 큐의 작업들 사이에 좁혀지지 않는 격차(?) 같은게 있기 때문인데, 오른쪽 예시의 시점 50ms에 작업 A 밖에 없는 상황에서 굳이 A를 Q2까지 끌어 올릴 필요가 없다. 끌어 올린다는 것도 결국은 다 비용일 테니까.
마찬가지로 이후에 시스템에 들어온 두 대화형 작업들이 Q1에서 RR로 계속 CPU를 점유하고 있었다고 하더라도, Q1 위의 다른 큐에 작업이 없는 한 모든 작업들을 굳이 Q2까지 끌어 올려줄 필요 없이 작업을 가지고 있는 큐들 중 가장 우선 순위가 높은 Q1까지만 작업들을 끌어 올려 주면 된다. -
이건 이유를 잘 모르겠는데, 우측 예시의 100~200ms 동안 분명 A는 주어진 time slice를 모두 소비했으므로 우선 순위가 강등되어야 하는데도 우선 순위가 그대로 유지 되고 있다.
위의 설명이 부족한 부분과, 문제(?) 두 가지를 보충 및 해결하면 아래와 같은 상황이 발생할 수 있을 것 같다.
일단 초록색 A가 가장 먼저 시스템에 도달해 실행되고 있다가 Q0까지 강등된 것은 같고, 이번엔 파란색 B와 빨간색 C 작업이 앞에서 주어진 time slice를 쓰는 바람에 Q1로 강등되었다고 가정해 보겠다. 그럼 이 시점에는 초록색 작업 A가 Q0까지 강등된 상황이기 때문에 어느 정도 굶고 있었겠지?
이때 시점 2t에서 boost가 발생해 시스템에 존재하는 모든 작업들이 들어 있는 큐 중 가장 높은 우선 순위의 큐인 Q1으로 A가 끌어 올려지고, 작업 B, C가 실행된 다음 이어서 작업 A가 Q1에서 RR에 의해 실행된 다음, 주어진 time slice를 모두 사용했기 때문에 그 아래 우선 순위인 Q0로 강등되어 그 다음 boost가 발생하기 이전인 3t 이후로는 작업 B, C만 계속해서 실행되고 있는 상황을 묘사했다. 그림 참 못그린다!
8.4. Attempt #3: Better Accounting
Boosting을 통해 기아 문제는 해결했지만, 문제가 아직 하나 남아 있다. CPU를 쓸만큼 쓰다가, time slice가 끝나기 직전에 아주 잠깐 I/O 등을 통해 CPU 사용권을 내려 놓는 꼼수를 쓰는 프로그램은 어떻게 처리해야 할까?
Rule 4a, 4b로 인해 이런 허점이 발생한 것인데, 이를 아래와 같이 고쳐보자.
Rule 4. 작업이 속해 있는 우선 순위 수준 안에서의 주어진 시간 할당량(time allotment)을 모두 사용하면, (얼만큼 CPU 사용을 포기했는지와는 상관 없이) 우선 순위가 강등된다. (그 아래의 큐로 이동된다.)
그렇다. 우선 순위 강등의 조건을 일회성의 time slice 전체를 사용했는지가 아니라 '주어진 절대적인 시간(time allotment)'을 모두 사용했는지로 바꿔준 것이다. 차이가 살짝 미묘할 수 있는데, 아래 예시를 보며 천천히 이해해보자.
느낌을 강조하려고 하다 보니 아예 회색 작업 B가 CPU 사용을 포기하는 모습이 Q2에선 안보이는데, 그 아래 Q0에서 50~200ms 구간에서 검은색 작업 A가 아주 짧게 실행되다가 그보다 상대적으로 긴 시간동안 다시 우선 순위가 높은 작업 B에게 CPU 사용권을 넘겨주는 상황이 왼쪽에 묘사되어 있다.
반면 Rule 4a, 4b를 통합/개정한 우측의 경우 time slice를 모두 소진했을 때 우선 순위가 강등되는 것이 아니라, 각각의 작업에게 주어진 10ms 정도의 time allotment가 모두 소진되었을 때 우선 순위를 강등하는 방법(Gaming Tolerance)이 적용되어 약 120ms까지는 B가 Q2, Q1를 거쳐 A보다는 우선 순위가 낮기 때문에 얌체처럼 이득을 볼 수 있지만, 이후로는 A와 동일하게 Q0에 소속되어 있기 때문에 RR 방식으로 사이좋게 각각 time allotment를 소진하기 때문에 A가 손해를 보지 않고 있다.
자세히 살펴보면 Q0에서 B의 빈 틈, 그러니까 CPU를 사용하지 않는 시점이 time allotment 10ms 안에서도 뒤쪽으로 조금씩 밀리고 있는데, 이를 통해 주기적으로 B가 고의로 짧은 I/O를 발생시키고 있었음을 확인할 수 있다.
8.5. Tuning MLFQ And Other Issues
기아 상태와 얌체 프로그램에 대한 해결책은 모두 해결 되었다. 말고도 몇 가지 문제점이 있을 수 있는데, 스케줄러를 매개변수화(Parameterize)할 수는 없는 걸까? 예를 들면,,
- MLFQ에는 몇 개의 큐가 있어야 하는가?
- 큐 별로 time slice는 얼마나 길게 주어야 하는가?
- 작업의 특성이 바뀜에 따라 발생하는 기아 상태를 해결하기 위해 boosting은 얼마나 자주 실행되어야 하는가?
정도가 있겠다. 아까 얘기했듯이 이런 Voo-doo constants를 다루는 것은 정말 어려운 작업이기 때문에,, workload를 겪어 가며 어느 부분에서 불균형이 발생할 수 있을지 조정해나가는 것이 필요하다.
예를 들어 대부분의 MLFQ는 위와 같이 큐마다 다른 길이의 time slice를 주는데, 높은 우선 순위의 큐의 경우 의도한 대로라면 대화형 작업 등의 CPU 사용 시간이 짧은 작업들이 주로 위치해 있을 것이므로 짧은 time slice로 설정하고, 낮은 우선 순위의 큐의 경우 상대적으로 긴 시간 동안 CPU를 사용할 것이므로 time slice를 길게 준다던지,, 하는 식으로 조정할 수도 있다.
특히 Solaris와 같은 운영 체제에서는 이런 값들의 매개 변수화를 좀 쉽게 할 수 있도록 지원해주기도 하고, 이외에도 다른 운영 체제들은 책에서 소개된 대로 딱딱하고, 뭉텅뭉텅 정해진 규칙이 아니라 Decay-Usage 알고리즘이나 정교한 수학 공식을 사용해 이런 voo-doo contants들을 제어하는 등 좀 더 고수준의 방법들을 사용한다고 한다.
마무리
MLFQ의 최종 규칙은 다음과 같다.
Rule 1. 작업 A의 우선 순위가 작업 B보다 높다면, 작업 A를 실행한다. (B는 실행하지 않는다.)
Rule 2. 작업 A와 B의 우선 순위가 같다면, A와 B는 RR 방식으로 실행된다.
Rule 3. 작업이 시스템에 도착하면, 가장 높은 우선 순위(최상위 큐)로 배정된다.
Rule 4. 작업이 속해 있는 우선 순위 수준 안에서의 주어진 시간 할당량(time allotment)을 모두 사용하면, (얼만큼 CPU 사용을 포기했는지와는 상관 없이) 우선 순위가 강등된다. (그 아래의 큐로 이동된다.)
Rule 5. 일정 주기 S마다, 시스템의 모든 작업들을 최상위 큐로 옮긴다.
아름답다. 만족스럽다!
이제 CPU Virtualization 관련해서는 Proportional Share만 남았다. 오늘 안에 깔끔하게 다 정리해봐야지.
