1、操作系統(tǒng)概念第十一講 內(nèi)存管理（3）回顧什么是頁式管理，什么是段式管理？它們之間的區(qū)別？本課總體綱要靜態(tài)與動(dòng)態(tài)頁面管理請求頁面調(diào)度頁面置換FIFO頁面置換OPT頁面置換LRU頁面置換靜態(tài)與動(dòng)態(tài)頁面管理靜態(tài)頁面管理：在作業(yè)或進(jìn)程開始執(zhí)行前，把該作業(yè)或進(jìn)程的程序段和數(shù)據(jù)全部調(diào)到內(nèi)存的各個(gè)頁面中，并通過頁表和硬件地址變換設(shè)備實(shí)現(xiàn)邏輯地址到物理地址的地址轉(zhuǎn)換動(dòng)態(tài)頁面管理：在作業(yè)或進(jìn)程開始執(zhí)行前，不把該作業(yè)或進(jìn)程的程序段和數(shù)據(jù)全部調(diào)到內(nèi)存的各個(gè)頁面中，而只裝入被認(rèn)為是經(jīng)常反復(fù)執(zhí)行和調(diào)用的工作區(qū)部分請求頁式管理預(yù)調(diào)入頁管理請求頁面調(diào)度只有需要時(shí)，才將頁面調(diào)入內(nèi)存優(yōu)點(diǎn)：減少執(zhí)行I/O需要較少的內(nèi)存較快的響應(yīng)

2、較多的用戶頁面調(diào)度過程：有頁面需求頁面無效？引用無效，產(chǎn)生缺頁中斷執(zhí)行頁面將頁面帶到內(nèi)存頁面在內(nèi)存終止進(jìn)程是否否是虛頁不在物理內(nèi)存的情況每個(gè)頁表?xiàng)l目都有一個(gè)有效無效位（頁面在內(nèi)存中1，頁面不在內(nèi)存中0）初始化時(shí)所有的位都設(shè)置位0如何將虛頁從外存調(diào)入內(nèi)存頁面置換問題的產(chǎn)生問題：過度分配頁面置換解決辦法修改頁錯(cuò)誤處理程序來實(shí)現(xiàn)頁置換通過修改位/臟位來降低額外開銷頁置換分開了邏輯內(nèi)存與物理內(nèi)存，使用小的物理內(nèi)存可以為用戶提供巨大的虛擬內(nèi)存。頁面置換頁處理程序查找所需頁在磁盤上的位置查找一個(gè)空閑幀如果有空閑幀，就使用若沒有空閑幀，就使用頁置換算法選擇一個(gè)淘汰幀將淘汰幀的內(nèi)容寫到磁盤上，更改頁表和幀表將

3、所需頁讀入空閑幀，改變頁表和幀表重新啟動(dòng)進(jìn)程請求頁面調(diào)度的性能頁錯(cuò)誤(缺頁)率p: 0 p 1.0P=0,沒有頁面錯(cuò)誤P=1,每個(gè)頁面都產(chǎn)生頁面錯(cuò)誤有效訪問時(shí)間 (EAT)內(nèi)存訪問時(shí)間maEAT = (1 p) ma+ p (頁面置換時(shí)間)頁面置換時(shí)間頁面錯(cuò)誤開銷頁面切換開銷重啟指令開銷請求頁面調(diào)度的性能舉例說明頁面錯(cuò)誤開銷1us頁切換開銷25ms重新啟動(dòng)開銷100us內(nèi)存訪問時(shí)間ma=100ns如果p=0.001,EAT=?如果p=0.1,EAT=?如果希望EAT性能降低不超過50，p=?本課總體綱要靜態(tài)與動(dòng)態(tài)頁面管理請求頁面調(diào)度頁面置換FIFO頁面置換OPT頁面置換LRU頁面置換頁面置換算

4、法選擇硬件變換機(jī)構(gòu)發(fā)現(xiàn)虛頁是否在內(nèi)存并產(chǎn)生相應(yīng)的頁錯(cuò)誤中斷軟件中斷處理程序根據(jù)內(nèi)存是否有空閑幀實(shí)現(xiàn)內(nèi)外存統(tǒng)一頁調(diào)度內(nèi)存利用率的提高是以犧牲系統(tǒng)開銷的代價(jià)實(shí)現(xiàn)的對于過度分配，選擇什么置換算法至關(guān)重要頁面置換算法選擇每個(gè)操作系統(tǒng)都可能有自己的置換算法：采用最小頁錯(cuò)誤率的算法隨著幀數(shù)量的增加，頁錯(cuò)誤數(shù)量會降低針對特定內(nèi)存的引用串運(yùn)行某個(gè)置換算法，并計(jì)算出頁錯(cuò)誤的數(shù)量。引用串（reference string）：某進(jìn)程在內(nèi)存中被訪問的頁號的序列。FIFO頁置換FIFO頁置換定義：當(dāng)必須進(jìn)行置換時(shí)，將選擇在內(nèi)存駐留時(shí)間最長的頁進(jìn)行置換FIFO頁置換例題在分頁系統(tǒng)中，假如對于過度分配的物理內(nèi)存中可進(jìn)行置換

5、分配的為3幀，作業(yè)的內(nèi)存引用序列為：2、3、2、1、5、2、4、5、3、2、5、2請問采用FIFO 頁面置換算法計(jì)算缺頁中斷率。頁面置換算法選擇Beladys異常OPT最優(yōu)頁置換OPT最優(yōu)頁置換：置換那些在引用串中將來再也不出現(xiàn)或在當(dāng)前最遠(yuǎn)的位置出現(xiàn)的頁。使用這種方法產(chǎn)生的頁錯(cuò)誤率最低，并且絕對沒有Belady異常。OPT最優(yōu)頁置換OPT最優(yōu)頁置換的缺點(diǎn)：難于實(shí)現(xiàn)，因?yàn)橐箢A(yù)先知道每個(gè)進(jìn)程所有引用串的情況LRU頁置換LRU最近最少使用算法：OPT不現(xiàn)實(shí)，可以使用離過去最近作為不遠(yuǎn)將來的近似，那么可以選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久時(shí)間沒有使用的頁進(jìn)行淘汰置換。LRU頁置換近似算法LFU（最不

6、經(jīng)常使用的頁面淘汰算法）：首先淘汰到當(dāng)前時(shí)間為止，被訪問次數(shù)最少的那一頁。實(shí)現(xiàn)方法：在頁表中給每一頁增設(shè)一個(gè)訪問記數(shù)器NUR(最近未使用頁面淘汰算法)：該算法需要淘汰某頁時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪問的頁中任選一頁淘汰。實(shí)現(xiàn)方法：每當(dāng)引用一個(gè)頁時(shí)，相應(yīng)頁的引用位就被硬件置位。否則，引用位置0。開始，所有引用位清零。系統(tǒng)周期性的對所有引用位清零通過檢查引用位，我們知道哪些頁用過，但不知道順序總結(jié)靜態(tài)與動(dòng)態(tài)頁面管理請求頁面調(diào)度頁面置換FIFO頁面置換OPT頁面置換LRU頁面置換作業(yè)在分頁存儲管理中，采用FIFO頁面淘汰算法，對于以下內(nèi)存引用序列，計(jì)算出內(nèi)存為3幀空閑幀和4幀空閑幀所對應(yīng)的缺頁中斷率內(nèi)存引用序列：4、3、2、1、4、3、5、4、3、2、1、5頁地址轉(zhuǎn)換例題解析有一段程序的邏輯首地址為2500，邏輯地址空間為分頁管理方式，每頁大小為1k，該程序調(diào)入內(nèi)存的頁表如下，試問該程序?qū)?yīng)物理內(nèi)