Scheduling Algorithms
How to guess the length of a CPU burst
It is only possible to estimate,
so it would be a good idea to look at previous bursts by that process
This is can be done using an equation
Exponential averaging
Note: alpha is normally set to 0.5, also note alpha is the weighting of nth burst in the calculation
Time Quantum
Time Quantum q - time allocated to each process (about 10-100ms)
Note too much context switching will slow things down, too little and then process response time is too low...
How do I pick the size of q?
80% of bursts should be shorter than q.
Different Algorithms
FCFS
First-Come, First-Served
Processes
Gantt Chart
AVG waiting time
p1 = 0
p2 = 24
p3 = 27
(0 + 24 + 27) / 3 = 17
SJF
Shortest Job First
gives minimum AVG waiting time
Note: hard to know the length of a CPU request, look above for how it maybe done
Process
Gantt Chart
Waiting time
(0 + 3 + 9 + 16) / 4 = 7
SRJF (preemptive SJF)
Shortest Remaining Job First
Process
Gantt Chart
Waiting time
((10-1)+(1-1)+(17-2)+(5-3)) / 4= 6.5
RR
Round Robin
Each process gets 1/n (number of processes),
In other words each process has the same time quantum
Timer Interrupts the process and starts the next one
Process
Gantt Chart
Waiting time
Typically slower turn around time than SJF,
But better response time