For the following page reference string: 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 — the number of page faults that occur using the Least Recently Used (LRU) page replacement algorithm with frame size 3 is:

Explanation

Tracing LRU with 3 frames (F = fault): ref 4→[4] F; 3→[4,3] F; 2→[4,3,2] F; 1→frames full, evict LRU 4→[3,2,1] F; 4→evict LRU 3→[2,1,4] F; 3→evict LRU 2→[1,4,3] F; 5→evict LRU 1→[4,3,5] F; 4→hit (in frames, just refresh recency)→no fault; 3→hit→no fault; 2→evict LRU 5→[4,3,2] F; 1→evict LRU 4→[3,2,1] F; 5→evict LRU 3→[2,1,5] F. Counting the faults gives 10 in total (every reference faults except the two hits on 4 and 3 in the middle of the string), so the answer is 10, option (iii).