Diagram Bank — 27 figures to redraw from memory
Visual revision bank

Every Diagram the Mid-Sem Can Ask, Drawn

Twenty-seven figures, each drawn as real inline SVG (no pictures to download, nothing that breaks offline), each followed by a short numbered recipe for reproducing it in the exam hall in under three minutes. Every figure is labelled with how likely it is to be asked, taken straight from the syllabus coverage matrix. Switch to dark mode — nothing here depends on colour alone, only on labels and stroke patterns.

The search box above filters the figures (each one is keyword-tagged). The priority and source chips exist for the question cards on the study pages; on this page use the likelihood column of the table below instead.

How to use this bankCover the picture, keep only the “How to draw this in exam” list, and redraw the figure on rough sheet from the steps alone. Then compare. A diagram is worth marks only if the labels and arrows are on it — a box with no arrow drawn on it is a box, not a diagram.

Contents — jump to a figure

27 figures
FigDiagramUnitLikelihood of being askedFull answer lives in
1Process state transition (5 states, 6 arrows)IVery high Nov-2023 Q.4(a) · Oct-2025 Q.2(a) · Jan-2024 Q.2(b)Unit I · Process states
2Extended seven-state diagram with suspended statesIHigh same syllabus point, textbook extensionUnit I · Process states
3Queueing diagram of process schedulingIVery high Jan-2024 Q.2(c) · Oct-2024 Q.1(e) · Dec-2024 Q.3(b)Unit I · Scheduling levels
4Three threading models (Many-to-One, One-to-One, Many-to-Many)ISafety May-2016 Q.1(e) asked M:1 vs 1:1 only; many-to-many never askedUnit I · Threading models
5Simple batch systemIHigh Jan-2024 Q.1(a) · Oct-2024 Q.4(b)Unit I · Batch vs time-sharing
6Multiprogramming in memoryIVery high Nov-2023 Q.1(a) · Oct-2024 Q.4(b) · Dec-2024 Q.2(c)Unit I · Multiprogramming
7Memory hierarchy pyramidIISafety not asked in the recent papers; May-June 2017 Q.1(e)Memory · Hierarchy
8MMU: logical 150 → physical 1150 with base and limitIIVery high Nov-2023 Q.1(c) · Dec-2025 Q.1(c)Memory · Logical vs physical
9Paging address translationIIVery high Oct-2024 Q.1(c) · Dec-2024 Q.5 · Oct-2025 Q.3(b)Memory · Paging
10Page table with valid/invalid bit, scattered framesIIVery high Dec-2025 Q.4(a) demand paging · Dec-2024 Q.5Memory · Demand paging
11Segmentation translation with d < limit checkIIVery high Jan-2024 Q.5(a) · Oct-2024 Q.1(c) · Oct-2025 Q.3(b)Memory · Segmentation
12Segmentation with paging (two-level mapping)IIVery high Jan-2024 Q.5(a) · Feb-2018 Q.3(a) · Jun-2019 Q.2(b)Memory · Segmentation + paging
13Contiguous allocation, variable partitions and holesIIHigh Oct-2025 Q.3(b) · Dec-2025 Q.5(a) first/best/worst fitMemory · Contiguous allocation
14Internal fragmentation in fixed 200K partitionsIIVery high Nov-2023 Q.1(b) · Oct-2024 Q.3(a) · Oct-2025 Q.1(e)Memory · Fragmentation
15External fragmentation before and after compactionIIVery high same fragmentation pair, always asked togetherMemory · Fragmentation
16Critical-section structure for two processesIIVery high Nov-2023 Q.3(a) · Oct-2024 Q.1(d) · Oct-2025 Q.1(b)synchronization.html · Critical section
17Producer–Consumer bounded circular bufferIIHigh Jan-2024 Q.4(a) · May-June 2018 Q.5(a)synchronization.html · Producer–Consumer
18Dining philosophers round tableIIVery high Nov-2023 Q.3(b) · Oct-2024 Q.3(b) · Oct-2025 Q.3(a) · Dec-2025 Q.5(b)synchronization.html · Dining Philosophers
19Sleeping barber shopIISafety not asked in either booksynchronization.html · Sleeping Barber
20Page-fault handling flowchartIIVery high Dec-2025 Q.4(a) · asked with every replacement questionMemory · Page fault
21Thrashing curve: utilisation vs degree of multiprogrammingIIVery high Nov-2023 Q.2(b) · Oct-2025 Q.1(d)Memory · Thrashing
22Overlay structure with an overlay driverIISafety Feb-2019 Q.2(b) onlyMemory · Overlays
23TLB plus page table: hit path and miss pathIIHigh Dec-2024 Q.5(c) · Jul-2016 Q.2(b) hit-ratio sumsMemory · TLB and EAT
24Context switch timeline with the overhead bandIVery high Jan-2024 Q.2(b) · Oct-2024 Q.2(a) · Oct-2025 Q.2(a)Unit I · PCB and context switch
25PCB in the process table, and what a switch movesIVery high process management with the PCB: Jan-2024 Q.2(b) · Oct-2024 Q.2(a)Unit I · PCB
26Shared memory versus message passingIVery high IPC: Jan-2024 Q.4(a) · May-2016 Q.4(a) · May-June 2018 Q.1(a)Unit I · Interprocess Communication
27Thread life-cycle (creation → ready → running → finished)IHigh thread states: Jan-2024 Q.1(b) · Feb-2018 Q.1(d)Unit I · Thread life-cycle

A. Processes, threads and system structure

Unit I
Fig 1 · Process state transition — five states, six labelled arrows
New just created Ready awaits the CPU Running holds the CPU Waiting / Blocked awaits an event Terminated PCB released 1 admitted 2 scheduler dispatch 3 interrupt / preemption 4 I/O or event wait 5 I/O or event completion 6 exit Ready has everything it needs except the CPU; Waiting cannot make progress even if the CPU is idle. Only one process is ever in Running — that single fact is why scheduling and synchronization exist at all.

Proves that a process cycles between Ready, Running and Waiting until it exits, and that the only arrow into Running is the dispatcher while the only arrow out of Running is one of interrupt, wait or exit. Likelihood: very high — Nov-2023 Q.4(a), Oct-2025 Q.2(a), Jan-2024 Q.2(b).

How to draw this in exam
  1. Three boxes across the top: New · Ready · Running. Two boxes below: Blocked (under Ready) · Terminated (under Running).
  2. Left to right along the top: “admitted”, then “scheduler dispatch”, and draw the return arrow back to Ready labelled “interrupt / preemption”.
  3. Diagonal from Running down to Blocked: “I/O or event wait”.
  4. Straight up from Blocked to Ready: “I/O or event completion”. Straight down from Running to Terminated: “exit”.
  5. Count the arrows — six labels. If you have five, you forgot preemption.
Fig 2 · Extended seven-state process diagram with the two suspended states
New in the job pool Ready in memory Running on the CPU Terminated gone Suspended-Ready on disk, can still never run Blocked waiting for event Suspended-Blocked swapped out AND blocked 1 admit 2 dispatch 3 interrupt / preemption 4 exit 5 I/O or event wait 6 I/O or event completion 7 suspend / swap-out medium-term scheduler 8 activate swap-in 9 suspend 10 event occurs while the process is swapped out The two suspended states are the ones the CPU can never reach directly: a swapped-out process must be brought back into memory by the medium-term scheduler first. Ready and Suspended-Ready both want the CPU; Blocked and Suspended-Blocked both want an event.

Proves that swapping adds two more states and four more transitions, and that the medium-term scheduler — not the CPU — is the only thing that can move a process in and out of memory. Likelihood: high; the five-state figure above is the version actually printed in the papers, this is the extension examiners use to test whether you memorised or understood.

How to draw this in exam
  1. Draw the normal five-state diagram first, then leave a clear row underneath it.
  2. Add two boxes in that lower row: Suspended-Ready under Ready, Suspended-Blocked to the right under Blocked. Hatching or a dashed border = “sits on disk”.
  3. Add exactly four arrows: Ready → Suspended-Ready “suspend”, Suspended-Ready → Ready “activate”, Blocked → Suspended-Blocked “suspend”, Suspended-Blocked → Suspended-Ready “event occurred”.
  4. Write beside the suspend pair: “medium-term scheduler (swap out / swap in)”.
Fig 3 · Queueing diagram of process scheduling — three schedulers, four queues
CPU P1 is executing now Ready queue in memory, want the CPU P2 P3 P4 P5 Waiting queue blocked on I/O P6 P7 P8 New queue job pool on disk J1 J2 J3 J4 Suspended queue — swapped out on disk neither in memory nor runnable; the memory copy of the PCB still exists P9 P10 P11 1 admitted by the long-term scheduler 2 dispatch short-term scheduler 3 interrupt / quantum expired 4 I/O request 5 I/O or event completed 6 suspend (swap-out) 7 activate (swap-in) 6 suspend (swap-out) 7 activate (swap-in) Long-term = “may I enter memory?” · Short-term = “who gets the CPU next?” · Medium-term = “who is thrown back out to disk?” Every box on the picture is a queue; every numbered line is a scheduling decision. The suspended pair uses dashed arrows because the papers ask medium-term scheduling far less often than the other two.

Proves the three levels of scheduling are three different decisions at three different frequencies, each attached to its own queue, and that the CPU is a resource rather than a queue. Likelihood: very high — Jan-2024 Q.2(c), Oct-2024 Q.1(e), Dec-2024 Q.3(b).

How to draw this in exam
  1. Put the CPU box top-centre (it is a resource, not a queue), and the ready queue bottom-left, waiting-for-I/O queue bottom-right.
  2. Draw the job pool at the top-left with a down arrow into the ready queue labelled “long-term scheduler: admit”.
  3. Ready → CPU up arrow “short-term scheduler: dispatch”; CPU → Ready down arrow “interrupt / quantum expired”.
  4. CPU → waiting queue “I/O request”; waiting → ready “I/O completed”.
  5. Add the suspended queue across the bottom and one swap-out and one swap-in arrow on each side, labelled “medium-term scheduler”.
Fig 4 · The three threading models side by side
Many-to-One user T1 user T2 user T3 kernel K1 many user threads : 1 kernel thread if one thread blocks, the whole process blocks; no real parallelism, so one core is wasted cheap to manage, library level only seen in early Solaris / classic POSIX pthreads One-to-One user T1 user T2 user T3 kernel K1 kernel K2 kernel K3 1 user thread : 1 kernel thread one thread blocking leaves the others runnable on other cores; true parallelism, but every thread creation is a system call — heavier, thread count may be capped by the kernel Linux NPTL, Windows Many-to-Many user T1 user T2 user T3 user T4 kernel K1 kernel K2 kernel K3 m user threads : n kernel threads the library multiplexes many user threads onto a smaller or equal number of kernel threads a blocking thread does not stop the process, and parallelism is possible the only model that needs a scheduler in BOTH layers — hardest to implement Read every panel the same way: user threads on the LEFT (managed by the thread library), kernel threads on the RIGHT (scheduled by the OS), and the arrows between them are the mapping — that mapping is the entire answer. Left column always 3 or 4 boxes; right column decides the model name.

Proves that the model name is just the ratio of user threads to kernel threads, and that blocking behaviour and parallelism follow from that ratio. Likelihood: safety for all three together — the older papers asked M:1 versus 1:1 (May-2016 Q.1(e)) and many-to-many has never been asked, but the syllabus lists it.

How to draw this in exam
  1. Rule three panels. In each, draw a left column of user-thread boxes and a right column of kernel-thread boxes.
  2. Panel 1: three left, ONE right, all arrows converging. Panel 2: three left, three right, straight one-to-one arrows. Panel 3: four left, three right, arrows criss-crossing.
  3. Under each panel write the trade-off in one line: blocked thread blocks all / independent but heavy / multiplexed, needs two schedulers.
  4. Never draw the kernel threads on the left — the arrow direction user → kernel is part of the mark.
Fig 5 · Simple batch system — one job at a time, no interaction
card J1 card J2 card J3 submitted OFFLINE (no terminal, no user) grouped One batch similar jobs, same language / same need J1 J2 J3 J4 the operator reads the whole batch in and hands the batch to the monitor resident monitor / FMS CPU strictly serial execution J1 J2 J3 J4 J1 leaves, J2 is loaded, and only then J3 — while J1 prints, the CPU sits idle Output line printer magnetic tape collected later by the operator MEMORY OF THE SYSTEM: the whole of it belongs to the single resident job — as soon as that job finishes, the monitor loads the next one What to write under the figure: (1) jobs are collected offline and grouped into batches by an operator; (2) one batch job owns the CPU and all of memory at a time; (3) the resident monitor is the first program to start and the last to leave — it is the ancestor of the modern OS; (4) there is NO user interaction, so turnaround is hours and low CPU utilisation follows directly from a job spending most of its life on card-reader or printer time.

Proves the defining weakness of a simple batch system: the CPU is idle whenever the one resident job is doing I/O, which is exactly the hole multiprogramming fills in the next figure. Likelihood: high — Jan-2024 Q.1(a), Oct-2024 Q.4(b).

How to draw this in exam
  1. Left: draw three punched-card shapes and write “offline, no user” under them.
  2. Arrow right into a big rounded box “Batch” containing four small job squares J1–J4.
  3. Label the next arrow “resident monitor (FMS)” and draw the CPU box with J1 J2 J3 J4 as four touching squares on one horizontal time line.
  4. Arrow out to a printer/tape box, then one line: “while job I/O runs the CPU is idle — low utilisation, no interaction”.
Fig 6 · Multiprogramming — several processes resident, one on the CPU
Main memory P1 blocked on the printer cannot use the CPU even if free P2 RUNNING on the CPU the only process executing P3 ready — wants the CPU next to be dispatched P4 blocked on disk I/O free memory left over Operating system (low memory) interrupt vectors · scheduler · drivers CPU executes P2 right now dispatch P2 asks for I/O, CPU goes to P3 Printer slow device, serving P1 Disk serving P4's read device interrupt on completion → P4 becomes ready Degree of multiprogramming here = 4 (three processes in memory plus one on the CPU). The OS keeps raising it until the CPU is busy, and lowers it when memory runs out — that trade is the whole point of a multiprogrammed batch system.

Proves the mechanism behind the phrase “keeps the CPU busy”: with two or more processes packed into memory, an I/O block by one hands the CPU to another instead of idling it. Likelihood: very high — Nov-2023 Q.1(a), Oct-2024 Q.4(b), Dec-2024 Q.2(c).

How to draw this in exam
  1. Draw one tall rectangle labelled “main memory” and shade the bottom strip as the resident OS.
  2. Stack four blocks above it: P1, P2, P3, P4. Mark P2 with a heavier border as the running one.
  3. Put the CPU box outside on the left and draw one solid arrow from P2 to it, plus a dashed return arrow labelled “P2 does I/O → give CPU to P3”.
  4. Draw printer and disk boxes on the right and dashed lines from P1 and P4 to them.
  5. Write one line under the figure: “CPU idle time falls as the degree of multiprogramming rises”.

B. Memory structure, addresses and allocation

Unit II
Fig 7 · Memory hierarchy pyramid — speed, size, cost per bit
1 2 3 4 5 1 Registers flip-flops inside the CPU · < 1 cycle · tens of bytes · dearest per bit 2 Cache (L1/L2/L3) SRAM on the CPU die · a few cycles · KB to MB · hardware managed 3 Main memory DRAM · tens to hundreds of ns · GB · the largest store the CPU can address 4 Disk / SSD magnetic or flash · milliseconds · hundreds of GB · backing store for paging 5 Tape / optical sequential archival media · minutes · TB · offline, cheapest per bit faster · smaller · costlier per bit bigger · slower · cheaper per bit The pyramid only works because of locality: a program keeps returning to a small, nearby region of memory, so a tiny fast level can answer most references while the cheap slow level supplies the capacity. Levels 1–3 are addressed directly; 4–5 are not.

Proves the three-way trade-off — you can have speed, size or price, so the OS stacks all three and hides the stack behind locality. Likelihood: safety as a standalone figure (not asked in 2023–2025; May-June 2017 Q.1(e) asked cache versus main memory instead), but it is the backdrop for paging, TLB and virtual memory.

How to draw this in exam
  1. Draw a triangle and slice it into five horizontal bands.
  2. Name them from the apex down: Registers · Cache · Main memory · Disk · Tape.
  3. Left edge: an upward arrow “faster, smaller, costlier per bit”; below it a downward arrow “bigger, slower, cheaper”.
  4. On the right of each band write carrier, access time and size — three words each.
  5. Close with one line: “the hierarchy works because of temporal and spatial locality”.
Fig 8 · MMU translation — logical 150 becomes physical 1150
CPU emits logical 150 Base register 1000 Limit register 400 MMU legality test: 150 < limit? then add base: 1000 + 150 logical 0 .. 399 physical 1150 if logical ≥ limit Addressing-error trap mode bits + limit = protection Main memory other processes above 1400 this process, 1000 – 1399 1150 lands here the same program at a different base gives a different physical range OS resident, 0 – 999 cannot be touched by 150 1400 1000 0 two jobs, one piece of hardware: base gives RELOCATION limit gives PROTECTION the sum is done in hardware, every memory reference, no exceptions The program itself still contains 150 — it is compiled and linked against a zero origin. Only the value on the wires into DRAM changes. Runtime binding is what makes this possible: the base is loaded by the OS at the moment the process is given memory.

Proves that logical and physical addresses are two different numbers for the same byte, and that one comparison against the limit register is what stops a process reaching outside itself. Likelihood: very high — Nov-2023 Q.1(c), Dec-2025 Q.1(c).

How to draw this in exam
  1. Three boxes in a row: CPU → MMU → Main memory, arrows left to right.
  2. Write “logical 150” on the first arrow and “physical 1150” on the second.
  3. Drop two small boxes above the MMU, Base = 1000 and Limit = 400, each with an arrow into the MMU.
  4. Inside the MMU write the two operations: “is 150 < limit?” then “1000 + 150”.
  5. Add a dashed branch out of the MMU to a trap box, and in memory draw the process block 1000–1399 with 1150 marked inside it.
Fig 9 · Paging address translation — page number in, frame number out
Logical address (what the CPU holds) page number p = 2 offset d = 10 logical = p × page size + d = 2 × 200 + 10 = 410 p is the index — not an address offset d passes straight through, untouched index frame no. valid 0 3 1 1 7 1 3 1 0 2 6 1 page table of this process — kept in main memory by the OS frame f Physical address (what memory sees) frame number f = 6 offset d (same 10) = 10 physical = f × frame size + d = 6 × 200 + 10 = 1210 frame size must equal page size Main memory F0 F1 · P3 F2 F3 F4 F5 F6 F7 free two fields, one hardware split: the high bits index the table, the low bits are copied across

Proves that paging turns “where does this address point” into a table lookup whose output is a frame number, and that the offset never changes — which is why page size and frame size must be equal. Likelihood: very high — Oct-2024 Q.1(c), Dec-2024 Q.5(a)(b)(c), Oct-2025 Q.3(b).

How to draw this in exam
  1. Draw the logical address as one bar split in two: page number | offset.
  2. Arrow down from the page number into a page table drawn as rows of (index, frame, valid); highlight the row you used.
  3. Draw the offset as a dashed line that sails past the table and lands on the right-hand half of the physical bar.
  4. Arrow from the highlighted frame value into the left half of the physical bar: frame number | offset.
  5. Finish with the formula under the picture: physical = f × frame size + d, and one line “page size = frame size”.
Fig 10 · Page table with the valid/invalid bit — four pages, four scattered frames
Logical pages page 0 bytes 0–199 page 1 bytes 200–399 page 2 bytes 400–599 page 3 bytes 600–799 the program sees 4 adjacent pages — one continuous address space Page table of this process page valid bit frame prot 0 1 5 RW 1 1 2 RW 2 1 7 RO 3 0 — — valid 1 = has a frame · valid 0 = not in memory at all 4 pages need only 4 small frames; nothing has to be adjacent Main memory (8 frames) F0 — free F2 holds page 1 F3 — free F4 — free F5 holds page 0 F6 — free F7 holds page 2 P1 P0 P2 page 3 is on the backing store referencing it = page fault page 0 → F5, page 1 → F2, page 2 → F7: three frames in three unrelated places, and the program still runs normally. Read the table as the definition of non-contiguous allocation: the pages stay logically adjacent, the frames need not be, and the table is what re-stitches them.

Proves two things at once: physical addresses need not be adjacent (external fragmentation is gone), and the valid bit is the single switch that separates simple paging from demand paging. Likelihood: very high — Dec-2025 Q.4(a), Dec-2024 Q.5, Oct-2024 Q.1(c).

How to draw this in exam
  1. Three columns: pages on the left, page table in the middle, frames on the right.
  2. Draw the table with four columns — page, valid bit, frame number, protection.
  3. Map the pages deliberately out of order: page 0 → frame 5, page 1 → frame 2, page 2 → frame 7, and draw thin crossing lines.
  4. Give the last page valid bit 0, frame blank, and a dashed line down to a hatched “on disk” box.
  5. Say the sentence: “a 0 here does not mean an error — it means a page fault”.
Fig 11 · Segmentation — segment number, offset, and the d < limit test
Logical address (user-visible pair) segment number s = 1 offset d = 200 s indexes the segment table seg base limit valid 0 1400 512 1 1 3000 400 1 2 800 1000 1 3 5200 256 1 variable-length segments, one row each — the table is the address space limit d < limit 200 < 400? yes no — d ≥ limit Segmentation fault illegal reference, OS traps offset d goes to the adder unchanged base + offset 3000 + 200 = 3200 no division, no masking — one addition Physical memory free S0 base 1400 hole S1 base 3000 3200 is here hole 3400–8000 S2 base 800 (lowest address, highest number) hole S3 base 5200 Segmentation is the user’s view of memory: code, data, stack, symbol table — each its own segment with its own length and its own protection bits. Because segments are variable length, holes appear between them: segmentation suffers EXTERNAL fragmentation, never internal. The limit register is the difference from paging: d < limit is both the bounds check and the protection mechanism.

Proves that a segment address is a pair chosen by the programmer, that physical = base + offset with no arithmetic split of the address, and that the limit test is what makes an out-of-range pointer a trap rather than another process’s data. Likelihood: very high — Jan-2024 Q.5(a), Oct-2024 Q.1(c), Oct-2025 Q.3(b). The worked numbers (1, 200) → 3200 are the same ones used on Memory Management · Segmentation.

How to draw this in exam
  1. Logical bar split segment-number | offset, then a table underneath with columns seg, base, limit, valid.
  2. Arrow from the segment number down into the table row; arrow out of that row into a diamond that says “d < limit?”.
  3. From the diamond draw two paths: “no” down to a fault box, “yes” right into an adder box writing base + offset.
  4. Draw the offset with a dashed line that skips the table and enters the adder directly — it must not be altered.
  5. On the right, draw memory as scattered blocks S0, S1, S2, S3 with holes between them, and mark the resulting physical address inside the block it belongs to.
Fig 12 · Segmentation with paging — segment table → page table → frame
Logical address — three fields segment no. s = 1 page no. p = 2 offset d = 5 s picks the segment seg page-table base length v 0 PT0 @ 4000 8 pg 1 1 PT1 @ 5000 5 pg 1 2 PT2 @ 6000 3 pg 1 one page table PER SEGMENT — that is the whole idea base of PT1 p indexes inside that segment’s page table p frame valid 0 8 1 1 3 1 2 7 1 page table of segment 1 only frame f = 7 Physical address frame f = 7 offset d = 5 d copied unchanged physical = f × page size + d Main memory F0 F1 F2 F3 · S0 pg F4 F5 F6 F7 S1 p2 Two levels of table — segment, then page, then frame: up to three lookups per reference, which is why this scheme is always paired with a TLB (Fig 23). Why it exists: pure segmentation leaves external holes; pages are fixed size, so even a segment can be scattered. Worked field widths, Jun-2019 Q.2(b): 8 segments, 256 B pages, a 2²⁹ B segment ⇒ segment 3 + page 21 + offset 8 = 32 bits total.

Proves the hybrid keeps the programmer’s logical view (segments, protection, sharing) while the machine’s view becomes fixed-size pages — which is exactly how the external-fragmentation problem of pure segmentation is removed. Likelihood: very high — Jan-2024 Q.5(a), Feb-2018 Q.3(a), Jun-2019 Q.2(b). See Memory Management · Segmentation with paging.

How to draw this in exam
  1. Logical bar with THREE fields: segment number · page number · offset. Getting the field count right is half the mark.
  2. Segment number drops into the segment table; write the middle column as “page-table base”.
  3. Draw a second table to its right — “page table for that segment only” — and feed it the page number.
  4. Its output is a frame number; concatenate frame ‖ offset, and let the offset sail past both tables on a dashed line.
  5. Close with memory at the bottom showing the segment’s pages in unrelated frames, and one line: “segmentation visible to the user, paging visible only to the OS”.
Fig 13 · Contiguous allocation with variable partitions — where each process landed
Main memory — one block each free 10 MB HOLE 8 MB @ 110 P3 — 12 MB loaded at 98 HOLE 4 MB @ 94 P2 — 30 MB loaded at 60 HOLE 10 MB @ 50 P1 — 25 MB loaded at 25 HOLE 5 MB @ 20 OS — 20 MB resident, low memory 0 20 25 50 60 90 98 110 118 120 MB address (MB) → A new process asks for 12 MB • first fit → first hole big enough scanning from low address = the 10 MB hole? too small, so the 8 MB hole? too small → it fails, and the OS must wait or suspend someone • best fit → smallest hole ≥ 12 MB → none exists · worst fit → largest hole → still none 22 MB is free on this picture, but the biggest single hole is 10 MB — that gap between “free” and “usable” is external fragmentation Rules this allocation scheme obeys • a process gets ONE consecutive run of addresses — no tables, no scattering • partitions are variable: they are exactly as large as the process, hence “dynamic” • when a process leaves, its block becomes a hole; adjacent holes merge into one bigger hole • the OS keeps a table of free blocks and chooses first / best / worst fit from it • internal fragmentation is NIL here — the block was cut to fit the process What to write next to the figure Fixed partitions waste the tail of every block (internal). Variable partitions waste the gaps between blocks (external). Contiguous allocation of either kind eventually needs compaction, and compaction costs as much CPU time as running a process — which is the argument that pushes you into paging.

Proves that in contiguous allocation the placement decision is “which hole”, the holes accumulate as processes come and go, and total free space can be adequate while still being unusable. Likelihood: high as a picture; the first/best/worst-fit decision on it is very high — Dec-2025 Q.5(a), Jul-2023 Q.2(b). See Memory Management · Contiguous allocation.

How to draw this in exam
  1. Draw one tall rectangle, mark 0 at the bottom and the memory size at the top.
  2. Shade the bottom strip as the resident OS, then alternate process blocks and hatched holes going up.
  3. Write the size and the start address inside every block — P1 25 MB @ 25, P2 30 MB @ 60, P3 12 MB @ 98.
  4. Add a request box: “new process needs X MB”, then show the largest hole is smaller than X.
  5. Finish with one sentence naming the disease: external fragmentation, cured by compaction or paging.
Fig 14 · Internal fragmentation — fixed 200K partitions, a 180K process
Fixed partitioning — every partition is exactly 200K 0K 200K 400K 600K 800K partition 1 · 0–200K 20K — wasted P1 — asked for 180K got the whole 200K partition partition 2 · 200–400K 110K — wasted no other process may be placed inside it P2 — 90K partition 3 · 400–600K P3 — exactly 200K waste = 0K the only clean case partition 4 · 600–800K empty NOT fragmentation — wholly free, the OS may load a new process here wasted inside already-allocated partitions: 20K + 110K = 130K Definition to write: internal fragmentation is the difference between the memory ALLOCATED to a process and the memory it REQUESTED. It is invisible to the process and unrecoverable by the allocator — the cure is to shrink the allocation unit: smaller partitions, buddy splitting, or paging.

Proves the wasted bytes are inside a block that has already been handed over, so no allocator can ever reuse them — the reason fixed partitioning is abandoned for paging. Likelihood: very high — Nov-2023 Q.1(b), Oct-2024 Q.3(a), Oct-2025 Q.1(e), always paired with the next figure. See Memory Management · Fragmentation.

How to draw this in exam
  1. Draw four equal boxes in a row and label the address scale under them: 0, 200K, 400K, 600K, 800K.
  2. In box 1 fill 180K of the 200K with P1 and hatch the remaining 20K at the top, writing “wasted”.
  3. Give box 2 a 90K process with a big hatch, box 3 an exact 200K process (no waste) and leave box 4 empty but NOT hatched.
  4. Bracket the hatched regions and total them: 20 + 110 = 130K.
  5. Write the one-line definition — allocated minus requested — and the cure in one more line.
Fig 15 · External fragmentation — before and after compaction (both halves)
BEFORE — holes everywhere free 3 @57 HOLE 6 MB @51 P5 — 11 MB start 40 HOLE 4 @36 P3 — 9 MB start 27 HOLE 5 @22 P1 — 12 MB start 10 OS — 10 MB pinned in low memory 0 60 MB New process needs 8 MB ✗ no single hole is big enough — 6 < 8 free memory = 5 + 4 + 6 + 3 = 18 MB ≥ 8 MB, yet the request is refused COMPACTION slide every process toward one end so the holes merge cost: relocating every byte + rewriting every absolute address = CPU time stolen AFTER — one big hole ONE HOLE 18 MB @ 42 8 MB fits here, 10 MB still free P5 — 11 MB moved from 40 → 31 P3 — 9 MB moved from 27 → 22 P1 — 12 MB moved from 10 → 10 OS — 10 MB never moves the same process, now lower down 8 MB admitted now External fragmentation = enough TOTAL free memory, but not CONTIGUOUS. It is fixed by compaction (slow), or avoided by paging (the OS stops needing blocks to be adjacent).

Proves the difference between “free” and “usable”, and that compaction trades CPU time for contiguity — the exact comparison the internal-versus-external question is built to test. Likelihood: very high — Nov-2023 Q.1(b), Oct-2024 Q.3(a), Oct-2025 Q.1(e).

How to draw this in exam
  1. Draw two identical vertical memory bars, one labelled BEFORE and one AFTER, with 0 at the bottom.
  2. In the first, stack OS, P1, hole, P3, hole, P5, hole — small hatched holes between every pair of processes.
  3. Write under it: “free = 18 MB, biggest hole = 6 MB, request = 8 MB → refused”.
  4. Draw a fat labelled arrow “compaction” pointing to the second bar.
  5. In the second bar push OS, P1, P3, P5 all down to the bottom and leave one 18 MB hatched hole at the top, with the 8 MB process admitted into it.

C. Synchronization diagrams

Unit II
Fig 16 · Critical-section structure — the same loop running in two processes
Process P0 Process P1 entry section wait / test the flag or turn CRITICAL SECTION reads / writes shared data exit section signal / release the lock remainder section nothing shared, no rules do { … } while (TRUE) entry section wait / test the flag or turn CRITICAL SECTION same shared data exit section signal / release the lock remainder section no shared data touched shared data count concurrent access CS(P0) ∩ CS(P1) = ∅ when P0 is inside its critical section, P1 must be held in its ENTRY section — it may not be stopped in the remainder, because it may already be on its way in the entry / exit pair is where the algorithm lives 1 · Critical-section condition two processes must never be executing in their critical sections at the same time 2 · Progress if no one is inside and someone wants in, that request must be granted — the remainder section cannot veto it 3 · Bounded waiting a bound on how many others may go in first, so no requester starves (aging is the scheduling twin of this) Draw the four blocks, then the loop arrow, then the second identical column. The picture IS the definition: entry and exit are the protocol, the critical section is the crime scene. Race condition = the same two columns with no entry/exit section, so both update count from the same stale register value.

Proves that mutual exclusion is enforced in the entry section, released in the exit section, and that the remainder section is irrelevant to the protocol — which is exactly what the three requirements are phrased around. Likelihood: very high — Nov-2023 Q.3(a), Oct-2024 Q.1(d), Oct-2025 Q.1(b).

How to draw this in exam
  1. Write the loop once: do { entry; critical; exit; remainder } while(TRUE) — then draw it as four stacked boxes.
  2. Add the loop-back arrow from remainder to entry and label it while (TRUE).
  3. Draw the identical column beside it, and one shared-data box between the two critical sections with arrows in both directions.
  4. Shade the space between the two critical sections and write CS₀ ∩ CS₁ = ∅.
  5. List the three requirements under the picture — progress and bounded waiting are the two most-marked.
Fig 17 · Producer–Consumer with a bounded circular buffer (n = 6)
bounded buffer n = 6 slots slot 0item slot 1item slot 2free slot 3free slot 4free slot 5free Producer wait(empty); wait(mutex); buffer[in] = item; in = (in + 1) % n; signal(mutex); signal(full); one buffer, many writers Consumer wait(full); wait(mutex); item = buffer[out]; out = (out + 1) % n; signal(mutex); signal(empty); consumes in FIFO order writes at in reads at out in → next FREE slot out → oldest ITEM empty = 4 (counting) free slots. producer waits on it, consumer signals it. empty = 0 → buffer FULL → producer sleeps full = 2 (counting) items present. consumer waits on it, producer signals it. full = 0 → buffer EMPTY → consumer sleeps mutex = 1 (binary) protects the buffer indices themselves — in and out are shared variables too. wait(mutex) must come before wait(empty) Invariant to write under the figure: empty + full = n always; mutex never exceeds 1; and the two waits must come before the two signals. Swapping the order — wait(mutex) then wait(empty) — is the classic deadlock answer: the producer holds mutex and sleeps on a full buffer. Unbounded version: no empty semaphore, no waiting, and the buffer grows without limit.

Proves the buffer is a ring whose two pointers never meet except through the two counters, and that overflow and underflow are simply “counter reached zero”. Likelihood: high — Jan-2024 Q.4(a) (inside the IPC answer), May-June 2018 Q.5(a).

How to draw this in exam
  1. Draw six circles in a ring and join them with thin lines; number them 0 to 5.
  2. Fill two of them (items present), leave four empty; mark n = 6 in the middle.
  3. Put an in arrow at the first free slot and an out arrow at the oldest item — arrowheads on the ring.
  4. Producer box on the left with its six statements, Consumer box on the right with its six.
  5. Below, three small boxes: empty = 4, full = 2, mutex = 1, and one line saying which process waits on which.
Fig 18 · Dining philosophers — five seats, five chopsticks, one bowl
round table, seen from above bowl of rice plate 0 plate 1 plate 2 plate 3 plate 4 1 2 3 4 5 P0 P1 P2 P3 P4 hungry left right chopstick 5 is P0's LEFT and P4's RIGHT — one stick, two owners, that is the whole problem Each chopstick is one binary semaphore. Eating needs BOTH, held at the same time. Rules to write: · a philosopher thinks or eats, never both · eating needs chopsticks i and (i+1) mod 5 · sticks are picked one at a time and put down one at a time Deadlock if all five pick LEFT first hold it and wait for the right one: circular wait, the 4th Coffman condition Fixes to list: limit the table to four · pick both sticks atomically inside a mutex · make P4 pick right first

Proves the table is a ring of resources in which each item is claimed by two neighbours, so a uniform pickup order produces circular wait. Likelihood: very high — Nov-2023 Q.3(b), Oct-2024 Q.3(b), Oct-2025 Q.3(a), Dec-2025 Q.5(b); also asked in the older papers four times.

How to draw this in exam
  1. Draw a big circle (the table) and a small ellipse in the middle (the bowl).
  2. Place five plates as a pentagon inside the circle, and five squares outside it as the seats P0–P4.
  3. Put one short thick line between every adjacent pair of plates and number the sticks 1–5.
  4. From one philosopher draw two arrows, labelled left and right, to its two sticks — show the pickup order.
  5. Write the deadlock line (all pick left → circular wait) and one or two of the three fixes.
Fig 19 · Sleeping barber — one server, N waiting chairs, an infinite source
The shop barber asleep — blocked on the customers semaphore "Z z z" chair 1 chair 2 empty N waiting chairs = the bounded buffer waiting-room counter count = 2 of N = 3 door arriving customer another and more — unbounded source shop full → customer leaves without waiting mutex = 1 (binary) protects the shared count, so two arrivals cannot both take the last chair customers = 0 (counting) how many are waiting. The barber waits on it and sleeps at 0; each arrival signals it once. barber = 0 (counting) how many are ready to be served. The customer waits on it — this is the handshake that wakes the barber. BARBER loop wait(customers) → wakes up, takes a customer from the chairs, cuts the hair, signal(barber) CUSTOMER wait(mutex): if count < N → count++, signal(customers), wait(barber); else signal(mutex), leave

Proves this is the bounded-buffer problem with one server: N chairs bound the waiting side, and the barber and each customer block on opposite counters, which is why a condition-style handshake is needed. Likelihood: safety — not asked in either book, but it is the classic named problem in the syllabus line “other classical synchronization problems”.

How to draw this in exam
  1. Draw a dashed room. Inside it, one barber chair at the left with an asleep barber, then a row of N chairs.
  2. Add a counter box on the wall (“count = number seated”) and a door in the right wall.
  3. Arrows in from a crowd of arriving customers; one dashed arrow back out labelled “shop full → leaves”.
  4. Under the room draw the three semaphore boxes: mutex = 1, customers = 0, barber = 0, one line each.
  5. State the two loops in three lines apiece, and note the equivalence to producer–consumer with one consumer.

D. Virtual memory and demand paging

Unit II
Fig 20 · Page-fault handling — from reference to restarting the instruction
1 · CPU references a virtual (logical) address 2 valid bit = 1? page in memory? yes — no fault 3a translate with the page table, access the frame, continue cost = ordinary memory access no — page fault 3b trap to the OS page-fault handler the process is blocked from here on 4 legal reference? if not, kill the process else locate the page on the backing store 5 free frame available? yes 6a take a frame from the free-frame list — nothing to evict no — memory is full 6b pick a VICTIM page — FIFO / LRU / Optimal if the victim's modified bit is 1, write it back to disk first; clear the OLD process's entry both branches merge here 7 read the needed page into that frame disk → memory: the expensive step 8 update the page table: frame number + valid bit = 1 9 RESTART the faulted instruction back to step 1 — this time the page is there Steps 3b–7 run in kernel mode; the CPU is given to another process while the disk read is in progress (Fig 1, Fig 6). Restart, not resume: the instruction runs again from the saved PC, which is why paging is invisible to the program. Hard (major) fault = the disk read is genuinely needed. Soft (minor) fault = the page is already in memory and only the table entry needs fixing. Sequence a marker looks for: trap → locate → frame → load → table → restart.

Proves demand paging is a trap-driven loop — the process is blocked while the disk runs, and the instruction is restarted rather than continued, which is what lets paging be invisible to the program. Likelihood: very high — the backbone of Dec-2025 Q.4(a) and of every page-replacement question.

How to draw this in exam
  1. Start with a rounded box “CPU references a virtual address”, then a diamond “valid bit = 1?”.
  2. Yes → a short side box “translate and continue”. No → straight down.
  3. Down the spine: trap to the OS → find the page on the backing store → diamond “free frame?”.
  4. Yes → allocate; No → pick a victim (name FIFO/LRU/Optimal) and write it back if modified; merge both into “read the page in”.
  5. Then “update the page table, set valid = 1”, end at “RESTART the instruction”, and draw the feedback arrow back to the top.
Fig 21 · Thrashing — CPU utilisation collapses past the optimum degree
75% 50% 0% 100% page-fault rate rises CPU utilisation rising: every new process still has enough frames to work in THRASHING REGION each process holds too few frames for its locality set, so the fault rate climbs, the paging device saturates and the CPU waits for pages instead of waiting for processes optimum degree of multiprogramming maximum CPU utilisation — the peak is the answer degree of multiprogramming → CPU utilisation → adding a process here REDUCES utilisation — the counter-intuitive half of the definition

Proves the reversal: past the optimum, more processes means less work, because the paging device — not the CPU — is the bottleneck. The remedy to write beside it: reduce the degree of multiprogramming (suspend processes) and let the survivors keep their working set. Likelihood: very high — Nov-2023 Q.2(b), Oct-2025 Q.1(d), plus four older papers. See Memory Management · Thrashing.

How to draw this in exam
  1. Axes: y = CPU utilisation (0–100%), x = degree of multiprogramming.
  2. Draw a curve that climbs to a rounded peak about halfway along, then falls steeply and flattens near zero.
  3. Drop a dashed vertical line from the peak to the x-axis and label it “optimum degree”.
  4. Hatch everything right of that line and write THRASHING REGION inside it.
  5. Add one upward dashed curve for the page-fault rate — it shows WHY the utilisation curve falls.
Fig 22 · Overlays — one fixed overlay area, mutually exclusive segments
Memory available to this job (fixed) root program + data always resident — never swapped COMMON module used by EVERY overlay, so it stays in OVERLAY AREA — one segment at a time OV3 loaded right now because the root just called a routine in it OV1, OV2, OV4, OV5 cannot coexist with it: mutually exclusive by construction size of the overlay area = the LARGEST segment, not the sum of them all The program as built, on disk backing store — the whole job OV1routines 1–26 OV2routines 27–40 OV341–60 · in memory OV4routines 61–88 OV5routines 89–120 COMMONalready resident the programmer groups routines that are never needed together — the grouping itself is the design work load discard no write-back: overlays are read-only code, never modified Overlay table + overlay driver call 1–26 → load OV1 into the overlay area call 41–60 → already resident, jump straight in call 89–120 → overwrite OV3 with OV5, then jump the driver is a few lines of the program's own code, not an operating-system service Overlays versus virtual memory — the sentence that gets the mark: in overlays the PROGRAMMER decides the division and loading is triggered by a CALL; in demand paging the HARDWARE and OS decide it and loading is triggered by an ADDRESS. No page table, no TLB, no page-fault trap here. Both let a program be larger than physical memory; only paging does it transparently.

Proves the trick is a single shared scratch region plus a table the program consults before every cross-segment call — manual virtual memory, defined by the programmer. Likelihood: safety — Feb-2019 Q.2(b) is the only sighting; know the picture and the contrast sentence. See Memory Management · Overlays.

How to draw this in exam
  1. Draw one memory box divided into three: root/data at the top, a COMMON band, then one OVERLAY AREA.
  2. Put the current overlay segment inside the overlay area and nothing else.
  3. Draw a second box for the disk holding OV1…OV5 plus the common part.
  4. Add a curved “load” arrow from a disk segment into the overlay area and a dashed “discard” arrow back out.
  5. Finish with a small call-number → segment table and one line: programmer-defined, call-triggered, no page table.
Fig 23 · TLB plus page table — the hit path and the miss path
Logical address page number p = 1 offset d = 20 searched in hardware TLB — associative, 8–64 entries p 0 → f 3 p 1 → f 7 · HIT p 2 → f 6 p 3 → f 1 checked before any page-table access HIT path MISS: drop to the page table Page table — lives in MAIN MEMORY index 0 · f 3 · v 1 index 1 · f 7 · v 1 ← the entry we need index 2 · f 6 · v 1 index 3 · f 1 · v 0 f found, then reload the TLB Physical address frame f = 7 offset d (copied) = 20 both paths arrive here Main memory F3 · F4 · F5 · F6 F7 — page 1 sits here; word at offset 20 read F8 · F9 … the frame table tracks the rest Times TLB search = 20 ns 1 memory access = 100 ns HIT 20 + 100 = 120 ns MISS 20 + 100 (table) + 100 (the word) = 220 ns EAT, h = 0.8 0.8(120)+0.2(220) = 140 ns Why the TLB exists: paging already doubles every access — one to read the page table, one to read the word. The TLB is a small, fast, fully associative cache of hot page-table entries that removes the second access on the common path. It is flushed on a context switch, or tagged with an address-space id, because its entries belong to one process's page table.

Proves the hit path costs one memory access while the miss path costs three operations, and that the hit ratio alone decides which one dominates the effective access time. Likelihood: high as a diagram, very high as a numerical — Dec-2024 Q.5(c), Jul-2016 Q.2(b), Feb-2019 Q.3(a). See Memory Management · TLB.

How to draw this in exam
  1. Draw the logical bar (p | d), then the TLB box directly under it with four p → f rows.
  2. Solid arrow out of the TLB to the right into the physical bar (f | d), labelled HIT.
  3. Draw the page table under the TLB, a dashed arrow down into it, and a second dashed arrow back up into the same physical bar, labelled MISS.
  4. Mark one TLB row as the matching entry (double rule or shade it).
  5. Add a narrow side column with the two cost lines (t + m, t + 2m) and the EAT formula.

E. Dispatch level

Unit I
Fig 24 · Context switch timeline — the band that produces nothing
One switch, drawn on a time axis (left to right) Process A executing — useful work trap / IRQ save A's context PC, SP, registers, state → Ready load B's context PC, SP, registers, state → Running Process B executing useful work resumes — page-table base and TLB may change too OVERHEAD — nothing the user asked for save + load + dispatcher code + mode switch typical magnitude: hundreds of ns to a few µs PCB of A written: state, PC, registers, stack pointer PCB of B read: the same fields, saved at its last switch-out write read t0 t1 interrupt t2 t3 t4 time → the hatched window t2 → t3 is the whole cost of the switch Not free either: TLB flush or address-space-tag switch, and re-reading the page-table base register. Consequence to write: as the quantum approaches the switch time the CPU spends its life switching — hence “keep the quantum much larger than the context-switch time”, the Round Robin rule of thumb.

Proves a context switch is pure overhead: the CPU is busy but no process advances, and the only work done is one write to a PCB followed by one read from another. Likelihood: very high — Jan-2024 Q.2(b), Oct-2024 Q.2(a), Oct-2025 Q.2(a). See Unit I · PCB and context switch.

How to draw this in exam
  1. Draw a horizontal time axis and a block for A running at the left end.
  2. Add a narrow trap/IRQ block, then two hatched blocks: “save A into PCBA”, “load B from PCBB”.
  3. Close with B running at the right, and bracket the two hatched blocks as OVERHEAD above the axis.
  4. Put the two PCB boxes above and connect them: an arrow into PCBA (write) and one out of PCBB (read).
  5. Tick t0–t4 under the axis and write the one-line consequence about the quantum.

F. More Unit I pictures worth having

Unit I
Fig 25 · PCB in the process table, and what a context switch moves
Operating system (kernel) process table PCB — P1 PCB — P2 PCB — P3 one PCB · process state · process ID · program counter · CPU registers · memory management info · scheduling info (priority) · accounting info · I/O status, open files CPU registers next process 1 save out 2 restore in A context switch is just these two arrows. The PCB is the only thing that makes a suspended process resumable, which is why it is the single most asked diagram of Unit I.

Draw this whenever the question says “explain PCB” — the field list alone is only half the marks; showing where the PCB sits and what moves through it is the other half.

How to draw this in exam
  1. Draw a “kernel” box with a “process table” box under it holding three stacked PCBs.
  2. Expand one PCB as a tall rectangle listing its eight fields.
  3. Add a CPU-registers box on the right with an arrow into the PCB labelled “save”.
  4. Add a second arrow out of the PCB to a “next process” box labelled “restore”.
Fig 26 · Shared memory versus message passing
Shared memory Process A Process B Shared Memory 1 write 2 read kernel only maps the region — data never re-enters it Message passing Process A Process B Kernel copy · queue · synchronise 1 send() 2 receive() every exchange is a system call and a copy

The whole trade-off in one picture: shared memory is faster for bulk data but pushes the synchronisation problem onto you; message passing is slower but the OS gives you mutual exclusion free.

How to draw this in exam
  1. Split the page in two and title the halves.
  2. Left: two process boxes with arrows into one shared box between them.
  3. Right: two process boxes with arrows going down into and up out of a kernel box.
  4. Write one caption line under each half saying where the copying happens.
Fig 27 · Thread life-cycle (the five-state version the Jan-2024 paper wants)
CREATION READY RUNNING FINISHED resources dispatch complete WAITING DELAYED BLOCKED external event sleep / snooze I/O request All three lower states eventually return to READY — never straight to RUNNING. DELAYED is the state the process/thread answer adds for a timed sleep; BLOCKED is specifically for I/O.

Note the difference from the process diagram: a thread has DELAYED, and it has no SUSPENDED state, because a thread cannot be swapped out on its own.

How to draw this in exam
  1. Draw four boxes in a straight line: Creation, Ready, Running, Finished.
  2. Hang Waiting, Delayed and Blocked below Running.
  3. Arrow each of the three down from Running, and dashed arrows back to Ready.
  4. Label the downward arrows external event, sleep or snooze, and I/O request.

Diagram Practice Checklist

Track

One line per figure. Cover the picture, redraw it from the “How to draw this in exam” steps on a rough sheet, then tick only if the labels and arrows match. Ticks are saved in this browser and feed the dashboard progress.

Exam tipDiagrams earn marks for labels, not artwork. Use a ruler, keep every box axis-aligned, write arrow text beside the arrow rather than inside it, and put one sentence under the figure saying what it proves — that sentence is usually the marking point the picture is supposed to carry. If you run out of time, draw the boxes and arrows first and the decoration never.