Bissoy.com
Doctors Medicines MCQs Q&A

Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then

Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then Correct Answer OPTIMAL < FIFO < LRU

The correct answer is Option 2.

Concept:

First In First Out (FIFO):

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.

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

Least Recently Used :
In this algorithm, the page will be replaced which is least recently used.

Solution: 

First In First Out (FIFO):

The given virtual page reference string is 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 and the main memory size is 3-page frames.

1 1 1 1 4 4 4 4 4 4
  2 2 2 2 1 1 1 1 1
    3 3 3 3 3 2 2 2
F F F H F F H F H H

Total number of page faults= 6

Optimal Page replacement:

1 1 1 1 1 1 1 1 1 1
  2 2 2 4 4 4 4 4 4
    3 3 3 3 3 2 2 2
F F F H F H H F H H

Total number of page faults= 5

Least Recently Used :

1 1 1 1 4 4 4 2 2 2
  2 2 2 2 2 3 3 3 1
    3 3 3 1 1 1 4 4
F F F H F F F F F F

Total number of page faults= 9

The number of page faults with OPTIMAL, FIFO, LRU (5,6,9) is OPTIMAL < FIFO < LRU.

Related Questions

Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 Let a computer system has main memory size of 3 page frames which are initially empty and it is running on demand paged virtual memory system. The number of page faults under LRU and FIFO page replacement policy are respectively:
Consider the following page reference string: 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 Assume that there are three-page frames which are initially empty. Let LRU, FIFO, OPTIMAL denote the number of page faults under the corresponding page replacement strategy. Then, which of the following is TRUE?
A computer has sixteen pages of virtual address space but the size of main memory is only four frames. Initially the memory is empty. A program references the virtual pages in the order of 0, 2, 4, 5, 2, 4, 3, 11, 2, 10. How many page faults occur if LRU page replacement algorithm is used?
How many page faults occur in a system with LRU page replacement policy having 3 (initially empty) page frames for the following string of page reference - 5, 1, 2, 3, 4, 3, 2, 3, 1, 2, 4, 3?
A virtual memory system uses FIFO page replacement policy and allocates a fixed number of frames to the process. Consider the following statements M : Increasing the number of page frames allocated to a process sometimes increases the page fault rate N : Some programs do not exhibit locality of reference Which one of the following is true?
A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements. P : Increasing the number of page frames allocated to a process sometimes increases the page fault rate Q : Some programs do not exhibit locality of reference Which of the following is TRUE?
A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?
Fact 1: Eyeglass frames cost between $35 and $350.
Fact 2: Some eyeglass frames are made of titanium.
Fact 3: Some eyeglass frames are made of plastic.

If the first three statements are facts, which of the following statements must also be a fact?
I: Titanium eyeglass frames cost more than plastic frames.
II: Expensive eyeglass frames last longer than cheap frames.
III: Only a few eyeglass frames cost less than $35.
Applying the LRU page replacement to the following reference string. 1 2 4 5 2 1 2 4 The main memory can accommodate 3 pages and it already has pages 1 and 2. Page 1 came in before page 2. How many page faults will occur?
Consider the following page reference string. 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 For LRU page replacement algorithm with 4 frames, the number of page faults is?