Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
17-Comp-A5, Operating Systems — National Examinations, December 2019. 3-hour closed-book paper, 7 questions of 20 marks each (candidates asked to answer any 5; all 7 answered here). Total 100 marks.
Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed., Wiley) — CPU scheduling (Ch.5), process synchronization (Ch.6–7), deadlocks (Ch.8), main memory (Ch.9), virtual memory (Ch.10), mass-storage/disk scheduling (Ch.11), file-system implementation/free-space management (Ch.12–14).
Data used below. (1) Q1(a): Proc3's execution time is 21 s (the printed column reads 14, 7, 21, 2, 1 for Proc1–5). (2) Q3(c): the base (relocation) register is 1500. (3) Q5(a) states that the disk has 160 tracks numbered 0 to 159, yet its request queue includes tracks 160, 174 and 176. This inconsistency in the paper is resolved by adopting a 200-track disk (0–199) for the C-SCAN calculation, the only sub-part affected. (4) Q6(b) lists the free holes as 305K/245K/405K/470K/270K/291K/325K/350K, but the next sentence restates the first two as 302K and 243K, a proofing slip in the paper; the full eight-value list is used throughout.
(a) Degree of multiprogramming vs. CPU/paging-disk utilization. The governing intuition (Silberschatz's CPU-utilization curve against degree of multiprogramming) is: as long as the paging device is not the bottleneck, adding more ready processes gives the scheduler more choice and raises CPU utilization; but once the paging disk is nearly saturated, the system is thrashing — processes spend almost all their time waiting on page faults rather than computing — and adding more processes only demands more page-in/out traffic, driving CPU utilization down further, not up.
(i) CPU 7%, paging disk 2%: YES. Both resources are nearly idle, so the system is not memory-constrained at all — there is simply not enough ready work. Increasing the degree of multiprogramming gives the scheduler more processes to interleave and should raise CPU utilization with essentially no thrashing risk.
(ii) CPU 15%, paging disk 98%: NO. The paging disk is nearly saturated while the CPU sits mostly idle — the classic thrashing signature (processes are almost always blocked on a page fault). Adding more processes would only add more page-fault traffic to an already-saturated disk, driving CPU utilization down further. The fix is the opposite: decrease the degree of multiprogramming (suspend/swap out some processes) so the remaining processes have enough resident frames to run with fewer faults, or add physical memory.
(iii) CPU 80%, paging disk 15%: YES, with more caution. The CPU is already fairly busy and the paging disk has considerable headroom, so there is still room to add processes and push CPU utilization higher before thrashing risk becomes significant; the increase should be smaller/more incremental than in scenario (i) since the CPU is closer to saturation.
(iv) Both CPU and paging disk at 50%: borderline — increase cautiously while monitoring. Neither resource is saturated, so there is headroom in principle, but the paging disk is already at a moderate load; this is the point on the utilization curve closest to the "knee" where further increases could tip into thrashing. The correct engineering response is to increase the degree of multiprogramming in small increments while watching whether paging-disk utilization rises much faster than CPU utilization does — if it does, that is the signal thrashing has begun and the increase should be reversed.
Check: the source's free-list sentence restates the first two holes as "302K"/"243K", which does not match its own fully-enumerated list of 305K/245K/…/350K given one paragraph earlier. We use the fully-enumerated 8-value list as authoritative.
Given. Free list, in order: 305K, 245K, 405K, 470K, 270K, 291K, 325K, 350K. Jobs arrive in order: 322K, 305K, 403K, 290K.
Find. Which hole each job is allocated to, under (i) best fit and (ii) first fit, updating the free list after each allocation (remainder of a partially-used hole becomes a new smaller hole in the same slot).
Approach. Best fit scans all current holes and picks the smallest one still $\ge$ the request; first fit scans the list from the start and picks the first hole $\ge$ the request. Both leave any unused remainder behind as a (possibly tiny) new hole.
(i) Best fit. Job 1 (322K): smallest hole $\ge322$K among {305,245,405,470,270,291,325,350} is 325K — allocated, leaving a 3K remainder. Job 2 (305K): smallest hole $\ge305$K is 305K itself — an exact fit, hole fully consumed. Job 3 (403K): smallest hole $\ge403$K among the survivors {245,405,470,270,291,3,350} is 405K — leaving a 2K remainder. Job 4 (290K): smallest hole $\ge290$K among {245,2,470,270,291,3,350} is 291K — leaving a 1K remainder.
(ii) First fit. Job 1 (322K): scanning from the start, 305K and 245K are too small; the first hole $\ge322$K is 405K — leaving an 83K remainder. Job 2 (305K): scanning from the start, the first hole $\ge305$K is 305K itself — exact fit. Job 3 (403K): scanning from the start, 245K/83K(remainder) are too small; the first hole $\ge403$K is 470K — leaving a 67K remainder. Job 4 (290K): scanning from the start, 245/67/270 are too small; the first hole $\ge290$K is 291K — leaving a 1K remainder.
Final Results – Question 6(b)
Job
Best fit — hole used
First fit — hole used
Job 1 (322K)
325K hole (3K remainder)
405K hole (83K remainder)
Job 2 (305K)
305K hole (exact fit)
305K hole (exact fit)
Job 3 (403K)
405K hole (2K remainder)
470K hole (67K remainder)
Job 4 (290K)
291K hole (1K remainder)
291K hole (1K remainder)
Best fit wastes far less space per allocation here (3K/0/2K/1K vs. first fit's 83K/0/67K/1K) but at the cost of scanning every hole on every allocation, and it tends to litter memory with many tiny unusable slivers (external fragmentation) exactly like the 3K/2K/1K remnants above.
