Operating Systems,
samjho ek baar mein.

Both — and that's the point. Linux is architecturally monolithic: the file system, device drivers, network stack and scheduler all run in a single kernel address space, and they call each other as ordinary function calls.

But Linux also supports loadable kernel modules (LKMs). A driver can be compiled separately and inserted at runtime with insmod / modprobe, and removed with rmmod. So the kernel is modular in how it is built and loaded, but monolithic in how it executes — a loaded module runs in kernel space with full privileges, so a bug in it can still panic the system.

A page fault is a trap (exception) — synchronous, generated by the MMU during the execution of a specific instruction, not by an external device.

The interesting difference from divide-by-zero is what happens after:

• Divide by zero — a fault the program cannot recover from by default. The OS typically sends SIGFPE and the process dies.
• Page fault — a recoverable fault. The OS brings the page in from disk, updates the page table, and then re-executes the very same instruction, which now succeeds. The program never knows it happened.

This restartability is the whole reason virtual memory works, and it puts a real constraint on CPU design: the instruction must be re-executable from the beginning without side effects. Instructions that modify memory before faulting (e.g. a block-move that half-completes) need special hardware handling.

Three reasons, in order of importance:

1. Protection. Direct disk access means any program could read or overwrite any other user's files, or the OS itself. All isolation collapses.
2. Correctness under sharing. Devices are shared. If two processes issue overlapping disk commands with no arbiter, the device gets contradictory instructions and data is corrupted. The OS serialises and queues requests.
3. Abstraction. Direct I/O means the program must know the exact controller registers of that specific hardware. Change the disk model and every program breaks. The system-call interface makes read() work on any device.

The enforcement mechanism: I/O instructions are marked privileged, so attempting one in user mode traps to the OS.

8 total processes (1 original + 7 new), and printf executes 8 times.

Reasoning. Each fork() doubles the number of running processes, because both parent and child continue from the instruction after the fork.

Here n = 3, so 2³ = 8 processes, 7 children. All 8 reach the printf.

4 processes total, so X is printed 4 times.

Two facts do all the work here: fork() returns non-zero (true) in the parent and 0 (false) in the child, and && short-circuits — if the left side is false, the right side never executes.

Note that C1 executes only one fork (the first one, which created it) and C2 executes two — the short-circuit is what keeps the total at 4 instead of 8.

No — the order is non-deterministic. After fork(), both processes are in the Ready queue and it is entirely up to the scheduler which runs first. On the same machine, the same binary can produce different orders on different runs. This is a race condition.

To force parent-after-child: the parent calls wait(), which blocks until the child terminates.

pid_t pid = fork();
if (pid == 0) {
    printf("child\n");
    exit(0);
} else {
    wait(NULL);              // blocks until child exits
    printf("parent\n");
}

To force child-after-parent you need explicit synchronisation — a pipe, a semaphore, or a signal — because there is no "wait for parent" call.

Case A — order P1, P2, P3

Average WT = (0 + 24 + 27)/3 = 17. Average TAT = (24 + 27 + 30)/3 = 27.

Case B — order P2, P3, P1

WT: P2 = 0, P3 = 3, P1 = 6. Average WT = 9/3 = 3. Average TAT = (3 + 6 + 30)/3 = 13.

Part A — SJF (non-preemptive)

At t=0 only P1 is present, so P1 runs to completion (t=0→8). At t=8, ready = {P2(4), P3(9), P4(5)} → shortest is P2. Then P4, then P3.

Avg TAT = (8+11+24+14)/4 = 57/4 = 14.25. Avg WT = (0+7+15+9)/4 = 31/4 = 7.75.

Part B — SRTF (preemptive)

Walk the timeline event by event:

• t=0 — only P1 (rem 8). P1 runs.
• t=1 — P2 arrives with 4 < P1's remaining 7. Preempt. P2 runs.
• t=2 — P3 arrives with 9 > P2's remaining 3. No preemption.
• t=3 — P4 arrives with 5 > P2's remaining 2. No preemption.
• t=5 — P2 finishes. Ready = P1(7), P3(9), P4(5). Shortest = P4. P4 runs.
• t=10 — P4 finishes. Ready = P1(7), P3(9). P1 runs.
• t=17 — P1 finishes. P3 runs → finishes at 26.

Avg TAT = (17+4+24+7)/4 = 52/4 = 13.0. Avg WT = (9+0+15+2)/4 = 26/4 = 6.5.

Ready queue starts as [P1, P2, P3, P4]. Track remaining times.

Avg TAT = (36+7+10+20)/4 = 73/4 = 18.25. Avg WT = (12+4+7+14)/4 = 37/4 = 9.25.

• q → ∞ (larger than the longest burst): no process is ever preempted, so RR degenerates to FCFS. Response time becomes terrible.
• q → 0: this is called processor sharing — in theory each of n processes appears to run on its own CPU at 1/n speed. In practice, context switch overhead dominates and the system does almost no useful work (thrashing on switches).

Overhead calculation:

• q = 1 ms: 0.1/(1 + 0.1) = 0.0909 → ≈ 9.1% of CPU wasted
• q = 10 ms: 0.1/(10 + 0.1) = 0.0099 → ≈ 0.99% wasted

The rule of thumb: q should be large compared to the context-switch time, but small enough that ~80% of CPU bursts finish within one quantum. Typical real values: 10–100 ms, with switch cost around 10 µs.

t=0: only P1 → runs 0→3.

t=3: ready = P2 (waited 3−2=1). Only choice → P2 runs 3→9.

t=9: ready = P3, P4, P5.

Highest = P3 → runs 9→13.

t=13: ready = P4, P5.

Highest = P5 → runs 13→15. Then P4 runs 15→20.

Avg TAT = 40/5 = 8.0. Avg WT = 20/5 = 4.0.

Notice at t=9 the shortest job P5 did not win — P3 had waited longer. Pure SJF would have picked P5. That is exactly the anti-starvation behaviour.

Deadlock. Here is the exact sequence:

1. Buffer is full, so empty = 0.
2. Producer executes wait(mutex) → succeeds, mutex is now 0. Producer holds the lock.
3. Producer executes wait(empty) → empty is 0, so the producer blocks — while still holding mutex.
4. Consumer arrives, executes wait(full) → succeeds (buffer has items).
5. Consumer executes wait(mutex) → mutex is 0 → consumer blocks.
6. Producer waits for the consumer to free a slot. Consumer waits for the producer to release mutex. Circular wait → deadlock.

No deadlock. It still works correctly — only a small efficiency loss.

Reason: signal() never blocks. It always increments and returns. So the order of two signals cannot create a circular wait.

The minor cost: after signal(full), a waiting consumer becomes ready and may be scheduled immediately, only to block on wait(mutex) because the producer hasn't released it yet. That's one wasted wakeup + context switch. Correct, just slightly slower.

Step 1 — compute Available.

Total allocated: A = 0+2+3+2+0 = 7, B = 1+0+0+1+0 = 2, C = 0+0+2+1+2 = 5.

Step 2 — compute Need = Max − Allocation.

Step 3 — run the safety algorithm. Work = (3, 3, 2).

All five finished. (a) The system IS in a safe state. Safe sequence: ⟨P1, P3, P0, P2, P4⟩.

(b) P1 requests (1, 0, 2). Run the resource-request algorithm:

1. Is Request ≤ Need[P1]? (1,0,2) ≤ (1,2,2) ✓ — legal request.
2. Is Request ≤ Available? (1,0,2) ≤ (3,3,2) ✓ — resources exist.
3. Pretend to grant it and check safety of the new state:
   Available = (3,3,2) − (1,0,2) = (2,3,0)
   Allocation[P1] = (2,0,0) + (1,0,2) = (3,0,2)
   Need[P1] = (1,2,2) − (1,0,2) = (0,2,0)

New Need table: P0(7,4,3), P1(0,2,0), P2(6,0,0), P3(0,1,1), P4(4,3,1). Work = (2,3,0).

Safe. Sequence ⟨P1, P3, P0, P2, P4⟩. So the request can be granted immediately.

Worst-case reasoning. Deadlock is worst when every process holds as much as it can without being able to finish — that is, each holds k − 1 instances and waits for one more.

In that state, the total held is n(k − 1). If even one extra instance exists, some process can grab it, reach k, finish, and release everything — breaking the chain.

Worked variant: "3 processes, each needs at most 4 instances. What is the minimum m for deadlock-freedom?"

m ≥ 3(4 − 1) + 1 = 3(3) + 1 = 10.

Reverse variant: "There are 12 instances and each process needs at most 3. What is the maximum number of processes such that the system is guaranteed deadlock-free?"

12 ≥ n(3 − 1) + 1 → 12 ≥ 2n + 1 → n ≤ 5.5 → n = 5.

First fit — scan from the start, take the first hole that fits.

Best fit — take the smallest hole that fits.

Worst fit — take the largest hole.

(a) Page size = 4 KB = 2¹² bytes → offset = 12 bits.
Logical address = 32 bits → page number = 32 − 12 = 20 bits.

(b) Number of pages = 2²⁰ = 1,048,576 pages (≈ 1 M).
Physical memory = 1 GB = 2³⁰ bytes; frame size = 2¹² → number of frames = 2³⁰/2¹² = 2¹⁸ = 262,144 frames.

(c) Page table size = 2²⁰ entries × 4 bytes = 2²² bytes = 4 MB per process.

On a TLB hit: 20 (TLB) + 100 (memory for data) = 120 ns.
On a TLB miss: 20 (TLB, wasted) + 100 (memory for page table) + 100 (memory for data) = 220 ns.

(a) h = 0.80

(b) h = 0.98

Interpretation. Raw memory access is 100 ns. At 80% hit ratio we pay 140 ns — a 40% slowdown. At 98% we pay 122 ns — only 22%. Pushing the hit ratio from 80% to 98% recovers almost half the overhead. This is why real TLBs are aggressively optimised and why hit ratios of 99%+ are typical.

Design. Offset = 12 bits, leaving 20 bits for the page number. Split it 10 / 10.

Each table then has 2¹⁰ = 1024 entries × 4 bytes = 4 KB — exactly one page. That's the whole reason for choosing a 10/10 split: every page table fits in exactly one frame.

Single-level: 4 MB, always, entirely resident.

Two-level:

• Outer page table: 4 KB (always needed)
• Code at the low end → 1 inner table: 4 KB
• Stack at the high end → 1 inner table: 4 KB

The cost: address translation now needs two page-table lookups instead of one, so a TLB miss costs 3 memory accesses (outer table + inner table + data) rather than 2.

Rule: valid iff offset < limit; then physical = base + offset.

First, put both in the same unit: 8 ms = 8,000,000 ns.

(a) p = 0.001

That is a 40× slowdown from 200 ns. One fault in a thousand accesses — which sounds rare — makes the machine 40 times slower.

(b) "Less than 10% degradation" means EAT < 220 ns.

That is fewer than 1 fault per 400,000 accesses.

FIFO — evict the oldest arrival.

FIFO = 15 page faults.

Optimal (OPT / MIN) — evict the page whose next use is farthest in the future. Positions in the string are numbered 1–20.

Optimal = 9 page faults.

LRU — evict the page with the oldest last-used time.

LRU = 12 page faults.

With 3 frames:

3 frames → 9 page faults.

With 4 frames:

4 frames → 10 page faults.

Why LRU and OPT are immune: they are stack algorithms — the set of pages in memory with n frames is always a subset of the set with n+1 frames. That subset property makes it impossible for a page present with n frames to be absent with n+1. FIFO does not have this property, because eviction order depends only on arrival time, which changes completely when frame count changes.

At t1 — the window covers 2 6 1 5 7 7 7 7 5 1. Distinct pages: {1, 2, 5, 6, 7} → WSS = 5.

At t2 — the window covers 3 4 4 4 3 4 3 4 4 4. Distinct pages: {3, 4} → WSS = 2.

Interpretation. The process has moved from one locality (pages 1,2,5,6,7) to a much tighter one (pages 3,4). Between t1 and t2 it needed 5 frames; now it needs only 2. The OS can reclaim 3 frames and give them to another process.

If the OS had allocated a fixed number of frames instead, it would either be wasting frames now or have been thrashing earlier. That adaptivity is the entire value of the working-set model.

(a) Rotational latency. 7200 RPM = 7200/60 = 120 rotations per second → one rotation = 1/120 s = 8.33 ms.

(b) One sector. Transfer time for one sector = (1/500) × 8.33 ms = 0.0167 ms.

(c) Full track sequentially. One seek, one rotational latency, then read the whole track — which takes exactly one full rotation.

(d) 500 random sectors. Every sector needs its own seek and its own rotational latency.

1. FCFS — serve in arrival order

Fair, simple, but the head swings wildly (183 → 37 → 122 → 14). No optimisation at all.

2. SSTF — Shortest Seek Time First

Always go to the closest pending request.

3. SCAN (elevator)

Head moves in one direction serving everything, goes all the way to the end of the disk, reverses, and serves on the way back.

Note the head goes to cylinder 0 even though no request is there — that's what distinguishes SCAN from LOOK.

4. C-SCAN — Circular SCAN

Serves in one direction only. On reaching the end, it jumps back to the other end without servicing anything on the return trip.

Why bother, if the number is worse? Because C-SCAN gives a more uniform wait time. In plain SCAN, a request just behind the head gets served twice as fast as one just in front — cylinders near the middle get served twice per sweep, edges once. C-SCAN treats the disk as circular, so every cylinder is visited at the same frequency.

5. LOOK

Like SCAN, but the head only goes as far as the last request in each direction — it doesn't run to the physical end.

6. C-LOOK

C-SCAN without going to the physical ends.

(a) Video editing scratch drive → RAID 0. Needs maximum sequential throughput and capacity; the data is temporary and re-creatable from the source footage. Losing it costs a re-import, not a disaster.

(b) Bank transaction database → RAID 10. OLTP is write-heavy with many small random writes, which is exactly where RAID 5's four-I/O write penalty hurts most. RAID 10 has no parity computation, fast rebuilds, and excellent random write performance. Paying 50% capacity is acceptable here.

(c) Cold archive → RAID 6. Reads are rare, writes rarer still, so the write penalty doesn't matter. What matters is surviving a second failure during a multi-day rebuild of large disks. RAID 6 gives 12 TB usable with two-disk tolerance.

Step 1 — how many parity bits? m = 7. Try r = 4: 2⁴ = 16 ≥ 7 + 4 + 1 = 12 ✓. (r = 3 gives 8 ≥ 11 ✗.) So r = 4, total length 11.

Step 2 — lay out the data. Data bits d1…d7 = 1, 0, 1, 1, 0, 0, 1 go into non-power-of-2 positions in order.

Step 3 — compute each parity bit (even parity → total number of 1s must be even).

P1 covers positions 1, 3, 5, 7, 9, 11 → values ?, 1, 0, 1, 0, 1

P2 covers positions 2, 3, 6, 7, 10, 11 → values ?, 1, 1, 1, 0, 1

P4 covers positions 4, 5, 6, 7 → values ?, 0, 1, 1

P8 covers positions 8, 9, 10, 11 → values ?, 0, 0, 1

Step 4 — assemble the codeword.

Step 1 — recompute each parity check, this time INCLUDING the parity bit itself. For even parity, each group's total must be even. Write 0 if OK, 1 if failed.

C1 — positions 1, 3, 5, 7, 9, 11 → 1, 1, 0, 1, 0, 1

C2 — positions 2, 3, 6, 7, 10, 11 → 0, 1, 1, 1, 1, 1

C4 — positions 4, 5, 6, 7 → 0, 0, 1, 1

C8 — positions 8, 9, 10, 11 → 1, 0, 1, 1

Step 2 — build the syndrome. Read the checks as a binary number, C8 C4 C2 C1 (most significant first):

Step 3 — correct it. The error is in position 10. Flip that bit: 1 → 0.

Step 4 — extract the data. Remove positions 1, 2, 4, 8:

(a) m = 16. Try r = 5: 2⁵ = 32 ≥ 16 + 5 + 1 = 22 ✓. Try r = 4: 16 ≥ 21 ✗. So r = 5, total codeword length 21.

(b) Encoding 1011 — m = 4, so r = 3 (2³ = 8 ≥ 4 + 3 + 1 = 8 ✓). Total length 7.

• P1 covers 1, 3, 5, 7 → data at 3, 5, 7 = 1, 0, 1 → two 1s (even) → P1 = 0
• P2 covers 2, 3, 6, 7 → data at 3, 6, 7 = 1, 1, 1 → three 1s (odd) → P2 = 1
• P4 covers 4, 5, 6, 7 → data at 5, 6, 7 = 0, 1, 1 → two 1s (even) → P4 = 0

Verify: C1 → positions 1,3,5,7 = 0,1,0,1 → sum 2 ✓ · C2 → 1,1,1,1 → sum 4 ✓ · C4 → 0,0,1,1 → sum 2 ✓. All even, so the encoding is right.

(c) Decoding 1001101.

• C1 — positions 1, 3, 5, 7 → 1, 0, 1, 1 → sum 3, odd → fails → C1 = 1
• C2 — positions 2, 3, 6, 7 → 0, 0, 0, 1 → sum 1, odd → fails → C2 = 1
• C4 — positions 4, 5, 6, 7 → 1, 1, 0, 1 → sum 3, odd → fails → C4 = 1

Error is at position 7. Flip it: 1 → 0.

Pointers per index block = 4 KB / 4 B = 1024.

The triple-indirect term dominates so completely that the others are rounding errors — but write them all out; examiners want the full breakdown.

A process is an independent program in execution with its own address space; a thread is a unit of execution within a process. Threads of one process share code, data, heap and open files, but each has its own stack, registers and program counter. Consequences: thread creation and context switching are cheaper (no address-space change), thread communication is just shared memory, but there is no isolation — one thread crashing takes the whole process down, and shared data needs explicit synchronisation.

The program counter, stack pointer, general-purpose registers, processor status word, and memory-management state (page table base register or base/limit) — all written into the outgoing process's PCB, then loaded from the incoming one. The bigger cost is usually indirect: cache pollution, TLB flush (unless ASID-tagged), and cold branch predictors. During a switch, zero useful work happens.

A mode switch changes the CPU privilege level (user ↔ kernel) but the same process continues — this is what a system call does. A context switch changes which process is running, requiring PCB save/restore and scheduler involvement. Every context switch involves a mode switch, but not vice versa. Mode switches cost hundreds of nanoseconds; context switches cost microseconds plus cache effects.

No. A process is defined by having at least one thread of execution — the main thread. If the main thread exits, the process terminates. A process with zero threads has nothing to execute, so it would be indistinguishable from a terminated process.

The gap between fork and exec gives the child a window to configure its environment while it is still a copy of the parent — redirect file descriptors (this is how shell redirection and pipes work), change the working directory, drop privileges, set signal handlers. A single spawn call would need dozens of parameters to express all of that. Copy-on-write makes the seemingly wasteful copy nearly free.

You can't — it is already dead; kill -9 has no effect since there is no running code to signal. The zombie exists only as a PCB entry holding an exit status. It disappears when the parent calls wait(). If the parent is buggy and never does, kill the parent: the zombie is then re-parented to init (PID 1), which reaps it automatically.

SJF (and its preemptive form SRTF) is provably optimal for average waiting time. It's not usable directly because burst times aren't known in advance; systems approximate it with exponential averaging of past bursts, or observe behaviour dynamically via MLFQ. SJF also risks starving long jobs, which HRRN and aging address.

Under FCFS, one long CPU-bound process holds the CPU while many short I/O-bound processes queue behind it. Average waiting time balloons, but the worse problem is that all the I/O devices sit idle during that time, because the processes that would drive them are stuck in the ready queue. Utilisation drops across the whole system, not just the CPU.

It must be large relative to the context-switch time or overhead dominates (0.1 ms switch with 1 ms quantum wastes ~9% of the CPU), and small enough that response time stays interactive. The standard rule of thumb: pick q so that roughly 80% of CPU bursts complete within one quantum. Typical values are 10–100 ms. If q exceeds the longest burst, RR degenerates to FCFS.

Gradually increasing the priority of processes that have been waiting a long time, so a low-priority process cannot be starved indefinitely by a stream of high-priority arrivals. It converts an unbounded wait into a bounded one. HRRN builds aging directly into its formula, since the response ratio grows with waiting time.

A mutex is a locking mechanism with ownership — only the thread that locked it may unlock it, which enables priority inheritance. A semaphore is a signalling mechanism with a counter and no ownership — any thread may signal, and the classic use is one thread notifying another that an event occurred. A binary semaphore looks like a mutex but lacks ownership semantics.

Mutual exclusion (only one process in its critical section at a time), progress (if the critical section is free, a process wanting to enter must be able to, and the decision can't be postponed indefinitely), and bounded waiting (a bound on how many times others can enter before a waiting process gets its turn). Most broken solutions fail progress, not mutual exclusion.

A lock where a waiting thread busy-waits in a loop instead of blocking. It wastes CPU while spinning, but avoids the two context switches that blocking costs. Use it when the lock is held for a very short time and you have multiple cores (on a uniprocessor, spinning can never succeed — the lock holder isn't running). Kernel code uses spinlocks heavily for short critical sections.

A high-priority thread is blocked waiting on a lock held by a low-priority thread, and a medium-priority thread preempts the low-priority one — so effectively the high-priority thread waits behind a medium-priority one. The fix is priority inheritance: temporarily raise the lock holder's priority to that of the highest waiter. This requires knowing the owner, which is why it works with mutexes but not semaphores. The 1997 Mars Pathfinder resets were caused by exactly this.

A monitor is a language-level construct in which only one process can be active inside at a time, with mutual exclusion supplied automatically by the compiler. Semaphores are low-level and require the programmer to place every wait and signal correctly. One behavioural difference matters: a semaphore remembers a signal (the counter increments even with no waiter), whereas a condition variable's signal is lost if nobody is waiting — which is why you always use while (cond) wait(); rather than if.

Mutual exclusion, hold and wait, no preemption, and circular wait. All four must hold simultaneously, so breaking any single one prevents deadlock. In practice, circular wait is the one that is broken — by imposing a global ordering on resource acquisition. That's why kernel code documents lock ordering.

Only if every resource type in the cycle has a single instance. With multiple instances, a cycle is a necessary but not sufficient condition — an instance held by a process outside the cycle may be released and break it. No cycle, however, always means no deadlock.

No. Unsafe means deadlock is possible if every process demands its maximum claim; it does not mean deadlock has occurred or will occur. Every deadlocked state is unsafe, but not every unsafe state is deadlocked. Deadlock avoidance is conservative — it refuses requests that would lead to unsafe states even though those states might have been fine.

Because prevention and avoidance impose a cost on every resource request — restricted request patterns, lower utilisation, runtime safety checks — while deadlocks are rare. Linux and Windows use the "ostrich algorithm": assume it won't happen, and if the system hangs, the user reboots. The economics favour a rare reboot over a permanent tax. Databases, where a deadlock is likely and a rollback is cheap, do use detection and recovery.

Deadlock: processes blocked forever in a circular wait; no CPU used; never resolves itself. Starvation: a process is runnable but never gets scheduled or granted a resource due to an unfair policy; fixable with aging. Livelock: processes are actively running and changing state in response to each other, but making no progress — CPU is busy, work is zero. Randomised backoff typically resolves livelock.

Internal fragmentation is unused space inside an allocated block, because the block is larger than requested — it occurs with fixed partitions and with paging (the last page of a process is partly empty). External fragmentation is free memory that exists but is scattered in non-contiguous holes, so a large request fails despite sufficient total free space — it occurs with dynamic partitioning and segmentation. Compaction fixes external fragmentation; paging avoids it entirely.

Because a process's pages don't need contiguous frames — any free frame will do for any page. Contiguity was the reason free space had to be in one usable run. The trade-off is that the last page of each process is usually partly empty, giving internal fragmentation of about half a page per process, which is small and predictable.

A small associative cache of recent page-number → frame-number translations. Without it, every memory reference needs an extra memory access to read the page table, halving performance — and with multilevel paging it's worse (n+1 accesses). Hit ratios above 99% are typical because of locality. On a context switch the TLB must be flushed or tagged with an ASID, which is why ASIDs matter for switch cost.

A single-level page table for a 32-bit address space with 4 KB pages and 4-byte entries is 4 MB per process, and must be contiguous in memory. Multilevel paging lets you omit inner tables for unused regions of the address space — and real processes use a tiny fraction of theirs. The cost is one extra memory access per level on a TLB miss.

Paging uses fixed-size blocks decided by hardware and is invisible to the programmer; it solves physical memory management and causes internal fragmentation. Segmentation uses variable-size blocks that match logical program units (code, stack, data) and is visible to the programmer; it enables natural protection and sharing but causes external fragmentation. Modern systems combine both — segmented paging.

Loading a page into memory only when it is actually referenced, rather than loading the whole program up front. Pages not in memory are marked invalid; touching one causes a page fault, the OS fetches it from disk and restarts the faulting instruction. This lets a program larger than physical memory run, and lets more processes fit in memory.

The counter-intuitive situation where increasing the number of frames increases the number of page faults. It affects FIFO but not LRU or Optimal, because those are stack algorithms: the set of pages resident with n frames is always a subset of the set with n+1 frames, which makes the anomaly impossible. The standard demonstration string is 1 2 3 4 1 2 5 1 2 3 4 5 — 9 faults with 3 frames, 10 with 4.

Both implementations — timestamp counters and a stack of page numbers — require work on every single memory reference, which needs hardware support that commodity CPUs don't provide. So systems use approximations based on a hardware-maintained reference bit: the clock (second-chance) algorithm, or enhanced clock using both reference and modify bits.

A process spends more time paging than executing, because it doesn't have enough frames to hold its active locality. It's self-reinforcing: low CPU utilisation makes the OS admit more processes, which steals more frames, which causes more faults. The fix is counter-intuitive — reduce the degree of multiprogramming by suspending processes. The working-set model sizes each process's frame allocation to its locality; the page-fault-frequency scheme adjusts allocation based on measured fault rate.

After fork(), parent and child share the same physical pages, all marked read-only. The first write by either triggers a protection fault; the OS then copies just that one page and lets the write proceed. This makes fork nearly free, which matters because the child usually calls exec() immediately and would have discarded a full copy anyway.

Seek time (moving the arm to the right cylinder — largest and most variable), rotational latency (waiting for the sector to arrive under the head, averaging half a rotation), and transfer time (actually reading the bytes). Only transfer time scales with data size, which is why large sequential transfers are dramatically more efficient than many small random ones.

SCAN sweeps to the physical end of the disk, reverses, and services on the way back. LOOK is the same but only travels as far as the last request in each direction, so it never wastes movement. C-SCAN services in one direction only and jumps back to the far end without servicing, which gives more uniform wait times at the cost of extra head movement. C-LOOK is C-SCAN without the trip to the physical end.

It can starve requests far from the current head position, because newly arriving nearby requests always win. It's also greedy, not optimal — choosing the locally nearest request can produce a worse total than a planned sweep. On the standard example (queue 98 183 37 122 14 124 65 67, head at 53), SSTF gives 236 cylinders while LOOK gives 208.

Each small write requires four physical I/Os: read the old data block, read the old parity, write the new data, write the new parity (computed as old parity XOR old data XOR new data). For random-write-heavy workloads like OLTP databases this is a severe penalty, which is why RAID 10 — which has no parity computation and rebuilds from a single partner disk — is usually preferred there.

Because modern disks are large enough that rebuilding a failed drive takes many hours or days, and the rebuild itself stresses every remaining disk. A second failure during that window is realistically likely, and in RAID 5 that means total data loss. RAID 6's dual parity survives two simultaneous failures at the cost of one more disk of capacity and a heavier write penalty.

RAID 2 — bit-level striping with Hamming ECC on dedicated parity disks. It's obsolete because modern disk drives already perform their own internal error detection and correction on every sector, so the array-level Hamming code is redundant overhead. It also required spindle synchronisation across drives. Parity-based levels (3–6) achieve the same fault tolerance with far fewer disks.

A hard link is another directory entry pointing at the same inode; the file survives until the link count reaches zero, but hard links can't cross filesystems or point to directories. A soft link is a separate file whose contents are a pathname; it can cross filesystems and point to directories, but breaks (dangles) if the target is removed. This is why rm is really unlink — it decrements a count rather than deleting data.

Most files are small. Twelve direct pointers cover ~48 KB with 4 KB blocks, so small files need no extra index reads at all. Indirect, double-indirect and triple-indirect pointers extend the maximum file size to terabytes, at the cost of one extra read per level — but only for the rare large file. It's the "optimise the common case, keep the rare case possible" principle.

Filesystem inconsistency after a crash that interrupts a multi-step metadata update. The intended changes are written to a log first (write-ahead logging); after a crash, committed transactions are replayed and uncommitted ones discarded. Recovery takes seconds instead of a full-disk fsck. Metadata-only journaling is faster; full data journaling is safer but writes everything twice.

An interrupt is asynchronous and comes from hardware (keyboard, disk, timer). A trap/exception is synchronous and caused by the executing instruction itself (divide by zero, page fault). A system call is a synchronous, deliberate request by the program for a kernel service. All three use the same underlying mechanism — save state, switch to kernel mode, dispatch through a vector table — only the trigger differs.

Direct Memory Access lets a controller transfer data between a device and memory without the CPU moving each byte. The CPU sets up the transfer and gets one interrupt per block instead of one per byte or word. It's essential for high-throughput devices like disks and network cards. The DMA controller "steals" memory bus cycles from the CPU, which slows it slightly — far less than per-byte interrupt handling would.

A hardware mode bit distinguishes kernel mode from user mode. Certain instructions — I/O, setting the timer, loading base/limit or page-table registers, changing the mode bit — are privileged and trap if attempted in user mode. Without it, any user program could perform I/O directly, disable the timer to hog the CPU, or read other processes' memory, so all protection would collapse.

A monolithic kernel puts the file system, drivers, networking and scheduler in one address space, so they call each other as function calls — fast, but a bug in any component can crash the system. A microkernel keeps only IPC, scheduling and basic memory management in the kernel and pushes everything else into user-space servers — reliable and extensible, but each service request becomes message passing with several mode switches, so it is slower. Linux is monolithic but modular; Windows NT and macOS are hybrids.

Multiprogramming keeps several jobs in memory and switches when the running one blocks for I/O — the goal is CPU utilisation. Multitasking (time sharing) adds a time quantum so switching also happens on a timer — the goal is response time. Multiprocessing means the system has more than one CPU or core, giving true parallelism. The first two are about one CPU; the third is about several.

Simultaneous Peripheral Operation On-Line — using disk as a buffer so a slow device (printer) doesn't block the CPU. Its deeper significance is that it created a job pool on disk: instead of running jobs in the fixed order they sat on tape, the OS could now choose any job. That choice is what made job scheduling possible in the first place.

Long-term decides which jobs are admitted, controlling the degree of multiprogramming; it runs infrequently and aims for a good mix of CPU-bound and I/O-bound jobs. Medium-term swaps processes out to disk and back, reducing multiprogramming when memory is tight. Short-term (CPU scheduler) picks which ready process runs next; it runs every few milliseconds and must be fast.

The scheduler is policy — it decides which process should run. The dispatcher is mechanism — it performs the context switch, switches to user mode, and jumps to the correct location in the program. The time the dispatcher takes is called dispatch latency, and it must be minimal since it is pure overhead.

In a hard real-time system, missing a deadline is a system failure (airbag controller, pacemaker) — so virtual memory is usually disallowed because a page fault introduces unpredictable delay. In a soft real-time system, a missed deadline degrades quality but the system continues (video playback, VoIP). The key insight: real-time means predictable, not fast. A system that always takes exactly 50 ms is real-time; one that usually takes 1 ms but sometimes 200 ms is not.

The working set WS(Δ) is the set of distinct pages a process referenced in its most recent Δ references — an approximation of its current locality. If the sum of all processes' working set sizes exceeds available frames, the system will thrash, so the OS suspends a process. It's adaptive: as a process moves between localities, its working set shrinks or grows and frames can be reallocated accordingly.

Both are synchronous traps, but a page fault has a defined remedy: fetch the page from disk, fix the page table entry, and re-execute the same instruction, which then succeeds transparently. A divide-by-zero has no such remedy — the OS delivers SIGFPE and the process typically dies. The restartability requirement puts a real constraint on CPU design: a faulting instruction must be re-executable with no partial side effects.