# What is the Working Set Page Replacement algorithm?

## Scenario

In the purest form of paging, when processes are loaded, none of their pages reside in memory.

When CPU fetch first instruction, this triggers page fault, and brings in page with first instruction.

This is known as .

We observe that most processes have .

This means that the things these processes need are in close proximity, memory wise. Hence they reside in a small collection of pages. e.g. multipass compiler.

The set of pages in memory is known as the .

If the working set is not fully loaded, page faults occurs. If page faults occur every few instructions, we term the program as thrashing.

Executing an instruction takes ns, reading a page takes ms.

To avoid , we can do .

## Definition

A working set, w(k, t) is indexed by:

1. k

No. of most recent memory references.

1. t

Instant of time.

Given , and its address space constraints, we will observe as k increases, w(k,t) increases at a decreasing rate.