操作系統(tǒng)教學(xué)課件第十二講

教學(xué)目的掌握動態(tài)頁式管理的基本原理掌握請求頁式管理中的置換算法理解Belady現(xiàn)象第五章存儲管理－－動態(tài)頁式管理1/16/20251內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系教學(xué)內(nèi)容5.4.3動態(tài)頁面管理5.4.4請求頁式管理中的置換算法5.4.5存儲保護(hù)5.4.6頁式管理的優(yōu)缺點第五章存儲管理－－動態(tài)頁式管理1/16/20252內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系所以，產(chǎn)生的原因——內(nèi)存不足。引入到目前為止，任何一個作業(yè)/進(jìn)程只有全部裝入內(nèi)存才能運行。但是，這會出現(xiàn)下面兩種情況。由于內(nèi)存有限，裝入內(nèi)存中的作業(yè)較少——不能提高系統(tǒng)的并發(fā)率作業(yè)太大，無法裝入內(nèi)存——不能滿足用戶的需要第五章存儲管理－－動態(tài)頁式管理1/16/20253內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系解決辦法從物理上擴(kuò)展內(nèi)存從邏輯上擴(kuò)展內(nèi)存——虛擬內(nèi)存虛擬存儲器的核心思想——

部分裝入、部分對換第五章存儲管理－－動態(tài)頁式管理1/16/20254內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系

局部性原理——P.Denning，1968——Fortheringham,1961指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。第五章存儲管理－－動態(tài)頁式管理1/16/20255內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系動態(tài)頁式管理的分類分為請求頁式管理和預(yù)調(diào)入頁式管理兩種。請求頁式管理當(dāng)需要執(zhí)行某條指令而又發(fā)現(xiàn)它不在內(nèi)存時或執(zhí)行某條指令需要訪問其他的數(shù)據(jù)或指令時，這些指令或數(shù)據(jù)不在內(nèi)存中，從而發(fā)生缺頁中斷，系統(tǒng)將外存中相應(yīng)的頁面調(diào)入內(nèi)存。第五章存儲管理－－動態(tài)頁式管理1/16/20256內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系預(yù)調(diào)入頁式管理系統(tǒng)對那些在外存中的頁的調(diào)入順序進(jìn)行計算，估計出這些頁中指令和數(shù)據(jù)的執(zhí)行和被訪問的順序，并按此順序?qū)⑺鼈冋{(diào)入和調(diào)出內(nèi)存。請求調(diào)入和預(yù)調(diào)入頁式管理只是在調(diào)入的方式上存在區(qū)別，其他方面基本相同，下面只介紹請求方式。第五章存儲管理－－動態(tài)頁式管理1/16/20257內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系

實現(xiàn)動態(tài)頁式管理需要的支持?jǐn)U充的頁表判斷該頁是否在內(nèi)存中、調(diào)度的參數(shù)實現(xiàn)缺頁處理缺頁中斷機(jī)構(gòu)頁面置換算法進(jìn)行頁面的調(diào)入和換出第五章存儲管理－－動態(tài)頁式管理1/16/20258內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系頁表頁號頁面號中斷位改變位外存始址頁表結(jié)構(gòu)中斷位表示該頁是否在內(nèi)存中第五章存儲管理－－動態(tài)頁式管理1/16/20259內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系外存地址表示該頁副本在外存中的起始位置改變位表示頁面內(nèi)容已經(jīng)修改第五章存儲管理－－動態(tài)頁式管理1/16/202510內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系作業(yè)1作業(yè)2作業(yè)30K1K0K1K2K0K1K2K3K頁面表存儲空間5600247000OS308011舉例第五章存儲管理－－動態(tài)頁式管理1/16/202511內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系缺頁中斷地址轉(zhuǎn)換過程中產(chǎn)生的一種特殊的中斷，同樣需要經(jīng)歷保護(hù)CPU現(xiàn)場、分析中斷原因、轉(zhuǎn)缺頁中斷處理程序進(jìn)行處理、恢復(fù)CPU現(xiàn)場。特殊性在指令的執(zhí)行期間產(chǎn)生和處理中斷一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷

動態(tài)頁式管理過程第五章存儲管理－－動態(tài)頁式管理1/16/202512內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系第五章存儲管理－－動態(tài)頁式管理1/16/202513內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系邏輯空間地址主存(用戶區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū))運行進(jìn)程頁表輔存缺頁中斷處理①分解地址③⑤訪問MMU②查快表③命中④不命中⑤頁表命中⑦發(fā)缺頁中斷⑧調(diào)頁⑨裝入、改表④查頁表運行進(jìn)程頁表基址⑥裝入快表運行進(jìn)程映象進(jìn)程切換時裝入物理地址頁框頁內(nèi)地址頁號頁內(nèi)地址第五章存儲管理－－動態(tài)頁式管理1/16/202514內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系

置換算法用來確定應(yīng)該淘汰哪一頁的一種策略。

隨機(jī)淘汰算法無法確定那個頁的訪問概率時，隨機(jī)地選取某個用戶的頁面將其換出。第五章存儲管理－－動態(tài)頁式管理1/16/202515內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系先進(jìn)先出頁面替換算法（FIFO)時間局部性原理。最早調(diào)入內(nèi)存的頁面，其不再被訪問的可能性最大。算法原理總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常駐的除外）。

依據(jù)第五章存儲管理－－動態(tài)頁式管理1/16/202516內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系算法舉例缺頁率σ=12/17=70.5%

3個頁面第五章存儲管理－－動態(tài)頁式管理1/16/202517內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系算法舉例

4個頁面缺頁率σ=9/17=52.9%第五章存儲管理－－動態(tài)頁式管理1/16/202518內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系Belady現(xiàn)象使用FIFO算法時，在未給進(jìn)程或作業(yè)分配足它需要的頁面數(shù)時，有時會出現(xiàn)分配的頁面數(shù)增加，缺頁次數(shù)反而增加的奇怪現(xiàn)象。第五章存儲管理－－動態(tài)頁式管理1/16/202519內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系Belady現(xiàn)象舉例

3個頁面缺頁率σ=9/12=75%第五章存儲管理－－動態(tài)頁式管理1/16/202520內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系Belady現(xiàn)象舉例

4個頁面缺頁率σ=10/12=83.3%第五章存儲管理－－動態(tài)頁式管理1/16/202521內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系最近最久未使用頁面替換算法（LeastRecentlyUsed）產(chǎn)生Belady現(xiàn)象的根本原因在于沒有考慮程序執(zhí)行的動態(tài)特征。原理根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。第五章存儲管理－－動態(tài)頁式管理1/16/202522內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系算法思想淘汰的頁面是在最近一段時間里較久未被訪問的那頁。算法舉例第五章存儲管理－－動態(tài)頁式管理1/16/202523內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系時刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210230230v4304204ffff23023f023v023v123f123v120f120v170f170v170v缺頁率σ=12/20=60%第五章存儲管理－－動態(tài)頁式管理1/16/202524內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系由于實現(xiàn)LRU算法復(fù)雜性和巨大的系統(tǒng)開銷，所以常采用近似算法實現(xiàn)。近似算法最不經(jīng)常使用頁面淘汰算法LFU（LeastFrequentlyUsed）在頁表中增設(shè)一個訪問計數(shù)器，當(dāng)需要淘汰頁面時，選擇那些計數(shù)器值最小的頁。第五章存儲管理－－動態(tài)頁式管理1/16/202525內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系最近沒有使用頁面淘汰算法NUR在頁表中增設(shè)一個訪問位(設(shè)：0表示未被訪問，1：表示被訪問)，當(dāng)需要淘汰頁面時，選擇那些訪問位為0的頁面。第五章存儲管理－－動態(tài)頁式管理1/16/202526內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系不是實際可行的算法，但是它可用來作為衡量各種具體算法的標(biāo)準(zhǔn)，具有理論意義。最佳替換算法（OPTIMAL）算法原理調(diào)入一頁而必須淘汰一個舊頁時，所淘汰的頁應(yīng)該是以后不再訪問的頁或距現(xiàn)在最長時間后再訪問的頁。特點第五章存儲管理－－動態(tài)頁式管理1/16/202527內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系時刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210230230v2342342fVVf34230f230v230v210f210v210V210v710f710v710v缺頁率σ=9/20=45%舉例第五章存儲管理－－動態(tài)頁式管理1/16/202528內(nèi)蒙古工業(yè)大學(xué)計算機(jī)系

存儲保護(hù)

越界保護(hù)通過地址變換機(jī)構(gòu)中的控制寄存器的值（頁表長度）與邏輯地址的頁號進(jìn)行比較實現(xiàn)。

存取控制保護(hù)通過在頁表中設(shè)置保護(hù)位來實現(xiàn)。第五章存儲管理－－動態(tài)頁式管理1/16/