Virtual Memory and Page Replacement Questions and Answers

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.

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: B

Thrashing means an increase in paging activity.

When too many processes are in memory and each has fewer frames than its working set, they page fault constantly. The system spends most of its time swapping pages in and out rather than executing, so paging activity rises sharply while useful work collapses.

Thrashing is the opposite of higher throughput and higher CPU utilisation: both fall. It is often triggered by raising the degree of multiprogramming too far, but the increase in multiprogramming is the cause, not what thrashing means.

Answer: C

The program would take 45 sec.

Each page fault costs 2001 microseconds instead of 1, so it adds 2000 microseconds over a normal instruction.

\[ \begin{aligned} \text{fault time} &= 15000 \times 2000\ \mu s = 30\ s \\ \text{normal time} &= 60 - 30 = 30\ s \end{aligned} \]

With twice the memory, the interval between faults doubles, so the number of faults halves to 7,500, while the normal execution time is unchanged:

\[ \begin{aligned} \text{new time} &= 30 + 7500 \times 2000\ \mu s \\ &= 30 + 15 = 45\ s \end{aligned} \]

30 seconds would be halving the whole run time, wrongly treating the normal instructions as reduced too, and 60 seconds ignores the saving.

Answer: B

The average time is 16.4 m.sec.

The page to be replaced is modified 70% of the time, costing 20 ms, and unmodified (or a free frame is available) 30% of the time, costing 8 ms.

\[ \begin{aligned} t &= 0.3 \times 8 + 0.7 \times 20 \\ &= 2.4 + 14 = 16.4\ \text{ms} \end{aligned} \]

11.6 ms comes from swapping the two percentages, 14 ms is the simple average of 8 and 20, and 28 ms adds them.

Answer: D

The correct matching is (i)-(b), (ii)-(c), (iii)-(d), (iv)-(a).

• The dirty (modified) bit tells the system whether a page must be written back to disk before replacement: the write-back policy.
• The R/W bit marks a page read-only or writable: page protection.
• The reference bit records recent use, which page replacement algorithms such as clock and LRU approximations use.
• The valid bit says whether the page is in memory and properly initialised for this process: page initialization.

The other codes give the dirty bit to replacement or protection, which is not its role.

Answer: D

The effective memory access time is 64 ns.

Every access first looks in the TLB (2 ns). On a hit (98%) the frame number is known and one memory access follows. On a miss (2%) the page table must be walked (100 ns) before the memory access.

\[ \begin{aligned} T_{hit} &= 2 + 60 = 62\ \text{ns} \\ T_{miss} &= 2 + 100 + 60 = 162\ \text{ns} \end{aligned} \]

\[ \begin{aligned} \text{EMAT} &= 0.98(62) + 0.02(162) \\ &= 60.76 + 3.24 = 64\ \text{ns} \end{aligned} \]

62 ns is the hit time alone and 162 ns the miss time alone; neither weights the two cases. 164 ns matches the miss path with the TLB lookup counted twice. Because misses are rare, the answer sits just above the hit time.

Answer: B

Thrashing occurs with low CPU utilization and a high page fault rate.

When too many processes share too few memory frames, none of them can keep its working set in memory. Each process faults, waits for a page to be loaded, and on resuming soon faults again because its pages were taken by others. The system spends its time moving pages to and from disk, the page fault rate soars and the CPU sits idle waiting for I/O, so CPU utilization falls. A naive scheduler may then admit even more processes, making it worse.

High CPU use with few faults is a healthy system, the opposite case. Memory fragmentation and a faulty disk scheduler are different problems and do not define thrashing.