04. 운영체제 - CPU Virtualization - MLFQ(3)

지난 게시글의 스케줄링 방식을 정리해보면 다음과 같다. 

STCF(PSJF) 스케줄러는 turn-around time 측면에서는 좋았지만 실행시간이 긴 job은 계속 뒤로 밀리며 response time 측면에서 좋지 않았다. 또한 이 방식을 사용하기 위해서는 job의 runtime이 미리 정해져있고 그걸 알아야한다는 조건이 필요한데, 이는 대부분의 경우 불가능한 조건이므로 한계가 있었다.

이를 해결한 방법으로 Round Robin(RR) 방식이 있었고, 모두 공평하게 돌아가며 실행되므로 response time 측면에서는 좋았지만 turn-around time 측면에서는 그다지 좋지 않았다. 하지만 아무런 사전 지식을 필요로 하지 않는 방식이기 때문에 꽤 좋은 방법이다.

Multi-Level Feedback Queue (MLFQ)

이제는 앞선 게시글에서 단순화된 워크로드를 위해 가정했던 모든 가정을 풀어버리고, 이러한 상황에서 turn-around time과 response time을 모두 향상시킬 수 있는 방식인 MLFQ에 대해 알아보자.

 

이 MLFQ 방식의 핵심 아이디어는 과거의 정보로부터 학습하여 미래를 예측한다는 것이다. 

1. Turn-around time을 최적화하기 위해 SJF나 STCF와 같이 더 짧은 job을 먼저 실행한다.

하지만 이제는 job의 정확한 실행시간을 알 수 없으므로 과거 정보에 근거하여 실행시간을 예측해야한다.

구체적인 방식은 아래에서 다루겠다.

2. Response time을 최소화하기 위해 Round Robin 방식을 사용한다.

우리는 이미 RR 방식이 response time을 최적화한다는 것을 알고 있다. 따라서 MLFQ에서는 이 방식을 일부 차용한다.

 

Basic Rules

MLFQ에서는 여러 개의 Queue가 있고, 각 queue는 서로 다른 priority level을 갖는다. 

실행가능한 job은 하나의 queue안에 들어있다.

 

job의 priority는 과거 CPU 점유율을 기준으로 정해진다. 즉, 과거 CPU 점유율이 높을수록 priority 가 낮아진다.

따라서 어떤 job이 자꾸 I/O 를 기다리며 CPU를 yield하면 해당 job의 priority는 높은 상태로 유지되고,

어떤 job은 CPU를 계속해서 오랜 시간동안 점유하면 priority가 낮아진다. 

1. 더 높은 priority level을 갖는 queue에 있는 job이 더 먼저 스케줄링된다.
2. 같은 priority queue에 들어있는 job들끼리는 round robin 방식으로 스케줄링된다.
3. 어떤 job이 처음 시스템에 들어오면 가장 높은 priority queue에 들어간다.
4. 어떤 job이 주어진 time slice를 모두 사용하면 priority가 하나 내려간다. (한칸 낮은 priority queue로 들어간다.)
5. 어떤 job이 주어진 time slice를 모두 사용하기 전에 CPU를 놓으면 같은 priority level에 남는다. 

 이러한 방식으로 MLFQ는 SJF 방식을 근사할 수 있다.

 

Problem 

위 Basic한 방식의 MLFQ에는 문제점이 발생할 수 있다.

• Starvation : 시스템에 너무 많은 interactive job이 있게되면 오래실행되는 job들은 CPU time을 절대 할당받지 못하게 되는 문제가 발생. 즉 highest priority에 있는 job이 너무 많아서 low priority큐에 있는 job들은 스케줄링되지 않는 문제.
• Game the scheduler : time slice를 모두 채우지 않고 CPU를 반납하면 priority가 내려가지 않는다는 것을 이용하여 99%의 time slice동안 CPU를 이용하여 I/O 를 수행하도록 의도적으로 프로그램을 짜는 것.

Priority Boost

Starvation문제를 해결하기 위해 도입할 수 있는 방법이다.

일정 시간이 지날때마다 모든 job들을 가장 높은 priority queue로 옮겨준다. 

그러면 boot period마다 적어도 한번은 실행될 수 있는 기회가 생기며 starvation 문제가 해결된다. 

Better Accounting

그럼 game the scheduler 문제는 어떻게 해결할 수 있을까?

이 문제의 원인은 job이 CPU를 얼마나 사용했는지 구체적으로 보지않고, 주어진 시간을 다 썼는지 안썼는지만 체크하기 때문에 발생하는 문제이다.

따라서 위의 4번과 5번 규칙 대신, job이 자신의 level에서 주어진 time allotment를 다썼다면 priority를 내리도록 규칙을 변경한다. (job이 CPU를 얼마나 많이 포기했는지와 상관없이 실제 사용한 시간을 기준으로 priority를 판단함)

이 규칙을 적용하기 전에는 99%의 time slice를 사용하고 CPU를 계속 포기하면 절대 priority가 내려가지 않았지만, 이 규칙을 적용하게되면 99%를 사용하고난 후 이후 스케줄링때 1%만 더 사용하면 priority가 내려가게된다.

 

Other Issues

MLFQ를 구현하려면 각 prioirty에서의 time slice 길이를 어떻게 할지를 정해야한다. 이 부분은 구현하는 사람의 디자인에 따라 달라질 수 있는 부분이므로 적절한 기준에 따라 설정해야한다.

일반적으로 더 높은 priority queue일수록 작은 time slice를 설정하고 낮은 priority일수록 더 긴 time slice를 설정한다.

낮은 priority에 있는 job일수록 자신의 순서가 돌아오는 경우가 적어지므로 한번 스케줄링되면 좀 더 오래 돌리고, 높은 priority queue에 있는 job일수록 자주 순서가 돌아오므로 너무 오래 실행하면 다른 job들이 그만큼 다같이 늦어지기 때문으로 생각된다.