virtual memory 4475

some posts in previous incarnation of this thread from

the original cp67 that was installed in the univ. last week jan68 used effectively a variation on fifo; it scanned storage looking for pages in state somewhat like your second chance ... and if it couldn't find one ... it took a standard page.

within several months, i had changed that and added testing and resetting of the reference bits in cycle. ... basically clock like operation.

grenoble used resetting of reference bits in local LRU.

so multics did a multi-bit reference cycle operation ... 5th floor, 545 tech. sq; science center was on 4th floor 545 tech sq.

the original cp67 didn't have any thrashing controls. early in '68, lincoln labs made a modification that limited the total number of processes in the active-dispatch set ... as a means of limiting page contention ... however, it didn't take into account amount of pages needed by different virtual address spaces.

i added some calculations that measured real storage requirements of a virtual address space. the real storage requierment calculations were dynamically adjusted that included some measure of proportion of time spent waiting for page fault servicing ... aka if total page fault service time was low, estimate of virtual address space requirement for real storage was lowered, if total page fault service time was high, estimate of virtual address space requirement for real storage was increased ... basically dynamically adapting amount of real storage requirements to configuration, workload, and contention (i.e. high paging rates that also introduced long queues and high service times would increase estimates of real storage requirements, the same high paging rates with higher speed devices and no queues, and much lower service times would have lower estimates of real storage requirements).

in the early 70s, we ran huge number of experiments with lots of different code implementation in live operation as well as having various kinds of detailed simulators that also tried wide variety of different implementation details.

one of the scenarios that i had come up with (in the early 70s) was something that would beat true LRU. in part, LRU is based on buttumption that pages used in the recent past are likely to be used in the near future. this is only a rough guess across a wide range of different operational characteristics. sometimes the LRU related buttumption about page use is very accurate and sometimes it has no relationship to what is actually happening. in some cases, LRU replacement degenerates to FIFO and is not the optimal strategy.

the simulators could mimick the actual implementations which all tended to be approximations of true LRU. the simulators could also implement actual LRU (ordering page reference on every instruction executed). In general, the simulators found that "true" LRU did 10-15 precent better than the real-world LRU approximation implementations. so there had been lots and lots of work attempting to come closer and closer to "true" LRU.

however, the gimick that I had come up looked, tasted and operated as standard clock ... a flavor of LRU approximation. The referenced multics experiment with multiple reference bits basically kept longer and longer history ... attempting to come closer and closer to a "true" LRU implementation.

I did a slight-of-hand coding trick in an implementation ... where all the standard LRU varieties degenerated to FIFO under various conditions ... this slight-of-hand coding gimick degneerated to RANDOM under the same conditions. as a result, when LRU was applicable, both "true" LRU and my LRU approximation gimick operated nearly the same. however, it operational regions when LRU would degenerate to FIFO, my coding slight-of-hand degenerated to RANDOM automagically (aka there was no explicit code to switch from LRU to RANDOM ... it just turned out that the coding slight-of-hand resulted in the implementation degenerating to RANDOM rather than FIFO).

L. Belady, A Study of Replacement Algorithms for a Virtual Storage Computer, IBM Systems Journal, v5n2, 1966

L. Belady, The IBM History of Memory Management Technology, IBM Journal of R&D, v25n5

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

P. Denning, Working sets past and present, IEEE Trans Softw Eng, SE6, jan80

J. Rodriquez-Rosell, The design, implementation, and evaluation of a working set dispatcher, cacm16, apr73

D. Hatfield & J. Gerald, Program Restructuring for Virtual Memory, IBM Systems Journal, v10n3, 1971

past posts mentioning lru, fifo, random:

past posts in this thread

--