Consider a hypothetical machine with 3 pages of physical memory, 5 pages of virtual memory, and as the stream of page references by an application. If P and Q are the number of page faults the application would incur with the FIFO and LRU page-replacement algorithms respectively (assuming enough space for storing 3 page frames), then (P, Q) = ____.

Explanation

FIFO (evict the oldest-loaded page, queue order): A,B,C fault to fill the 3 frames; D faults, evicting A; A faults again, evicting B; B faults, evicting C; E faults, evicting D (frames now A,B,E) — the next A and B are hits; C faults evicting A; D faults evicting B; E is now a hit (frames E,C,D); B faults evicting E; A faults evicting C; the final B is a hit — giving 11 faults (P=11). LRU (evict the least-recently-used page): the first 7 references (A,B,C,D,A,B,E) fault identically to FIFO; the two hits on A and B refresh their recency; then C faults evicting the now-LRU E; D faults evicting A; E faults evicting B; B faults evicting C; A faults evicting D; the final B is a hit — giving 12 faults (Q=12). Hence (P,Q) = (11,12), option (iv).