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 demand paging .
We observe that most processes have reference locality .
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 working set .
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 page fault overheads , we can do prepaging .
Definition
A working set, w(k, t) is indexed by:
- k
No. of most recent memory references.
- t
Instant of time.
Given reference locality , and its address space constraints, we will observe as k increases, w(k,t) increases at a decreasing rate.
