Scheduling algorithms: shortest remaining time, multi-level feedback queues, traces and choosing an algorithm

Overview

Recall questions on shortest remaining time and multi-level feedback queues, knowing burst times in advance, traces comparing first come first served, shortest job first, shortest remaining time and round robin, starvation, and justifying a scheduling algorithm.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   How does shortest remaining time scheduling work?

   Model answer

   It is the pre-emptive form of shortest job first. The scheduler always runs the process with the smallest remaining burst time. Whenever a new process arrives, its burst time is compared with the remaining time of the running process, and if the new one is shorter the running process is pre-empted and returned to the ready queue.

2. 2

   What does shortest remaining time optimise for, and what are its failure modes?

   Model answer

   It gives the best average turnaround time of the standard algorithms, because short jobs are always cleared out of the way quickly. Its failure modes are the same starvation problem as shortest job first but worse, since a long job can be pre-empted repeatedly and may never finish while short jobs keep arriving; the continuing need to know or estimate burst times; and extra overhead, because the scheduler must re-evaluate the choice every time a process arrives, causing more context switches.

3. 3

   How do multi-level feedback queues work?

   Model answer

   Several ready queues are maintained, each with a different priority and often a different time slice length. A new process joins the highest-priority queue. If it uses up its whole time slice without finishing, it is moved down to a lower-priority queue with a longer time slice; if it gives up the processor early to wait for input or output, it stays at its level or moves up. The processor always serves the highest-priority non-empty queue, so a process's priority is set by its observed behaviour rather than by a figure supplied in advance.

4. 4

   What do multi-level feedback queues optimise for, and what is the failure mode?

   Model answer

   They optimise for a good compromise: short and interactive processes, which give up the processor quickly, stay in the high-priority queues and get fast response, while long processor-bound jobs drift down and are run in longer, less frequent bursts, which reduces context-switching overhead for them. The failure mode is starvation of the lowest queues if high-priority work keeps arriving; real implementations counter this by periodically promoting all processes back to the top queue. They are also much more complex to design and tune than the other algorithms.

5. 5

   Which scheduling algorithm needs to know the burst time in advance, and why is that a problem?

   Model answer

   Shortest job first and shortest remaining time both need the burst time, and shortest remaining time needs the remaining time too. The problem is that a general-purpose operating system cannot know how long a process will run before it runs it; it can only estimate, usually from how long similar or previous bursts from that process took. If the estimate is wrong the algorithm makes poor choices, and a process could in principle be written to understate its needs to gain priority.

6. 6

   Three processes arrive: A at time 0 needing 6 ms, B at time 1 needing 3 ms, C at time 2 needing 2 ms. Trace first come first served and give the average turnaround time.

   Model answer

   Order of service is A, B, C. A runs 0-6, B runs 6-9, C runs 9-11. Completion times are A 6, B 9, C 11. Turnaround is completion minus arrival: A 6 - 0 = 6, B 9 - 1 = 8, C 11 - 2 = 9. Average turnaround = (6 + 8 + 9) / 3 = 23/3 = 7.67 ms.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.