Question

When a virtual memory system replaces the page that has not been used for the longest period of time, what specific page replacement algorithm is being applied?

Accepted Answer

When a virtual memory system replaces the page that has not been used for the longest period of time, the Least Recently Used (LRU) page replacement algorithm is being applied. In a virtual memory system, programs use logical memory addresses which are mapped to physical memory addresses. Memory is divided into fixed-size blocks called pages. When a program tries to access a page that is not currently in physical memory, a page fault occurs. If physical memory is full, the operating system must choose an existing page to remove, or replace, to make room for the new page. The LRU algorithm selects the page for replacement that has not been referenced or accessed by the CPU for the longest duration among all pages currently residing in physical memory. The fundamental assumption behind LRU is that pages that have been heavily used in the recent past are likely to be used again soon (a concept known as temporal locality), while pages that have not been used for a long time are less likely to be accessed again in the near future. To implement LRU accurately, the system must continuously track the exact time or order of last access for every page in physical memory. This typically involves maintaining timestamps for each page or using a stack-like structure where pages are moved to the top on each access, making the page at the bottom the least recently used. While LRU often provides excellent performance by minimizing page faults, its precise implementation can be complex and incur significant overhead due to the continuous tracking required for every memory access.

Home → All Courses → Science and Mathematics Courses → Computer Science → Flashcard

When a virtual memory system replaces the page that has not been used for the longest period of time, what specific page replacement algorithm is being applied?