25-Comp-A5 Operating Systems · December 2017

Question 2 of 7: Multiprogramming, Effective Access Time, Fragmentation

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2017. 3 hours, closed book (one approved pocket calculator only). Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.

Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — CPU scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), real-time systems (ch. 19); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.

Question 2: Multiprogramming, Effective Access Time, Fragmentation (20 marks)

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) Multiprogramming degree vs. CPU utilization — four scenarios. Increasing the multiprogramming degree helps CPU utilization only when the bottleneck is "not enough ready work," not when it is "the disk is already saturated servicing page faults." Each case is judged against that rule.

(i) CPU 5%, disk 1%. Both are far below saturation — the system is mostly idle with hardly any I/O activity, which is the signature of too few active processes rather than thrashing. YES, increasing the degree of multiprogramming should raise CPU utilization: more ready processes give the scheduler something to run whenever the current process blocks, and the paging disk has ample spare capacity to absorb any extra page faults this introduces.
(ii) CPU 10%, disk 98%. The paging disk is almost saturated while the CPU sits idle — the classic signature of thrashing: processes spend nearly all their time waiting on page faults instead of computing. NO, adding more processes would only intensify competition for physical frames, increase the fault rate further, and drive CPU utilization down toward zero. The fix is the opposite of increasing multiprogramming: decrease the degree of multiprogramming (suspend/swap out some processes) so the remaining processes have enough resident frames to satisfy their working sets, or add physical memory.
(iii) CPU 80%, disk 10%. The CPU is already well utilized and the disk has slack. There is room to push utilization higher without risking thrashing. YES, cautiously — increasing multiprogramming can still help close the remaining 20% idle gap, since the low disk utilization shows the system is far from its thrashing knee; but it should be increased incrementally, watching the disk utilization to stop before it climbs toward the region seen in scenario (ii).
(iv) CPU 50%, disk 50%. This is the ambiguous middle case: both figures are moderate, and this single snapshot cannot tell whether the system is heading toward the "few processes, room to grow" regime of (i)/(iii) or already climbing the thrashing curve toward (ii). The correct answer is that the data alone is insufficient to say yes or no with confidence — the recommended change is not a blind increase, but to add processes in small increments while monitoring the trend of both utilizations: if CPU utilization keeps rising with disk utilization staying moderate, continue; if disk utilization spikes disproportionately, stop and reduce the degree of multiprogramming immediately (this is exactly the operating-point description behind Denning's working-set thrashing curve).

Given (b). Page-fault service time: 25 ms if a free frame is available or the victim page is unmodified; 60 ms if the victim page is modified. Memory access time $m_a=200$ ns. 70% of page faults require replacing a modified page (so 30% cost 25 ms, 70% cost 60 ms). Target effective access time (EAT) $\le 300$ ns.

Find. The maximum page-fault probability $p$ consistent with $\text{EAT}\le 300$ ns.

Approach. Compute the probability-weighted average fault-service time, then solve the standard demand-paging EAT formula $\text{EAT}=(1-p)\,m_a+p\cdot t_{\text{fault}}$ for $p$.

Weighted average fault-service time. Convert both service times to nanoseconds and blend by the given probabilities: $$t_{\text{fault}}=0.30(25\times10^{6}\,\text{ns})+0.70(60\times10^{6}\,\text{ns})=7.5\times10^{6}+42\times10^{6}=49.5\times10^{6}\,\text{ns}$$
Set up and solve the EAT inequality. $$\text{EAT}=(1-p)(200)+p(49{,}500{,}000)\le 300$$ $$200-200p+49{,}500{,}000\,p\le 300 \;\Rightarrow\; 49{,}499{,}800\,p\le 100$$ $$\boxed{p_{\max}=\dfrac{100}{49{,}499{,}800}\approx 2.02\times10^{-6}}$$ That is, at most about 1 page fault per 495,000 memory references keeps the effective access time within 1.5× of the fault-free 200 ns access time.

Final Results – Question 2(b)
Quantity	Value
Weighted fault-service time	49.5 × 10⁶ ns (49.5 ms)
Maximum acceptable page-fault rate	≈ 2.02 × 10⁻⁶

(c) Internal vs. external fragmentation in paged memory management. Internal fragmentation is wasted space inside an allocated unit: because pages/frames have a fixed size, a process's last page is almost never exactly full, so the unused space between the end of the process's data and the end of that final frame is wasted but cannot be given to any other process — it belongs to this process's allocation whether it uses it or not. Average internal fragmentation is about half a frame per process (frame-size $\div$ 2). External fragmentation is wasted space between allocated units — free memory that exists somewhere in the system but is scattered into pieces too small or too oddly placed to satisfy a request, even though the total free space might be sufficient. Pure paging eliminates external fragmentation entirely, because every frame is the same fixed size and any free frame can satisfy any process's next page request (no need for physically contiguous space) — the trade-off paging makes is accepting internal fragmentation (bounded, predictable, at most one partial frame per process) in exchange for removing external fragmentation (unbounded, unpredictable, the dominant problem in contiguous/variable-partition schemes such as Question 3(b)'s best-fit/first-fit allocation).

Concept & Theory

Topic. The multiprogramming/thrashing trade-off, the demand-paging effective access time formula, and paging's fragmentation profile.

Key relations. $\text{EAT}=(1-p)\,m_a+p\cdot t_{\text{fault}}$; thrashing onset when CPU utilization falls as multiprogramming degree rises past the system's aggregate working-set capacity.

Why this works. CPU and disk utilization together diagnose which side of the thrashing curve the system sits on: low-low means idle capacity (add work), low-CPU/high-disk means thrashing (remove work), high-CPU/low-disk means near-optimal with headroom. The EAT formula linearly blends the no-fault and fault-path costs by their probabilities, so solving for $p$ at a target EAT is a one-line algebra step once the blended fault cost is known.

Common pitfall. In (a), students often answer all four scenarios the same way ("more multiprogramming always helps") without reading the paging-disk utilization, which is the actual signal for thrashing. In (b), a common slip is forgetting to convert milliseconds to nanoseconds before blending with the 200 ns access time, or applying the 70%/30% split to the wrong branch.

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), §9.6 (thrashing, working-set model), §10.4 (effective access time, demand paging performance), §9.3.1 (fragmentation in paging).

← Question 1 Next: Question 3 →