Scheduling algorithms: first come first served, round robin and shortest job first

Overview

Recall questions on why an operating system schedules processes, pre-emptive and non-pre-emptive scheduling, burst, waiting, turnaround and response time, and how first come first served, round robin and shortest job first work and fail.

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

   What is scheduling, and why does an operating system need to do it?

   Model answer

   Scheduling is deciding which of the ready processes gets the use of the processor next and for how long. There are normally far more processes wanting to run than there are processor cores, so the operating system must share the processor between them in a way that keeps it busy, gives every process a fair share, avoids any process waiting for ever, and keeps interactive programs feeling responsive.

2. 2

   Distinguish between pre-emptive and non-pre-emptive scheduling, and classify the five common algorithms.

   Model answer

   Under non-pre-emptive scheduling, once a process has the processor it keeps it until it finishes or blocks for input or output. Under pre-emptive scheduling the operating system can take the processor away from a running process and give it to another. First come first served and shortest job first are non-pre-emptive; round robin, shortest remaining time and multi-level feedback queues are pre-emptive.

3. 3

   Define these scheduling measurements: burst time, waiting time, turnaround time and response time.

   Model answer

   Burst time is the amount of processor time a process needs. Waiting time is the total time a process spends in the ready queue not running. Turnaround time is the time from a process arriving to it completing, so turnaround time equals waiting time plus burst time. Response time is the time from a process arriving to the moment it first gets the processor.

4. 4

   How does first come first served scheduling work?

   Model answer

   Processes are placed in a queue in the order in which they arrive, and the processor runs each one to completion before starting the next. It is non-pre-emptive and needs no information about the processes beyond their arrival order.

5. 5

   What does first come first served optimise for, and what is its failure mode?

   Model answer

   It optimises for simplicity and absolute fairness in the order of service, and it can never starve a process, since every process eventually reaches the front of the queue. Its failure mode is very poor response for short and interactive jobs: if a long job arrives first, every job behind it waits for the whole of it. This is the convoy effect, and it makes the system feel unresponsive.

6. 6

   How does round robin scheduling work?

   Model answer

   Each process in the ready queue is given the processor for a fixed period called a time slice or quantum. If it has not finished when the quantum expires, a timer interrupt pre-empts it and it is placed at the back of the queue, and the next process runs. The queue is cycled through repeatedly until all processes have finished.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.