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
Solution and Explanation
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.
Top Questions on Memory hierarchy
Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is __________. (Answer in integer)
1001: i = 1
1002: j = 1
1003: t1 = 10i
1004: t2 = t1+j
1005: t3 = 8t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013A 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)
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)
Consider the following operations on an initially empty stack:
Push 10
Push 20
Pop
Push 30
Pop
Push 40
What is the final content of the stack?Which of the following is true about the binary search algorithm when applied to a sorted array?
Questions Asked in GATE CS exam
The value printed by the given C program is __________ (Answer in integer).
- GATE CS - 2025
- Programming and Data Structures
- GATE CS - 2025
- Programming in C
Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into the I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _________ (Answer in integer).
- GATE CS - 2025
- Programming in C
- In a double hashing scheme, \( h_1(k) = k \mod 11 \) and \( h_2(k) = 1 + (k \mod 7) \) are the auxiliary hash functions. The size \( m \) of the hash table is 11. The hash function for the \( i \)-th probe in the open address table is \( [h_1(k) + i \cdot h_2(k)] \mod m \). The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is:
- GATE CS - 2025
- Programming and Data Structures
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ___________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures