Virtual Memory MCQ Quiz - Objective Question with Answer for Virtual Memory - Download Free PDF

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.

The correct answer is FIFO (First In First Out)

Concept:

Belady’s anomaly is the phenomenon in which increasing the number of page frame results in  increase in the number of page faults.

Explanation:

FIFO replacement algorithm results in page faults by increasing the number of page frames.

Consider the example:

Frame = 3

String = 0 1 5 3 0 1 4 0 1 5 3 4

REQUEST	0	1	5	3	0	1	4	0	1	5	3	4
Frame 3			5	5	5	1	1	1	1	1	3	3
Frame 2		1	1	1	0	0	0	0	0	5	5	5
Frame 1	0	0	0	3	3	3	4	4	4	4	4	4
Miss/Hit	Miss	Miss	Miss	Miss	Miss	Miss	Miss	Hit	Hit	Miss	Miss	Hit

 

Number of page faults = 9

Take number of frames = 4

REQUEST	0	1	5	3	0	1	4	0	1	5	3	4
Frame 4				3	3	3	3	3	3	5	5	5
Frame 3			5	5	5	5	5	5	1	1	1	1
Frame 2		1	1	1	1	1	1	0	0	0	0	4
Frame 1	0	0	0	0	0	0	0	4	4	4	3	3
Miss/Hit	Miss	Miss	Miss	Miss	Hit	Hit	Miss	Miss	Miss	Miss	Miss	Miss

Number of page faults = 10

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.