FOR FREE YEAR SOLVED

Working Set algorithm

 

Disadvantage of static page replacement algorithm

All page replacement algorithms which are discussed in previous chapters like optimal, FIFO, LRU, MRU and LFU, etc. are local page replacement algorithms. We can also say static page replacement algorithms where the number of the frames in the main memory is fixed.

 

With local replacement, if one process starts thrashing, it cannot steal frames from another process and cause the latter to thrash as well so, the average access time of memory will be increased due to the overhead of page fault service time.

 

Solution: 

To prevent thrashing we must provide frames to process as per its needs. 

 

The working-set strategy is a dynamic page replacement algorithm that starts by looking at how many frames a process is actually using. It greatly reduces the page fault rate. 

 

Working set model provides frames a basis for deciding how many and which pages of a process should be in memory to obtain a good performance of the process. It is based on locality of reference.

 

Definition: Working set model is a dynamic page replacement algorithm that allocates frames to a particular process assuming that the nearest future of pages will be used is a closed approximation of the recent past pages in memory.

 

This model uses a parameter to define the working-set window. The idea of this window to examine the most recent page references. 

 

The set of pages that a process is currently using is its working set.

 

Example: 

Let,

Page references: 2  6 1  5  7 7  7  5 1  6  2 3  4  1  2  3  4 4  4

 

Maximum Working set window (w): 5.

 

Note: We always take a maximum of five pages in memory because the maximum window is 5.

 

Explanation: 

 

Step 1: 

 

 

Working set: w = {2}, initially it requires page 2 and window size is 1 (because it is dynamic create as per requirement). So, working set w = {2}. Page fault.

 

Step 2:

 

 

Working set: w = {2, 6},  now, it require page 6and window size is 2. So, working set w = {2, 6}. Page fault.

 

Step 3:

 

 

Working set: w = {2, 6, 1}, here it require page 1and window size is 3. So, working set w = {2, 6, 1}. Page fault

 

Step 4:

 

 

Working set: w = {2, 6, 1, 5}, next requirement is page 5and window size is 4. So, working set w = {2, 6, 1, 5}. Page fault

 

Step 5:

 

 

Working set: w = {2, 6, 1, 5, 7}, now, it require page 7and window size is 5. So, working set w = {2, 6, 1, 5, 7}. Page fault

 

Step 6:

 

 

Working set: w = {6, 1, 5, 7}, next requirement is again page 7 but it is already loaded at main memory frameIn that case, only four pages are required so, window size is 4, and working set w = {6, 1, 5, 7}. No Page fault

 

Step 7:

 

 

Working set: w = {1, 5, 7}, next requirement is again page 7 but it is already loaded at main memory frameHere three pages are required so, window size is 3 and working set w = {1, 5, 7}. No Page fault

 

Step 8:

 

 

Working set: w = {5, 7}, next requirement is page 5 but it is already loaded at main memory frameThe next two pages are required so, window size is 2, and working set w = {5, 7}. No Page fault

 

Step 9:

 

 

Working set: w = {1, 5, 7}, next requirement is page 1 but it is already present at main memory frameHere three pages are required so, window size is still 3, and working set w = {1, 5, 7}. Page fault

 

Step 10:

 

 

Working set: w = {1, 5, 7, 6}, next requirement is page 6Here four pages are required so, window size is 4 and working set w = {1, 5, 7, 6}. Page fault

 

Step 11:

 

 

Working set: w = {1, 5, 7, 6, 2}, next requirement is page 2Here five pages are required so, window size is 5 and working set w = {1, 5, 7, 6, 2}. Page fault

 

Step 12:

 

 

Working set: w = {1, 5, 6, 2, 3}, next requirement is page 3Here next five pages are required so, window size is 5 and working set w = {1, 5, 6, 2, 3}. Page fault

 

Step 13:

 

 

Working set: w = {1, 6, 2, 3, 4}, next requirement is page 4Here next five pages are required so, window size is 5 and working set w = {1, 6, 2, 3, 4}. Page fault

 

Step 14:

 

 

Working set: w = {1, 6, 2, 3, 4}, next requirement is page 1. Here next five pages are required so, window size is 5 and working set w = {6, 2, 3, 4, 1}. Page fault

 

Step 15:

 

 

Working set: w = {1, 2, 3, 4}, Now distinct four pages are required so, window size is 4 and working set w = {1, 2, 3, 4}. No Page fault

 

Step 16:

 

 

Working set: w = {1, 2, 3, 4}, Now here four pages are required so, window size is 4 and working set w = {1, 2, 3, 4}. No Page fault

 

Step 17:

 

 

Working set: w = {1, 2, 3, 4}, Now here four pages are required so, window size is 4 and working set w = {1, 2, 3, 4}. No Page fault

 

Step 18:

 

 

Working set: w = {1, 2, 3, 4}, here again four pages are required so, window size is 4 and working set w = {1, 2, 3, 4}. No Page fault

 

Step 19:

 

 

Working set: w = {2, 3, 4}, Now here three pages are required so, window size is 3 and working set w = {2, 3, 4}. No Page fault

 

The number of total page faults= 11.

 

Now, we are calculating the average frame requirement

 

 

 

So, average frame requirement = 3.73

 

Important note:

In the examination, we have no time to calculate the average frame requirement in this way. The above elaborate explanation is only to clear concept better way. 

 

Shortcut:

We can draw it more precise way like:

 

 

Here we calculate the number of windows on each page reference the same way.