virtual memory 4485

ref:

besides the numerous different variations on LRU approximations, "true" LRU implemented in simulators ... there was also belady's "OPT" ... basically with a full trace of all storage accesses ... OPT chose the page to replace that resulted in the fewest future page faults (of course ... you were no longer working on past history ... like LRU or LRU approximation ... you needed a full prediction of the future ... which you could simulate given a complete trace of all storage access to replay).

a few recent posts mentioning other of belady's references

here is a spring 2005 clbutt buttignment

requiring implementation & comparison of:

* FIFO: First In, First Out * GC: Global Clock * LFU: Least Frequently Used * LRU: Least Recently Used * MFU: Most Frequently Used * OPT: Belady's Optimal Algorithm * RAND: Random

.....

for some drift:

R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78-117, 1970.

with respect to the cache investigation using simulator that had full trace of all record accesses for production systems ...

I had implemented much of the data collection stuff in 1979 and Mattson had done most of the simulator implementation.

One of the other outcomes of Mattson 1979 simulation work was that he developed a process that could analyse the record access activity in real-time ... looking at being able to do real-time optimal disk data reorganization.

a more recent paper referencing Mattson's 1970 work.

--