页面置换算法.pdf

Paging works because of Locality of Reference. Good Replacement Algorithms minimize frequency of page faults 2 SIGNIFICANCE OF REPLACEMENT ALGORITHMS Basic Replacement Algorithms and Variants which balnce efficient replacement and algorithm complexity 3 REPLACEMENT ALGORITHMS EXAMPLES: FIFO (QUEUE, CIRCULAR), OPT 4. PAGE INPUT SEQUENCE,REPLACEMENT ALGORITHMS-SECOND CHANCE FIFO, 5 BASIC PLANS: FIFO (QUEUE, CIRCULAR), LRU, OPT, Another Variant 6 REPLACEMENT ALGORITHMS- AGING, WORKING SET (APPROX) Hybrid Approaches (Practical) 7 1-2 Handed Clock Algorithm Based On Second Chance-FIFO Clever , but expensive true LRU Replacement algorithm 8 REPLACEMENT ALGORITHMS TRUE LRU- MATRIX IMPLEMENTATION 9 EFFECTIVENESS OF CLOCK, AGING ALGORITHMS THE WORKING SET ALGORITHM A Variety of Working Set Replacement Algorithms 10 TIME INTERVAL APPROXIMATION WORKING SET ALGORITHM IN CLOCK ALGORITHM CONTEXT 1. 11 TIME INTERVAL APPROXIMATION WORKING SET ALGORITHM IN CLOCK ALGORITHM CONTEXT 2. 12 DIRECT APPROXIMATION WORKING SET ALGORITHM 1 13 BIT MAP APPROXIMATION WORKING SET ALGORITHM 2 14 REPLACEMENT ALGORITHMS ACTUALLY USED Algorithms guaranteed to improve performance as the number of pages increases 15 STACK REPLACEMENT ALGORITHM 16 STACK REPLACEMENT ALGORITHM- LRU IS ONE 17 STACK REPLACEMENT ALGORITHM-OPT IS ONE TOO Notes on Unix’s method for managing page free lists and dirty pages 18 UNIX DEMAND PAGING: DAEMONS, SWAP LIST, PAGE MAP 19 DAEMONS, CRON, PRINTER, MAIL Interesting relation between data stuctures 20 THE EQUIVALENCE OF FIFO QUEUE AND CLOCK DATA STRUCTURES CONTENTS © M C Paull 2005 1 2-4, 6-8,