Multi-level Feedback Queue

Towards a General CPU Scheduler

• Goals

  • turnaround time을 최적화하는 것
    • turnaround time : 큐에 들어온 다음 수행 완료될 때까지의 시간. cpu burst time을 알아야함.
      
    • SJF, STCF : workload에 대한 사전 지식 없음
    • workload : 작업을 완료하거나 성과를 창출하는 데 소요되는 컴퓨팅 리소스와 시간의 양
  • interactive 작업에서 response time을 최소화하는 것
    • RR : turnaround time은 좋지 않았음. Round Robin의 줄임말로 cpu burst time을 알지 않아도 됨.
      

• Challenge : workload에 대한 사전 지식이 없이도 가능한 것

  • 지금까지 배운 것들을 각 작업의 대한 수행 시간을 알고 있어야 했음

• 스케쥴러는 어떻게 작업의 특징을 배우고 더 나은 의사결정을 할 수 있을까?

  • 과거 history를 통해 배우고 미래를 예측한다.
    
    
    

Multilevel Feedback Queue

• 프로세스는 move between the various queues.
• 즉, Queue 여러개 사용할 수 있고, 각 Queue마다 사용하는 알고리즘을 다르게 적용할 수 있음.

Basic Rules

• MLFQ는 수많은 구별된 Queue들을 가지고 있다.

  • 각각의 큐는 서로 다른 우선순위가 배정되어 있다.

    

• 준비 상태의 작업은 저 Queue에 들어가 있다.
  • on a higher queue에 있는 작업이 먼저 선택된다. 즉, 우선순위 높은 queue부터 실행된다.
  • 같은 큐 안에서는 프로세스끼리 round-robin 스케쥴링을 사용한다

라고 베이스 규칙을 설정해보고 있다.

💡 Rule 1 : If Priority(A) > Priority(B), A runs (B doesn’t) Rule 2 : If Priority(A) = Priority(B), A & B run in RR.

• MLFQ는 관찰된 행동을 기반으로 작업의 우선순위를 바꾼다.
• 일반적인 워크로드 : a mix of
  • Interactive jobs (I/O - intensive jobs)
    • short-running, 빠른 response time을 요구
    • IO를 대기하는 동안 CPU를 반복적으로 포기함.
    • 우선순위를 높게 유지함.
  • CPI-Intensive jobs
    • 긴 시간 동안 CPU를 집중적으로 사용함.
    • response time에 대해 신경 쓰지 않음.
    • 우선순위를 줄여나간다.
      
      

Example

priority adjustment algorithm

• Rule 3: 작업이 시스템으 들어올 때, 가장 높은 우선순위로 둔다.
• Rule 4a : 만약 작업이 실행하는 동안 전체 time slice를 모두 사용하면, 우선순위를 줄인다.
• Rule 4b : 만약 작업이 time slice가 다 끝나기 전에 cpu를 포기하면, 계속 같은 우선순위를 유지한다.

💡 이러한 방법으로 MLFQ는 SJF에 근사한다. 가까워진다.

A Single Long-Running Job

3가지 Queue가 있고, time slice = 10ms이다.

• 가장 먼저 우선순위가 높은 Q2에 들어오고
• time slice = 10ms를 모두 사용하면 우선순위를 낮춘다.

Along came a short Job

• 가정

  • A는 CPU-intensive job, long-running

  • B는 interactive job, short-running (20ms runtime)

  • A가 실행되고 있는 동안 B가 T=100일 때 도착한다.

    

### What About I/O?

• 가정:

  • A : long-running CPU-intensive job

  • B : interactive job인데 I/O 수행하기 전 CPU를 1ms만 필요로 함.

    

    → time slice = 10ms인데 cpu를 1ms만 사용하고 I/O처리를 하기 ㄸ문에 우선순위가 떨어지지 않는다.

💡 MLFQ 접근법은 interactive job을 높은 우선순위에 계속 유지시킨다.

Problems

1. Starvation 기아

우선순위 기반이면 무조건 발생하는 문제이다.

만약 거기에 “너무 많은” interactive job이 시스템 안에 있다면?

즉, 우선순위 높은게 너무 많으면?

Long-runnning job(cpu-intensive job)들은 CPU 시간을 절대 받을 수 없을 것임.

## 2. Game the scheduler

스케쥴러의 맹점을 이용한 장난

time slice의 99%를 실행한 다음, I/O 수행을 한다면?

그 작업은 계속해서 cpu의 높은 퍼센트지를 얻는다.

3. 프로그램은 시간이 지남에 따라 바꿀 수 있다.

CPU bound process → I/O bound process

Priority Boost

Rule5 : S라는 기간이 지난 다음엔 모든 작업을 최상단으로(가장 높은 우선순위로) 옮긴다.

예를 들어 long-running job(A)와 short-unning interactive job(B, C) 가 있을 때

Better Accounting

time slice가 끝나기 전에 멈춰서 priority를 유지하려는 악용 문제가 있었다.

Solution

Rule 4 : 작업이 uses up its time allotment 하면 우선순위를 낮춘다

→ 즉, 전체적인 time allotment를 줘서 다 쓰면 time slice 남아있어도 낮추는 것이다.

Tuning MLFQ And Other Issues

💡 Lower Priority, Longer Quanta

→ Priority 낮을 수록 time slice를 더 길게 준다.

• high-priority queues → Short time slices
  • e.g., 10 or fewer milliseconds
• low-priority queue → Longer time slices
  • e.g., 100 milliseconds
    

Solaris MLFQ 구현

Time-Sharing scheduling class (TS)를 위해

• 60개의 Queue
• 느리게 증가하는 time-slice length
  • highest priority : 20msec
  • lowest priority : a few hundred milliseconds
• priorities boosted around every 1 second or so

Summary

MLFA의 규칙

1. A > B 우선순위라면 A 실행
2. A = B 우선순위라면 RR(Round-Robin) 알고리즘 사용
3. 시스템 안에 작업이 들어오면 가장 우선순위 높은 큐에 놓는다.
4. 주어진 level에서의 총 time allotment를 사용하면 우선순위를 낮춘다.
5. 일정시간이 지나면 priority boost를 한다.