Priority Scheduling

Priority Scheduling

• SJF, STCF are both priority schedulers
• Priority = CPU burst time

Problem with priority scheduling

• Starvation: high priority tasks can dominate the CPU

Possible solution: dynamically vary priorities

• Vary based on process behavior
• Vary based on wait time (i.e. length of time spent in the ready queue)
  • 오래 기다리면 우선순위 증가

Simple Priority Scheduler

Associate a priority with each process

• Schedule high priority tasks first
• Low numbers = high priority
• No preemption
  
  1. Cannot automatically balance response vs turnaround time
  2. Prone to starvation

Earliest Deadline First (EDF)

Each process has a deadline it must finish by
Priorites are assigned according to deadlines

• Tighter deadlines are given higher prioirty
  
  EDF is optimal (assuming preemtion)
• cpu 1개 & deadline을 반드시 알아야 함
• EDF로 스케줄링이 안 되면 어떤 기법으로도 deadline을 만족시킬 수 없음
  But, it's only useful if processes have known deadlines
  • Typically used in real-time OSes

Multilevel Queue (MLQ)

Key idea: divide the ready queue in two
1. High priority queue for interactive processes

• RR scheduling
• 사용자 레벨은 빠른 응답이 중요
• 우선순위 같을 때 & interactive면 RR

2. Low priority queue for CPU bound

• FCFS schedulinh
  Simple, static configuration
• Each process is assigned a priority on start up
• Each queue is given a fixed amount of CPU tume
  • 80% to processes in the high priority queue
  • 20% to processes in the low priority queue
    

Problem with MLQ

Assumes you can classify processes into high and low priority

• How could you actually do this at run time?
• What of a processes' behavior changes over time?
  • i.e. CPU bound protion, followed by interactive portion
    - CPU, interactive 중 무슨 작업인지 명확하지 않은데, 안다고 가정
    - 알아도 중간에 CPU<-> interactive or CPU, interactive 혼합 작업 존재
    - 80% 20% 어떻게 나누는가?
    Highly biased use of CPU time
• Potentially too much time dedicated to interactive processes
• Convoy problems for low priority tasks

Multilevel Feedback Queue (MLFQ)

Goals

• Minimize response time and turnarround time
• Dynamically adjust process priorities over time
  • dynamically: 여러 큐를 둔다, 움직일 수 있는 큐
  • No assumptions or prior knowledge about burst times or process behavior
    High level design: generalized MLQ
• Serveral priority queues
• Move processes between queu based on observed behavior (i.e. ther history)

First 4 Rules of MLFQ

Rule1: If Priority(A) > Priority(B), A runs, B doesn't
Rule2: If Priority(A) = Priority(B), A & B run in RR

• 같은 큐에 있으면 Round Robin
  Rule3: Processes start at the highest priority
• 뭔지 모르니까 interactive로 가정하고 아니면 낮춤
  Rule4
• Rule 4a: If a process uses an entire time slice while running, its priority is reduced
  • queue의 time slice를 다 쓰면 우선순위 낮추기
    - Rule 4b: If a process gives up the CPU before its time slice is up it remains at the same priority
  • for interactive, time slice 다 쓰기 전에 종료하면 순위 유지
    
• time slice 끝나기 전에 I/O 수행 -> 우선순위 낮아지지 않고 (해당 큐에서) 계속 수행 -> response time 빠르게 유지
  
• 우선순위 높은 게 계속 들어오면 Q2는 굶주림

MLFQ Rule 5: Priority Boost

Rule 5: After some time period S, move all processes to the highest priority queue

• Rule 4 까진 우선순위를 내리기만 했음
  Solve the problems
• Starvation: low priority processes will eventually become high priority, acquire CPU time
• Dynamic behavior: a CPU bound process that has become interactive will now be high priority
  • CPU -> interactive된 애가 있으면 순위를 올려줌
    

Revised Rule 4: Cheat Prevention

time slice마다 얼마나 썼는지 체크하는 게 문제
-> 현재 queue에서 얼마나 작업했는지 체크를 계속 유지하여 정도 넘으면 넘겨주기

Rule 4a and 4b let a process game the scheduler

• Repeatedly yield just before the time limit expires

Solution: better accounting

- Rule 4: Once a process uses up its time allotment at a given priority (regardless of whether it gave up the CPU), demote its priority

• Basically, keep track of total CPU time used by each process during each time interval S instead of just blocking at continous CPU time
  
• 마지막 Q2 queue에서는 Round Robin

MLFQ Rule Review

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

Rule 3: Processes start at the highest priority

Rule 4: Once a process uses up its time allotment at a given priority, demote it

After some time period S, move all processes to the highest priority queue

Parameterizing MLFQ

MLFQ meets out golas

• Balance response time and turnaround time
• Doest not require prior knowledge abount processes

But, it has many knobs to tune

• Number of queues?
  • typically, 4
• How to divide CPU time between the queues?
• For each queue:
  • Which scheduling regime to use?
  • Time slice/quantime?
    • 각 queue마다 time slice 다름
    • priority low이면, time slice 길게, CPU bound 작업으로 context switching $\downarrow$, overhead $\downarrow$
    • 마지막 줄에는 FCFS가 됨
• Method for boosting priorities?
  • 얼마나 자주?

MLFQ in Practice

Many OSes use MLFQ-like schedulers
OSes ship with "reasonable" MLFQ parameters

• Variable length time slices
  • High priority queues - short time slices
  • Low priority queues - long time slices
• Priority 0 sometimes reserved for OS processes
  • interrupt는 우선순위로

Giving Adivce

Some OSes allow users/processes to give the scheduler "hints" about priorities
Example: nice command on Linux

• $ nice <command [args..]>
  • Run the command with adjusted priority
  • Values range form -20 (high) to 19 (low)
  • Added to the process priority