[ OS ] Multi-Level Feedback Queue

 

1. Multi-Level Feedback Queue

 

1.1 Scheduling Metrics

Turnaround time - 일반적인 작업 실행시간을 알 수 없으므로 Turnaround에 효율적인 SJF와 STCF은 사용하기 힘들다

response time- OS는 사용자에게 반응하는 것처럼 느끼게 하는 것을 좋아한다. RR은 응답시간을 줄이지만 Turnaround 시간에서는 되게 별로다.

 

어떻게 하면 작업기간에 대한 사전지식 없이 Turnaround time와 response time 모두 효율적인 스케줄러를 설계할 수 있을까?

 

1.2 Multi-Level Feedback Queue Rule1, Rule2

MLFQ 알고리즘은 기본적인 조건을 가지고있다. 먼저 여러개의 큐를 가지고 있고 이는 각각 다른 우선순위 수준을 주고 ready 상태인 프로세스들은 대기열에 들어간다는 것이다. 또, MLFQ 알고리즘은 기본적인 룰을 가지고 있다.

Rule1) 우선순위가 높은 프로세스가 실행된다

Rule 2) 우선순위가 같을시 RR알고리즘을 이용한다.

 

위 사진은 MLFQ 알고리즘의 예시이다. A, B 는 동시에 도착했음으로 RR방식으로 돌아가고 A,B가 실행이 완료되거나 I/O 실행을 하러가면 다른 프로세스가 실행된다. 

 

1.3 How the Scheduler Sets Priorities

1) 각 작업에 고정 순위 부여

2) 관찰된 동작에 따라 우선순위 변경 (기록으로 미래 판단)

 - I/O를 위해 CPU를 반복적으로 포기하는 job은 우선순위를 높게 유지해준다

 - job이 CPU를 장시간 독점하면 우선순위를 낮춘다

 

1.4 Multi-Level Feedback Queue Rule3, Rule4-a,  Rule4-b

Rule 3) job이 시스템에 들어가면 가장 높은 우선순위를 준다

Rule 4-a) 작업이 실행되는 동안 양보하지 않고 모든 시간을 사용하면 우선순위가 감소한다.

Rule 4-b) 작업이 시간이 끝나기 전에 CPU를 포기하면 우선순위를 유지해준다  

 

위 규칙을 적용한 예시 사진이다.

 

- 하나의 긴 프로그램이 실행될때

 - 중간에 짧은 프로그램이 실행됐을 때

- 실행 중에 I/O 수행을 할 때

 

1.5 Problems

위에까지 나온 룰로 스케줄링을 진행하기에는 몇가지 문제가 있다.

 

1) 굶주림현상

cpu bound한 job 들은 우선순위가 자꾸 낮아져서 굶주려지고 I/O bound 한 job들은 자꾸 나눠써야해서 굶주림

2) Gaming the scheduler

필요도 없는데 괜히 기준에만 맞춰 I/O 호출

3) Changing behavior

CPU-bound 하다가도 I/O-bound 해질 수 있고 그 반대가 될 수도 있다.

 

1.5 Priority Boost (Rule5)

 

Rule 5) 시스템의 모든 작업의 우선순위를 주기적으로 높여준다. 

이 룰은 위에 문제 중 굶주림을 해결해 준다. 

 

 

1.6 Modify Rule4-a,  Rule4-b 

 룰 4-a 와 4-b의 내용을 조금 수정하면 문제점 중 Gaming the scheduler 문제를 해결할 수 있다.

 

Rule 4) 작업이 지정된 수준에서 모든 시간 할당을 사용하는 경우 우선순위를 낮춘다. 

 

룰을 이렇게 바꾸면 횟수와 상관없이 시간으로 계산 되기에 악의적인 행위를 막을 수 있다.

 

 

1.7 How often Priority Boost 

 

문제 3인 job이 bound 하는 대상이 바꼈을 때 문제는 Boost 주기로 해결할 수 있다.

이는 여러가지 고려할 것이 많음으로 선택하기 어려운 문제이다. 현재는 1초로 많이 이용중이다.

 

또, time slice는 얼마로 설정해야하는가도 어려운 문제이다. 현재는 우선순위가 높은 큐에서는 20ms 정도이고 우선순위가 낮은 큐에서는 수백ms 정도 이다.