Test: Page Replacement Algorithm - Computer Science Engineering (CSE) MCQ

In FIFO Page Replacement Algorithm, page fault rate may increase as the number of allocated frames increase. Hence its suffer from the belady's anomaly

LRU:

9-page faults:

FIFO:

9-page faults:

Hence LRU and FIFO will have 9-page faults.

S1: Random page replacement algorithm (where a page chosen at random is replaced)
Suffers from Belady’s anomaly.
Random page replacement algorithm can behave like any replacement algorithm. It may behave as FIFO, LRU, MRU etc.). When random page replacement algorithm behaves like a FIFO page replacement algorithm in that case there can be chances of belady’s anamoly.
For this let us consider an example of FIFO case, if we consider the reference string 3  2 1 0 3 2 4 3 2 1 0 4 and 3 frame slots, in this we get 9 page fault but if we increase slots to 4, then we get 10 page faults.
So, page faults are increasing by increasing the number of frame slots. It suffers from belady’s anamoly.

S2: LRU page replacement algorithm suffers from Belady’s anomaly
It doesn’t suffers from page replacement algorithm because in LRU, the page which is least recently used is replaced by the new page. Also, LRU Is a stack algorithm. (A stack algorithm is one that satisfies the inclusion property.) and stack algorithm doesn’t suffer from belady’s anamoly.

Page frames = 4
Pages: 1, 2, 3, 4 .... 45, 46, 47, 48, 49, 50, 50(H), 49(H), 48(H), 47(H), 46, 45, .....4, 3, 2, 1
First 50-page accesses will cause page fault but in reverse order page number 50, 49, 48, and 47 will not cause a page fault.
Hence total page faults are 50 + 46.

Least Recently Used (LRU) page replacement algorithm:
LRU policy follows the concept of locality of reference as the base for its page replacement decisions. LRU policy says that pages that have not been used for the longest period of time will probably not be used for a long time.

The given data, 
Array size= 64 x64 x size of each element.
Array size=64 x64x 64-bit
Array size= 64 x64 x8 bytes
The data cache with 32 blocks of 64 bytes each.
Data cache= 64 bytes
Initially, the data cache loads blocks when i=0 and j=0 and one cache miss after that till i=0 and j=8 there is no cache misses because at one-time cache loads the 64 bytes of data.
So number for 64 bytes 1 miss then,
64 x64 x8 bytes=?
Number of miss= 64 x64 x8 bytes / 64
The number of miss= 512.
Hence the correct answer is 512.

From the table below, we can see that pages have been transferred into frames 9 times.

Given that page frame size = 4
As there are 100 distinct pages which are first accessed → 100 page faults
when it accesses the same 100 pages but now in the reverse order → (100-4)
Because page frame size is four.
There fore, Total number of page faults = 100+ (100-4)= 196

First In First Out (FIFO):
This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

Page Fault:
A page fault happens when a running program accesses a memory page that is mapped into the virtual address space but not loaded in physical memory.

Hence the page faults= 15
Hence the correct answer is 15.

There are four-page frames are given and an LRU page replacement policy is used.

The given page size= 4,

The given page reference string is =  7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1

Number of Page faults = 9
Number of Page hits = 6
Number of memory access = 15
Page fault rate = Number of page faults / Number of memory access
Page fault rate = 9/15
Page fault rate = 0.6
Hence the correct answer is 0.6.

All algorithms strive to lower the number of page defects. The OS changes the page in this algorithm that will not be used for the longest amount of time in the future.