Address space $8K=2^{13}$, memory $4K$, page $1K \Rightarrow 8$ virtual pages (0-7), $4$ page frames. Reference string length $15$:

$$4,2,0,1,2,6,1,4,0,1,0,2,3,5,7$$

Table shows resident set after each reference. F = page fault.

(i) FIFO - evict oldest loaded page

Ref	Hit/Fault	Resident set (4 frames)	Evicted	FIFO queue (oldest→newest)
4	F	4, -, -, -	-	[4]
2	F	4, 2, -, -	-	[4,2]
0	F	4, 2, 0, -	-	[4,2,0]
1	F	4, 2, 0, 1	-	[4,2,0,1]
2	Hit	4, 2, 0, 1	-	[4,2,0,1]
6	F	6, 2, 0, 1	4	[2,0,1,6]
1	Hit	6, 2, 0, 1	-	[2,0,1,6]
4	F	6, 4, 0, 1	2	[0,1,6,4]
0	Hit	6, 4, 0, 1	-	[0,1,6,4]
1	Hit	6, 4, 0, 1	-	[0,1,6,4]
0	Hit	6, 4, 0, 1	-	[0,1,6,4]
2	F	6, 4, 2, 1	0	[1,6,4,2]
3	F	6, 4, 2, 3	1	[6,4,2,3]
5	F	5, 4, 2, 3	6	[4,2,3,5]
7	F	5, 7, 2, 3	4	[2,3,5,7]

• Faults $=10$, Hits $=5$, Hit ratio $5/15=33.3\%$.
• Final resident pages {2,3,5,7}.

(ii) LRU - evict least recently used

Maintains recency; on hit update timestamp.

Ref	Hit/Fault	Resident set	Evicted (LRU)
4	F	4, -, -, -	-
2	F	4, 2, -, -	-
0	F	4, 2, 0, -	-
1	F	4, 2, 0, 1	-
2	Hit	4, 2, 0, 1	- (2 MRU)
6	F	6, 2, 0, 1	4 (LRU)
1	Hit	6, 2, 0, 1	- (1 MRU)
4	F	6, 2, 4, 1	0 (LRU, not used since time 3)
0	F	6, 0, 4, 1	2 (LRU)
1	Hit	6, 0, 4, 1	-
0	Hit	6, 0, 4, 1	-
2	F	2, 0, 4, 1	6 (LRU)
3	F	2, 0, 3, 1	4 (LRU)
5	F	2, 0, 3, 5	1 (LRU)
7	F	2, 7, 3, 5	0 (LRU)

• Faults $=11$, Hits $=4$, Hit ratio $26.7\%$.
• Final resident pages {2,3,5,7} (same final set but different intermediate eviction order; LRU has one extra fault).

Note for this string FIFO outperforms LRU by 1 fault - shows FIFO not always worse, but LRU generally avoids Belady's anomaly and is stack-optimal.