【正文】 age that will not be used for longest period of time. （ 被置換的頁將是今后最長時間不被使用的頁） 缺頁次數(shù)： 9次 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Optimal Algorithm ? 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ? How do you know this? ?情況與 SJF CPUscheduling算法相似 ? Used for measuring how well your algorithm performs. （ 用來衡量你的算法的效率） 1 2 3 4 6 page faults 4 5 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts LRU Page Replacement 缺頁次數(shù)： 12次 Least Recently Used (LRU) Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Least Recently Used (LRU) Algorithm ? Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ? 實現(xiàn)方式： （ 1） Counter implementation （ 計數(shù)器的實現(xiàn)） ? Every page entry has a counter。 ?此時， User1中的 load M指令需要使用第 3頁上的數(shù)據(jù)，但是，該頁并未在內(nèi)存中，該如何處理？ ? OS 有三種處理方法 : ?中止一個用戶進程 ?交換出 (Swap out)一個進程 ?頁面置換 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Basic Page Replacement Steps: 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. 如果沒有空閑頁框，使用頁代替算法選擇一個犧牲 (淘汰 )頁框。 ? Also allows several processes to map the same file allowing the pages in memory to be shared. 允許若干個進程映射到相同的文件，以此達到內(nèi)存中頁面被共享的目的 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Memory Mapped Files Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Page Replacement ? Prevent overallocation of memory by modifying pagefault service routine to include page replacement（ 通過修改缺頁服務(wù)例程，來包含頁置換，防止分配過多的內(nèi)存） . ? Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk（通過設(shè)置 修改位 以減少頁面?zhèn)魉偷拇螖?shù) —只有被修改的頁面才寫入磁盤） . ? Page replacement pletes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory（ 頁置換完善了邏輯內(nèi)存和物理內(nèi)存的劃分 —在一個較小的物理內(nèi)存基礎(chǔ)之上可以提供一個大的虛擬內(nèi)存 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Need For Page Replacement Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Need For Page Replacement ?在前面的例子中 , User1的第 3頁和 User2的第 1頁尚未分配相應(yīng)的物理內(nèi)存。 ? Simplifies file access by treating file I/O through memory rather than read()/write() system calls. 通過內(nèi)存處理文件 I/O可簡化文件訪問。文件的一頁大小從文件系統(tǒng)被讀入一物理的頁。 ? System call vfork() in Unix (for virtual memory fork()). With vfork() ,the parent process is suspended and the child process uses the address space of parent Silberschatz, Galvin and Gagne ?2022 Operating System Concepts MemoryMapped Files ? Memorymapped file I/O allows file I/O to be treated as routine memory access by mapping a disk block to a page in memory. 通過映射磁盤塊到內(nèi)存中一頁的方式，內(nèi)存映射文件 I/O 允許文件的 I/O操作被處理成常規(guī)的存儲訪問。 s w ap A , BABP a ge xx+1yy +1zz+1Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Some Example（ 1） ? Example 1. ADD A, B = C 1. Fetch and place the instruction (ADD) 2. Fetch A 3. Fetch B 4. Add A and B 5. Store the sum in C ? 在取指令、取操作數(shù) A和 B、 保存結(jié)果到 C的任何一個步驟中都有可能發(fā)生缺頁中斷 ? 此外，指令、操作數(shù)等可能跨在相鄰的兩個頁之間 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Some Example（ 2） ? Example 2. 塊操作指令 (如 IBM 360/370 MVC 指令） ?可移動 256個字節(jié) ?可能源或目的地數(shù)據(jù)塊分跨在不同頁上 ?可能源和目的地之間有重疊 ? Example 3. 自動增、自動減間接指令 ?MOV (R2)+， (R3) Silberschatz, Galvin and Gagne ?2022 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 頁置換 —找到內(nèi)存中并沒有使用的一些頁，換出 . 需要考慮 : ?Algorithm（ 算法） ?Performance（ 性能） – want an algorithm which will result in minimum number of page faults（ 找出一個導(dǎo)致最小缺頁數(shù)的算法） . ? Same page may be brought into memory several times 同一個頁可能會被裝入內(nèi)存多次 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Performance of Demand Paging ? Page Fault Rate（ 缺頁率 ） 0 ? p ? ?if p = 0 no page faults （ 如果 p = 0 ， 沒有缺頁） ?if p = 1, every reference is a fault （ 每次訪問都缺頁） ? Effective Access Time (EAT) EAT = (1 – p) x ma + p x page fault time = (1 – p) x memory access + p (page fault overhead + [swap page out ] + swap page in + restart overhead) Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Demand Paging Example ? Swap page time (交換頁的時間 ) = 25 msec = 25,000,000 nsec ? a memory access time is 100nsec ? EAT = (1 – p) x 100 + p (25,000,000) = 100 + 24,999,900 x p (in nsec) ? 可見 EAT 與缺頁率（ pagefault rate） 成正比 ? If p=1/1000, EAT = 25us ? If p=1/10000, EAT = ? If p=1/100000, EAT = ? 假設(shè) memory access time is 100nsec，為確保因缺頁引起的性能下降低于 10%，即： EAT110ns, 則： ? 100 + 24,999,900 x p 110 ? p ?也即必須確保 缺頁率 1/2500000 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Process Creation ? Virtual memory allows other benefits during process creation: 在進程創(chuàng)建過程中虛存存在其它的好處： CopyonWrite 寫拷貝 MemoryMapped Files 內(nèi)存映射文件 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts CopyonWrite ? Fork()—creates a child process as a duplicate of its parent. ? CopyonWrite (COW) allows both parent and child processes to initially share the same pages in memory. COW允許父進程和子進程在內(nèi)存中初始共享相同頁 ? If either process modifies a shared page, only then is the page copied. 如果任一進程（父或子）需要修改一個共享頁，則僅僅是該頁被拷貝，隨后再修改該頁。所缺的頁面調(diào)入之后， 重新執(zhí)行被中斷的指令 。 1. 虛擬存儲的基本原理 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts 2. 引入虛擬存儲技術(shù)的好處 ?大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序； ?大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存 (real memory) ?并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行； ?易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時的程序結(jié)構(gòu) Silberschatz, Galvin and G