virtual memory 4474

Anne & Lynn Wheeler

After our previous discussions, I looked high and low for any details on the grenoble system, and fifo or local working sets on cp67. Unfortunately I found nothing.

My suspicion is that Grenoble used strict fifo local working sets. These are now known (possibly as a result of that very project) to not perform well.

VMS and WNT use Second Chance Fifo, which has very different behavior to strict Fifo, and is reputed to have the same behavior as WSClock. VMS also has an option for a third chance - I don't know if WNT also has that. This gives them all the control advantages that local working sets allow with the same paging statistics as global.

In second chance fifo, pages removed from a local working set are tossed into a global Valid list to become a candidate for recycling. If referenced again quickly the page is pulled page into the local working set for almost no cost. This is essentially the same as the WSClock and its referenced bits.

In 3rd chance, VMS allows a page to make 2 trips through the working set list. After the first trip a flag is set on the working set entry it goes to the tail of the list and the PTE's valid flag is cleared. If it gets touched again then the handler just enables the PTE. When it gets to the head of the list again the PTE is checked to see if it was referenced. If is was, it cycles again, otherwise it goes into the global Valid list. 1

The working set size is not fixed but can vary if memory is available. If a process pages too much the size is increased until it stops. 2}

The combination of all these features makes the VMS-WNT local working sets completely different from the early strict fifo models.

1 My informal experiments on VMS found that enabling the 3rd chance mechanism had no effect on performance. The 2nd chance mechanism appears to be quite sufficient.

2 A valid criticism of VMS, and possibly WNT, is they use boot time sized arrays to track the working set entries rather than linked lists. Because of this there is an absolute maximum working set size and processes which reach that maximum will page fault even when there is gobs of free memory on a system. However that is a deficiency in a particular implementation and not due to the local working sets.

There is no technical reason for these to not allow process working sets to be arbitrarily large, up to all of virtual space is memory is available, and use dynamic software controls to limit their size.

Thanks, I didn't see this reference before. Unfortunately it is imprisoned inside the ACM.

Eric