Multi-Level Feedback Queue(MLFQ)
- 미래를 예측하기 위해 과거로부터 배워오는 스캐줄러
- 목적
- turnaround time을 최적화 한다. -> 짧은 작업을 먼저한다.(작업의 길이에 대한 사전 지식없이)
- 상호적 작업을 위한 response time을 최소화 한다.
MLFQ의 기본적인 규칙
- MLFQ는 별개의 queue를 여러개 가지고 있다.
- 각 큐들은 다른 우선순위 레벨을 가지고 있다.
- 수행을 위해 준비된 작업은 single queue에 있다.
- 높은 큐에 존재하는 작업은 수행되기로 결정된다.
- 같은 큐에 있는 작업들 중에서 RR스케줄링을 이용한다.
규칙1 : Priority(A) > Priority(B)면 A는 작동(B는 작동하지 않음)
규칙2 : Priority(A) = Priority(B)면 A&B가 RR스케줄링을 이용하여 수행됨
- MLFQ는 관찰된 행동을 기반으로 우선순위를 달리 만든다.
- 예시
- A 작업은 I/O를 기다리는 동안에 CPU를 양도한다. -> A의 우선순위를 높게 유지한다.
- A 작업이 CPU를 긴 시간동안 집중적으로 사용한다. -> A의 우선순위를 낮춘다.
MLFQ 우선순위를 어떻게 바꿀까?
- MLFQ 우선순위 적용 알고리즘
- 규칙3 : 작업이 시스템에 들어오면, 이것은 가장 높은 우선순위에 위치한다.
- 규칙4a : 작업이 동작중에 모든 time slice를 이용한다면, 우선순위가 감소한다.(큐에서 아래로 내려간다.)
- 규칙4b : 만일 작업이 time slice동안에 CPU를 포기한다면 이는 같은 우선순위 레벨을 유지한다.
- 이 알고리즘들에 의해서 MLFQ는 SJF의 turnaround time이 낮아지는 것과 유사하게 낮아진다.
ex1) Single Long-Running Job
ex2) Along came a short job
- 가정
- 작업A : 길게 동작하는 CPU를 많이 쓰는 작업
- 작업B : 짧게 동작하는 interactive 작업(runtime 20ms)
- A는 얼마정도 수행되고 있다가, B가 T=100에서 도착한다.
ex3) I/O는?
- 가정
- 작업A : A는 길게 동작하는 CPU를 많이 쓰는 작업
- 작업B : B는 I/O를 수행하는 1ms의 CPU를 필요로 하는 interactive작업이다.
- MLFQ 접근에서 interactive job를 가장 높은 우선순위에 둔다.
MLFQ의 문제점은 무엇이 있을까?
- Starvation
- 시스템에 너무 많은 interactive job가 있을 때
- 오랬동안 동작하는 작업은 CPU time을 부여받지 못할 것이다.
- Game the scheduler
- 99%의 time slice를 작동시킨 후 I/O작업이 동작한다면?
- 작업은 높은 퍼센트의 CPU time을 얻는다.
- 프로그램이 행동을 시간마다 바꿀 수 있다.
- CPU bound process -> I/O bound process
Priority Boost
- 규칙5: 특정 시간 간격 S이후에, 시스템의 모든 작업들을 가장 높은 큐에 넣는다.
- 예시
긴시간 작동하는 작업A, 두개의 짧게 작업하는 interactive 작업 B,C 존재시
더 좋은 방법
- 스캐줄러의 gaming을 어떻게 방지할까?
- 해결책
- 규칙4(4a와 4b 규칙을 바꾼다.) : 작업이 주어진 레벨에서 시간 할당량을 이용 한다면(CPU를 얼마나 포기했던간에), 우선순위가 낮아진다.(큐를 내린다.)
MLFQ 튜닝과 다른 고려할 점
-
낮은 우선 순위일 수록 높은 시간을 할당해준다.
-
높은 우선순위의 큐에서 -> 짧은 time slice
- ex) 10 또는 더 작은 ms
-
낮은 우선순위의 큐에서 -> 더 긴 time slice
- ex) 100ms
solaris MLFQ 적용
- Time-Sharing 스케줄링 클래스에서(TS)
- 큐 개수 : 60개
- 우선순위에 따라 조금씩 time slice길이를 늘려준다.
- 가장 높은 우선순위 : 20ms
- 가장 낮은 우선순위 : 몇백 ms
- 우선순위는 매 1s나 그이외에서 boost된다.
요약
- MLFQ 규칙에 대한 정제된 정의는
- 규칙1. Priority(A) > Priority(B) 일때 A는 작동, B는 작동하지 않는다.
- 규칙2. Priority(A) = Priority(B) 일때 A와 B는 RR방식으로 작동한다.
- 규칙3. 작업이 시스템에 들어오면 가장 높은 우선순위에 할당된다.
- 규칙4. 작업이 주어진 priority level에서 시간 할당량을 다 사용한다면(CPU를 얼마나 많이 포기했던 간에), 우선순위는 감소한다.(큐의 하강)
- 규칙5. 특정 시간간격 S이후에는 시스템의 모든 작업을 가장 높은 큐에 위치시킨다.
