Page Replacement Algorithms

FIFO Algorithm (First In, First Out)

The FIFO algorithm replaces the oldest page that was brought into memory first when a new page needs to be swapped in.

Example:

Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Cache Size: 3

Initial State: 
Cache: []

Step 1: Page 1 loaded. Cache: [1] (Page Fault)

Step 2: Page 2 loaded. Cache: [1, 2] (Page Fault)

Step 3: Page 3 loaded. Cache: [1, 2, 3] (Page Fault)

Step 4: Page 4 loaded. Cache: [1, 2, 4] (Page Fault)

Step 5: Page 1 loaded. Cache: [2, 4, 1] (Page Fault)

Step 6: Page 2 already in cache. Cache: [2, 4, 1]

Step 7: Page 5 loaded. Cache: [4, 1, 5] (Page Fault)

Step 8: Page 1 already in cache. Cache: [4, 1, 5]

Step 9: Page 2 already in cache. Cache: [4, 1, 5]

Step 10: Page 3 loaded. Cache: [1, 5, 3] (Page Fault)

Step 11: Page 4 loaded. Cache: [5, 3, 4] (Page Fault)

Step 12: Page 5 already in cache. Cache: [5, 3, 4]

Total Page Faults: 8

LRU Algorithm (Least Recently Used)

The LRU algorithm replaces the page that has not been accessed for the longest period of time.

Example:

Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Cache Size: 3

Initial State: 
Cache: []

Step 1: Page 1 loaded. Cache: [1] (Page Fault)

Step 2: Page 2 loaded. Cache: [1, 2] (Page Fault)

Step 3: Page 3 loaded. Cache: [1, 2, 3] (Page Fault)

Step 4: Page 4 loaded. Cache: [2, 3, 4] (Page Fault)

Step 5: Page 1 loaded. Cache: [2, 3, 1] (Page Fault)

Step 6: Page 2 loaded. Cache: [3, 1, 2] (Page Fault)

Step 7: Page 5 loaded. Cache: [1, 2, 5] (Page Fault)

Step 8: Page 1 already in cache. Cache: [1, 2, 5]

Step 9: Page 2 already in cache. Cache: [1, 2, 5]

Step 10: Page 3 already in cache. Cache: [1, 2, 5] 

Step 11: Page 4 loaded. Cache: [2, 5, 4] (Page Fault)

Step 12: Page 5 already in cache. Cache: [2, 5, 4]

Total Page Faults: 7

Optimal Algorithm

The Optimal algorithm replaces the page that will not be used for the longest period of time in the future.

Example:

Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Cache Size: 3

Initial State: 
Cache: []

Step 1: Page 1 loaded. Cache: [1] (Page Fault)

Step 2: Page 2 loaded. Cache: [1, 2] (Page Fault)

Step 3: Page 3 loaded. Cache: [1, 2, 3] (Page Fault)

Step 4: Page 4 loaded. Cache: [2, 3, 4] (Page Fault)

Step 5: Page 1 loaded. Cache: [2, 3, 1] (Page Fault)

Step 6: Page 2 loaded. Cache: [3, 1, 2] (Page Fault)

Step 7: Page 5 loaded. Cache: [1, 2, 5] (Page Fault)

Step 8: Page 1 already in cache. Cache: [1, 2, 5]

Step 9: Page 2 already in cache. Cache: [1, 2, 5]

Step 10: Page 3 already in cache. Cache: [1, 2, 5] 

Step 11: Page 4 loaded. Cache: [2, 5, 4] (Page Fault)

Step 12: Page 5 already in cache. Cache: [2, 5, 4]

Total Page Faults: 7

MRU Algorithm (Most Recently Used)

The MRU algorithm replaces the page that has been accessed most recently.

Example:

Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Cache Size: 3

Initial State: 
Cache: []

Step 1: Page 1 loaded. Cache: [1] (Page Fault)

Step 2: Page 2 loaded. Cache: [1, 2] (Page Fault)

Step 3: Page 3 loaded. Cache: [1, 2, 3] (Page Fault)

Step 4: Page 4 loaded. Cache: [1, 2, 4] (Page Fault)

Step 5: Page 1 loaded. Cache: [2, 4, 1] (Page Fault)

Step 6: Page 2 loaded. Cache: [4, 1, 2] (Page Fault)

Step 7: Page 5 loaded. Cache: [1, 2, 5] (Page Fault)

Step 8: Page 1 already in cache. Cache: [1, 2, 5]

Step 9: Page 2 already in cache. Cache: [1, 2, 5]

Step 10: Page 3 loaded. Cache: [1, 5, 3] (Page Fault)

Step 11: Page 4 loaded. Cache: [5, 3, 4] (Page Fault)

Step 12: Page 5 already in cache. Cache: [5, 3, 4]

Total Page Faults: 8

LIFO Algorithm (Last In, First Out)

The LIFO algorithm replaces the page that was most recently brought into memory.

Example:

Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Cache Size: 3

Initial State: 
Cache: []

Step 1: Page 1 loaded. Cache: [1] (Page Fault)

Step 2: Page 2 loaded. Cache: [1, 2] (Page Fault)

Step 3: Page 3 loaded. Cache: [1, 2, 3] (Page Fault)

Step 4: Page 4 loaded. Cache: [2, 3, 4] (Page Fault)

Step 5: Page 1 loaded. Cache: [3, 4, 1] (Page Fault)

Step 6: Page 2 loaded. Cache: [4, 1, 2] (Page Fault)

Step 7: Page 5 loaded. Cache: [1, 2, 5] (Page Fault)

Step 8: Page 1 already in cache. Cache: [1, 2, 5]

Step 9: Page 2 already in cache. Cache: [1, 2, 5]

Step 10: Page 3 already in cache. Cache: [1, 2, 5] 

Step 11: Page 4 loaded. Cache: [2, 5, 4] (Page Fault)

Step 12: Page 5 already in cache. Cache: [2, 5, 4]

Total Page Faults: 8