Question:
In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:
The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.
A process accesses the pages in the following order of page numbers:
1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.
If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is __________. (Answer in integer)
In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:
The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.
A process accesses the pages in the following order of page numbers:
1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.
If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is __________. (Answer in integer)
Show Hint
The optimal page replacement algorithm minimizes page faults by replacing the page that will not be used for the longest time. In this modified version, the system can predict up to 4 future page references to make better decisions.
Updated On: Jan 30, 2026
Hide Solution
Verified By Collegedunia
Correct Answer: 6
Solution and Explanation
Step 1: Understand the Optimal Page Replacement Algorithm
In the optimal page replacement algorithm, the page to be replaced is the one that will not be used for the longest period of time in the future. Given the modification that the OS can predict up to the next 4 page references, the page replacement is based on this knowledge. Step 2: Simulate the Page Access Process
We have three memory frames that are initially empty. Let's go step by step: 1. Access Page 1: - Frames: `[1]`
- Page fault occurs.
2. Access Page 3: - Frames: `[1, 3]`
- Page fault occurs.
3. Access Page 2: - Frames: `[1, 3, 2]`
- Page fault occurs.
4. Access Page 4: - The frames are full. The OS predicts the next 4 pages will be `[2, 3, 1, 2]` and determines that page 1 will not be used again soon. We replace page 1 with page 4.
- Frames: `[4, 3, 2]`
- Page fault occurs.
5. Access Page 2: - Page 2 is already in the frame.
- No page fault.
6. Access Page 3: - Page 3 is already in the frame.
- No page fault.
7. Access Page 1: - The OS predicts the next pages will be `[2, 4, 3, 1]`. Page 3 will not be used in the future. We replace page 3 with page 1.
- Frames: `[4, 1, 2]`
- Page fault occurs.
8. Access Page 2: - Page 2 is already in the frame.
- No page fault.
9. Access Page 4: - Page 4 is already in the frame.
- No page fault.
10. Access Page 3: - The OS predicts the next pages will be `[1, 4, 2, 3]`. We replace page 2 (which will not be used soon) with page 3.
- Frames: `[4, 1, 3]`
- Page fault occurs.
11. Access Page 1: - Page 1 is already in the frame.
- No page fault.
12. Access Page 4: - Page 4 is already in the frame.
- No page fault.
Step 3: Counting the Page Faults
From the above simulation, we can see that the total number of page faults is 6. Thus, the number of page faults that will occur during execution of the process is 6.
In the optimal page replacement algorithm, the page to be replaced is the one that will not be used for the longest period of time in the future. Given the modification that the OS can predict up to the next 4 page references, the page replacement is based on this knowledge. Step 2: Simulate the Page Access Process
We have three memory frames that are initially empty. Let's go step by step: 1. Access Page 1: - Frames: `[1]`
- Page fault occurs.
2. Access Page 3: - Frames: `[1, 3]`
- Page fault occurs.
3. Access Page 2: - Frames: `[1, 3, 2]`
- Page fault occurs.
4. Access Page 4: - The frames are full. The OS predicts the next 4 pages will be `[2, 3, 1, 2]` and determines that page 1 will not be used again soon. We replace page 1 with page 4.
- Frames: `[4, 3, 2]`
- Page fault occurs.
5. Access Page 2: - Page 2 is already in the frame.
- No page fault.
6. Access Page 3: - Page 3 is already in the frame.
- No page fault.
7. Access Page 1: - The OS predicts the next pages will be `[2, 4, 3, 1]`. Page 3 will not be used in the future. We replace page 3 with page 1.
- Frames: `[4, 1, 2]`
- Page fault occurs.
8. Access Page 2: - Page 2 is already in the frame.
- No page fault.
9. Access Page 4: - Page 4 is already in the frame.
- No page fault.
10. Access Page 3: - The OS predicts the next pages will be `[1, 4, 2, 3]`. We replace page 2 (which will not be used soon) with page 3.
- Frames: `[4, 1, 3]`
- Page fault occurs.
11. Access Page 1: - Page 1 is already in the frame.
- No page fault.
12. Access Page 4: - Page 4 is already in the frame.
- No page fault.
Step 3: Counting the Page Faults
From the above simulation, we can see that the total number of page faults is 6. Thus, the number of page faults that will occur during execution of the process is 6.
Was this answer helpful?
0
0
Top Questions on Memory hierarchy
- Consider the following types of memories.
(A) Hard Disk Drive (HDD)
(B) Cache Memory
(C) Random Access Memory (RAM)
(D) Registers
Arrange the above memories according to their access speed (from fastest to slowest):- CUET (PG) - 2025
- Computer Science
- Memory hierarchy
- A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)
- A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found in L1 cache, it goes to L2 cache. If it fails to get the data from L2 cache, it goes to main memory, where the data is definitely available. Hit rates and access times of various memory units are shown in the figure. The average memory access time in nanoseconds (ns) is __________. (rounded off to two decimal places)
\includegraphics[width=0.5\linewidth]{53.png} 
A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)
View More Questions
Questions Asked in GATE CS exam
- With respect to a TCP connection between a client and a server, which of the following is true?
- GATE CS - 2026
- Computer Networks
- Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?
- GATE CS - 2026
- Database Management Systems
- Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?
- GATE CS - 2026
- Theory of Computations
- A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
- GATE CS - 2026
- Computer Organization and Architecture
- Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:
- GATE CS - 2026
- Computer Organization and Architecture
View More Questions