[OS/OSTEP] 08.CPU-sched-mlfq : 멀티 레벨 피드백 큐(MLFQ) #5

08.CPU-sched-mlfq

# 시작하며

 멀티레벨피드백큐(Multi-level Feedback Queue, MLFQ)는 기본적으로 두가지 문제를 해결하기 위해 고안 됐다. 첫번째는 짧은 작업을 먼저 실행시켜 반환 시간을 최적화 하려는 것이다. SJF와 STCF도 같은 목적을 띄지만 실행되는 작업시간을 알아야하지만, 그것을 아는 것은 불가능하다. 두번째로는 응답이 빨라보이도록 하는 것이다. RR은 응답시간을 최적화 시켜 응답시간은 매우 빠르지만 반대로 반환시간이 매우 최악이었다. 프로세스의 실행시간에 대한 정보가 없이 이러한 조건을 만족시키는 스케줄러를 고안해보는 것이다. 

 즉 작업의 대한 정보 없이 반환시간도 빠르고, 응답시간도 빠른 스케줄링을 해보자는 것이다.

 

# MLFQ : 기본 규칙

 MLFQ는 우선순위를 가지는 여러개의 큐를 가진다. 큐가 각각의 계층으로 나누어 져 있다는 뜻이다. 그리고 가장 우선순위가 높은 큐부터 작업을 처리한다. MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아닌 작업의 특성에 따라 동적으로 우선순위를 부여한다. 예를 들면, 반복적으로 키보드 I/O를 기라디면서 CPU를 양보하면 높은 우선순위 큐를 부여하고, 오랫동안 긴시간의 CPU를 점유하고 있으면 낮은 우선순위를 부여하는 것이다. 미래의 정보를 얻을 수 없듯이 이러한 정보는 작업이 진행되는 동안에 얻어오는 것이다.

 

 그렇다면 가장 높은 우선순위 큐에 있는 두 작업이 계속해서 반복(RR) 된다면 그 아래 우선순위큐에 있는 작업은 실행되지 않을 것이다. 이제 작업들에게 우선순위를 아래로 내려줄 수 있어야한다.

 

# 시도 1 : 우선순위 변경

 바로 위에서 설명 했듯 큐의 조정이 일어나지 않는다면 A,B의 작업이 종료될때까지 실행될 것이다.우선순위 큐를 아래로 내리기 위해 추가적인 규칙을 부여해야한다.

4a 규칙은 우선순위를 하향시킬 수 있는 새로운 규칙이다. 이제 이 규칙이 어떻게 적용되는지 살펴보자.

## 한개의 긴 실행 시간을 가진 작업, 우선순위가 낮아짐

 규칙 3에 의해 가장 높은 우선순위를 부여받은 후, 정해진 time slice(10)을 다 사용하면 큐를 한단계 하향 시킨다. 거기서도 다 사용하면 또 하향 시키고, 가장 낮은 큐에서 더 내려갈 곳이 없으므로 계속 실행된다. 물론 여기서 의문이 생길 수 도 있다. 일단은 넘어가자.. 난 Q0에서에 대해서 의문이 남었었다.

 

## 짧은 작업 + 긴작업 : SJF에 근접하는 MLFQ

 대화형 작업은 B와 같이 짧게 짧게 일어나는 작업이다. A는 오랜 시간이 걸리는 작이다. SJF알고리즘은 짧은 작업을 우선적으로 처리했다. Q2가 긴지 짧은지는 모르지만 일단 처음 들어오면 짧다고 가정하고 실행시키면서 큐를 낮춰가는 것이다. B는 운좋게도 짧은 작업이었다. 그러면 Q0에 도착하기전 Q1에서 작업을 마지막으로 실행된다. SJF도 똑같은 방식으로 실행 했을 것이다.

 마치 무죄추정 원칙처럼 일단 짧다고 가정을 시키고, 짧지 않다는 것은 실행됨에 따라서 증명 된다. B는 억울할뻔 한거다..ㅎ

 

## 입출력 작업이 추가된다면?

  규칙 4b에 의거하여, 타임 슬라이스(time slice)를 모두 소진하기 전에 프로세서를 양도( 입출력 I/O )하게 되면 같은 우선순위를 가지게 된다. 하향되지 않고 유지되는 것이다. 

위 그림과 같이, B는 타임 슬라이스를 소모하기전에 I/O가 발생했다. B는 대기(Blocked)상태로 변하고 A는 그사이를 이용해서 CPU를 사용한다. 그리고 I/O가 끝나면 4b의 규칙에따라 우선순위가 유지된다. 이 과정을 반복한다. 공부했던거와 같이 효율적으로 사용하는 것처럼 보인다. B가 대화형 작업( 사용자와 입력을 주고 받는 ) 이라면 MLFQ는 대화형 작업을 빨리 실행시킨다는 목표에 근접한다.

### 문제점

현재까지의 상황으로는 MLFQ의 문제점이 발생한다.

첫번째는, 시스템에 너무 많은 대화형 프로세스가 존재하면 자기들끼리 다 해먹을 거다. 예를 들면, B의 I/O시간동안 활동할수 있는 C라는 대화형 작업이 존재한다면 그시간동안 C가 쓰고, 다시 B가 쓰고 지들끼리 다해먹어서 A는 불쌍하게도 한번도 실행되지 못할 것이다. 이러한 상황을 기아 상태(starvation)이라고 한다.

stravation이 발생하는 상황

둘째는, 정말 똑똑한 사용자라면 또는 개발자라면, 타임 슬라이스 시간을 계산하여 나의 time slice가 끝나기 직전에 아무런 쓸데 없는 I/O요청을 줌으로써 우선순위를 유지하려고 할 것이다. 그러면 CPU를 공평하게 사용하지 않고 독점하게 된다. 극단적이게 99.99%의 타임슬라이스를 사용하고 I/O요청을 주는 것이다.

셋째는, 처음에는 CPU위주의 긴시간이 걸리는 작업이여서 맨 밑 큐(그림에서는 Q0)로 내려왔지만 일정 시간이 지난 후에는 대화형 작업으로 변하는 작업이라면, 이미 맨 밑에 있기 때문에 대화형 작업의 특성(빠르게 반응)을 이용하지 못할 것이다. 맞는 예가 될지 모르겠지만 게임이 시작하기전 시네마틱 영상이나 스토리를 보고 있다가 게임이 시작되면 엄청난 마우스 클릭과 키보드입력이 일어날 것이다.

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

 위의 문제를 보완하기 위한 가장 좋은 방법은 작업을 맨위로 올려주는 것이다. 이것을 상향 조정(boost)라고 하는데, 어떤식으로 구현하기 나름이고 이 교재에서는 간단히 모두 최상위 큐로 올려 보내는 규칙을 세운다.

그렇다면 Q0에 있는 작업만을 최상위로 올리는 것일까?

새로운 규칙에 의거하여 부스팅 시킨다.

새롭게 생긴 규칙5에 의거하여 모든 작업을 부스팅 시킨다. 이 간단한 규칙5는 위에서 생긴 세가지 문제중 두가지를 해결한다. 첫번째로는 기아 상태(starvation)현상을 막아, 어찌됐든 부스팅 주기에 맞춰서 한번은 실행이 될 수 있다. 두번째는 작업의 특성이 일반적인 긴 작업에서 대화형 작업으로 바뀔 경우, 그 바뀌고 난 후 부스팅이 된다면 대화형의 특성을 그때부터 적용받을 수 있다.

 이 부스팅을 결정짓는 시간 S는 사실 마법과 같은 시간이라 정확히 할 수 없다고 한다. 이걸 부두 상수(voo-doo constrants)라고 교재에서는 표현했다.

# 시도 3: 새로운 시간측정법 추가

세가지 문제중 두가지 문제를 해결했다. 이제 99.99%까지 사용하고 I/O를 발동시키는 악질의 유저 또는 프로세스를 해결하면 된다. 근데 이건 누굴 탓 할 수 없다. 왜냐하면 우리가 세운 규칙을 교묘히 이용했기 때문이다.

위 4a와 4b를 통해서 최우선 순위 큐에 남아 있을 수 있었기 때문에 두 규칙을 합쳐 새로운 규칙으로 재정의한다.

이제 I/O를 할당받은것과 상관없이 해당 우선순위 큐에서 정의된 총 사용시간을 다 사용하게 된다면 아래로 강등되는 것이다.

 

# MLFQ가 신경써줘야 할 것들

 MLFQ스케줄링에는 최적의 스케줄링을 제공하기 위해서는 또 많은 쟁점을 해결해야한다. 예를들면 몇개의 큐가 존재해야하는지, 큐당 타임슬라이스 값을 어떻게 하는지, 얼마나 자주 부스팅을 해줘야하는지 등등 말이다. 정답은 충분히 조정하면서 균형점을 찾아가는 것이다. 당연하고도 가장 어렵다.

 

# 정리

MLFQ는 반환시간과 응답시간을 모두 최적화 시킨다. 또 공정하게 실행하고 가장 낮은 우선순위에 있는 작업이 실행이 안되는것을 방지하기 위해 부스팅을하여 조금이라도 실행되게한다. Windows 운영체제를 포함한 많은 시스템이 기본 스케줄러로 MLFQ를 사용한다고 한다.

 

# 끝내며

 규칙 4a와 4b를 4로 수정함으로써 대화형작업에 대한 이점이 없어질거 같다는 의문이 남았었는데, 교재를 유심히 읽어보니까 "짧게 실행되는 대화형 작업에 대해서는 우수한 전반적인 성능을 제공한다" 라고 했다. 결국 밑으로 내려가니까..! 전반적인 성능이 었다..