Scheduling: The Multi-Level Feedback Queue (MLFQ)

Multi-Level Feedback Queue의 목적

Multi-Level Feedback Queue (MLFQ)는 두가지의 목적을 갖는다.

 

1. turnaround time(반환시간) 최적화

반환시간 기준에 있어 SJF/STCF에 근접한 성능을 만드려고 한다.

기존의 SJF/STCF는 프로그램의 실행전에 그 실행시간을 스케줄러가 미리 알아야 한다는 현실적인 제약사항이 있었다. 이것을 극복하기 위해 MLFQ는 실제 미래는 모르지만 일단 작고 짧은 job에게 우선순위를 부여하는 방식을 시도하게 된다.

 

2. response time(반응시간) 최소화

반응시간 기준에 있어 Round Robin에 근접한 공평성을 구현하려고 한다.

Round Robin은 반응시간은 좋지만 반환시간에 있어서는 매우 나쁘다. MLFQ는 이러한 단점을 보완하려고 시도한다.

 

 

MLFQ의 기본 원칙

mlfq의 큐 예시

 

상단에 있을수록 우선순위가 높은 큐이다. 우선순위가 높은 큐일수록 먼저 실행되고, 위에 있는 큐가 다 비게 되면 아래에 있는 큐가 스케줄된다. 만약 같은 큐에 위치한다면, 즉 우선순위가 같다면 Round Robin으로 실행된다. (time slicing, time sharing을 통해서 공평하게 실행되게 한다.)

일단 MLFQ의 목적은 짧은 job에게 우선순위를 주는것이다. 그런데 job이 시스템에 처음 들어올때는 이것이 짧은지 긴지 알 수가 없다. 따라서 타이머를 걸어서 time slice를 초과할때까지 job이 계속 실행되면 long job, 그렇지 않고 time slice가 끝나기 전에 스스로 cpu를 반납하면(예를 들어 io요청을 통해 block될때) short job이라고 판단한다.

만약 들어온 job이 short job으로 판단되면 현재의 우선순위에 계속 머무를 수 있지만, time slice를 다 써버려서 long job으로 판단되면 현재보다 아래 우선순위로 강등당하게 된다. 

위 그래프는 왼쪽부터 각각 job이 하나일 경우, job이 두개일 경우, job 두개중 하나가 io요청이 섞여있는 job일 경우를 표현한 것이다.

여기서 제일 오른쪽 그래프의 경우, 두번째 job인 B는 io요청이 많이 일어나는 io bound job으로서 CPU를 짧게 사용한다. 그렇기 때문에 time out이 일어나지 않아서 계속 Q2라는 최우선순위 큐에 머무를 수 있는 것이다.

이렇게 time out이 일어나지 않는 interactive job은 우선순위를 강등당하지 않고 필요할 때 계속 cpu를 사용할 수가 있다.

 

 

Problems with our current MLFQ

그러나 multi level feedback queue에도 잠재적인 문제점이 존재한다. 과연 어떤것일까? 그리고 어떤 방법을 통해 이 문제점을 개선할 수 있을까?

 

1. Starvation 현상 > Priority Boost로 해결

왼쪽이 starvation, 오른쪽이 priority boost

우선순위가 높은 큐가 다 비어야만 아래 큐의 job이 실행되기 때문에, 아래 큐는 굶어야하는 일이 생길 수 있다. 이것을 말 그대로 starvation현상이라고 한다.

이것은 Priority Boost를 통해 해결할 수 있는데, 이는 주기적으로 특정시간(S)이 지나면 모든 job을 top priority queue로 올려주는 방법이다.

같은 priority queue내에서는 round robin으로 실행되기 때문에, 실행될 수 있는 기회가 주기적으로 모든 job에게 공평하게 주어진다.

VOO-DOO Constant

starvation의 해결법으로 priority boost가 있지만, 문제는 그 기준시간 S를 어떻게 잡느냐이다! 여기에는 변수가 매우 다양하기 때문에 정말 적당히, 잘 잡아야 한다! 때문에 이 기준시간을 잘 정하지 못하면 실질적으로 효과가 없을 수도 있다.
또한, boost의 기준을 단순한 시간이 아니라 cpu의 사용통계등을 근거로 잡기도 한다.

 

2. Game the scheduler > Time allotment로 해결

왼쪽이 Time slice에 의존하는 예시, 오른쪽이 time alloment를 기준으로 하는 예시이다.

현재 MLFQ에서 job의 길이를 판단하는 기준은 단순히 time slice를 초과할때까지 해당 job을 실행했느냐이기 때문에 이러한 규칙을 아는 프로그래머가 인위적으로 코드를 조작할 수 있다. 예를 들어 코드 중간에 불필요한 io operation을 추가하는 등의 일이 있을 수 있다.

실제로는 그렇지 않은데도 스케줄러가 해당 job을 짧은 job이라고 착각하게 만드는 꼼수를 쓰는 것이다.

이것은 job의 길이를 판단하는 기준으로 time slice가 아닌 time allotment, 즉 시간 할당량을 사용함으로써 해결할 수 있다.

time slice와 관계없이 정해진 time allotment를 다 사용하면 강등되는 것이다.

 

 

Lower Priority, Longer Quanta

우선순위에 따라 time slice(quanta)를 다르게 줄 수 있다. 우선순위가 낮아질수록 time slice는 길어진다.

우선순위가 낮은 큐일수록 cpu를 확보할 가능성은 낮아지지만, 그래도 한번 확보하면 보다 오래 cpu를 사용할 수 있는 것이다.

 

* 2023 국민대학교 소프트웨어학부 황선태 교수님의 운영체제 수업을 듣고 정리한 내용입니다.

* 원서 출처 : https://pages.cs.wisc.edu/~remzi/OSTEP/