Virtual Memory and Page Replacement Questions and Answers

Answer: D

The policy could only be the Optimal page replacement policy.

Check each replacement against the policies, counting for LFU and MFU every reference made to a page so far:

• Reference 4 (frames 1, 2, 3): page 2 is replaced. Optimal evicts the page used farthest in the future: 1 is next used at the 7th reference, 3 at the 12th, 2 at the 13th, so 2 goes. LRU would evict 1, the least recently used, so LRU is ruled out.
• Reference 6 (frames 1, 4, 5): page 1 is replaced. Optimal agrees (next uses: 4 at the 9th, 5 at the 10th, 1 at the 11th). LFU would evict 5, referenced once, against twice for 1 and 4, so LFU is ruled out.
• Reference 3, the 12th (frames 6, 1, 5): page 5 is replaced. Page 1 has by then been referenced three times, 5 twice and 6 once, so MFU would evict 1, ruling MFU out. Optimal is free to evict 5, since none of the three pages is used again.

The remaining replacements (5 replaces 3, 1 replaces 4, 2 replaces 6) also agree with Optimal, so it is consistent with every step.

Answer: A

Virtual memory is the storage allocation scheme in which secondary memory (the disk) can be addressed as if it were part of main memory, so a program can be larger than the physical RAM. Secondary memory is the storage itself and not the scheme, and CPU registers and CPU buffers are small fast storage inside or beside the processor, not a way of addressing the disk as memory. A page of a program that is not in RAM is kept on the disk and brought in when needed, so the program behaves as if it had a much larger memory than is installed.

Answer: D

The algorithm is FIFO (First In First Out).

FIFO can suffer from Belady’s anomaly: for some reference strings, giving a process more frames produces more page faults. The standard example is the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, which causes 9 faults with 3 frames but 10 with 4.

LRU and OPT are stack algorithms: the set of pages in memory with \(k\) frames is always a subset of the set with \(k + 1\) frames, so adding frames can never increase the faults. MRU, which evicts the most recently used page, is not the algorithm the anomaly is known for; FIFO is the classic case.

Answer: B

The page fault rate is \((X - M) / (D - M)\).

If \(p\) is the page fault rate, a fraction \(p\) of accesses take \(D\) units and the rest take \(M\) units, so the measured average is

\[ \begin{aligned} X &= (1 - p)M + pD \\ X - M &= p(D - M) \\ p &= \frac{X - M}{D - M} \end{aligned} \]

Check: if no access faults, \(X = M\) and \(p = 0\); if every access faults, \(X = D\) and \(p = 1\). The option \((D - M)/(X - M)\) is the reciprocal and exceeds 1. \((D - X)/(D - M)\) is the hit rate \(1 - p\), and \((X - M)/(D - X)\) is the ratio of faults to hits.