lavinus@csgrad.cs.vt.edu (06/20/91)
Hi!
After my post a while back, I thought I'd summarize the references I got,
in case anyone out there is interested. The original request was for any
references to any 'advanced' paging algorithms.
---
%A Alfred V. Aho
%A Peter J. Denning
%A Jeffrey D. Ullman
%T Principles of Optimal Page Replacement
%J Journal of the Association for Computing Machinery
%V 18
%N 1
%P 80-93
%D January 1971
%L AhoDen71
%A Timo O. Alanko
%A Hannu H. A. Erikio
%A Ilkka J. Haikala
%T Virtual Memory Behavior of Some Sorting Algorithms
%J IEEE Transaction of Software Engineering
%V SE-10
%N 4
%D July 1984
%P 422-431
%L AlaEri84
%A Barbara S. Brawn
%A Frances G. Gustavson
%A Efrem S. Mankin
%T Sorting in a Paging Environment
%J CACM
%V 13
%N 8
%D August 1970
%P 483-494
%L BraGus70
%A Robert L. Budzinaki
%A Edward S. Davidson
%A Wataru Mayeda
%A Harold S. Stone
%T DMIN: An Algorithm for Computing the Optimal Dynamic Allocation in a Virtual Memory Computer
%J IEEE Transactions on Software Engineering
%V SE-7
%N 1
%D January 1981
%P 113-121
%L BudDav81
%T WSClock - A Simple and Effective Algorithm for Virtual Memory Management
%A Richard W. Carr
%A John L. Hennessy
%J Proceedings of the 8th SOSP
%D DEC 1981
%P 87-95
%L CarHen81
%A Hong-Tai Chou
%A David J. DeWitt
%T An Evaluation of Buffer Management Strateties for Relational Database Systems
%J Proceedings of VLDB 1985
%P 127-141
%C Stockholm
%L ChoDew85
%A Wesley W. Chu
%A Holger Opderbeck
%T Program Behavior and the Page-Fault-Frequency Replacement Algorithm
%J IEEE Computer
%D November 1976
%P 29-38
%L ChuOpd76
%A Wesley W. Chu
%A Holger Opderbeck
%T The Page Fault Frequency Replacement Algorithm
%J FJCC
%V 41
%D 1972
%P 597-609
%L ChuOpd72
%A Domenico Ferrari
%A Yiu-Yo Yih
%T VSWS: The Variable-Interval Sampled Working Set Policy
%J IEEE Transactions on Software Engineering
%V SE-9
%N 3
%D May 1983
%P 299-305
%L FerYih83
%A Mohammad Malkawi
%A Janak Patel
%T Compiler Directed Memory Management Policy for Numerical Programs
%J
%P 97-106
%D 1985
%L MohJan85
%A A. C. McKellar
%A E. G. Coffman
%T Organizing Matrices and Matrix Operations for Paged Memory Systems
%J CACM
%V 12
%N 3
%D 1969
%P 153-165
%L MckCof69
%A Dylan McNamee
%A Katherine Armstrong
%T Extending the Mach External Pager Interface to Accommodate User-Level Page Replacement Policies
%J Usenix Mach Workshop
%D October 1990
%L McnArm90
%A Holger Opderbeck
%A Wesley W. Chu
%T Performance of the Page Fault Frequency Replacement Algorithm in a Multiprogramming Environment
%J IFIP Congress '74
%D August, 1974
%P 235-241
%L OpdChu74
%A Barton G. Prieve
%A R. S. Fabry
%T VMIN- An Optimal Variable-Spaced Page Replacement Algorithm
%J CACM
%V 19
%N 5
%D May 1976
%P 295-297
%A E. Sadeh
%T An Analysis of the Performance of the Page Fault Frequency (PFF) Replacement Algorithm
%J ACM 5th SOSP
%D 1975
%V 9
%N 5
%C Austin
%P 6-13
%L Sad75
%A Stephen W. Sherman
%A Richard S. Brice
%T Performance of a Database Manager in a Virtual Memory System
%J ACM Transactions on Database Systems
%V 1
%N 4
%P 317-343
%D December 1976
%L SheBri76
%A Alan Jay Smith
%T Bibliography on Paging and Related Topics
%J ACM OS Review
%V 12
%N 4
%D October 1978
%P 39-56
%L Smi78
%A Kishor S. Trivedi
%T Prepaging and Applications to Array Algorithms
%J IEEE Transactions on Computers
%V C-25
%V 9
%D September 1976
%P 915-921
%L Tri76
%A I. Verkamo
%T Performance of Quicksort Adapted for Virtual Memory Use
%J The Computer Journal
%V 30
%N 4
%D 1987
%P 362-371
%L Ver87
---
The local scheduler for the Stealth Distributed Scheduler uses a prioritized
page replacement algorithm. Pages used by low-priority processes are more
likely to be replaced than those used by high-priority processes.
A description of the algorithm is contained in:
P. Krueger and R. Chawla, "The Stealth Distributed Scheduler", Proceedings of
the 11th International Conference on Distributed Computing Systems, pp. 336-343
(May 1991).
---
"FIDO: a cache that learns to fetch" by Mark Palmer and Stan Zdonik. To
appear in this year's VLDB conference proceedings.
---
Much thanks to the folks who sent those references, and to several others who
provided some interesting discussion on such algorithms, and some reasons why
they might or might not be a good idea.
Joe
--
_______________________________________________________________________
Joseph W. Lavinus, Virginia Tech email: lavinus@csgrad.cs.vt.edu
"They're not broken, they're ... uh ... modular!"