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

1、會(huì)計(jì)學(xué)1 操作系統(tǒng)原理存儲(chǔ)管理請(qǐng)求分頁系統(tǒng)操作系統(tǒng)原理存儲(chǔ)管理請(qǐng)求分頁系統(tǒng) PPT課件課件 第1頁/共34頁 頁號(hào)頁號(hào)狀態(tài)位狀態(tài)位 物理塊號(hào)物理塊號(hào)外存地址外存地址訪問位訪問位 修改位修改位 1 1、頁表機(jī)制、頁表機(jī)制 2.缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(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ù)，是指能保證進(jìn)程正常運(yùn)行所

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

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

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

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

6、進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程 頁面數(shù)的總和為： 又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能 分到的物理塊數(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)的分配算法 在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快 地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把 內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地 分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦?加其相應(yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的 實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配

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

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

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

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

11、訪問的頁面 圖 4-29 用棧保存當(dāng)前使用頁面時(shí)棧的變化情況 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置換算法的流程和示例 入口 查尋指針前進(jìn)一步，指向 下一個(gè)表目 頁面訪問位0? 選擇該頁面淘汰 是

12、 返回 置頁面訪 問位“0” 否 塊號(hào)頁號(hào)訪問位指針 0 1 240 3 421 5 650 711 替換 指針 又稱為二次機(jī)會(huì)算法、NRU最近未使用算法 實(shí)現(xiàn)：需要構(gòu)建循環(huán)隊(duì)列，引入實(shí)現(xiàn)：需要構(gòu)建循環(huán)隊(duì)列，引入 一個(gè)查找指針一個(gè)查找指針 第27頁/共34頁 2. 改進(jìn)型改進(jìn)型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) 從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊(duì)列， 尋 找A=0且M=0的第一類頁面， 將所遇到的第一個(gè)頁面作為所 選中的淘汰頁。 在第一次掃描期間不改變?cè)L問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇 到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，將所 有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁面，則將指 針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第 一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找 到被淘汰的頁。 第29頁/共34頁 4.7.4 其它置換算法其它置換算法 最少使用(LFU： Least Frequently Used)置換算法： 該算法在需要淘汰某一頁時(shí)，首先淘汰到當(dāng)前時(shí) 間為止，被訪問次數(shù)最少的那一頁。這只要在頁 表中給每一頁增設(shè)一個(gè)訪問計(jì)