Question

Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string: \[ 7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 1, 5, 6, 1 \] The page fault rate, defined as the ratio of the number of page faults to the number of memory accesses (rounded off to one decimal place) is \(\underline{\hspace{1cm}}\).

Hint:

The page fault rate can be minimized using the LRU algorithm, which replaces the least recently used page in the memory.

Answer 1

Correct Answer: 0.6

To solve this, we can analyze the stack property of the Least Recently Used (LRU) algorithm. In LRU, the page frames act like a stack where the most recently accessed page is moved to the top, and the page at the bottom (the least recently used) is evicted when a new page needs to be loaded into a full memory.

Given Parameters:

Reference String: 7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 1, 5, 6, 1 Number of Frames: 4

---

Step 1: Track Page Hits and Misses

We monitor the "recency" of each page. A Page Fault (Miss) occurs when the referenced page is not in the current set. 

Ref	Result	Frames (Least $\rightarrow$ Most Recent)
7	Miss	[7]
2	Miss	[7, 2]
7	Hit	[2, 7]
3	Miss	[2, 7, 3]
2	Hit	[7, 3, 2]
5	Miss	[7, 3, 2, 5]
3	Hit	[7, 2, 5, 3]
4	Miss	[2, 5, 3, 4] (7 evicted)
6	Miss	[5, 3, 4, 6] (2 evicted)
7	Miss	[3, 4, 6, 7] (5 evicted)
1	Miss	[4, 6, 7, 1] (3 evicted)
5	Miss	[6, 7, 1, 5] (4 evicted)
6	Hit	[7, 1, 5, 6]
1	Hit	[7, 5, 6, 1]

---

Step 2: Aggregate the Totals

Counting the "Miss" entries from the simulation:

• Total Memory Accesses = 14
• Total Page Faults = 9

*Note: Re-evaluating the simulation shows that the 12th access (Page 5) is actually a Miss because 5 was evicted during the access of Page 7.

 

---

Step 3: Calculate the Page Fault Rate

Using the ratio of faults to total requests:$$Page\ Fault\ Rate = \frac{9}{14} \approx 0.64$$

---

Final Answer:

The calculated page fault rate for this sequence is: 0.6