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

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

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

3、現(xiàn)缺頁(yè)中斷，降低了系統(tǒng)的吞吐量；若 太多，又必然使內(nèi)存中駐留的進(jìn)程數(shù)目減少，進(jìn)而可能造成 CPU空閑或其它資源空閑的情況，而且在實(shí)現(xiàn)進(jìn)程對(duì)換時(shí)， 會(huì)花費(fèi)更多的時(shí)間。 第8頁(yè)/共34頁(yè) 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)缺頁(yè)時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中取 出一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的(缺)頁(yè)裝入其中。 這樣，凡產(chǎn)生缺頁(yè)(中斷)的進(jìn)程，都將獲

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

5、當(dāng)減少分配給該 進(jìn)程的物理塊數(shù)，但不應(yīng)引起其缺頁(yè)率的明顯增加。 第10頁(yè)/共34頁(yè) 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頁(yè)，只分配給它20個(gè)塊，這樣，它必然會(huì) 有很高的缺頁(yè)率；而另一個(gè)進(jìn)程只有10頁(yè)，卻有10個(gè)物理塊 閑置未用。 第11頁(yè)/共34頁(yè) 2) 按比例分配算法 這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系 統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)

6、進(jìn)程的頁(yè)面數(shù)為Si，則系統(tǒng)中各進(jìn)程 頁(yè)面數(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頁(yè)/共34頁(yè) 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)來(lái)為各進(jìn)程分配

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

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

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

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

11、訪(fǎng)問(wèn)的頁(yè)面 圖 4-29 用棧保存當(dāng)前使用頁(yè)面時(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頁(yè)/共34頁(yè) LRUNRU 近未使用）算法和LFU（最少 使用）算法。 第25頁(yè)/共34頁(yè) 第26頁(yè)/共34頁(yè) 4.8.3 Clock置換算法置換算法 1. 簡(jiǎn)單的簡(jiǎn)單的Clock置換算法置換算法 圖 4-31 簡(jiǎn)單Clock置換算法的流程和示例 入口 查尋指針前進(jìn)一步，指向 下一個(gè)表目 頁(yè)面訪(fǎng)問(wèn)位0? 選擇該頁(yè)面淘汰 是

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

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