PROBLEM DESCRIPTION
In operating systems that use paging for memory management, page replacement algorithm is needed to decide which page needs to be replaced when the new page comes in. Whenever a new page is referred and is not present in memory, the page fault occurs and Operating System replaces one of the existing pages with a newly needed page.
Given a sequence of pages in an array pages[] of length N and memory capacity C, find the number of page faults using Least Recently Used (LRU) Algorithm.
SOLUTION
We can solve this by using the Least Recently Used (LRU) page replacement algorithm with a Deque and a Set. The Deque keeps track of the pages in memory, placing the most recently used ones at the front. As we go through the page requests, we check if a page is already in memory. If it is, we move it to the front; if not, we count it as a page fault. If memory is full, we remove the least recently used page from the back.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
static int pageFaults(int N, int C, int pages[]) {
// Deque to keep track of pages currently in memory (most recently used at the front)
Deque<Integer> memory = new LinkedList<>();
// Set to allow O(1) lookup for pages in memory
Set<Integer> pageSet = new HashSet<>();
int pageFaults = 0;
// Iterate through each page request in the pages array
for (int i = 0; i < pages.length; i++) {
int currentPage = pages[i];
// Check if the current page is already in memory
if (pageSet.contains(currentPage)) {
// Remove it from its current position
// and add it to the front
memory.remove(currentPage);
memory.addFirst(currentPage);
} else {
// Page fault occurs; the page is not in memory
pageFaults++;
// Check if memory is full
if (memory.size() == C) {
// Remove the least recently used page (last in the deque)
int last = memory.removeLast();
pageSet.remove(last);
}
// Add the current page to the front (most recently used)
memory.addFirst(currentPage);
pageSet.add(currentPage);
}
}
return pageFaults;
}
}