[OS] Virtualization #3.Multi-level Feedback Queue
현대의 대부분의 OS들은 Round-Robin Algorithm의 변형 형태의 Algorithm을 통해 프로세스들에게 CPU를 공평하게 분배하려 한다. [OS] Virtualization #2.CPU Scheduling
대부분의 프로세스들이 I/O 작업을 더 많이 필요로 하는 I/O-bound job이긴 하지만, 여전히 CPU의 처리를 더 많이 필요로 하는 CPU-bound job 또한 있기 마련이다.
I/O-bound job은 Response time이 중요하기 때문에 짧은 Time Slice를 가지는 Round-Robin이 꽤나 효과적인 반면,
CPU-bound job은 Turnaround time이 더 중시되어서 상대적으로 긴 Time Slice를 가지는 Round-Robin algorithm이 더 효과적이다.
따라서 하나의 Time Slice만을 두고 프로세스를 운용하면 프로세스의 효율적 분배에 한계가 있을 수밖에 없다.
그러한 맥락에서 여러개의 Time Slice를 가지는 Multi-level Feedback Queue라는 아이디어가 발생하였다.
이번 포스팅은 Multi-level Feedback Queue에 대해 작성한다.
INDEX
1. Multiple Queues
Multi-level Feedback Queue는 Round-Robin Algorithm이 적용되는, 다른 Time Slice를 가지는 여러개의 Queues를 배치하는 방법이다.
아래 Multi-level Feedback Queue를 그림으로 나타내었다.
그림에 8개의 Quque가 존재하는데, 위로 갈수록 우선 순위가 높은 Queue이고, 존재하는 여러개의 Queue들간 적용되는 규칙은 다음과 같다.
-
우선 순위가 높은 Queue에 있는 job이 먼저 실행된다.
-
우선 순위가 같은 Queue의 job들간에는 Round-Robin Algorithm을 적용한다.
위 규칙에 따라 job A, B간에는 Round Robin이 적용되며, A/B가 C,D보다는 항상 먼저 CPU Scheduling된다.
2. How the Scheduler sets Priorities
그렇다면 각 job들의 우선 순위는 어떠한 방식으로 설정될까?
늘 그렇듯 유저에게 자율로 맡기는 방법이 있겠으나, 유저가 자신이 실행하려는 job의 우선 순위만 높게 실행할 가능성이 충분하므로 그러한 방식을 취하지는 않는다.
따라서 OS는 Queue에 존재하는 job이 어떠한 경향성을 갖는지 관찰하고, 그 경향성에 따라 job의 우선 순위를 적절히 조절한다.
우선 순위 조정 규칙은 아래와 같다.
-
Job이 system에 진입할 때, 최상위 우선 순위를 가짐
-
Time Slice가 모두 소요될 때까지 job이 CPU를 점유하고 있으면(=CPU-bound) 우선 순위를 감소시킴
-
Time Slice가 모두 소요되기 전에 job이 CPU 점유를 포기하면(=I/O-bound) 우선 순위를 동일하게 유지
위 규칙에 따라 새로운 CPU-bound job이 시스템에 진입했을 때 job은 아래와 같이 행동한다.
맨 처음 job이 시스템에 진입했을 때에는 최상위 우선순위인 Q2에 위치하다가, Time Slice를 계속해서 소모하면 더 낮은 우선 순위의 Queue로 이동한다.
아직까지 또 다른 job이 시스템에 없으므로, 계속해서 CPU를 점유하고 있다가 새로운 job이 들어오면 아래와 같은 양상을 보인다.
새로운 job이 들어오면 해당 job은 최상위 우선 순위를 가지므로, 위와 같이 CPU를 먼저 할당받고 다시 우선 순위가 하락할 때까지 CPU를 점유하다가 job이 Q0에 위치하면 Round-Robin Algorithm 방식으로 CPU Scheduling된다.
만약 파란색 job이 I/O bound job이어서 Time Slice를 모두 소진하기 전에 CPU를 포기하는 경향이 있으면 해당 job은 아래와 같이 계속해서 높은 우선 순위를 점유한다.
3. Rule Problems
위와 같이 다계층 Round-Robin Queue 형태의 기법을 취하면 I/O bound job과 CPU bound job을 확실히 분리할 수 있지만, 발생할 수 있는 몇 가지의 문제점들이 있다.
대표적으로 Starvation, Gaming the Scheduler, Changing Behavior problems를 소개한다.
먼저 Starvation(굶주림) 현상은 시스템에 아주 많은 I/O bound job이 존재하여 CPU bound job이 상대적 우선 순위에 밀려 CPU 할당을 받지 못하는 상태에 빠지는 것이다.
Gaming the Scheduler란, 프로그램을 제작한 유저가 Time Slice가 종료되기 직전에 일부러 의미없는 I/O operation을 실행하여 CPU 우선 순위를 고의적으로 유지하는 행위를 말한다.
마지막으로 Changing Behavior는 처음에 CPU bound job으로 시작했다가, 이후에 I/O bound job으로 전환되는 process는 자신이 가져야할 우선 순위와 다른 우선 순위를 가지게 되는 경우이다.
이러한 문제들의 해결은 모두 Multi-level Feedback Queue의 존재 이유에 영향을 미치므로, 그것의 기능을 온전히 동작하기 위해 꼭 해결해주어야 한다.
4. Solutions
이와 같은 문제들을 해결하기 위해, 시스템은 모든 프로세스의 우선 순위를 일정 주기마다 처음의 상태인 최상위 우선 순위로 갱신하는 Priority Boost 기법을 사용한다.
Priority Boost 기법을 적용한 시스템에서 Starvation 문제는 아래와 같이 해결된다.
여전히 I/O bound job이 더 높은 우선 순위를 유지하지만, 일정 주기마다 CPU bound job 또한 CPU를 점유할 수 있다.
Changing Behavior의 문제 또한 이 방식으로 하여금 변화된 적정 우선 순위를 가지게 될 것을 예상해볼 수 있다.
Gaming the Scheduler의 문제를 해결하기 위해서는 job의 우선 순위를 변화시키는 방식에 약간의 개선이 필요하다.
기존에는 Process가 CPU를 점유한 시간이 Scheduling될 때마다 계속해서 초기화 되었으므로 일부러 I/O operation을 실행하는 것이 우선 순위 유지에 큰 도움을 주었다.
따라서 이 부분을 개선하여, CPU를 점유한 시간을 매번 초기화하는 것이 아니라 CPU 점유 누적 시간을 기준으로 우선 순위를 설정해준다면 Priority Boost와 함께 작동하여 CPU를 덜 점유한 프로세스에게 CPU를 더 많이 배분하여 공평한 CPU 분배가 가능하다.
5. Specific Figures
Job의 경향성에 따라 그들의 우선 순위를 조정하여 CPU를 할당받는 방법론적인 이야기는 이만하고, 구체적으로 어느정도 수치를 가지고 CPU Scheduling이 운영되는지 알아보면 좋을 듯하다.
지금은 Sun Microsystems사가 Oracle에 인수되어 운영되지 않는 OS인 Solaris OS를 기준으로 보면
Priority Boost는 1초마다 실행되어 Starvation과 Changing Behavior 문제를 해결하였다.
또한 Multiple Queue 각각이 다른 Time Slice를 가질텐데, 제일 높은 우선 순위를 가지는 Queue의 경우 20ms의 Time Slice를 갖고 최하위 우선 순위를 가지는 Queue의 경우 몇백ms의 Time Slice를 가진다.
이유는 I/O bound job은 더 상위 우선 순위를 갖는 경향을 보이고, CPU bound job은 하위 우선 순위를 갖는 경향을 보일텐데, I/O bound job이 중시하는 것은 Response time, CPU bound job이 중시하는 것은 Turnaround time이기 때문에 높은 우선순위의 Queue는 Time Slice를 크게 설정하고, 낮은 우선순위의 Queue는 Time Slice를 작게 설정한다.