Question 2 of 7: Memory Increase vs. CPU Utilization; Best-Fit and First-Fit Allocation
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-COMP A-5 Operating Systems — National Examinations, May 2015. 3 hours, closed book (approved calculators only), 100 marks. 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.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.
Question 2: Memory Increase vs. CPU Utilization; Best-Fit and First-Fit Allocation (20 marks)
The relationship between CPU utilization and paging-disk utilization traces out a curve against the degree of multiprogramming: as more processes are admitted, both utilizations initially climb together; past a "knee," further multiprogramming makes the page-fault rate explode, paging-disk utilization saturates near 100%, and CPU utilization collapses because processes spend nearly all their time blocked on page-ins rather than computing — this is thrashing. Reading each observed pair against that curve:
(i) CPU 12%, paging disk 5%.No, increasing memory will not raise CPU utilization here. Both figures are low, which is the signature of the left end of the curve, far from the knee — there simply are not enough resident, runnable processes to keep the CPU busy, and since paging activity is already light, memory is demonstrably not the bottleneck. Adding physical memory changes nothing unless it is actually used to admit more work. Change needed: increase the degree of multiprogramming — admit more jobs into memory (or otherwise reduce whatever else is limiting how many processes are ready), rather than simply installing more RAM.
(ii) CPU 10%, paging disk 94%.Yes. A paging disk pinned near saturation while the CPU sits almost idle is the textbook signature of thrashing: the resident processes' combined working sets exceed the frames available to them, so nearly every reference faults and the CPU spends its time waiting on page-ins instead of computing. Increasing physical memory directly attacks the cause — more frames per process shrinks the fault rate, which frees the paging disk and lets the CPU spend its time on useful work instead of servicing faults, raising CPU utilization. (Reducing the degree of multiprogramming, i.e. swapping some processes out entirely, would relieve the same pressure without needing new memory, but the question asks specifically about adding memory, and more memory does resolve it here.)
(iii) CPU 60%, paging disk 60%.Yes, with more modest headroom. A balanced, moderate reading on both axes places the system before the knee, not past it — CPU utilization has room to grow (it is far from saturated at 100%) and the paging load, while non-trivial, is not yet the runaway saturation seen in (ii). Extra memory here lets each resident process retain a larger working set with fewer faults, which should push CPU utilization higher without yet risking thrashing. The caveat is that this is close enough to the middle of the curve that continuing to add multiprogramming without adding memory (or adding too many further processes even with more memory) risks eventually crossing the knee into the (ii)-style collapse.
Given (b). Free list, in list order: 100K, 42K, 205K, 180K, 70K, 91K, 125K, 150K. Jobs arrive strictly in the order Job 1 (120K), Job 2 (104K), Job 3 (204K), Job 4 (88K).
Given data — free list and job requirements
Hole (in list order)
Size
H1
100K
H2
42K
H3
205K
H4
180K
H5
70K
H6
91K
H7
125K
H8
150K
Find. Which hole each job is allocated to, in arrival order, under (i) best-fit and (ii) first-fit.
Approach. First-fit scans the free list from its head and takes the first hole large enough; best-fit scans the entire free list and takes the smallest hole that is still large enough. After each allocation the used hole's leftover remainder stays in the list, at the same position, as a smaller hole.
(i) Best-fit. Job 1 (120K): among all eight holes, the smallest one $\ge120$K is H7 (125K) — 180K, 150K, 205K are all larger candidates but not the tightest fit. Allocate H7, leaving a 5K remainder. Job 2 (104K): smallest remaining hole $\ge104$K is H8 (150K) (180K and 205K are also candidates but bigger). Allocate H8, leaving 46K. Job 3 (204K): only H3 (205K) still qualifies ($\ge204$K). Allocate H3, leaving just 1K. Job 4 (88K): smallest remaining hole $\ge88$K is H6 (91K) (100K and 180K also qualify but are larger). Allocate H6, leaving 3K.
$$\boxed{\text{Best-fit: Job1}\to\text{H7(125K)},\ \text{Job2}\to\text{H8(150K)},\ \text{Job3}\to\text{H3(205K)},\ \text{Job4}\to\text{H6(91K)}}$$
All four jobs are placed.
(ii) First-fit. Job 1 (120K): scanning from the head, H1(100K) and H2(42K) are both too small; H3(205K) is the first hole that fits. Allocate H3, leaving 85K in its place. Job 2 (104K): scanning again from the head, H1(100K), H2(42K), and the now-85K remainder of H3 are all too small; H4(180K) is the first fit. Allocate H4, leaving 76K. Job 3 (204K): scanning the whole list — every remaining hole (100, 42, 85, 76, 70, 91, 125, 150) is smaller than 204K, because the one hole that could have held it (the original 205K) was already consumed by Job 1, which only needed 120K of it. No hole fits — Job 3 cannot be placed and must wait. Job 4 (88K): scanning from the head, H1 (100K) is the first hole $\ge88$K. Allocate H1, leaving 12K.
$$\boxed{\text{First-fit: Job1}\to\text{H3(205K)},\ \text{Job2}\to\text{H4(180K)},\ \text{Job3}\to\textbf{blocked (no fit)},\ \text{Job4}\to\text{H1(100K)}}$$
