操作系統(tǒng)原理存儲管理請求分頁系統(tǒng)PPT學(xué)習(xí)教案

1、會計學(xué)1 操作系統(tǒng)原理存儲管理請求分頁系統(tǒng)操作系統(tǒng)原理存儲管理請求分頁系統(tǒng) PPT課件課件 第1頁/共34頁 頁號頁號狀態(tài)位狀態(tài)位 物理塊號物理塊號外存地址外存地址訪問位訪問位 修改位修改位 1 1、頁表機制、頁表機制 2.缺頁中斷機構(gòu)缺頁中斷機構(gòu) 第3頁/共34頁 第4頁/共34頁 缺頁中斷引發(fā)的連續(xù)中斷缺頁中斷引發(fā)的連續(xù)中斷 頁面 B： A： 6 5 4 3 2 1 指令 copy A TO B 第5頁/共34頁 第6頁/共34頁 4.7.24.7.2內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 1 1最小物理塊數(shù)的確定最小物理塊數(shù)的確定 這里所說的最小物理塊數(shù)，是指能保證進程正常運行所

2、需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進程分配的物理塊數(shù)少于此值 時，進程將無法運行。進程應(yīng)獲得的最少物理塊數(shù)與計算機 的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。 第7頁/共34頁 2 2物理塊的分配策略物理塊的分配策略 1) 固定分配局部置換(Fixed Allocation，Local Replacement) 為每個進程分配一定數(shù)目的物理塊，在整個運行期間都 不再改變。采用該策略時，如果進程在運行中發(fā)現(xiàn)缺頁，則 只能從該進程在內(nèi)存的n個頁面中選出一個頁換出，然后再調(diào) 入一頁，以保證分配給該進程的內(nèi)存空間不變。實現(xiàn)這種策 略的困難在于：應(yīng)為每個進程分配多少個物理塊難以確定。 若太少，會頻繁地出

3、現(xiàn)缺頁中斷，降低了系統(tǒng)的吞吐量；若 太多，又必然使內(nèi)存中駐留的進程數(shù)目減少，進而可能造成 CPU空閑或其它資源空閑的情況，而且在實現(xiàn)進程對換時， 會花費更多的時間。 第8頁/共34頁 2) 可變分配全局置換(Variable Allocation，Global Replacement) 這可能是最易于實現(xiàn)的一種物理塊分配和置換策略，已 用于若干個OS中。在采用這種策略時，先為系統(tǒng)中的每個進 程分配一定數(shù)目的物理塊，而OS自身也保持一個空閑物理塊 隊列。當(dāng)某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中取 出一個物理塊分配給該進程，并將欲調(diào)入的(缺)頁裝入其中。 這樣，凡產(chǎn)生缺頁(中斷)的進程，都將獲

4、得新的物理塊。僅 當(dāng)空閑物理塊隊列中的物理塊用完時，OS才能從內(nèi)存中選擇 一頁調(diào)出，該頁可能是系統(tǒng)中任一進程的頁，這樣，自然又 會使那個進程的物理塊減少，進而使其缺頁率增加。 第9頁/共34頁 3) 可變分配局部置換(Variable Allocation，Local Replacement) 為每個進程分配一定數(shù)目的物理塊，但當(dāng)某進程發(fā)現(xiàn)缺 頁時，只允許從該進程在內(nèi)存的頁面中選出一頁換出，這樣 就不會影響其它進程的運行。如果進程在運行中頻繁地發(fā)生 缺頁中斷，則系統(tǒng)須再為該進程分配若干附加的物理塊，直 至該進程的缺頁率減少到適當(dāng)程度為止；反之，若一個進程 在運行過程中的缺頁率特別低，則此時可適

5、當(dāng)減少分配給該 進程的物理塊數(shù)，但不應(yīng)引起其缺頁率的明顯增加。 第10頁/共34頁 3 3物理塊分配算法物理塊分配算法 1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊平均分配給各個進 程。例如，當(dāng)系統(tǒng)中有100個物理塊，有5個進程在運行時， 每個進程可分得20個物理塊。這種方式貌似公平，但實際上 是不公平的，因為它未考慮到各進程本身的大小。如有一個 進程其大小為200頁，只分配給它20個塊，這樣，它必然會 有很高的缺頁率；而另一個進程只有10頁，卻有10個物理塊 閑置未用。 第11頁/共34頁 2) 按比例分配算法 這是根據(jù)進程的大小按比例分配物理塊的算法。如果系 統(tǒng)中共有n個進程，每個

6、進程的頁面數(shù)為Si，則系統(tǒng)中各進程 頁面數(shù)的總和為： 又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能 分到的物理塊數(shù)為bi，將有： n i i SS 1 m S S b i i b應(yīng)該取整，它必須大于最小物理塊數(shù)。 第12頁/共34頁 3) 考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法 在實際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快 地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把 內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地 分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當(dāng)?shù)卦?加其相應(yīng)份額后，分配給各進程。在有的系統(tǒng)中，如重要的 實時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進程分配

7、其物 理塊的。 第13頁/共34頁 4.7.3調(diào)頁策略調(diào)頁策略 1調(diào)入頁面的時機調(diào)入頁面的時機 1) 預(yù)調(diào)頁策略預(yù)調(diào)頁策略 如果進程的許多頁是存放在外存的一個連續(xù)區(qū)域中， 則一次調(diào)入若干個相鄰的頁，會比一次調(diào)入一頁更高效些。 但如果調(diào)入的一批頁面中的大多數(shù)都未被訪問，則又是低 效的?？刹捎靡环N以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù) 計在不久之后便會被訪問的頁面預(yù)先調(diào)入內(nèi)存。如果預(yù)測 較準確，那么，這種策略顯然是很有吸引力的。但遺憾的 是，目前預(yù)調(diào)頁的成功率僅約50%。故這種策略主要用于 進程的首次調(diào)入時，由程序員指出應(yīng)該先調(diào)入哪些頁。 第14頁/共34頁 2) 請求調(diào)頁策略 當(dāng)進程在運行中需要訪問

8、某部分程序和數(shù)據(jù)時，若發(fā) 現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請求，由OS將其所 需頁面調(diào)入內(nèi)存。由請求調(diào)頁策略所確定調(diào)入的頁，是一 定會被訪問的，再加之請求調(diào)頁策略比較易于實現(xiàn)，故在 目前的虛擬存儲器中大多采用此策略。但這種策略每次僅 調(diào)入一頁，故須花費較大的系統(tǒng)開銷，增加了磁盤I/O的啟 動頻率。 第15頁/共34頁 2、從何處調(diào)入 請求分頁系統(tǒng)中把外存分成兩部分：一是文件 區(qū)，用于存放文件；二是對換區(qū)（swap）， 用于存放對換頁面。當(dāng)發(fā)生換頁時，從缺的頁 從何處調(diào)入通常有3種實現(xiàn)： （1）全部從對換區(qū)調(diào)入。這要求系統(tǒng)有足夠 的對換區(qū)空間，進程裝入時全部復(fù)制到對換區(qū) （2）只將修改過的頁放

9、在對換區(qū)。適合對換 區(qū)空間小的情形 （3）首次從文件區(qū)調(diào)入，運行后所有換出的 頁面都放在對換區(qū)，以后再次調(diào)入是從對換區(qū) 調(diào)入。Unix系統(tǒng)采用此方式。 第16頁/共34頁 第17頁/共34頁 第18頁/共34頁 算法名稱、思想及實現(xiàn)是關(guān)鍵！算法名稱、思想及實現(xiàn)是關(guān)鍵！ 第19頁/共34頁 n注意到對注意到對4 4個可用內(nèi)存塊的缺頁次數(shù)（個可用內(nèi)存塊的缺頁次數(shù)（1010）比）比3 3個內(nèi)存塊的個內(nèi)存塊的 缺頁次數(shù)（缺頁次數(shù)（9 9）還要大。這種令人難以相信的結(jié)果稱為）還要大。這種令人難以相信的結(jié)果稱為 BeladyBelady異?，F(xiàn)象，即缺頁次數(shù)隨內(nèi)存塊增加而增加。異?，F(xiàn)象，即缺頁次數(shù)隨內(nèi)存塊增

10、加而增加。 第20頁/共34頁 第21頁/共34頁 2. LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器寄存器 為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個 在內(nèi)存中的頁面配置一個移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1R0 LRU算法實現(xiàn)時需要為每個頁面設(shè)置一個時 間項，用來記錄該頁面上次被訪問的時間， 每次將時間數(shù)值最小的頁面淘汰掉。 第22頁/共34頁 圖 4-28 某進程具有8個頁面時的LRU訪問情況 第23頁/共34頁 2) 棧：棧： 棧頂始終存放最新被訪問的頁面，而棧底則存放最近最棧頂始終存放最新被訪問的頁面，而棧底則存放最近最 久久 未訪問的頁面未

11、訪問的頁面 圖 4-29 用棧保存當(dāng)前使用頁面時棧的變化情況 4 4 7 4 7 0 7 4 0 7 0 4 7 1 7 0 4 1 0 1 7 4 0 1 0 7 4 1 2 1 0 7 4 2 1 2 0 7 4 1 2 1 0 7 4 2 6 2 1 0 7 6 第24頁/共34頁 LRUNRU 近未使用）算法和LFU（最少 使用）算法。 第25頁/共34頁 第26頁/共34頁 4.8.3 Clock置換算法置換算法 1. 簡單的簡單的Clock置換算法置換算法 圖 4-31 簡單Clock置換算法的流程和示例 入口 查尋指針前進一步，指向 下一個表目 頁面訪問位0? 選擇該頁面淘汰 是

12、 返回 置頁面訪 問位“0” 否 塊號頁號訪問位指針 0 1 240 3 421 5 650 711 替換 指針 又稱為二次機會算法、NRU最近未使用算法 實現(xiàn)：需要構(gòu)建循環(huán)隊列，引入實現(xiàn)：需要構(gòu)建循環(huán)隊列，引入 一個查找指針一個查找指針 第27頁/共34頁 2. 改進型改進型Clock置換算法置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有 可能

13、再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被 訪問。 第28頁/共34頁 其執(zhí)行過程可分成以下三步： (1) 從指針所指示的當(dāng)前位置開始， 掃描循環(huán)隊列， 尋 找A=0且M=0的第一類頁面， 將所遇到的第一個頁面作為所 選中的淘汰頁。 在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇 到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所 有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁面，則將指 針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第 一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找 到被淘汰的頁。 第29頁/共34頁 4.7.4 其它置換算法其它置換算法 最少使用(LFU： Least Frequently Used)置換算法： 該算法在需要淘汰某一頁時，首先淘汰到當(dāng)前時 間為止，被訪問次數(shù)最少的那一頁。這只要在頁 表中給每一頁增設(shè)一個訪問計