Principles of Optimal Page Replacement
作者： Alfred V Aho , Peter J Denning , Jeffrey D Ullman , None
关键词: System organization 、 Program behavior 、 Parallel computing 、 Page replacement algorithm 、 Dynamic programming 、 Demand paging 、 Mathematical optimization 、 Flat memory model 、 Computer science 、 Paging
摘要: ABSTP~CT. A formal model is presented for paging algorithms under /-order nonstationary assumptions about program behavior. When processing a in given memory, policy generates certain (expected) number of page calls, i.e., its "cost." Under usual memory system organization, minimum cost always achieved by demand algorithm. The behavior expressed as dynamic programming problem whose solution yields an optimal replacement Solutions are exhibited several 0-order cases interest. Paging that implement and approximate the discussed.
acm.org
sci-hub.se 参考文章(15)
Tad Brian Pinkerton, Program behavior and control in virtual storage computer systems University of Michigan. ,(1968)
John L. Smith, Microprogamming under a page on demand strategy Communications of the ACM. ,vol. 10, pp. 636- 646 ,(1967) , 10.1145/363717.363763
E. G. Coffman, L. C. Varian, Further experimental data on the behavior of programs in a paging environment Communications of The ACM. ,vol. 11, pp. 471- 474 ,(1968) , 10.1145/363397.363398
Laszlo A. Belady, None, A study of replacement algorithms for a virtual-storage computer Ibm Systems Journal. ,vol. 5, pp. 78- 101 ,(1966) , 10.1147/SJ.52.0078
B. W. Arden, B. A. Galler, T. C. O'Brien, F. H. Westervelt, Program and Addressing Structure in a Time-Sharing Environment Journal of the ACM. ,vol. 13, pp. 1- 16 ,(1966) , 10.1145/321312.321313
Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems Journal of the ACM. ,vol. 12, pp. 589- 602 ,(1965) , 10.1145/321296.321310
H. Hellerman, Complementary replacement: a meta scheduling principle symposium on operating systems principles. pp. 43- 46 ,(1969) , 10.1145/961053.961070
Laszlo A Belady, Robert A Nelson, Gerald S Shedler, None, An anomaly in space-time characteristics of certain programs running in a paging machine Communications of The ACM. ,vol. 12, pp. 349- 353 ,(1969) , 10.1145/363011.363155
J. E. Shemer, G. A. Shippey, Statistical Analysis of Paged and Segmented Computer Systems IEEE Transactions on Electronic Computers. ,vol. EC-15, pp. 855- 863 ,(1966) , 10.1109/PGEC.1966.264467
Gerald H. Fine, Calvin W. Jackson, Paul V. McIsaac, Dynamic program behavior under paging Communications of The ACM. ,vol. 9, pp. 478- ,(1966) , 10.1145/365719.366406