Problem of the day
In computing, a page fault is an exception for the memory management unit (MMU) when a process accesses a memory page without proper preparations.
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 to and is not present in memory, the page fault occurs, and the Operating System replaces one of the existing pages with a newly needed page.
You have given a sequence of pages in an array ‘Pages’ of length ‘N’ and memory capacity ‘C’. You have to find the number of page faults using the Least Recently Used (LRU) Algorithm. Initially, memory doesn't contain any pages.
'N' = 7, 'C' = 4, pages = [1, 2, 1, 4, 2, 3, 5].
For the first four pages, memory allocated with four pages, {1, 2, 1, 4}, page fault = 3.
For fifth, page number 2 is required, which is already present, page fault = 3.
Then, page number 3 is required, replaces LRU 2, page fault = 4.
Then, page number 5 is required, replaces LRU 1, page fault = 5.
The total page fault is 5.
The first line contains two space-separated integers, ‘N’ and ‘C’.
The next line contains the array ‘Pages’ of the length ‘N’, denoting the page sequences.
Output Format-
The only line contains a single integer denoting the total number of page faults.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
4 3
1 3 2 1
3
Memory allocated with three pages, {1, 3, 2}.
Hence total page faults = 3.
Then, Page number '1' is required, which is already present. Hence total page faults = 3 + 0 = 3.
9 4
5 6 1 3 2 4 1 6 5
8
1 <= ‘N’ <= 10^5
0 <= ‘C’ <= 10^5
1 <= Pages[i] <= ‘N’, for 1 <= i <= ‘N’
Time Limit: 1 sec
Which page is Least Recently Used in the set of Pages?
Approach: According to LRU, if the page we need is not present in the set of pages, the page fault occurs, and we replace the least recently used page with the current page. And if the page is present, we just use it, and no page fault occurs.
Algorithm:
O(N * C), where ‘N’ is the length of the array and ‘C’ is the memory capacity.
For each Page, we are removing an element from the vector with O(C) cost. Hence the overall complexity is O(N * C).
O(N), where ‘N’ is the length of the array.
We might store all the numbers to use a total of O(N) space. Hence the overall complexity is O(N).