23 Scheduling Algorithms

First-Come, First-Served (FCFS)

Jobs are put in a queue, and served according to arrival time. Easy to implement but CPU-intensive process can cause long waiting time.
FCFS with pre-emption is called Round Robin, standard method in time.

Question

get the time quantum (time before pre-emption) right.

• too short : too many context switches
• too long : Process can monopolise CPU.

Shortest Job First

Next job is one with shortest CPU-burst time (shortest CPU-time before next I/O-operation). Not implementable, but this is algorithm with smallest average waiting time.
$\Rightarrow$ Strategy against which to measure other ones

Question

Can we predict the burst-time ?

Only hops is extrapolation from previous behaviour done by weighting recent times more than older ones.

$${\tau }_{n+1}=\alpha t_n+(1-\alpha ){\tau }_n$$

Priority Scheduling

Assumption : A priority is associated with each process. CPU is allocated to process with highest priority. Equal-priority processes scheduled according to FCFC. Two variations :

• With pre-emption : newly-arrived process with highest priority may gain processor immediately if process with lower priority is running
• Without pre-emption : newly arrived process always waits.
  Pre-emption good for ensuring quick response time for high-priority processes.
  Disadvantages : Starvation of low-priority processes possible.
  Solution : Increase priority of processes after a while (Ageing).

Multilevel Queue Scheduling

Applicable when processes can be partitioned into groups (e.g. interactive and batch processes).
Split ready-queue into separate queues, with separate scheduling algorithm
Scheduling between queues usually implemented as pre-emptive priority scheduling
Possible setup of queues :

• System processes
• Interactive processes
• Interactive editing processes
• Batch processes