The shape of the lesson
By the end of the lesson, learners can
- Resources, the interface and processes: At A Level you need to explain HOW the OS gets the most out of the hardware, not just list what it manages.
- Four scheduling routines: Scheduling is needed because there are more processes than processor cores.
- The kernel as interrupt handler: Scheduling decisions are triggered by interrupts.
- States: running, ready (needs only the CPU), blocked (needs an event); blocked goes to ready, never straight to running.
- Non-pre-emptive: FCFS (arrival order) and SJF (shortest burst).
- Pre-emptive: SRT (least time left; a new shorter job interrupts) and RR (fixed time slice, back of the queue).
- Waiting time = finish − arrival − burst. Draw the timeline first, then calculate.
One picture every idea returns to
A process is a program that has been loaded into memory and is being executed. In multi-tasking the OS switches the processor between processes so quickly that they appear to run at the same time. Each process is running (on the processor), ready (waiting only for the processor) or blocked (waiting for an event such as I/O). The scheduler chooses the next ready process using a routine such as first come first served, shortest job first, shortest remaining time or round robin. The kernel acts as the interrupt handler: timer and I/O interrupts trigger the low-level scheduler to change which process runs.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Whose turn is it?. A single processor core can only run one instruction stream at a time, yet a computer appears to run dozens of programs at once. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Resources, the interface and processes | At A Level you need to explain HOW the OS gets the most out of the hardware, not just list what it manages. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Four scheduling routines | Scheduling is needed because there are more processes than processor cores. Model the worked example Four jobs, three routines on the board, one line at a time. | Pairs |
| 21 to 30 min | Teach and check: The kernel as interrupt handler | Scheduling decisions are triggered by interrupts. Project tab 7 of the lab (Interrupts handled by priority) and let a student drive it while the class predicts. Your turn: Explain why round robin scheduling depends on interrupts. | Think-Pair-Share |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 21 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in The kernel as interrupt handler, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Think-Pair-Share
Pose the question, give thirty seconds of silent thinking, then a minute to compare with a partner before a few pairs share with the class. The silent minute is the part that cannot be cut.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| A blocked process never goes straight to running. | When its I/O completes it joins the ready queue and waits to be scheduled like everyone else. |
| SJF is non-pre-emptive: once a job starts it runs to the end. | If a question lets a newly arrived short job interrupt the running one, it is describing SRT. |
Process states and scheduling: worksheet
6 questions, 21 marks. Written in the style of the papers; no past paper question is reproduced.
Describe three ways in which an operating system can maximise the use of computer resources.
Describe the three process states and explain how a process moves from running to blocked and back.
Four processes arrive as follows: W at time 0 needing 7 ms, X at time 2 needing 4 ms, Y at time 4 needing 1 ms, Z at time 5 needing 4 ms. Using shortest remaining time scheduling, give the order in which the processor is allocated and calculate the average waiting time.
Jobs J1, J2 and J3 arrive together in that order, needing 5, 3 and 7 ms. Using round robin with a 2 ms time slice, state when each job finishes and calculate the average waiting time.
Explain how the kernel of the operating system uses interrupts to manage low-level scheduling.
A system runs many short interactive tasks and a few long batch jobs. Compare shortest job first with round robin for this system.
Answer key and marking notes
- When a process is waiting for I/O it is blocked and another process is given the processor, so the CPU is not idle.
- Memory is allocated dynamically and freed when a process ends / virtual memory allows more processes to be in memory than RAM alone.
- I/O is handled with buffers, spooling or DMA and interrupts, so the processor can do other work during slow transfers.
- Running: the process is being executed by the processor.
- Ready: the process is waiting only for processor time.
- Blocked: the process cannot continue until an event happens, e.g. I/O completes.
- A running process that requests I/O becomes blocked; when the I/O completes it moves to ready (not directly to running) until the scheduler dispatches it.
- W 0-2; X arrives needing 4, less than W's 5 left, so X 2-4; Y arrives needing 1, less than X's 2 left, so Y 4-5.
- X 5-7 (2 left, shorter than Z 4 and W 5); Z 7-11; W 11-16.
- Waits: W 16 − 0 − 7 = 9, X 7 − 2 − 4 = 1, Y 0, Z 11 − 5 − 4 = 2.
- Average waiting time = 12 / 4 = 3 ms.
- Timeline: J1 0-2, J2 2-4, J3 4-6, J1 6-8, J2 8-9, J3 9-11, J1 11-12, J3 12-15.
- J2 finishes at 9, J1 at 12, J3 at 15.
- Waits: J1 12 − 5 = 7, J2 9 − 3 = 6, J3 15 − 7 = 8; average = 21 / 3 = 7 ms.
- The kernel acts as the interrupt handler: at the end of a fetch-execute cycle the processor checks for interrupts and passes control to the kernel.
- A timer interrupt signals the end of a time slice; the kernel saves the running process's context in its PCB and moves it to the ready queue.
- The low-level scheduler selects the next ready process and loads its context so it runs (context switch).
- An I/O interrupt causes the kernel to move the process waiting for that device from blocked to ready.
- SJF gives the short interactive tasks a very low average waiting time.
- But SJF is non-pre-emptive, so a long job that has started holds up interactive tasks, and long jobs may starve if short jobs keep arriving.
- Round robin gives every task a time slice in turn, so interactive tasks get a fast response and no job starves, at the cost of more context switches and a higher average waiting time.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
A running process asks to read a block of data from the hard disk. Which state change happens next?
- ARunning to blocked, until the disk transfer is complete
- BRunning to ready, so it can wait for its next time slice
- CRunning to blocked, then straight back to running when the data arrives
- DIt stays running and waits for the data while holding the processor
Jobs P, Q and R arrive at time 0 in that order, needing 4, 9 and 2 ms of processor time. What is the average waiting time using first come first served?
- A5.67 ms
- B2.67 ms
- C10.33 ms
- D4.33 ms
Jobs A, B, C and D arrive at time 0 in that order, needing 7, 3, 5 and 2 ms. They are scheduled by round robin with a 3 ms time slice. In which order do the jobs finish?
- AB, D, C, A
- BD, B, C, A
- CA, B, C, D
- DB, D, A, C
A timer interrupt arrives at the end of a process's time slice. What does the kernel do?
- ASaves the process's context in its PCB, moves it to ready and lets the low-level scheduler dispatch another process
- BMoves the process to the blocked state and loads a new program from disk into memory
- CEnds the process and removes it from memory so that the next process can be loaded
- DPasses the interrupt to the high-level scheduler, which restarts the same process from the beginning
Four processes arrive as follows: P1 at 0 ms needing 6 ms, P2 at 2 ms needing 3 ms, P3 at 3 ms needing 7 ms and P4 at 5 ms needing 1 ms. What is the average waiting time using shortest remaining time scheduling?
- A2.75 ms
- B3.25 ms
- C5.25 ms
- D7.00 ms
P1 arrives at 0 ms needing 6 ms, P3 arrives at 1 ms needing 8 ms and P2 arrives at 2 ms needing 2 ms. The processor log shows P1 0-6, P2 6-8, P3 8-16. Which scheduling routine produced this log?
- AShortest job first
- BFirst come first served
- CShortest remaining time
- DRound robin with a 4 ms time slice
Quiz key
A process waiting for I/O cannot continue, so it is moved to the blocked state and the processor is given to another process. Moving to ready would be wrong: a ready process could run immediately, but this one needs its data first. When the transfer completes it goes from blocked to ready, never straight back to running. Keeping the processor while waiting would waste it, which is exactly what multi-tasking avoids.
FCFS runs P 0-4, Q 4-13, R 13-15, so the waits are 0, 4 and 13 ms: 17 / 3 = 5.67 ms. 2.67 ms is the shortest job first result (R, P, Q: waits 0, 2 and 6). 10.33 ms is the average finish (turnaround) time, (4 + 13 + 15) / 3, not the waiting time. 4.33 ms drops Q's wait, adding only 0 + 13 before dividing by 3.
Timeline: A 0-3, B 3-6 (done), C 6-9, D 9-11 (done), A 11-14, C 14-16 (done), A 16-17 (done). So the finishing order is B, D, C, A. D, B, C, A is the shortest job first order, and A, B, C, D is first come first served. B, D, A, C forgets that C needs only 2 more ms after its first slice and so finishes before A's third turn.
The kernel is the interrupt handler: it saves the registers and program counter in the process control block, puts the process at the back of the ready queue and the low-level scheduler loads the next ready process (a context switch). The process is not blocked, because it is not waiting for an event. It is not ended, because it still has work to do. The high-level scheduler decides which programs are loaded as processes, and nothing is restarted from the beginning.
SRT: P1 runs 0-2; P2 arrives needing 3, less than P1's 4 left, so P2 runs 2-5; at 5 P4 (1) runs 5-6; then P1 (4 left) 6-10 and P3 10-17. Waits = finish − arrival − burst: P1 10 − 0 − 6 = 4, P2 0, P3 17 − 3 − 7 = 7, P4 0; 11 / 4 = 2.75 ms. 3.25 ms is non-pre-emptive SJF (P1 runs to 6 first). 5.25 ms is FCFS. 7.00 ms is the average turnaround time (10, 3, 14 and 1), not the waiting time.
P1 was not pre-empted when the short P2 arrived, so the routine is non-pre-emptive; then P2 was chosen ahead of P3 even though P3 arrived first, so the choice was by shortest burst: shortest job first. FCFS would have run P3 (arrived at 1) before P2. SRT would have pre-empted P1 at 2 ms, because P2's 2 ms is less than P1's 4 ms remaining. Round robin with a 4 ms slice would have stopped P1 at 4 ms.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.