Comparison of page replacement startegies


Test example: 
Set of 3 jobs running concurrently in VM UNT
Drum file with program images: prog4/four.123.dat


SWAP OUT STRATEGY
allocate page until physical memory is exhausted, then find a victim
and swap it out.


	PID NF   PID  NF    PID NF    PID  NF   PID NF	Total
Job #1  4   0     9   2     10  1      1   3		  6

Job #2  5   2     7   0     12  2     11   1     2  2	  7

Job #3  6  43     8  30      3  2			 75
						---------------
							 88
Note,
	PID	- process ID of a process in the job
	NF	- the total number of the page faults the process
		  has incurred by the time it finishes


LOCAL LRU STRATEGY
The working set quota is set to 14 and reinforced. Any process that
fills its working set up to the quota and still needs more pages,
should first unreference (and swap out) the least recently used
page. The current context of the process keeps a count of the time
(in runs of the process on CPU) a page has last been used. The present
strategy is somewhat similar to that implemented in VAX/VMS.


	PID NF   PID  NF    PID NF    PID  NF   PID NF	Total
Job #1  4   0     9   2     10  1      1   3		  6

Job #2  5   2     7   0     12  2     11   1     2  1	  6

Job #3  6  47     8  32      3  1			 80
						---------------
							 92

CONCLUSION

The grand total number of page faults is slightly higher than with the
simple "rob-first-appropriate" page replacement strategy. Yet one has
to keep in mind that processes #6 and #8 are far from being "local",
they were designed to systematically access all their address space.
Typically a process spends most of the time fooling around a limited
segment of data and code. Anyway, it should be stressed that the
present system run has completed without any process swapping. In
reality, process swapping is actually quite expensive and involves a
lot of flurry. The process performance suffers from that as well (if
the process is interactive, the user notices that right away). Note
that with the local LRU strategy, only a memory-greedy process
incurres some extra page faults. But it does not affect other process.
In fact, the number of page faults of other processes is as small as
possible. It means, the process with large memory requirements would
suffer a little from its greed, but it would not punish "moderate"
processes.  So, the bottom line is, the overall system performance
with the local LRU strategy seems to be better.