virtual memory 4484

clock and global lru uses an LRU approximation ... that kind of sorts pages into two categories ... those that have their reference bit used since the last examination-reset, and those that haven't had their reference bit used since their last examination-reset.

we did significant simulation with full instruction traces some of it was part of the vs-repack technology previously referenced

where in detailed simulation with full instruction traces of i-refs, d-refs, and d-stores ... compared lots of global and local lru approximations as well as "true" lru ... where exact ordering of page references were maintained.

the clock approach to lru approximation (that i had come up with as an undergraduate in the 60s) ... which is also described in Carr's phd thesis previously mentioned (and can be found online) misc. recent past posts mentioning Carr's thesis

R. Carr, Virtual Memory Management, Stanford University, STAN-CS-81-873 (1981)

R. Carr and J. Hennessy, WSClock, A Simple and Effective Algorithm for Virtual Memory Management, ACM SIGOPS, v15n5, 1981

.... typically operated within 10-15percent of "true" lru with extremely nominal overhead (based on the detailed simulation). their was no list manipulation at all, just the cyclic examination ... which was approx. six instructions per page examined and not taken ... and the avg. depth of search typically avg. six pages before finding a page to select (i.e. on the order of 36 instructions to find and select a page for replacement).

during this period with the work on extensive full instruction traces and analysis of wide variety of replacement strategies ... both real implementation in live deployment and the extensive simulation and modeling work ... I discovered a coding hack that allowed a kind of clock operation to actual beat "true" LRU ... the instructions and pathlength was identical to regular clock ... but there was a coding slight of hand the resulted in being able to beat "true" LRU (based on the detailed simulation work). post in this thread mentioning the detailed simulation work, comparing the LRU approximations with "true" LRU ... and coming up with the slight-of-hand clock that would beat "true" LRU

--