25-Comp-A5 Operating Systems · May 2013
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.
(a) Free-space management tracks which disk blocks are currently unallocated so the system can find space quickly when a file needs to grow or be created, without scanning the entire disk. Allocation strategy decides, given a request for one or more new blocks, exactly which free block(s) to hand out and how the chosen blocks are linked or indexed together as a file — the concern of Q3(a) above (contiguous, linked, or indexed allocation).
One common free-space-management strategy is a bit vector (bitmap): one bit per disk block, 0 = free, 1 = allocated. Finding $n$ contiguous free blocks reduces to finding a run of $n$ consecutive 0-bits, which can be done efficiently using word-at-a-time bit tricks (e.g., skipping over words that are all-1s). Its main advantage is compactness (a 1 TB disk with 4 KB blocks needs only about 32 MB of bitmap) and simplicity of finding contiguous runs; its main drawback is that the entire bitmap is normally kept in memory for speed, and it must be scanned linearly in the worst case (no free block nearby), which can be slow on a nearly-full disk.
(b) On a single-CPU system, scheduling only has to answer one question at each decision point: which single ready process/thread runs next on the one available CPU — a total order over ready processes is sufficient. On a multiprocessor system, scheduling is substantially more complex because it must additionally decide: (i) which of several CPUs a given process runs on (load balancing across CPUs, not just ordering in time); (ii) whether to allow a process to migrate between CPUs at all, given that migration destroys cache affinity (a process's working set, cached in one CPU's local cache, must be re-fetched into a different CPU's cache after migration, hurting performance) — so many multiprocessor schedulers add processor-affinity heuristics that bias a process toward re-running on the CPU it last used; (iii) for systems with related/cooperating threads (e.g. a parallel program's threads that frequently synchronize), whether to use gang scheduling (dispatch all related threads simultaneously across multiple CPUs) so that a thread does not block waiting on a partner thread that has been descheduled; and (iv) how to keep per-CPU ready queues balanced without excessive cross-CPU locking overhead (contention on a single shared ready-queue data structure itself becomes a bottleneck as the CPU count grows, motivating per-CPU run-queues with periodic load-balancing passes). In short, uniprocessor scheduling is a pure ordering problem, while multiprocessor scheduling is a joint ordering-and-placement problem with cache/affinity and synchronization concerns layered on top.
(c) Both deadlock avoidance and deadlock prevention aim to ensure the system never enters a deadlocked state, but they differ in when and how they act. Deadlock prevention works structurally, by ensuring that at least one of the four necessary conditions for deadlock (mutual exclusion, hold-and-wait, no preemption, circular wait) can never hold at all — e.g., requiring every process to request all the resources it will ever need at once (eliminating hold-and-wait), or imposing a strict global ordering on resource types and requiring requests in increasing order only (eliminating circular wait). Because it rules a condition out entirely, prevention needs no runtime bookkeeping of resource requests, but it is typically overly conservative: it restricts how processes are allowed to request resources in the first place, often leading to poor resource utilization (e.g. holding resources far longer than needed, to request everything up front) and lower concurrency. Deadlock avoidance, by contrast, allows the four conditions to remain possible in principle but uses runtime information (each process's maximum possible future claim on each resource type, declared in advance) to grant a request only if the resulting state is still "safe" — i.e., there exists some ordering in which every process could still finish even in the worst case (the Banker's algorithm is the canonical example). Avoidance achieves better resource utilization than prevention because it only rejects requests that would actually create risk, not every request of a certain shape; its shortcoming is that it requires processes to know and declare their maximum resource needs in advance (often unrealistic) and it must run a safety check (polynomial but non-trivial cost) on every resource request.
(d) The deadlock detection-and-recovery approach has two components. The first, detection, periodically (or on-demand) runs an algorithm over the current resource-allocation state to determine whether a deadlock currently exists — for single-instance resource types this is a cycle-detection search in a wait-for graph; for multiple-instance resource types it is a Banker's-algorithm-like reachability test (can every process's outstanding request eventually be satisfied from available plus soon-to-be-released resources). The second, recovery, is invoked only once detection confirms a deadlock exists, and breaks it either by process termination (abort one or more of the deadlocked processes, one at a time or all at once, releasing their held resources) or by resource preemption (forcibly take a resource away from one process in the cycle and give it to another, then roll the victim process back to a safe checkpoint so it can be safely restarted later). Both recovery methods require the system to choose a victim (usually by a cost heuristic: process priority, how much computation would be lost, how many resources it holds) and must guard against starvation, since a process that is repeatedly chosen as the cheapest victim could otherwise never complete.
