What happens if there is no free frame? Page replacement -find some page in memory, but not really in use, swap it out(页置换一找到内存中并没有使用的一些页,换出) Algorithm(算法) Performance(1A)want an algorithm which will result in minimum number of page faults(找出一个导致最小缺页数的 算法). Same page may be brought into memory several times(同一个页可 能会被装入内存多次) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.6 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts What happens if there is no free frame? • Page replacement – find some page in memory, but not really in use, swap it out（页置换—找到内存中并没有使用的一些页，换出） . – Algorithm（算法） – Performance（性能） – want an algorithm which will result in minimum number of page faults（找出一个导致最小缺页数的 算法）. • Same page may be brought into memory several times（同一个页可 能会被装入内存多次）
Performance of Demand Paging ° Page Fault Rate0Sp≤1.0(缺页率0≤p≤10) ifp=0 no page faults(如果p=0,没有缺页) ifp=1, every reference is a fault(每次访问都缺页) Effective Access Time(EAT)(有效存取时间) EAT=(1-p)x memory access p(page fault overhead [swap page out] t swap page in restart overhead) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.7 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Performance of Demand Paging • Page Fault Rate 0 p 1.0（缺页率0 p 1.0） – if p = 0 no page faults （如果p = 0 ，没有缺页） – if p = 1, every reference is a fault（每次访问都缺页） • Effective Access Time (EAT)（有效存取时间） EAT = (1 – p) x memory access + p (page fault overhead + [swap page out ] + swap page in + restart overhead)
Demand Paging EXample ° Memory access time=1 microsecond(存取内存的时间) 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out(50%的时间, 所置换的页被修改,因此需要被换出) · Swap Page Time=10msec=10,000msec(交换页的时间) EAT=(1-p)×1+p(15000 1+ 15000P(in msec) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
10.8 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Demand Paging Example • Memory access time = 1 microsecond （存取内存的时间） • 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out（ 50%的时间， 所置换的页被修改，因此需要被换出）. • Swap Page Time = 10 msec = 10,000 msec（交换页的时间） EAT = (1 – p) x 1 + p (15000) 1 + 15000P (in msec)
Page Replacement Prevent over-allocation of memory by modifying page-fault service routine to include page replacement(通过修改缺页服务 例程,来包含页置换,防止分配过多) Use modify(dirty) bit to reduce overhead of page transfers-only modified pages are written to disk(修改(脏)位来防止页面转 移过多一只有被修改的页面才写入磁盘) Page replacement completes separation between logical memory and physical memory -large virtual memory can be provided on a smaller physical memory(页置换完善了逻辑内存和物理内存 的划分一在一个较小的物理内存基础之上可以提供一个大的虚拟 内存 Applied Operating System Concepts 10.9 Silberschatz, Galvin, and Gagne @1999
10.9 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Page Replacement • Prevent over-allocation of memory by modifying page-fault service routine to include page replacement（通过修改缺页服务 例程，来包含页置换，防止分配过多）. • Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk（修改（脏）位来防止页面转 移过多—只有被修改的页面才写入磁盘）. • Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory（页置换完善了逻辑内存和物理内存 的划分—在一个较小的物理内存基础之上可以提供一个大的虚拟 内存
Page-Replacement Algorithms ° Want lowest page-fault rate(需要一个最小的缺页率) Evaluate algorithm by running it on a particular string of memory references(reference string) and computing the number of page faults on that string(通过运行一个内存访问的特殊序列(访问序 列),计算这个序列的缺页次数) n all our examples, the reference string is(在所有的例子中,访一 问序列是) 1,2,3,4,1,2,5,1,2,3,4,5 Applied Operating System Concepts 10.10 Silberschatz, Galvin, and Gagne @1999
10.10 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Page-Replacement Algorithms • Want lowest page-fault rate（需要一个最小的缺页率）. • Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string（通过运行一个内存访问的特殊序列（访问序 列），计算这个序列的缺页次数）. • In all our examples, the reference string is （在所有的例子中，访 问序列是） 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5