Final pass

Revision & Formula Sheet

Everything on this page is derived from the six 2023–2025 papers plus the older ETCS-304 papers in your two books. Priority comes from how often a topic was actually asked — there are no invented probability percentages anywhere on this site.

1. Most Important Questions

Ranked by PYQ evidence

Each line shows the evidence that put it in that tier. Tick a line only after you can write it out cold in the time its marks allow.

Very high Asked repeatedly across the six recent papers

High Asked once or twice in the recent papers

Cover for safety In your syllabus but not asked recently

2. Top Difference Tables

Memorise these

Every one of these has been asked as a “differentiate / compare / distinguish” question in one of the papers. Answer difference questions only in table form.

Multiprogramming vs Time Sharing

Basis	Multiprogramming	Time sharing
Goal	Maximise CPU utilisation	Minimise response time
Switch trigger	Only when the running job needs I/O	Every fixed quantum, I/O or not
Users	Single operator, many jobs	Many users, each with a terminal
Memory	Several jobs resident	Several users' processes resident
Quantum	No concept of a quantum	10–100 ms time slice
Feel	Throughput-oriented batch feel	Each user feels exclusive control

Process vs Thread

Basis	Process	Thread
Definition	A program in execution	A lightweight unit of execution inside a process
Address space	Separate	Shared with sibling threads
Owns	Code, data, heap, stack, registers, file table, PCB	Stack, program counter, registers only
Creation cost	High and slow	Low and fast
Context switch	Slower — address space changes	Faster — only registers and stack
Communication	IPC — needs kernel support	Direct through shared memory
Crash blast radius	Isolated to that process	Can kill the whole process

Preemptive vs Non-preemptive

Basis	Preemptive	Non-preemptive
CPU takeover	Can be taken away mid-execution	Runs to completion or until it blocks
Who controls switching	The OS	The running process
Response time	Better — suits interactive and real-time	Worse for short urgent tasks
Starvation	Higher risk	Lower risk
Overhead	More context switches	Fewer context switches
Shared data	Process can stop mid-update → inconsistency	Safer inside critical sections
Examples	RR, SRTF, preemptive priority	FCFS, SJF, non-preemptive priority

User threads vs Kernel threads

Basis	User-level (ULT)	Kernel-level (KLT)
Managed by	Thread library in user space	The operating system kernel
Kernel knows them?	No	Yes
Creation / switch	Cheap, no system call	Costly, traps into the kernel
Blocking call	Blocks the entire process	Blocks only that thread
Multiprocessor	Cannot run threads in parallel	Can run threads in parallel
Portability	High	Kernel dependent

Internal vs External Fragmentation

Basis	Internal fragmentation	External fragmentation
Where the waste is	Inside an allocated block	Outside every allocated block, in the free holes
Cause	Fixed-size partitions / pages larger than the request	Variable-size allocation and deallocation leaving scattered gaps
Seen in	Paging, fixed partitions	Segmentation, first/best/worst-fit variable partitions
Is the free space usable?	No — it belongs to the allocated block	Yes in total, but not as one contiguous piece
Remedy	Choose a smaller page/partition size; paging avoids it in the sense that only the last page wastes	Compaction; or paging / segmentation with paging
Cost of the remedy	Smaller pages → bigger page tables	Compaction → expensive copying and CPU stall

Logical vs Physical Address

Basis	Logical (virtual) address	Physical address
Generated by	The CPU while executing the program	What the memory unit actually sees
Seen by the programmer?	Yes	No
Set of all such addresses	Logical address space	Physical address space
Translated by	The MMU, at run time, by adding the relocation/base register value
Binding time	Compile-time and load-time give absolute code; execution-time binding needs hardware support and is flexible
Example (Dec-2025)	150	150 + base 1000 = 1150

Paging vs Segmentation

Basis	Paging	Segmentation
Block size	Fixed (page = frame)	Variable — one segment per logical unit
Decided by	The hardware	The programmer / compiler
Address is	Page number + offset	Segment number + offset
Table	Page table → frame base addresses	Segment table → base + limit per segment
Fragmentation	Internal only	External only
View of memory	Invisible, system-oriented split	Matches the user's view (code, data, stack)
Sharing & protection	Coarse — per page	Natural — per logical segment
Speed	Faster, simpler allocation	Slower — needs compaction and variable-size handling

Contiguous vs Non-contiguous Allocation

Basis	Contiguous	Non-contiguous
Placement	One single block of consecutive memory	Scattered blocks / pages / frames
Addressing	Base + offset is enough	Needs a page or segment table to stitch pieces together
Fragmentation	External (and internal under fixed partitions)	Internal only (paging)
Hardware cost	Low — base and limit registers	Higher — page table, TLB
Growth	Hard — may need to copy the whole process	Easy — just allocate another frame
Examples	MFT / MVT, first / best / worst fit	Paging, segmentation, segmentation with paging

Binary vs Counting Semaphore

Basis	Binary semaphore (mutex)	Counting semaphore
Value range	Only 0 or 1	Any non-negative integer
Manages	Access to a single shared resource	Instances of a resource pool
Initial value	1	= number of available instances
Purpose	Enforce mutual exclusion	Control concurrency level
Example	One printer, one critical section	3 printers, n buffer slots
Inter-changeable?	A binary semaphore can implement a mutex, but a mutex cannot implement a counting semaphore

FCFS vs SJF vs SRTF vs Round Robin

Basis	FCFS	SJF	SRTF	RR
Preemptive	No	No	Yes	Yes
Chooses by	Arrival order	Shortest total burst	Shortest remaining burst	Fixed quantum, round robin
Avg waiting time	Usually worst	Optimal among non-preemptive	Optimal of all four	Between SJF and FCFS
Response time	Poor	Poor for long jobs first	Moderate	Best
Starvation	None	Long jobs can starve	Long jobs can starve	None
Context switches	Fewest	Few	Many	Many (more as quantum shrinks)
Needs burst known	No	Yes	Yes	No

Demand paging vs Pure (non-demand) paging

Basis	Pure paging	Demand paging
When pages load	The whole process at load time	Only when a page is referenced
Virtual memory	Not really used	Yes — logical space exceeds physical
Page faults	None after loading	Expected; handled by the OS
Startup latency	High	Low
Needs	Simple page table	Valid/invalid bits, backing store, replacement policy

3. Formula Sheet

Print this

CPU scheduling

Quantity	Formula	Note
Turnaround time	TAT = CT − AT	Completion time minus arrival time
Waiting time	WT = TAT − BT	Burst time is never “waiting”
Response time	RT = first CPU start − AT	Only asked for preemptive / RR
Average waiting time	ΣWT / n	n = number of processes
Average turnaround time	ΣTAT / n
CPU utilisation	1 − (idle time ÷ total time)	Report as a percentage
Throughput	processes completed ÷ total time
RR context switches	≈ Σ⌈BT q⌉ − 1	q = quantum; last slice of a process needs no switch

Paging and address structure

Quantity	Formula
Number of pages	Pages = logical address space ÷ page size
Number of frames	Frames = physical memory ÷ frame size
Offset bits	offset bits = log₂(page size)
Page number bits	logical address bits − offset bits
Frame number bits	physical address bits − offset bits
Page number from an address	address ÷ page size (integer part)
Offset from an address	address mod page size
Physical address	frame number × frame size + offset
Page-table entries	= number of pages (normal) · = number of frames (inverted)
Internal fragmentation	page size − (process size mod page size), or 0 when it divides exactly

Effective access time

Case	Formula
TLB present	EAT = h × (TLB + mem) + (1 − h) × (TLB + 2 × mem)
Simple form	EAT = h × t_hit + (1 − h) × t_miss
Without TLB	EAT = 2 × memory access time (page table + data)
With page faults	EAT = (1 − p) × ma + p × page-fault time
Page-fault time	= service interrupt + restart + seek + latency + transfer + start + done + dispatch ≈ tens of milliseconds

Page replacement

Quantity	Formula
Hit ratio	Hits ÷ Total references
Fault ratio	Faults ÷ Total references
Hits	Total references − Faults
Compulsory faults	at least the number of distinct pages in the string
Ordering rule	Optimal ≤ LRU ≤ FIFO in page faults (usually)

Memory allocation

Quantity	Formula
Remaining space after allocation	partition size − process size
Total internal fragmentation	Σ(allocated block − requested size)
Total external fragmentation	Σ(free holes) that no single waiting request can fit into
Degree of multiprogramming	= number of processes resident in memory

Verification noteThe formula TAT = WT + BT appears in some printed answers (for example the Oct-2025 Q.2(b) turnaround table). It is the same thing as TAT = CT − AT once you define WT = TAT − BT, so either is fine — but write TAT = CT − AT first because it is the definition, then derive WT from it.

4. Don't Lose Marks Here

Common mistakes

Scheduling numericals

Starting the Gantt chart at t = 0 when the first process arrives at t = 1. Leave the idle slot and label it.
Forgetting to re-check arrivals inside a quantum — a new shorter job preempts SRTF immediately, but not SJF.
Using WT = CT − AT. That is TAT. WT = TAT − BT.
Reporting an average over the wrong n. Count processes, not time units.
Writing the RR ready queue but drawing a Gantt that does not match it — the Jan-2024 book answer does exactly this and it is wrong.
Not stating your tie-break rule when two bursts are equal. One line at the top of the answer prevents an argument with the examiner.
Forgetting that total CPU busy time = Σ burst times. Use it as a check: your Gantt must end at (first dispatch + Σ BT) if there is no later idle gap.

Page replacement

Counting a hit as a fault when a page is already resident.
In FIFO, evicting the page used longest ago — that is LRU. FIFO evicts the page loaded longest ago.
In Optimal, looking backwards instead of forwards for the next use.
Forgetting the initial cold-start faults while filling empty frames.
Not writing the final totals line — the marks are usually on the count, not the grid.
Claiming “more frames always means fewer faults”. Belady's anomaly is the counter-example for FIFO.

Paging & segmentation arithmetic

Mixing bytes / words / bits. Write the unit on every line.
Saying page size is a power of 2 “to save memory”. It is so the CPU can split the address with bit masking instead of division.
Confusing the number of page-table entries (= pages) with the number of frames.
Internal fragmentation: if the process size divides exactly by the page size the answer is 0, not “page size”. The Feb-2018 book answer gets this wrong.
Adding a page-fault service time in ms to a memory access in ns. The Jun-2019 book answer writes “25 + 100 = 125 ns” — dimensionally impossible.

Theory answers

Answering a “differentiate” question in paragraphs. Always a table with a Basis column.
Writing the process state diagram without labelling the arrows — the labels are the marks.
Confusing progress with bounded waiting. Progress = no deadlock among willing processes. Bounded waiting = a cap on how many times others may jump ahead of you.
Saying a mutex and a binary semaphore are the same thing. A mutex has ownership (only the holder may release it); a binary semaphore does not.
Writing thrashing as “high page faults” only. You must link it to degree of multiprogramming ↑ → page faults ↑ → CPU utilisation ↓, and draw the curve.
Answering “why is strict non-preemptive scheduling unlikely” with a definition instead of the four consequences: poor responsiveness, unsuitable for multitasking, blocking issues, no interrupt handling.
Copying the book's confusing phrasing (for example “virtual memory allows too fast and easy processes”). Rephrase in your own clear English.

5. The 30-Minute Final Revision

Do this last

Set a timer. Five minutes per block. Do not read new material — only recall, and open the linked page when you get stuck.

Minutes 0–5 · Definitions

Say out loud, then check: operating system · process · thread · program vs process · interrupt · IPC · context switch · deadlock (one line only, it is not in your syllabus) · virtual memory · fragmentation.

Pages: Unit I A · Memory

Minutes 5–10 · Scheduling

Draw the five-state process diagram from memory with all six arrow labels. Then recite the three schedulers table and the six criteria. Then name which of FCFS/SJF/SRTF/RR/Priority is preemptive.

Pages: Process states · Schedulers · Diagram

Minutes 10–15 · Synchronization

Recite the three requirements (Mutual Exclusion, Progress, Bounded Waiting) precisely. Then the wait/signal code for a semaphore. Then the Dining Philosophers pseudocode and one deadlock fix. Then say what the Sleeping Barber problem is.

Page: Synchronization

Minutes 15–20 · Paging + Segmentation

Draw the paging address-translation picture and the segmentation one next to it. Say why paging gives internal and segmentation gives external fragmentation. Then explain segmentation-with-paging in one sentence: each segment is paged.

Pages: Memory · Paging diagram · Seg+Paging

Minutes 20–25 · Virtual memory + replacement

Draw the page-fault handling flowchart. Then state FIFO / LRU / Optimal in one line each and recite Belady's anomaly. Then explain thrashing with the curve and name the fix.

Pages: Memory · Page fault · Thrashing

Minutes 25–30 · Formulas + diagrams

Copy the formula sheet onto a blank sheet from memory. Then flip through the Diagram Bank and, for each, say only the “How to draw this in exam” steps out loud.

Pages: Formula sheet · Diagram Bank

6. Final Checklist — every syllabus topic

Interactive

This is the complete Unit I + Unit II syllabus as one list. Tick only what you can write in an exam hall without notes. Your ticks persist across refreshes and roll up on the dashboard.

Unit I · Introduction

What is an Operating System + its functions Simple batch systems Multi-programmed batch systems Time-sharing systems Personal-computer systems Parallel systems Distributed systems Real-time systems (hard and soft) OS as a resource manager

Unit I · Processes

Introduction to processes; process vs program Process states + transition diagram Process management, PCB, context switching Interrupts and interrupt handling Interprocess communication (shared memory, message passing)

Unit I · Threads

Introduction to threads Thread states / life-cycle Thread operation; user vs kernel threads Threading models — many-to-one, one-to-one, many-to-many

Unit I · Processor Scheduling

Scheduling levels (long / medium / short term) Preemptive vs non-preemptive Priorities and aging Scheduling objectives Scheduling criteria (all six) Scheduling algorithms — FCFS, SJF, SRTF, RR, Priority, MLQ, MLFQ Demand scheduling Real-time scheduling Solved every CPU scheduling numerical and checked the answers

Unit II · Process Synchronization

Mutual exclusion — meaning, need, requirements Software solutions — Peterson, Dekker, Bakery Hardware solutions — Test-and-Set, Swap Semaphores — binary and counting, wait and signal Critical section problem + three requirements Dining Philosophers problem and solution Barber shop (Sleeping Barber) problem Race condition and Producer–Consumer

Unit II · Virtual Memory

Demand paging and the page-fault path Page replacement and why it is needed FIFO, LRU, Optimal; Belady's anomaly Performance of demand paging / effective access time Thrashing and its relation to CPU utilisation Demand segmentation Overlay concepts Solved every page-replacement numerical and checked the answers

Revision & Formula Sheet

1. Most Important Questions

Very high Asked repeatedly across the six recent papers

High Asked once or twice in the recent papers

Cover for safety In your syllabus but not asked recently

2. Top Difference Tables

Multiprogramming vs Time Sharing

Process vs Thread

Preemptive vs Non-preemptive

User threads vs Kernel threads

Internal vs External Fragmentation

Logical vs Physical Address

Paging vs Segmentation

Contiguous vs Non-contiguous Allocation

Binary vs Counting Semaphore

FCFS vs SJF vs SRTF vs Round Robin

Demand paging vs Pure (non-demand) paging

3. Formula Sheet

CPU scheduling

Paging and address structure

Effective access time

Page replacement

Memory allocation

4. Don't Lose Marks Here

Scheduling numericals

Page replacement

Paging & segmentation arithmetic

Theory answers

5. The 30-Minute Final Revision

Minutes 0–5 · Definitions

Minutes 5–10 · Scheduling

Minutes 10–15 · Synchronization

Minutes 15–20 · Paging + Segmentation

Minutes 20–25 · Virtual memory + replacement

Minutes 25–30 · Formulas + diagrams

6. Final Checklist — every syllabus topic

Unit I · Introduction

Unit I · Processes

Unit I · Threads

Unit I · Processor Scheduling

Unit II · Process Synchronization

Unit II · Memory Organization & Management

Unit II · Virtual Memory