25-Comp-A5 Operating Systems · May 2017
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) Given. 180 tracks (0–179); head currently at track 141, having just serviced track 130 (so the head's most recent motion was in the INCREASING direction, 130→141); pending FIFO queue: 96, 158, 100, 177, 104, 160, 115, 175, 140. Find. Total head movement for (i) FCFS and (ii) LOOK. Approach. FCFS simply visits the requests in queue order from the current position; LOOK continues in the head's CURRENT direction of travel (increasing, since it just came from a lower track), servicing all pending requests on that side in nearest-first order, then reverses and services the remaining requests on the other side — without physically travelling all the way to track 0 or 179 the way SCAN would.
| Algorithm | Service order | Total head movement |
|---|---|---|
| (i) FCFS | 96, 158, 100, 177, 104, 160, 115, 175, 140 (queue order) | 511 tracks |
| (ii) LOOK | 158, 160, 175, 177, 140, 115, 104, 100, 96 | 117 tracks |
(b) Thrashing occurs when the degree of multiprogramming is pushed so high that the sum of all resident processes' working sets exceeds available physical memory, forcing the paging system to constantly evict pages that are still actively needed — each process then faults almost immediately after every eviction, spending nearly all its time waiting on page-fault I/O instead of executing, and CPU utilization collapses even though the system appears extremely busy. Example: a system with enough physical memory for 4 processes' working sets is given a 5th process to run; to make room, the OS steals frames from the other four, but those frames were still part of each process's actively-used working set, so all five processes now fault repeatedly — effective throughput drops even though the CPU scheduler is nominally busier than before, precisely because it schedules a process, that process immediately faults, the CPU sits mostly idle waiting for the page-in, and the cycle repeats for whichever process runs next. Detection: monitor CPU utilization together with the page-fault rate — a sharp INCREASE in fault rate accompanied by a DROP in CPU utilization (the classic inverted-U shape, where increasing multiprogramming degree initially raises then sharply collapses CPU utilization) is the signature of thrashing. Control: the standard fix is the working-set model — track each process's working set (the set of pages referenced in its most recent $\Delta$ time window) and admit/keep resident only as many processes as can each be given AT LEAST their full working set of frames; if the sum of working sets would exceed physical memory, suspend (swap out entirely) one or more processes rather than let all of them starve for frames, reducing the multiprogramming degree until the remaining processes' combined working sets fit.
(c) External fragmentation occurs when a memory management scheme (e.g. variable-partition multiprogramming, or contiguous file allocation) leaves the FREE memory/disk space broken up into many small, scattered holes, such that the TOTAL free space is large enough to satisfy a request but no single hole is individually large enough — the free space exists but is unusable because it is not contiguous. (This is distinct from internal fragmentation, where allocated space itself contains wasted padding.) A standard control method is compaction: periodically relocate all allocated blocks so they are packed contiguously at one end of memory, coalescing every scattered free hole into a single large contiguous region; this eliminates external fragmentation entirely but at the cost of the CPU time spent copying data and relocating any address references (base-register update, in a relocatable-partition scheme) during the compaction pass, and it typically requires briefly halting the affected processes. An alternative used more commonly today is to sidestep the problem structurally via paging or segmentation with paging, which allocates memory in FIXED-size frames rather than variable-size contiguous regions, so free frames anywhere in memory can satisfy any request — eliminating external fragmentation by design (at the cost of internal fragmentation within the last, partially-used frame of each process).
