Exams › GATE › Technical

A computer has twenty physical page frames containing pages numbered 10 through 120. A program accesses the pages numbered 1, 2, ..., 100 in that order and repeats the access sequence three times. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

1. Least-recently-used
2. First-in-first-out
3. Last-in-first-out
4. Most-recently-used

Correct answer: Least-recently-used

Solution

The program scans pages 1 to 100 repeatedly, which is much larger than the 20 available frames. For this pattern, LRU behaves like the optimal policy because the least recently used page is also the least likely to be needed soon in a sequential scan. Therefore, LRU incurs the same number of page faults as OPT here.

Related GATE Technical questions

• Which of the following statements about threads is/are TRUE?
• Which of the following process state transitions is/are NOT possible?
• Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption. T1: \[ a = a + 1;\] \[ b = b + 1;\] T2: \[ b = 2b;\] \[ a = 2a;\] Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?
• Consider a demand paging memory management system with a 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte-addressable, what is the maximum number of entries in the page table?
• A computer has two processors, M1 and M2. Four processes P1, P2, P3, and P4 have CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, and arrive at the same time. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows: - M1 uses the priority order P1 > P3 > P2 > P4, i.e., P1 has the highest and P4 the lowest priority. - M2 uses the priority order P2 > P3 > P4 > P1, i.e., P2 has the highest and P1 the lowest priority. A process $P_i$ is scheduled to a processor $M_k$ if the processor is free and no other process $P_j$ is waiting with higher priority. At any given point in time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore context-switch time. What will be the average waiting time of the processes in milliseconds?
• Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2. Group 1 P. Gang Scheduling Q. Rate Monotonic Scheduling R. Fair Share Scheduling Group 2 1. Guaranteed Scheduling 2. Real-time Scheduling 3. Thread Scheduling

⚔️ Practice GATE Technical free + battle 1v1 →