virtual memory 4487

actually LRU replacement strategy has the property that it can degenerate to FIFO replacement strategy ... i.e. program behavior that cycles through memory location. An example is the apl-360 memory management within a workspace ... referenced here

it worked ok, in small real-memory workspaces ... but porting apl-360 to cms-apl large virtual memory was disasterous. the issue is that some number of applications can have transient end patterns that resumble such cyclic behavior.

the problem with LRU degenerating to FIFO is that even if the virtual memory pages, that are being cycled, are only one larger than the available real memory ... every virtual page in the cycle will be faulted on every pbutt thru the cycle (aka the first-FIFO page in such a cycle is also the least recently used). Say there are N available real pages (for the cycle) and there are N+1 pages in the cycle. Page fault for page N+1 will replace page 1 (since it is both LRU and FIFO) ... but the next page to be accessed will be page 1 ... the page just replaced. In the N+1 scenario, this replacing the very next page that is going to be needed will continue throughout the cycle.

global clock is a very good and efficient approximation to global LRU replacement strategy ... including degenerating to FIFO under various conditions. as i mentioned before

in the early 70s, i came up with a coding slight of hand that resulted in global clock (LRU approximation) that degenerating to RANDOM rather than FIFO. in the N+1 case where FIFO replacement was constantly selecting the very next page that was about to be used ... a RANDOM page would be selected for replacement instead. This significantly reduced the overall fault rate ... since you were constantly replacing the very page that you were about to use.

misc. past posts on page replacement algorithms, virtual memory, etc

--