1.2.1 - Interrupts and processor scheduling
A CPU must respond to events while sharing its time between running programs. You will follow an interrupt through a saved processor state, then compare five scheduling policies using complete small traces. The timing assumptions matter: a different arrival time or preemption rule can change the correct schedule.
Events that request processor attention
An interrupt is a signal or event requesting processor attention. A device can report that input is ready or that an operation has finished; a timer can signal that a time interval has elapsed; software can request an OS service through an appropriate software-interrupt mechanism. Different interrupt sources have different purposes and priorities.
Suppose an application requests a storage read. Instead of having the CPU repeatedly ask whether the device has finished, the system can let the device signal completion. The CPU can do other ready work meanwhile. Repeatedly checking status is polling; interrupts can avoid that repeated checking, although handling each interrupt still has an overhead.
In the simplified fetch-decode-execute model, the CPU checks for eligible pending interrupts between completed instruction cycles. It completes the current instruction before transferring control. It considers whether interrupts are enabled and the request's priority. A pending request is not a guarantee of immediate service: it may wait because it is masked or because a higher-priority handler is running.
The boundary is crucial. If a device signals halfway through executing an addition, the model does not abandon the addition with an undefined half-result. It finishes that instruction, then handles an eligible request before fetching the next ordinary instruction. Exact hardware details vary, but this stated model makes the sequence traceable.
Saving state and running an ISR
An interrupt service routine (ISR) is code that deals with a particular interrupt. The interrupted program must later continue with its own state, so the processor saves relevant registers, including the next instruction address in the program counter and status information, before entering the handler. A stack is a common place to preserve this context.
Assume the CPU has just completed an instruction, PC = 41, ACC = 12 and the status flags have a particular saved value. A keyboard interrupt is accepted, and its ISR begins at address 900. The system saves PC 41, ACC 12 and the relevant flags; the PC is set to 900 and the handler executes. Even if the ISR uses ACC and changes flags, returning restores the saved context. PC becomes 41, so the interrupted program's next instruction is fetched from 41, with its original ACC of 12.
The ISR identifies and services the event, for example placing received input into an appropriate buffer and acknowledging the device. Interrupt-control state may be changed to prevent unsuitable nested handling. On return it is restored as required. Some systems allow a higher-priority interrupt to interrupt an ISR; if so, another context must be saved and later restored in the correct order. Do not assume every request interrupts every handler.
A timer interrupt may return directly to the interrupted process, or the OS may use the event to choose another ready process. Saving state enables that later resumption, but an interrupt and a process switch are different concepts: handling a device request does not automatically mean a different application will run.
Scheduling ready work and FCFS
A scheduler decides which ready process receives processor time. A ready process can execute; a blocked process is waiting for something such as an I/O result. Running a blocked process will not make its missing input appear. Scheduling can aim for responsiveness, efficient CPU use, throughput or fairness, and those aims can conflict.
Preemptive scheduling can suspend a running process before its current CPU burst finishes. Nonpreemptive scheduling lets it continue until completion or blocking. A context switch preserves the old process's state and restores the selected process's state. Switching takes time, so sharing more often has a cost.
For all four single-queue worked traces below, use one CPU; times are in arbitrary time units; each process has one CPU burst and no I/O; context-switch overhead is zero; arrivals at a decision time are eligible at that time. Break selection ties by earlier arrival, then by name, except that SRT keeps the current process on an equal remaining-time tie.
| Process | Arrival time | CPU burst |
|---|---|---|
| A | 0 | 6 |
| B | 1 | 3 |
| C | 2 | 1 |
First come first served (FCFS) uses arrival order and is nonpreemptive in this model. A is ready at time 0 and runs to 6. B then runs from 6 to 9, and C from 9 to 10. A new arrival does not interrupt A.
Turnaround time is completion time minus arrival time. In this one-burst model, waiting time is turnaround time minus CPU burst. B's turnaround is and its waiting time is . A, B and C wait 0, 5 and 7 units, so mean waiting time is units. A long first job delays short jobs behind it: the convoy effect. FCFS is simple and respects arrival order, but that is not the same as giving every interactive task a quick response.
Round robin and its time quantum
Round robin gives the process at the front of a ready queue at most one time quantum, then places it at the back if it still needs CPU time. A process that finishes before its quantum ends releases the CPU immediately. This is preemptive time sharing, with no requirement to predict the full burst length.
Use the A, B, C data above with quantum 2. New arrivals join the back as they arrive. At a quantum boundary, arrivals at that exact time join before the expired process is requeued. Queue states below omit the currently running process and are recorded just before the next dispatch.
| Running interval | What happens at its end | Ready queue for next dispatch |
|---|---|---|
| A: 0–2 | A has 4 left; B and C have arrived | B, C, A |
| B: 2–4 | B has 1 left | C, A, B |
| C: 4–5 | C finishes after 1 unit | A, B |
| A: 5–7 | A has 2 left | B, A |
| B: 7–8 | B finishes | A |
| A: 8–10 | A finishes | empty |
B gets its first CPU time at 2, only 1 unit after arrival, rather than waiting until 6 under FCFS. Round robin can improve interactive response and gives repeatedly ready processes turns. It does not imply that all processes finish equally soon.
A very large quantum can make a one-burst workload behave like FCFS. A very small quantum gives frequent turns but may waste a greater proportion of time on real context switches. The zero-overhead trace deliberately excludes that cost; an argument about actual performance must put it back.
Shortest job first without preemption
Shortest job first (SJF) selects the ready process with the shortest predicted next CPU burst. In the nonpreemptive model it then lets that burst finish. A shorter process arriving during the burst waits until the next choice.
With the A, B, C data, only A is ready at 0, so it runs from 0 to 6. At 6, B needs 3 units and C needs 1. C runs from 6 to 7, then B from 7 to 10. The schedule is A, C, B; choosing C at time 0 would be wrong because C has not arrived yet.
Serving short ready jobs can reduce average waiting time, but the burst length generally needs an estimate. It is not free knowledge available for every real process. A long job can wait a very long time if short ready jobs keep arriving: starvation is the indefinite postponement of work. The possibility of starvation depends on continuing arrivals; all jobs in the finite worked example eventually finish.
SJF and FCFS both let a selected burst finish in these models, but choose differently when several jobs are ready. SJF's emphasis is length; FCFS's emphasis is arrival order. That difference is visible at time 6 here.
Shortest remaining time with preemption
Shortest remaining time (SRT) selects the ready process with the least CPU time remaining. Unlike SJF, it can preempt a running process when an arriving process has a shorter remaining burst. In this trace, an equal remaining-time tie keeps the current process; that stated tie rule avoids an unnecessary switch.
For the same A, B, C data, A runs from 0 to 1, leaving 5. B arrives needing 3, so it preempts A. B runs from 1 to 2, leaving 2. C arrives needing 1 and preempts B. C finishes at 3; B then has 2 left compared with A's 5, so B runs from 3 to 5. A finally runs from 5 to 10.
| Interval | Running process | Reason for next selection |
|---|---|---|
| 0–1 | A | B arrives with 3 < A's 5 remaining |
| 1–2 | B | C arrives with 1 < B's 2 remaining |
| 2–3 | C | C completes; B is shorter than A |
| 3–5 | B | B completes; only A remains |
| 5–10 | A | A completes |
B's waiting time is . C's is . A's is . Those short jobs respond quickly, but A finishes later than under FCFS. SRT requires remaining-time estimates and can starve long jobs under repeated short arrivals. It can also introduce more switches than nonpreemptive SJF. A best policy depends on the workload and goal, not on this one favourable example alone.
Multilevel feedback queues
Multilevel feedback queues (MLFQ) place ready processes in queues with different priorities and possibly different quanta or scheduling policies. Processes can move between queues in response to observed behaviour. This feedback distinguishes the policy from permanently assigning each process to a fixed queue.
A system can give new or interactive work high priority and demote a process that repeatedly uses its full quantum. Longer CPU-bound work still gets service in lower queues when higher queues are empty. Because rules vary, a trace needs the number of queues, their quanta, movement rules and priority decisions. Ageing or periodic priority boosts can prevent lower-queue work starving; they are possible rules, not automatic features of every MLFQ.
Here is one fully stated example: all work arrives at 0 in order R then S; R needs 5 CPU units and S needs 1. Q0 is higher priority with quantum 1; Q1 uses round robin with quantum 2. New jobs enter Q0. An unfinished job using its full Q0 quantum moves to the back of Q1; an unfinished Q1 job returns to Q1's back. Always choose Q0 if nonempty. There is no I/O, no new arrival, no boosting and no switching overhead.
R runs in Q0 from 0–1, leaving 4, and is demoted. S runs in Q0 from 1–2 and completes. Q0 is now empty, so R runs in Q1 from 2–4, leaving 2, then again from 4–6 and completes. S was served after only R's short first turn; the long job still completed when the high-priority work ended.
This example illustrates a policy rather than claiming that every OS uses those quanta. MLFQ adapts without needing an exact full-burst prediction, but poor movement rules may penalise some jobs or starve low-priority work. Its extra flexibility also makes it more complex to configure and reason about than FCFS.