Scheduling: round robin, FCFS, multi-level feedback queues, SJF and SRT

Scheduling: round robin, first come first served, multi-level feedback queues, shortest job first and shortest remaining time

1.2.1 Systems Software

Practise exam questions

Systems Software — Note 4 of 8

Candidates need to understand the need for scheduling of tasks by an operating system and the benefits that scheduling brings. Candidates need to understand that there are different scheduling algorithms, with each having benefits and drawbacks for tasks with specific characteristics. Candidates need to understand how the following scheduling algorithms work; round robin, first come first served, multi-level feedback queue, shortest job first and shortest remaining time.

What you need to know

The scheduler is the part of the operating system that decides which process gets the processor next and for how long. Different scheduling algorithms balance fairness, responsiveness and throughput in different ways.

What to know

Aims of scheduling: keep the processor busy, give every process fair processor time, keep response times low for interactive users, and maximise the number of processes completed.
Round robin: each process gets a fixed time slice in turn; if it is not finished it goes to the back of the queue. Fair and responsive, but does not take priority or job length into account.
First come first served (FCFS): processes run to completion in the order they arrive. Simple, but a long job can make short jobs wait a long time. Non-pre-emptive.
Shortest job first (SJF): the waiting process with the shortest estimated total run time goes next. Reduces average waiting time, but needs run times to be estimated and long jobs may be starved. Non-pre-emptive.
Shortest remaining time (SRT): the process with the shortest time LEFT to complete runs next, and a new shorter process can pre-empt the current one. Good throughput, but long jobs can be starved and it needs time estimates.
Multi-level feedback queues (MLFQ): several queues of different priorities. Processes can move between queues depending on their behaviour, e.g. a process using too much CPU time moves to a lower-priority queue, and one waiting too long moves up. Flexible, but more complex to implement.

Key terms

Pre-emptive scheduling: The OS can stop a running process (e.g. when its time slice ends) to let another run. Non-pre-emptive: a process runs until it finishes or blocks.
Starvation: A process waits indefinitely because others are always given priority.

Exam technique

Tip:You may be asked to show the order in which given processes complete, or which algorithm suits a scenario. Always mention whether the algorithm is pre-emptive and its main drawback.
Mistake:Mixing up SJF and SRT. SJF uses the total job length and does not interrupt; SRT uses the time remaining and can pre-empt.