Virtual Memory MCQ Quiz - Objective Question with Answer for Virtual Memory - 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 option 2: FIFO incurs two more page faults than LRU

Key Points

Given:

• Page reference sequence = 13, 18, 12, 13, 19, 11, 16, 13, 18, 19, 13, 16, 12, 11, 13
• Number of frames = 5

FIFO (First-In-First-Out):

Page faults occur when a page is not found in the memory and must be brought in. FIFO replaces the oldest page first.

FIFO Page Fault Count: 10

LRU (Least Recently Used):

In LRU, the page that hasn’t been used for the longest time is replaced.

LRU Page Fault Count: 8

Hence:

• FIFO incurs two more page faults than LRU.

Additional Information

• Page Replacement Algorithms are crucial in Operating Systems to manage memory effectively.
• FIFO is simple but may lead to Belady’s anomaly.
• LRU is more efficient as it replaces the least recently used page, usually resulting in fewer page faults.

Therefore, the correct answer is: option 2: FIFO incurs two more page faults than LRU

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.

Virtual Memory in Operating System:

• A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that's set up to emulate the computer's RAM.
• Virtual memory implements the translation of a program's address space to physical addresses.
• Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using the disk.
• Second, it allows us to have memory protection because each virtual address is translated into a physical address.

Concept:

The working set model: The memory that is being accessed frequently by an application.

Same thing is done by principle of locality.

Explanation:

There are two types of principle of locality

1. Spatial locality: whenever we are looking for an element the chances are that, the particular element will be present in a close proximity around the one which we have previously referred.
2. Temporal locality: Least recently used element is going to be used again.

Principle of locality is the correct answer, hence option 3 is the correct answer.

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.