working set

Question

How working set algorithm is related to principle of locality?

Answer 1

working set algorithm tells how many frames a process is actually need.

Coming to locality of reference :

In  locality of reference a particular memory location is referenced then it may refer the same location in future. 

Here locality is set of pages that are actively used together.

In working set algorithm working set window tells how many page references are there in a locality.If all page references are there in memory then there is no page fault else page fault occured.

when a process executes it moves from one locality to another locality.

Eg:

Suppose page refereneces are 3,2,3,4,${\color{Red} 6,{\color{Red} 2},{\color{Red} 4,{\color{Red} 1}}}$ ${\color{Green} 6,{\color{Green} 7,{\color{Green} 4,{\color{Green} 3}}}}$,${\color{Blue} 3,{\color{Blue} 5,{\color{Blue} 4,{\color{Blue} 1}}}}$

working set window $\Delta$=4.

So in the above  there are 4 locality of page reference tables are there.when process executes it changes from one locality to another and no of frames needed is calculated based on working set window.

In the first locality No of frames needed =3

and 2nd locality no of frames=4

and in last locality no of frames=4.