Page Faults in LRU
Problem link: https://www.geeksforgeeks.org/problems/page-faults-in-lru5603/1
Problem Statement
Given a sequence of pages and a memory capacity, find the number of page faults using the Least Recently Used (LRU) page replacement algorithm. A page fault occurs when a requested page is not present in memory and must be loaded, possibly replacing an existing page if memory is full. The LRU algorithm replaces the page that has not been used for the longest period of time.
Input
N: Length of the page reference sequence.C: Capacity of memory (number of page frames).pages[]: Array representing the sequence of page references.
Output
- Return the total number of page faults that occur.
Example
Input: N = 9, C = 4, pages = [5, 0, 1, 3, 2, 4, 1, 0, 5]
Output: 8
Explanation:
- Initially, all frames are empty, so the first 4 pages (5, 0, 1, 3) cause page faults.
- Next, page 2 replaces LRU page 5.
- Page 4 replaces LRU page 0.
- Page 1 is already in memory.
- Page 0 replaces LRU page 3.
- Page 5 replaces LRU page 2.
Total page faults: 8
Explanation
The output is 8 because each time a new page is referenced and not found in memory, a page fault occurs. When memory is full, the least recently used page is replaced, which may also cause a page fault if the new page is not already in memory.
Brute Force
Intuition
The brute force approach involves simulating the LRU process using a list to keep track of pages in memory. For each page in the sequence, check if it is already in memory. If not, add it to memory (causing a page fault). If memory is full, remove the least recently used page (the first element in the list) before adding the new page. This approach is straightforward but inefficient for large inputs due to O(N*C) time complexity, as it requires searching the list for each page.
Approach
- Initialize an empty list to represent memory.
- For each page in the sequence:
- If the page is not in memory, increment the page fault count.
- If memory is full, remove the first page (LRU) from the list.
- Add the current page to the end of the list.
- Return the total page fault count.
Visualization
Code (Java)
// Brute Force Approach: Using ArrayList to simulate LRU
import java.util.*;
class Solution {
static int pageFaults(int N, int C, int[] pages) {
ArrayList<Integer> memory = new ArrayList<>();
int pageFaults = 0;
for (int page : pages) {
if (!memory.contains(page)) {
pageFaults++;
if (memory.size() == C) {
memory.remove(0); // Remove LRU page (first element)
}
memory.add(page); // Add new page to end
} else {
memory.remove((Integer) page); // Remove to update LRU order
memory.add(page); // Add to end (most recently used)
}
}
return pageFaults;
}
public static void main(String[] args) {
int N = 9, C = 4;
int[] pages = {5, 0, 1, 3, 2, 4, 1, 0, 5};
System.out.println(pageFaults(N, C, pages)); // Output: 8
}
}
Complexity Analysis
- Time: O(N*C) because for each page, we may search the entire memory list (O(C)) to check for presence and update order.
- Space: O(C) for storing the pages in memory.
Optimal Solution
Intuition
The optimal approach for LRU uses a combination of a hash map and a doubly linked list. The hash map allows O(1) lookups to check if a page is in memory, while the doubly linked list maintains the order of pages from least to most recently used. This reduces the time complexity to O(N) for the entire sequence, as each operation (insert, delete, update) on the linked list is O(1).
Approach
- Use a hash map to store page keys and their corresponding nodes in a doubly linked list.
- For each page in the sequence:
- If the page is in the hash map, move its node to the end of the list (most recently used).
- If not, increment the page fault count. If memory is full, remove the first node (LRU) from the list and its entry from the hash map. Add the new page to the end of the list and update the hash map.
- Return the total page fault count.
Visualization
Code (Java)
Complexity Analysis
- Time: O(N) because each operation (insert, delete, update) on the hash map and doubly linked list is O(1).
- Space: O(C) for storing the pages in memory and the hash map.
Quick Revision (Brute Force)
- Use an ArrayList to simulate memory and LRU order.
- For each page, check if it is in memory; if not, add it and increment page fault count.
- If memory is full, remove the first page (LRU) before adding the new page.
- Time: O(N*C), Space: O(C).
Quick Revision (Optimal)
- Use a HashMap for O(1) lookups and a doubly linked list to maintain LRU order.
- For each page, if present, move it to the end of the list (most recently used).
- If not present, add it to the end; if memory is full, remove the first node (LRU).
- Time: O(N), Space: O(C).