Whiteboard session
2 Sept 2001

CPU Scheduling Algorithms

Issues:
- CPU utilization
- throughput: number of processes completed per time unit
- turnaround time (avg flow time): interval from time of submission to
time of completion
- waiting time
- response time

Little's Law
  n = lambda * omega

  n = avg queue length (things inside the box)
  lambda = avg arrival rate of new processes (things / sec)
  omega = avg waiting time (flow time) (sec)

  Assume steady state (same completion rate as arrival rate)

-----

FCFS (first come first served)
  - NO starvation
  - CONVOY problem
  - not preemptive
  - simple, flow time is bad

SJF (shortest job first)
  - starvation
  - maybe preemptive
  - requires future knowledge
  - OPTIMAL in the sense of minimal average waiting time

SETF (shortest elapsed time first)
  - starvation
  - maybe preemptive
  - approximation to SJF

RR (round robin)
  - NO starvation
  - preemptive
  - fair, flow time is bad

MLQ (multi-level queue)
  - starvation
  - maybe preemptive
  - priority levels

MLFQ (multi-level feedback queue)
  - starvation
  - maybe preemptive
  - dynamic priority levels
  - most general of all algorithms listed
    - # of queues
    - scheduling algorithm for each queue
    - when to move between queues
    - which queue to enter first