Interrupts and processor scheduling

Interrupts in the fetch–decode–execute model

Repeatedly checking a device is polling and can waste CPU time. With interrupts, a device can signal that input is ready or output has completed. A timer interrupt gives the OS an opportunity to regain control and implement preemptive time slicing.

Hardware events are not the only possible sources: software can also request privileged services or raise exceptions, depending on the machine's conventions.

In the school model, the CPU checks pending enabled interrupts after completing an instruction. Priorities and masking may defer one or allow a higher-priority interrupt to interrupt an ISR.

• An interrupt does not necessarily switch processes. The CPU can service it and resume the same process.

Define the quantities before drawing a timeline

A ready process can run but is waiting for a CPU; a blocked process waits for an event such as I/O completion. Do not schedule a blocked process just because its priority is high.

A CPU burst is an interval of processing before termination or blocking. Our examples have one burst per job and ignore context-switch overhead.

Turnaround = completion − arrival. Waiting = turnaround − CPU burst, in this one-burst/no-I/O model. Response = first start − arrival. A process can receive a quick first response but finish much later.

A preemptive scheduler can stop a running process before its burst finishes; a non-preemptive scheduler lets it run until it blocks or finishes.

FCFS and round robin

First come first served (FCFS) takes ready jobs in arrival order. It is simple and incurs few switches, but a long burst delays short jobs behind it: the convoy effect. In the non-preemptive model, a later arrival cannot displace the running job.

Round robin gives each ready process up to a quantum of CPU time, then returns an unfinished job to the queue's end. A smaller quantum improves opportunities for interaction but increases switching overhead. A very large quantum approaches FCFS.

Specify how arrivals at a slice boundary are ordered; otherwise two defensible traces may differ.

Shortest job first and shortest remaining time

Shortest job first (SJF) selects the shortest estimated next CPU burst when the CPU becomes available, and is non-preemptive in this guide. It can reduce average waiting for a known workload, but estimating burst lengths is difficult.

A newly arrived short job still waits for the current burst to finish.

Shortest remaining time (SRT) is preemptive: a new job with less required CPU time than the current job has left can take over. A trace must compare remaining time, not the original burst.

Both shortest-first policies can starve a long job if short jobs keep arriving; ageing can increase waiting jobs' priority. No average metric alone guarantees fairness or deadlines.

Multilevel feedback queues

A multilevel feedback queue (MLFQ) uses several ready queues at different priorities. Higher-priority ready work runs first; jobs at the same level commonly use round robin. New jobs often start high, and using up an allocation can move a CPU-intensive job down.

Behaviour feeds back into scheduling, unlike a fixed multilevel arrangement that never moves jobs between levels.

Exact MLFQ rules vary: quantum sizes, demotion budgets, I/O behaviour and periodic priority boosts must be stated. Boosts/ageing help prevent low-priority starvation. Feedback scheduling can favour interactive work without knowing exact burst lengths, but introduces policy complexity and still has context-switch overhead.

Original A-Level practice

5 original questions total 18 marks. Attempt each before opening the independently written indicative marking guidance.