virtual memory 4481
Brian Inglis
On Mon, 15 May 2006 19:25:53 +0000 (UTC) in alt.folklore.computers, The accessed bit should be in the hardware just like the mod bit. FIFO avoids tracking anything to...
Hard to tell exactly what was going on then. In Belady's "A study of replacement algorithms for a virtual-storage computer" from 1966 (I just quickly scanned it - it is a bit of a heavy read) he compares RAND, FIFO, OPT and something called MIN which sounds very similar to working sets. He mentions ATLAS, and talks about how reference and modify bits can be helpful, but no mention of LRU. Denning's working set paper was in 1968.
clock and global lru uses an LRU approximation ... that kind of sorts pages into two categories ... those that have their reference bit used...
So fifo was obviously on peoples minds, but Lynn says he was doing LRU around this time so it was probably gathering steam.
I don't see why linked list overhead would be significantly different.
VMS uses a circular buffer with tail (add) and head (remove) indexes. Dirt cheap but if the tail meets the head, the list is full.
A slightly more sophisticated mechanism would have a linked list of page-sized working set "buckets", with each bucket containing fields for the list link, some house keeping fields, and a vector of working set entries. Basically a linked list of small arrays. It is no more expensive than the circular buffer, but has no intrinsic size limit. The vast majority of processes would only use one or two buckets.
As for global, it needs to maintain a linked list of reverse pointers to all the PTE's that reference each frame so that it can remove the frame from all address spaces and recycle with a minimum of work. Without reverse pointers, it requires scanning all process page tables (yeech - try that in a 48 bit address space).
So these list overheads appear equivalent.
Eric
Alt Folklore Computers from Newsgroups