Operating systems — page replacement: Which page replacement policy removes a page if it is not in the currently favoured subset (working set) of a process's pages?

Introduction / Context:In virtual memory systems, the operating system must decide which page to evict when physical frames are full. Policies like FIFO, LRU, LFU, and working set differ in how they choose a victim page. This question tests understanding of working set–based replacement, which focuses on a process’s current locality of reference.

Given Data / Assumptions:

• The process exhibits locality: a subset of pages is actively used at any time.
• The “favoured subset” refers to the process’s working set within a window of recent references.
• When a fault occurs and memory is full, one page must be evicted.

Concept / Approach:

The working set model tracks the set of pages referenced during the last tau references (or within a time window). Pages outside this set are considered inactive and are the preferred eviction candidates because they are unlikely to be needed soon, reducing the chance of immediate faults.

Step-by-Step Solution:

Verification / Alternative check:

Empirical results and textbook analyses show working set–aware policies reduce thrashing by aligning memory allocation with the process’s active footprint.

Why Other Options Are Wrong:

• FIFO: Evicts the oldest loaded page, ignoring locality.
• LRU: Prefers the least recently used page, not explicitly the non-working set.
• LFU: Uses long-term frequency, which can lag phase changes.
• None of the above: Incorrect because working set matches the description.

Common Pitfalls:

Confusing LRU with working set; LRU approximates recent use but does not explicitly track a time-window set. Also, ignoring overhead of tracking the working set window is a common oversight.

Final Answer:

Working set