Last Updated: 12 Nov, 2021
Page Faults
Moderate
Asked in companies
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.
For example:
'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.
Input Format-
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.
Approaches
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:
- Create a variable ‘ans’ and initialize it to 0.
- Create an empty vector ‘currentPages’.
- Iterate using a for loop from i = ‘0’ to ‘N - 1’.
- If Pages[i] in ‘currentPages’.
- Remove Pages[i] from ‘currentPages’.
- Append Pages[i] to ‘currentPages’.
- Else.
- Increment ‘ans’ by 1.
- If currentPages.size() == C.
- Remove currentPages[0] from ‘currentPages’.
- Append Pages[i] to ‘currentPages’.
- If Pages[i] in ‘currentPages’.
- Print ‘ans’.
Approach: Our goal is to efficiently maintain the order of the pages in the set of pages according to their last usage time. We can do this by storing the last time we used a page. We will use two pointers, ‘i’ to denote the starting position and ‘j’ to denote the ending position in the array ‘Pages’. If the last occurrence of Pages[i] is equal to ‘i’, then Page[i] is the Least Recently used page in the current set of pages. Otherwise, we move our ‘i’ pointer forward as Pages[i] is not the Least Recently used page.
Algorithm:
- Create an array ‘last’ of length ‘N + 1’ and initialize all its values to ‘-1’.
- Create four variables ‘ans’, ‘i’, ‘j’, ‘tot’ and initialize all of them to 0.
- Create an unordered set ‘S’.
- While j < N.
- While j < N.
- If Pages[i] not in S.
- If ‘tot’ == C.
- Break.
- Else.
- Add Pages[i] to ‘S’.
- Increment ‘ans’ by 1.
- Increment ‘tot’ by 1.
- Update last[Pages[j]] to j.
- Increment ‘j’ by 1.
- If ‘tot’ == C.
- Else.
- Update last[Pages[j]] to j.
- Increment ‘j’ by 1.
- If Pages[i] not in S.
- While i <= j.
- If last[Pages[i]] == i.
- Remove Pages[i] from ‘S’.
- Decrement ‘tot’ by 1.
- Increment ‘i’ by 1.
- Break.
- Increment ‘i’ by 1.
- If last[Pages[i]] == i.
- While j < N.
- Print ‘ans’.