Frame Allocation Under a Cyclic Working Set
An online judge runs three processes on a machine with 24 physical frames of 4 KiB each. P1 scans a 64 MiB log file once, front to back. P2 executes a fixed loop over the same 9 code/data pages, repeating that 9-page sequence 50,000 times. P3 touches 30 pages uniformly at random. The scheduler currently gives each process 8 frames. Measurements show P2 takes 9 page faults per loop, P1 takes one fault per page scanned, and P3's fault rate is high but essentially unchanged when its allocation moves by plus or minus 2 frames. A page fault costs 8 ms; a TLB hit costs 1 ns. An engineer proposes moving 2 frames from P1 to P2, arguing that P1 will benefit from more room to prefetch and that P2 must stop thrashing. Assume LRU replacement and no prefetching.
1. Compute P2's page-fault count per loop and total time lost at 8, 9, and 10 frames. What is the marginal value of the 10th frame?
Read the worked answer
P2's reference string is a cycle of 9 distinct pages. With 8 frames, LRU cannot hold the whole cycle, so the page needed next has always been evicted: all 9 references per loop fault. Over 50,000 loops that is 450,000 faults, costing 450,000 x 8 ms = 3,600 s of fault service time. With 9 frames, after the initial 9 cold faults, every page of the cycle remains resident, so steady-state faults per loop are 0. With 10 frames the result is also 0. The 10th frame has zero marginal value: the working set is exactly 9 pages, so allocating 9 is sufficient. The correct fix is to give P2 9 frames, not 10, and to use the extra frame elsewhere.
2. P1 scans 64 MiB sequentially under LRU. How many faults does it incur with 2, 8, and 16 frames? Does taking frames away from P1 increase its fault count?
Read the worked answer
The scan touches 64 MiB / 4 KiB = 16,384 pages exactly once each. Under LRU with no prefetching, every page is a cold miss regardless of whether P1 has 2, 8, or 16 frames: each page is referenced once, and no later reference exists. Thus P1 incurs 16,384 faults in all three cases, and the count does not increase when frames are removed as long as at least one frame remains. The engineer's prefetch argument is false for a one-pass scan with no prefetching. Reducing P1 from 8 frames to 2 saves 6 frames without changing its fault count, so those frames should be reallocated to a process whose working set exceeds its allocation.
3. Propose a specific 24-frame allocation and justify it using working-set behavior. What should be done if P3's fault rate truly does not improve with more frames?
Read the worked answer
A sound allocation is P1 = 2, P2 = 9, P3 = 13. P1 needs only enough frames to stream the file; 2 is ample and avoids wasting frames on a one-pass scan. P2 needs exactly 9 to eliminate cyclic thrashing. P3 is the only process whose random references can exploit additional frames, so it receives the remainder 24 - 2 - 9 = 13. This removes P2's 3,600 s of fault service at no cost to P1. If P3's fault rate genuinely does not respond to more frames, the extra frames are not useful there either; they should be held as a global free pool or used for a buffer cache rather than handed to P1 or P2, since neither can benefit. The key judgement is to allocate to the process whose working set is just above its current allocation, not to the process with the longest reference string.