【正文】 chatz, Galvin and Gagne ?2022 Operating System Concepts CopyonWrite ? Free pages are allocated from a pool of free pages， called zeroedout pages. The technique is known as zerofilledondemand. (預(yù)先清零 ) 空閑頁(yè)從一個(gè) zeroedout頁(yè)池中被分配。 ? A file is initially read using demand paging. A pagesized portion of the file is read from the file system into a physical page. Subsequent reads/writes to/from the file are treated as ordinary memory accesses. 一個(gè)文件開(kāi)始被讀使用請(qǐng)求頁(yè)。隨后文件讀 / 寫(xiě)處理被當(dāng)作普通存儲(chǔ)器訪問(wèn)。這種處理方式要優(yōu)于通常的 read()/write()系統(tǒng)調(diào)用。此時(shí)物理內(nèi)存已經(jīng)全部被占用。 3. Read the desired page into the (newly) free frame. Update the page and frame tables. 讀入該頁(yè)到 ( 最新 )空閑頁(yè)框。 every time page is referenced through this entry, copy the clock into the counter. （ 每一個(gè)頁(yè)表項(xiàng) 有一個(gè)計(jì)數(shù)器，每次頁(yè)通過(guò)這個(gè)表項(xiàng)被訪問(wèn)，把時(shí)間拷貝到計(jì)數(shù)器中） ? When a page needs to be changed, look at the counters to determine which are to change. （ 當(dāng)一個(gè)頁(yè)需要替換時(shí)，查看計(jì)數(shù)器來(lái)決定改變哪一個(gè)頁(yè)。 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁(yè) 1 4 3 2 1 1 1 5 5 5 2 1 1頁(yè) 2 4 3 3 3 3 3 3 3 5 5 5頁(yè) 3 4 4 4 4 4 4 4 4 4 4 x x x x 3 3 x 3 3 x x 3 共缺頁(yè)中斷 7 次Silberschatz, Galvin and Gagne ?2022 Operating System Concepts 置換算法舉例（ 2） LRU 4 3 2 1 4 3 5 4 3 2 1 5頁(yè) 1 4 3 2 1 4 3 5 4 3 2 1 5頁(yè) 2 4 3 2 1 4 3 5 4 3 2 1頁(yè) 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x 3 3 x x x共缺頁(yè)中斷 10 次Silberschatz, Galvin and Gagne ?2022 Operating System Concepts 置換算法舉例（ 3） FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁(yè) 1 4 3 2 1 4 3 5 5 5 2 1 1頁(yè) 2 4 3 2 1 4 3 3 3 5 2 2頁(yè) 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x 3 3 x x 3共缺頁(yè)中斷 9 次Silberschatz, Galvin and Gagne ?2022 Operating System Concepts LRU Approximation Algorithms ? Reference bit（ 訪問(wèn)位） ?With each page associate a bit, initially = 0 每個(gè)頁(yè)都與一個(gè)位相關(guān)聯(lián)，初始值位 0 ?When page is referenced bit set to 1 當(dāng)頁(yè)被訪問(wèn)位時(shí)，設(shè)位 1 ?Replace the one which is 0 (if one exists). We do not know the order, however. 如果存在的話(huà)，置換位為 0的頁(yè)。每次定時(shí)中斷時(shí)將每頁(yè)的 8位右移 1位，去掉最右位 ? 某頁(yè)被訪問(wèn)時(shí)，最高位（最左位）置 1 ? 需要置換頁(yè)時(shí)，比較各頁(yè)中 8位數(shù)的大小。 ? Least frequently used (LFU) pagereplacement Algorithm: replaces page with smallest count. 以最小的計(jì)數(shù)置換一個(gè)頁(yè) ? 缺點(diǎn)：一些頁(yè)可能前期被密集訪問(wèn)，隨后就不在被訪問(wèn)，但計(jì)數(shù)值很大 ? 改進(jìn)：計(jì)數(shù)器定期右移，使計(jì)數(shù)值呈指數(shù)衰減 ? Most frequently used (MFU) pagereplacement Algorithm : based on the argument that the page with the smallest count was probably just brought in and has yet to be used. 處理方式剛好與 LFU相反。 ? 實(shí)際上，自由頁(yè)表和修改頁(yè)表充當(dāng)著頁(yè)的 Cache的角色。 ? Used in VAX/VMS system Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Allocation of Frames ? Each process needs minimum number of pages（ 每個(gè)進(jìn)程所需要的最少的頁(yè)的數(shù)目） ? 有計(jì)算機(jī)的體系結(jié)構(gòu)所決定的 ? Example: IBM 370 – 6 pages to handle SS MOVE instruction: ? instruction is 6 bytes, might span 2 pages. ? 2 pages to handle from. ? 2 pages to handle to. ? 最壞情況：許多次的間接內(nèi)存訪問(wèn)指令，每一個(gè)間接地址分跨在兩個(gè)頁(yè)架上，造成一條指令需要很多頁(yè)架 ? 如果一個(gè)進(jìn)程只給分配 2個(gè) page該怎么辦？ ? Two major allocation schemes（ 兩個(gè)主要的分配策略）： ? fixed /equal allocation（ 固定 /平均分配） ? priority /proportional allocation（ 優(yōu)先 /按比例分配） Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Fixed Allocation ? （ 1） Equal allocation （ 平均分配） – ., if 100 frames and 5 processes, give each 20 pages. （ 例：如果有 100個(gè)頁(yè)框，和 5個(gè)進(jìn)程，則每個(gè)進(jìn)程分給 20個(gè)頁(yè)） ? （ 2） Proportional allocation （ 按比例分配） – Allocate according to the size of process. （ 根據(jù)每個(gè)進(jìn)程的大小來(lái)分配） mSspamsSpsiiiiii??????? f o r a l l o c a t i o n f r a m e s of n u m b e r t o t a l p r o c e s s of s i z e 59641 3 71 2 75641 3 7101 2 71064212?????????aassmiSilberschatz, Galvin and Gagne ?2022 Operating System Concepts Priority Allocation ? （ 3） Use a proportional allocation scheme using priorities rather than size. 根據(jù)優(yōu)先級(jí)而不是大小來(lái)使用比率分配策略 ? If process Pi generates a page fault, 如果進(jìn)程 Pi產(chǎn)生一個(gè)缺頁(yè) ?select for replacement one of its frames 選擇替換該進(jìn)程中的一個(gè)頁(yè)框 ?select for replacement a frame from a process with lower priority number 從一個(gè)較低優(yōu)先級(jí)的進(jìn)程中選擇一個(gè)頁(yè)面來(lái)替換 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Global vs. Local Allocation ? Global replacement（ 全局替換） – process selects a replacement frame from the set of all frames。 但是，系統(tǒng)代價(jià)將大增！ Silberschatz, Galvin and Gagne ?2022 Operating System Concepts PageFault Frequency Scheme ? Establish ―acceptable‖ pagefault rate（ 設(shè)置可接受的缺頁(yè)率） . ? If actual rate too low, process loses frame（ 如果缺頁(yè)率太低，回收一些進(jìn)程的頁(yè)框） . ? If actual rate too high, process gains frame（ 如果缺頁(yè)率太高，就分給進(jìn)程一些頁(yè)框） . ? 如果缺頁(yè)率很高，但又沒(méi)有空的頁(yè)架可分配，則掛起某些進(jìn)程，將其空閑的頁(yè)架分配出去。在虛擬頁(yè)式管理中有兩種常用策略。 ?優(yōu)點(diǎn)：容易 實(shí)現(xiàn) 。 ?優(yōu)點(diǎn)：提高調(diào)頁(yè)的 I/O效率 。常用于 程序裝入時(shí) 的調(diào)頁(yè)。關(guān)于調(diào)入頁(yè)面的來(lái)源，這里有兩種做法： ? 進(jìn)程裝入時(shí)，將其全部頁(yè)面復(fù)制到交換區(qū)，以后總是 從交換區(qū)調(diào)入 。 ? 凡是未被修改的頁(yè)面，都直接 從文件區(qū)讀入 ，而被置換時(shí) 不需調(diào)出 ；已被修改的頁(yè)面，被置換時(shí)需調(diào)出到交換區(qū)，以后從交換區(qū)調(diào)入。 ?可能引發(fā)問(wèn)題。有兩種常用清除策略： ? 請(qǐng)求清除 (demand cleaning)： 該頁(yè)被置換時(shí)才調(diào)出， 把清除推遲到最后一刻 。 ?缺點(diǎn)：可能形成 不必要的開(kāi)銷(xiāo) 。這種策略發(fā)展成為頁(yè)面緩沖算法 (page buffering)。否則有很高的缺頁(yè)率。但是 , 因?yàn)椴皇撬械膽?yīng)用程序都要求一個(gè)較大的頁(yè)面尺寸，這可能導(dǎo)致碎片的增加。允許要求很大頁(yè)大小的應(yīng)用程序有機(jī)會(huì)使用他們 , 且同時(shí)沒(méi)有增加碎片。 但是，這需要增加相應(yīng)的支持 ?to manage the TLB,可能會(huì)導(dǎo)致系統(tǒng)性能下降 Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Inverted Page Table ? 與 〈 Inverted Page Table〉 情況相似 ? Create a table that has only one entry per physical memory page, indexed by the pair processid, pagenumber ? The information about which virtualmemory page is stored in each physical frame ? Reduce the amount of physical memory needed to store table information Silberschatz, Galvin and Gagne ?2022 Operating System Concepts Program structure （ 程序結(jié)構(gòu)） ? Example: a java program to init to 0 each element of a 1024 by 1024 array: ?int A[ ][ ] = new int[1024][1024]。 j 。 i 。 ?1024 x 1024 page faults ?Program 2 for (i = 0。 i++) for (j = 0。 j++)