[운영체제] 5. Process-Scheduling / MLFQ(Multi-level Feedback Queue)

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

CPU Scheduling Policies

 

지난 포스팅에서 프로세스를 실행하는 low-level에서의 매커니즘을 알아봤다면, 이번 파트에선 OS 스케줄러가 프로세스 실행에 사용하는 high-level polices를 알아보겠다.

스케줄링 policy를 비교하는 기준(scheduling metric)은 다음과 같다.

Turnaround time = Completion time - arrival time

Response time = First Run time - arrival time

Fairness = 완료 시간이 얼마나 비슷한가

Throughput = 단위 시간당 완료된 프로세스 수

Deadline = Turnaround time이 Deadline time보다 작아야 함

 

이러한 작업들은 관점에 따라 중요도가 달라진다. Turnaround time의 경우 response time과 trade off 관계이므로 두 metric 간의 밸런스를 잡는 것이 중요하다고 볼 수 있다.

 

스케줄링 policy의 이해를 돕기 위해 몇가지 가정을 해보겠다. (Workload assumption)

 

- 모든 작업은 한번 실행될 때 실행시간 동일

- 모든 작업은 동시에 도착

- 작업이 시작되면 끝날때까지 실행

- 모든 작업은 CPU에서만 동작. I/O 발생시키지 않음

- 모든 작업의 실행시간을 알고 있음

 

이제부터 이같은 비현실적인 가정을 하나씩 제거하며 policy를 세워보겠다.

 

- FIFO (First In First Out)

Queue와 같은 원리를 가진 스케줄링 기법이다. 이 방법은 시간이 많이 걸리는 작업이 먼저 수행되면, 나중에 도착한 시간이 적게 걸리는 일들도 훨씬 늦게 시작하고 끝마친다. 이를 convoy effect라 한다.

 

-SJF (Shortest Job First)

convoy effect를 해결하기 위해 수행시간이 짧은 애들부터 실행하는 스케줄링 기법이다. 작업이 동일한 시간에 도착했을 때 Turnaround time이 FIFO보다 현저하게 줄어든다. 

하지만 이것은 모든 작업이 동일한 시간에 도착했을 때의 얘기고, 현실은 그렇지 않다.

수행시간이 짧은 프로세스가 조금이라도 늦게 도착하면 오래 걸리는 프로세스가 끝날때까지 기다려야한다.

 

-STCF (Shortest Time-to-Complition First)

SJF의 단점을 보완하기 위해 '작업이 시작되면 끝날때까지 실행한다'는 가정을 없애보겠다.

스케줄러에 timer interrupt와 context switch를 통해 preempt(선점)을 추가한다. 즉, 프로세스 진행 중 다른 프로세스를 수행할 수 있다는 뜻이다.  이렇게 한다면 Turnaround time을 획기적으로 줄일 수 있다.

나중에 설명하겠지만, 치명적인 단점은 바로 프로세스의 수행시간을 알고 있어야 가능한 방법이라는 점이다.

 

여기까지는 Turnaround time을 가장 중요한 metric으로 여겼다. 하지만 현대 컴퓨터는 interactive system이 많다.

키보드와 마우스의 I/O만 생각하더라도 컴퓨터의 반응이 조금이라도 늦다면 사용자 경험에 큰 반감이 생길 것이다.

따라서 CPU scheduling은 Turnaround time과 response time의 balance를 맞춰야 한다.

이 Response time을 줄이는 방법이 바로 RR이다.

 

-RR (Round Robin)

Round Robin은 작업이 끝날 때까지 수행하는 것이 아니라, 정해진 time slice만큼만 수행한다.

time slice란 timer interrupt의 배수인 변수로, 지정한 time slice마다 context switch를 수행한다.

모든 작업을 time slice만큼 잘게 나누어 수행하게 된다면, First run time이 무척 빨라지므로 Response time도 굉장히 줄어든다. 하지만 역설적으로 모든 작업이 나뉘어져 늦게 끝나기때문에, 작업이 끝나는 시간과 관련있는 Turnaround time은 매우 길어진다. 

 

-Incorporating I/O

처음 가정했던 5가지 중 "모든 작업은 CPU에서 동작하며 I/O를 수행하지 않는다"는 가정이 있었다. 이전 포스팅에서 말한 Process state에 따라, 프로세스가 I/O를 수행하면 CPU가 다른 프로세스를 수행하도록 Blocked 상태로 만든다. I/O가 완료되면 다시 Ready 상태가 되야 한다. 모든 process state는 PCB에 저장된다.

 

Multi-Level Feedback Queue 

 

 "모든 작업의 수행 시간을 알고 있다"는 마지막 가정이 남았다. 위의 SJF, STCF 등은 프로세스의 수행시간을 알아야 사용할 수 있다. 그렇지 않고 RR을 쓰면 Turnaround time이 너무 안좋아진다. 현실에선 프로세스 수행 시간을 정확히 알 수 없기에, interactive job(ex. I/O와 같은 상호작용)을 위한 response time을 최소화하고 batch job(ex. 상호작용이 없는 job)을 위한 turnaround time을 최적화하는 방향으로 스케줄링이 이루어져야 한다. 이를 위해 고안된 것이 MLFQ(Multi-level Feedback Queue) 스케줄링이다. 실제로 solaris OS에서 활용된 스케줄링 기법이다.

 

MLFQ를 한국말로 하면 다단계 피드백 큐, 여러개의 큐가 서로 다른 단계를 가진다는 뜻이다.  이를 잘 상기하며 더욱 자세히 살펴보자. MLFQ는 아래와 같은 특징이 있다.

- 여러 개의 큐를 가지고 있다.

- 각 큐는 서로 다른 우선순위를 갖는다.

- Ready 상태인 모든 프로세스들은 어떤 큐 안에 들어있다.

 

MLFQ는 동일한 큐에 여러개의 작업이 있을땐 RR로 수행하며, 큐의 우선순위가 높은 프로세스들을 먼저 수행한다. 이때 우선순위를 설정하는 방법이 MLFQ 스케줄링의 핵심이다.

MLFQ에 Feedback이 들어간 이유는 이 우선순위를 결정하는 과정이 과거의 실행에 따라 변하기 때문이다.

예를 들면, 어떤 작업이 I/O를 계속  발생시킨다면 MLFQ가 이를 대화형 프로그램이라 판단하고 우선순위를 높게 설정한다. 그러다 I/O를 멈추고 batch job만 수행한다면 우선순위를 낮춘다. 이제 구체적으로 우선순위를 정하는 규칙들을 살펴보자.

 

1. 우선순위가 높은 프로세스를 먼저 수행한다.

2. 작업들이 우선순위가 같으면 RR로 수행한다.

3. 새로운 프로세스가 시스템에 들어가면 가장 높은 우선순위를 부여한다.

4a. 작업이 실행될 때 time slice를 모두 사용하면 우선순위를 감소시킨다.

4b. 작업이 실행될 때 time slice를 모두 사용하지 않고 CPU를 포기(I/O)하면 우선순위를 유지한다.

 

여기까지의 규칙들은 몇가지 문제가 발생한다.

 

- 프로세스가 time slice가 끝나기 직전에만 I/O를 요청하여 우선순위를 유지하는 등 스케줄러를 속일 수 있음. 

=> 4a, 4b를 통합하여 "4. 작업은 모든 우선순위에서 주어진 time slice를 모두 사용하면 우선순위가 감소한다."

는 규칙을 통해 해결

 

- Starvation(=여러개의 interactive job이 지속될경우 batch job은 오랜 시간동안 cpu를 가져갈 수 없음)

- 프로세스가 한참 수행한 뒤에 I/O가 발생될 때 우선순위를 높일 수 없음.

위 문제를 해결하기 위한 5번 규칙

"5. 일정 시간 후 시스템의 모든 작업을 우선순위가 가장 높은 큐로 이동한다. (Priority Boost)"

이를 통해 위 문제들을 해결할 수 있다. 하지만 최적화에 대한 고민이 남는다.

MLFQ에서 큐의 개수를 몇개로 해야할까? 큐마다 time slice는 어떻게 해야할까?

Priority Boost의 일정 시간은 어떻게 정해야하는가? 

 

time slice의 경우 우선순위가 높은 큐일수록 interactive job일 확률이 높으니 time slice를 줄이는 방식은 꽤 유효하다고 한다.  그 외 다른 문제에서 MLFQ를 튜닝하는 것은 정답이 있지 않고, 어려운 문제다. 설계 시 복잡도나 context switch에서의 overhead등도 모두 고려해야한다.