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

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

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

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

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

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

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

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

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

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

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

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

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

存儲保護

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

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