Page Replacement Algorithms and Thrashing Explained

Page Replacement Algorithms

• Random: The least efficient method, though simple to implement.
• FIFO (First-In, First-Out): Replaces the page that has resided in real memory the longest. It is easy to implement using a list to track page order.
• LRU (Least Recently Used): Replaces the page that has not been referenced for the longest period. It is highly effective because past behavior is often a reliable indicator of future needs.
• NUR (Not Used Recently): Selects a victim page cyclically, specifically targeting pages that have not been accessed or modified within a recent time window.
• LFU (Least Frequently Used): Replaces the page with the lowest reference count. This requires maintaining reference counters for each page.
• The Clock: A variant of LRU that gives each page a second chance. It organizes pages in a circular list and uses a pointer that moves clockwise.
• Clock with Two Hands: Designed to favor pages that are frequently referenced while they reside in memory.

Locality of Reference

This phenomenon describes how processes utilize only a limited set of pages during specific periods of their execution.

Thrashing

Thrashing occurs when a system spends more time swapping pages than executing processes. This leads to a significant drop in system performance and can cause a total collapse due to excessive page faults. Thrashing is directly related to the degree of multiprogramming; reducing this level can alleviate the issue. Essentially, thrashing indicates that a process exhibits poor locality.

Working Set Model

The Working Set is the collection of pages a process requires during a specific time interval. Informally, it represents the minimum set of pages that must reside in real memory to ensure acceptable efficiency. The working set model allows a process to execute only when its working set is fully loaded into memory.

Working Set (WS) Definition

The WS is defined as the set of virtual pages of process P accessed during the last t seconds of virtual time. The WS strategy calculates the value for each process whenever it completes a unit of CPU usage.

Factors Influencing WS Size

• The frequency of memory accesses made by the process.
• The time interval between WS loads.
• The page size.