MLFQ (Multi-Level Feedback Queue)

구조

여러 개의 큐로 구성되어 있음

각 큐는 우선순위를 가지고 있음

실행될 준비가 되어있는 일은 큐에 들어가있음

 

룰

룰1: 우선순위가 높은 큐에 들어가 있는 일이 먼저 실행됨

룰2: 우선순위가 같다면 (같은 큐에 들어가 있다면) RR 방식으로 실행됨

룰3: 새로운 일이 들어오면, 그 일은 우선순위가 가장 높은 큐에 들어감

룰4a: 일이 자신에게 주어진 시간을 다 쓰면 우선순위가 낮아짐

룰4b: 자신에게 주어진 시간을 다 쓰기 전에 CPU를 포기하면 우선순위를 유지함

 

Feedback 특성

CPU intensive: 우선순위를 낮춰줌

Recently do I/Os: 우선순위를 높여줌

Batch (낮은 우선순위) vs Interactive (높은 우선순위)

즉 I/O intensive한 job에 유리함 -> 응답시간을 매우 짧게해줌.

 

Pros

오래 실행되는 일은 공평하게 수행

짧게 실행되는 (I/O intensive) 일은 빨리 실행

 

Issues

• 기아상태: 낮은 우선순위의 일이 굶는 현상

룰5: 어느정도 주기가 지나면 모든 일을 최우선순위 큐로 올림 (boost)

 

• 스케줄러를 속일 수 있음

자기에게 주어진 시간을 다 쓰기 직전에 의도적으로 CPU를 포기

 

• 프로그램이 중간에 특성을 바꿈

룰4: 특정 레벨에서 할당된 모든 시간을 봐서 우선순위를 내림

 

• 큐의 개수를 얼마로 설정할 것인지

보통 약 170개

 

• 큐당 time slice의 크기

우선순위가 낮을수록 크기가 커짐 (문맥교환 비용 낮추기 위해)

 

• boost 얼마나 자주?