Virtual Memory and Page Replacement Questions and Answers

Answer: A

A page fault occurs when the page is not in RAM.

In virtual memory, a program's pages may be in main memory or on disk. When the CPU references a page whose page-table entry is marked invalid (not present), the hardware raises a page fault. The OS then finds the page on disk, loads it into a free frame (evicting another page if needed), updates the page table and restarts the instruction.

If the page is in RAM, the access proceeds normally with no fault. A locked page is pinned in memory precisely so that it never faults. Pages are not swapped out 'manually' by programs; and it is the later access to a page that has been moved out that causes the fault, not the moving itself.

Answer: A

A technique used in virtual memory management is Paging.

Paging divides a process's logical memory into fixed-size pages and physical memory into frames of the same size, so pages can be loaded on demand and placed anywhere. This lets a program larger than physical memory run.

Scheduling decides which process runs on the CPU, fragmentation is a problem of memory allocation rather than a technique, and time-sharing is a way of sharing the CPU among users.

Answer: B

Thrashing is excessive page faults.

When the processes running do not have enough frames for their working sets, nearly every memory reference causes a page fault. The system spends most of its time swapping pages in and out and very little doing useful work, so CPU utilisation collapses. Raising the degree of multiprogramming then makes it worse.

Heavy disk I/O is a symptom of thrashing, not its definition, and the CPU is under-used during thrashing rather than over-used. Memory fragmentation is a separate problem of unusable gaps in memory.

Answer: C

LRU replaces the page that was least recently accessed.

LRU assumes that a page not used for a long time is unlikely to be used soon, using the recent past to predict the near future. On a page fault it evicts the page whose last use is furthest in the past, tracked with counters or a stack of page numbers.

Replacing the page that will not be used for the longest time is the optimal (OPT or Belady) algorithm, which needs knowledge of the future. Replacing the page that has been in memory longest is FIFO. Priority-based replacement is not LRU.

Answer: D

The average access time is 1.9999 microseconds.

Weight each case by its probability, working in microseconds (10 ms = 10,000 µs):

\[ \begin{aligned} t &= 0.9999 \times 1 + 0.0001 \times 10000 \\ &= 0.9999 + 1 = 1.9999\ \mu\text{s} \end{aligned} \]

The milliseconds options mix up the units by a factor of 1000. 9.999 microseconds would follow from a 99.9% hit ratio, ten times as many faults.

Answer: A

There are 2 page hits.

Trace the string 0 1 7 2 3 2 7 1 0 3 with three frames, replacing the least recently used page on each miss.

Only the references to 2 and 7 in the middle find their page already loaded, so there are 2 hits and 8 faults. Evicting by arrival order (FIFO) instead of last use would give 3 hits, the usual trap; 4 and 5 match no replacement rule here.

Answer: C

The page faults are 10.

FIFO with four frames, trace 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5. The first four references 4, 3, 2, 1 load the empty frames, which makes 4 faults. The next 4 and 3 are hits.

\[ 5 \to \text{fault (evict 4)} \]

\[ 4 \to \text{fault (evict 3)} \]

\[ 3 \to \text{fault (evict 2)} \]

\[ 2 \to \text{fault (evict 1)} \]

\[ 1 \to \text{fault (evict 5)} \]

\[ 5 \to \text{fault (evict 4)} \]

That makes 6 more faults, so there are 10 in all out of 12 references. The options are counts (8, 9, 10, 12), so the answer is 10. With three frames the same trace gives 9 faults, which is what 9 comes from, and 12 would mean every reference faults.

Answer: A

An instruction takes i microseconds, and a page fault, which happens once in every k instructions on average, adds j microseconds. So over k instructions the total time is k times i plus one extra j, and dividing by k gives the average time for one instruction:

\[ T = \frac{k i + j}{k} = i + \frac{j}{k} \]

So the effective instruction time is i + j/k, option (A). Multiplying j by k, or dividing the sum of i and j by k, would not give the average time per instruction.

Answer: C

The effective access time is the memory access time plus the average fault penalty: with one page fault in every 10^6 accesses the fault rate is p = 10^-6. The fault service time is 10 ms = 10,000,000 ns, so the penalty per access is 10^-6 x 10,000,000 ns = 10 ns. EAT = (1 - p) x 20 + p x 10,000,000 = about 20 + 10 = 30 ns, option (C). Values of 21 ns and 23 ns would need a much smaller page fault penalty than the 10 ns that is the case here, and 35 ns would need a rate of 1.5 faults in 10^6 accesses.

Answer: C

With two frames and the reference string ABACABDBACD, FIFO gives 9 page interrupts and LRU gives 8, which is option (C).

FIFO: A, B, C, A, B, D, A, C and D each cause a page to be brought in, while the second A and the second B in the string hit. That makes 9.

LRU: the faults are A, B, C, B, D, A, C and D, since the second A, the third A and the second B find the page in memory. That makes 8.

Options (A) and (B) give too few faults for FIFO and (D) too few for FIFO and too many for LRU.