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