CSC 711 Answers 4 - OS structure & deadlock

OS-Q4 Monolithic vs client-server (microkernel)

Organisation. Monolithic: all core services (process/memory, file system, drivers, networking) run in one kernel in supervisor mode, one address space; components call each other directly (UNIX, MS-DOS). Microkernel: a minimal kernel provides IPC, CPU scheduling, low-level memory and interrupts; all other services run as user-space servers; applications are clients (Mach, MINIX 3, QNX).

Invocation. Monolithic: system call/trap, then ordinary procedure calls in the same space. Client-server: message passing over IPC (user -> kernel -> server), with context switches and message copying.

Implications. Reliability: monolithic weak (one bug can crash all); microkernel strong (isolated servers restart). Performance: monolithic faster (direct calls); microkernel slower (IPC tax). Extensibility: monolithic weak (recompile/relink); microkernel strong (add/replace a server).

Trade-off: performance vs reliability/extensibility; real systems use hybrids.

OS-Q5 Deadlock and the four Coffman conditions

A deadlock is a set of two or more processes permanently blocked, each waiting for an event that only another blocked process in the set can cause. The four necessary conditions (all must hold at once):

Mutual exclusion - a resource is non-sharable.
Hold and wait - a process holds one resource while waiting for others.
No preemption - resources are released only voluntarily.
Circular wait - a closed chain P0 waits P1, P1 waits P2, ... Pn waits P0.

Necessary but not sufficient: breaking any one makes deadlock impossible; all four make it possible but not certain. Mnemonic: M-H-N-C ("Must Have No Circles").

OS-Q5b Prevention vs avoidance vs detection

Prevention (static): design so a condition can never hold - request all resources at once, total ordering, preemption, shareable resources.

Avoidance (dynamic): allow the conditions but use maximum-claim info to stay in a safe state; run a safety check (Banker's Algorithm) on each request; else wait.

Detection & recovery: let deadlock happen, build a wait-for graph, find a cycle, then terminate processes or preempt with rollback.

Trade-offs. Prevention: lowest utilisation, no extra info, cheap runtime, deadlock impossible. Avoidance: good utilisation, needs max claims, high runtime (O(n^2 m)). Detection: highest utilisation, only current state, periodic O(n^2) + costly recovery. Most general-purpose OSes use detection or partial ordering.