Page Replacement Policy MCQ Quiz - Objective Question with Answer for Page Replacement Policy - Download Free PDF

For some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases. This most unexpected result is known as Belady’s anomaly. FIFO suffers from Belady's anomaly.

An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms and will never suffer from Belady’s anomaly. It replaces the page that will not be used for the longest period of time.

The correct answer is FIFO.

Key Points

• FIFO (First-In-First-Out) is a page replacement algorithm that suffers from Belady's anomaly.
• Belady's anomaly refers to the counterintuitive situation where increasing the number of page frames results in an increase in the number of page faults.
• In the FIFO algorithm, pages are replaced in the order they arrive, which can lead to suboptimal page replacement decisions.
• Belady's anomaly is not observed in other algorithms like LRU (Least Recently Used) and Optimal Page Replacement.

Additional Information

• LRU (Least Recently Used) algorithm replaces the page that has not been used for the longest period of time. It does not suffer from Belady's anomaly.
• Optimal Page Replacement algorithm replaces the page that will not be used for the longest period of time in the future. It also does not suffer from Belady's anomaly.
• Belady's anomaly occurs because the FIFO algorithm does not take into account the frequency or recency of page accesses.
• Understanding and addressing Belady's anomaly is important for designing efficient memory management systems.

The correct answer is Option 1: 7.

Key Points

• The Second Chance Page Replacement Algorithm is a modification of the FIFO (First In First Out) algorithm that reduces the number of page faults by giving pages a second chance to stay in memory if they have been referenced recently.
• When a page needs to be replaced, the algorithm inspects the reference bit of the pages in the order they were loaded into memory (FIFO order).
• If a page's reference bit is 0, it is replaced. If the reference bit is 1, the bit is cleared and the page is given a second chance, moving to the back of the queue.
• Consider the memory references in the working set: 2, 1, 2, 3, 5, 4, 1, 3, 4, 2, 1 with three frames in memory.
• The detailed steps are as follows:
  • Initially, all frames are empty.
  • Reference 2: Page 2 is loaded into the frame. (Page Fault)
  • Reference 1: Page 1 is loaded into the frame. (Page Fault)
  • Reference 2: Page 2 is already in the frame. (No Page Fault)
  • Reference 3: Page 3 is loaded into the frame. (Page Fault)
  • Reference 5: Page 2 is given a second chance (reference bit cleared), Page 1 is given a second chance (reference bit cleared), Page 3 is replaced by Page 5. (Page Fault)
  • Reference 4: Page 2 is given a second chance, Page 1 is given a second chance, Page 5 is replaced by Page 4. (Page Fault)
  • Reference 1: Page 1 is already in the frame. (No Page Fault)
  • Reference 3: Page 2 is given a second chance, Page 1 is given a second chance, Page 4 is replaced by Page 3. (Page Fault)
  • Reference 4: Page 2 is given a second chance, Page 1 is given a second chance, Page 3 is given a second chance (reference bit cleared), Page 4 is loaded into the frame. (Page Fault)
  • Reference 2: Page 2 is replaced by Page 2. (Page Fault)
  • Reference 1: Page 1 is already in the frame. (No Page Fault)
• In total, there are 7 page faults.

Additional Information

• The Second Chance Algorithm is also known as the Clock Algorithm because it can be visualized as a circular queue with a clock hand pointing to the next page to be considered for replacement.
• This algorithm helps reduce page faults by considering whether a page has been used recently before deciding to replace it.

Data:

page fault service time = S = 10 ms = 107 ns

page fault rate = p = \(\frac{1}{10^{6}}\)

memory access time = m = 30 ns

Formula:

Effective access time (EAT) = p × S + (1 - p) × m

Calculation:

EAT = \(\frac{1}{10^{6}}\)× 107 + (1 - \(\frac{1}{10^{6}}\)) × 30

EAT = 39.99 ns

The correct answer is 39.99ns which is approximately equal to 40ns.

Concept

Demand paging allows the execution of programs large than the size of physical memory. It is similar to a paging system with swapping. With this, a page is brought into main memory only when a reference is made to a location on that page. The lazy swapper concept is used in demand paging.

Points about demand paging:

• It combines the features of simple paging and overlaying to implement virtual memory.
• Each page of the program is stored contiguously in the paging swap space on secondary storage.
• Once the page is in the memory, it is accessed as in simple paging.
• Some form of hardware support is required to distinguish between those pages that are in memory and those are on the disk. Valid and invalid bits are used for this.

Data:

page fault service time = S = 10 ms = 10⁷ ns

page fault rate = p = \(\frac{1}{10^{6}}\)

memory access time = m = 20 ns

Formula:

Effective access time (EAT) = p × S + (1 - p) × m

Calculation:

EAT = \(\frac{1}{10^{6}}\)× 10⁷ + (1 - \(\frac{1}{10^{6}}\)) × 20

EAT = 29.99 ns

LRU page replacement algorithm:

Hit miss table:

5	1	2	3	4	3	2	3	1	2	4	3
M	M	M	M	M	H	H	H	M	H	M	M

 

∴number of miss = page faults = 8 

Important Points:

M is miss which corresponds to a page fault

H is hit which corresponds to page hit (no page fault)

The correct answer is option 4. 

Concept:

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.

Explanation:

Page reference	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
Hit (H)/ Miss(M)	M	M	M	M	H	M	M	M	M	M	M	H	H	M	M	H	H	M	M	M
page frame size= 3	7	7	7	2	2	2	2	4	4	4	0	0	0	0	0	0	0	7	7	7
		0	0	0	0	3	3	3	2	2	2	2	2	1	1	1	1	1	0	0
			1	1	1	1	0	0	0	3	3	3	3	3	2	2	2	2	2	1

Hence the page faults= 15

Hence the correct answer is 15.

Correct answer: option 3

Explanation:

• The RAM constitutes the physical memory of a computer. So, increasing the RAM does not increase the virtual memory.
• The speed of RAM remains constant, irrespective of its size. The cache memory is faster than the RAM.
• Increasing the RAM signifies that the memory will be able to hold more pages. As a result, when a process needs a particular page, chances are higher that the page will already be present in the memory. This will lead to lower page faults.

Optimal Page replacement:
In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

No. of hits = 11
No. of misses = 9

Concepts:

Belady’s anomaly is that the page-fault rate may increase as the number of allocated frames increases.

Explanation:

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.

Concept –

• Main Memory access time: 100 ns
• TLB lookup time: 20 ns
• Time to transfer one page to/from disk: 5000 ns
• TLB hit ratio: 0.95
• Page fault rate: 0.10
• 20 % of page faults need to be written back to disk

 

Effective memory access time = 0.95 (20 + 100) + 0.05 {0.90 (20 + 100 + 100) + 0.10 [0.80 (20 + 100 + 5000 + 100) + 0.20 (20 + 100 + 5000 + 5000 + 100)]}

= 155.0 ns

Explanation –

Breaking down the question for understanding the hierarchy.

We have three storage parts – TLB, Main memory, Hard disk

1. If that page’s address is in TLB (TLB hit 0.95)

• Address obtained from TLB lookup – TLB access (20 ns)
• Accessing page data from memory – Single memory access (100 ns)

2. If that page’s address is not in TLB (TLB miss 0.05)

• TLB accessed but address not obtained – TLB access
• Looking up Page table residing in main memory – One memory access
  • If Page fault does not occur (0.90), we find the page address and access the page data from main memory – Second memory access
• Looking up Page table residing in main memory – One memory access
  • If Page fault occurs (0.10), then first memory access wasted and we have to retrieve data from hard disk.
    • In this, we either have to only fetch the page (0.80) from hard disk – One Hard disk access
    • Or, we have to write a dirty page to disk (0.20) – Two Hard disk accesses
  • And in either case, we have brought the page back to main memory – Second memory access.

Correct answer is Option 3

Explanation: Using Least Recently Used(LRU) page replacement algorithm:

Frame size 3

4	4	4	1	1	1	5	5	5	2	2	2
	3	3	3	4	4	4	4	4	4	1	1
		2	2	2	3	3	3	3	3	3	5
miss	miss	miss	miss	miss	miss	miss	hit	hit	miss	miss	miss

total number of page fault=10