25-Comp-A5 Operating Systems · May 2014
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) Deadlock avoidance lets a process request resources dynamically but requires each process to first declare its maximum possible future claim on every resource type; before granting any request, the system runs a safety algorithm (the Banker's algorithm being the canonical example) that checks whether the resulting allocation state still leaves at least one ordering in which every process could finish even in the worst case, and only grants the request if the resulting state remains "safe." Its merit is good resource utilization — it only refuses a request that would actually create risk of deadlock, not every request of a certain shape. Its shortcoming is that it requires processes to know and honestly declare their maximum resource needs in advance (often unrealistic for interactive or data-dependent workloads) and it pays a real-time cost, since the safety check runs on every resource request (polynomial in the number of processes and resource types, but non-trivial at high request rates). Deadlock detection with recovery, in contrast, imposes no restriction on how resources are requested and does nothing preventive at all — it periodically (or on demand) runs a detection algorithm over the current allocation state to determine whether a deadlock currently exists, and only then invokes a recovery procedure. Its merit is zero overhead during normal (non-deadlocked) operation and no requirement for processes to predeclare anything. Its shortcoming is that a deadlock is allowed to actually happen before anything is done about it, and recovery (terminating processes or preempting/rolling back resources) is potentially expensive and lossy — work already done by a terminated process is thrown away. The choice between them is a bet on how frequent and how costly deadlocks are expected to be: avoidance suits systems where predeclaration is feasible and deadlocks would be very costly; detection-and-recovery suits systems where deadlocks are believed rare and an occasional rollback is cheaper than paying a safety-check cost on every request.
(b) Deadlock is a situation where two or more processes are each permanently blocked, waiting for a resource (or the critical section) held by another process in the same waiting cycle — none of them can ever proceed, no matter how long the system runs, because the circular wait-for chain never breaks on its own. Starvation (indefinite postponement) is different: a process is not blocked forever by a fixed cycle, but is repeatedly passed over in favour of other processes each time the critical section (or resource) becomes available, so it eventually could enter but, in practice, never actually does because it always loses to newer or higher-priority contenders. In short, deadlock is a structural impossibility of progress; starvation is a possible-but-perpetually-deferred progress. Starvation CAN occur even with a semaphore-protected critical section if the semaphore's internal queue of blocked processes is not fairly (FIFO) ordered — e.g., an implementation that wakes an arbitrary or LIFO-ordered waiter on every signal() could keep re-selecting recently-blocked processes and leave an early waiter permanently at the back. The standard fix is to guarantee the semaphore's wait queue is served in FIFO order (the POSIX/textbook convention), which bounds how many times any other process can enter ahead of an already-waiting one — but the question is correct to flag this as an implementation detail, not a guarantee of the semaphore abstraction itself: a semaphore only guarantees mutual exclusion and a correct count, not fairness, unless the implementation specifically commits to FIFO wake-up.
(c) Starvation in CPU scheduling occurs when a low-priority process is perpetually denied the CPU because a continuous stream of higher-priority processes keeps arriving and always wins the scheduling decision — the low-priority process is never technically blocked forever (a deadlock), it simply never gets picked. A classic example is strict priority scheduling on a busy system: a background batch job at the lowest priority level can wait indefinitely if interactive/real-time jobs at higher priority levels never stop arriving, since the scheduler always prefers any ready higher-priority job over it. It is controlled chiefly by aging: gradually increasing a waiting process's effective priority the longer it remains ready without running (e.g., +1 priority level for every fixed interval spent waiting), which guarantees that even the lowest-priority process will eventually out-rank every competitor and be scheduled. A complementary control is using time-sliced round-robin scheduling in the first place (rather than strict, non-preemptive priority), since round-robin structurally guarantees every ready process gets the CPU within a bounded number of time quanta regardless of arrival pattern.
(d) The directory in a file system provides the mapping from human-readable file names to the underlying physical storage location (and metadata: size, permissions, timestamps) of each file, and organizes the set of files on a volume into a structure a user or program can navigate and search — without it, files would only be addressable by raw block/inode numbers. (i) A single-level directory keeps every file name for the entire system (or volume) in one flat list/table; it is simple to implement and search, but it requires every file on the whole system to have a globally unique name, which becomes unworkable with multiple users (two users cannot both create a file called "report") and offers no way to group related files together. (ii) A tree-structured directory allows directories to contain both files and other (sub-)directories, forming a hierarchy rooted at a single top-level directory; each user (or project) can have their own subtree, and file names only need to be unique within their own directory, not system-wide. The advantages of the tree structure are: (1) name uniqueness is scoped locally, so two different users' files named "report" coexist without conflict (a full path, e.g. /users/alice/report, is still globally unique); (2) natural grouping/organization of related files (a project's files live together, separate from an unrelated project's files of the same names); (3) efficient, scoped searching — a search can be restricted to a subtree instead of scanning the entire file system; and (4) it maps naturally onto how users conceptually organize work (nested folders), whereas a single-level directory forces an artificial flat namespace that quickly becomes unmanageable as the number of files grows.
