PDF《操作系统原理与设计》

.

Page Replacement Allocation of Frames 小结和作业 . . . . . . . 操作系统原理与设计 第9章VM(虚存2) 陈香兰 中国科学技术大学计算机学院 2009年09月01日 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 . . 提纲 . ..

1 Page Replacement Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . ..

2 Allocation of Frames . ..

3 小结和作业 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . . Page Replacement I Free page frame is managed by OS using free-frame-list What happens if there is no free frame? ?Page replacement over-allocation no free frames;

all memory is in use Prevent over-allocation of memory by modifying page-fault service routine to include page replacement example: 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . . Page Replacement II 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . . Outline . ..

1 Page Replacement Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . ..

2 Allocation of Frames . ..

3 小结和作业 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . . Basic Page Replacement . ..

1 Find the location of the desired page on disk . ..

2 Find a free frame: If there is a free frame, use it If there is no free frame, use a page replacement algorithm to select a victim frame . ..

3 Bring the desired page into the (newly) free frame;

update the page and frame tables . ..

4 Restart the process 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . . Page Replacement 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms NO MODIFY, NO WRITTEN (to disk/swap space) Use modify (dirty) bit to reduce overhead of page transfers only modi?ed pages are written to disk This technique also applies to read-only pages for example, pages of binary code Page replacement completes separation between logical memory and physical memory large virtual memory can be provided on a smaller physical memory demand paging, to lowest page-fault rate, two major problems frame-allocation algorithms page-replacement algorithms 陈香兰 操作系统原理与设计 Page Replacement Allocation of Frames 小结和作业 Basic Page Replacement First-In-First-Out (FIFO) Algorithm Optimal Algorithm Least Recently Used (LRU) Algorithm LRU Approximation Algorithms Counting Algorithms Page-Bu?eing Algorithms . . Page Replacement Algorithms I GOAL: to lowest page-fault rate Di?erent algorithms are evaluated by running it on a particular string of memory references (reference string) and computing the number of page faults on that string A reference string is a sequence of addresses referenced by a program Example: An address reference string: