Scheduling and Dispatch

When several processes or threads are ready to run, the OS decides which gets CPU time. Scheduling is the decision process; dispatching is the mechanism that gives the CPU to the selected task.

Scheduler and dispatcher

  • The CPU scheduler selects a process or thread from the ready queue.

  • The dispatcher transfers control to the selected task. It may switch context, change to user mode and resume the task at the correct instruction.

The time taken to stop one task and start another is called dispatch latency. A context switch uses time but does not advance the application’s work.

Preemptive and non-preemptive scheduling

  • Non-preemptive: a task keeps the CPU until it finishes or waits for something, such as I/O.

  • Preemptive: the OS can interrupt a running task and give the CPU to another one.

Preemption can improve responsiveness, but the OS must safely save and restore task state.

Scheduling algorithms

First Come, First Served (FCFS)

Tasks run in the order they arrive.

  • Simple to understand and implement.

  • A long task at the front can make shorter tasks wait a long time. This is called the convoy effect.

Shortest Job First (SJF)

The task with the shortest expected CPU burst runs first.

  • Can minimise average waiting time when burst lengths are known.

  • The OS may not know the next burst length exactly.

  • A long task may wait a long time if short tasks keep arriving.

Round Robin (RR)

Each task gets a limited time slice called a time quantum. If it has not finished when the quantum ends, it returns to the ready queue.

  • Supports responsiveness and sharing.

  • A very long quantum makes it behave more like FCFS.

  • A very short quantum causes frequent context switches and extra overhead.

Scheduling measures

  • Arrival time (AT): when a process enters the ready system.

  • Burst time (BT): CPU time the process needs.

  • Completion time (CT): when it finishes.

  • Turnaround time (TAT): total time from arrival to completion.

  • Waiting time (WT): time spent waiting in the ready queue.

  • Response time: time from a request arriving until the first response begins.

Formulas:

Turnaround time = completion time − arrival time
Waiting time = turnaround time − burst time

Worked FCFS example

Three processes arrive together:

Process

CPU burst

P1

5

P2

3

P3

2

FCFS runs them in that order:

0       5       8      10
|  P1   |  P2   |  P3  |

Waiting times:

  • P1 waits 0

  • P2 waits 5

  • P3 waits 8

Average waiting time = (0 + 5 + 8) ÷ 3 = 4.33 time units

How to solve scheduling questions

  1. Write down each process’s arrival and burst times.

  2. Apply the requested scheduling rule.

  3. Draw a timeline or Gantt chart.

  4. Record each completion time.

  5. Calculate turnaround time and waiting time.

  6. Find the averages if requested.

Key terms to remember

Ready queue · scheduler · dispatcher · dispatch latency · context switch · preemptive · non-preemptive · FCFS · SJF · Round Robin · time quantum · turnaround · waiting time · response time

Check your understanding

A process arrives at time 2, finishes at time 12 and needs 6 units of CPU time.

  1. What is its turnaround time?

  2. What is its waiting time?

  3. Which part of scheduling chooses the task, and which part hands over the CPU?

Answers:

  1. 12 − 2 = 10 time units.

  2. 10 − 6 = 4 time units.

  3. The scheduler chooses; the dispatcher gives it the CPU.