【正文】 0的頁(yè)。 當(dāng)淘汰這樣一頁(yè)時(shí)，要將被淘汰的頁(yè)寫(xiě)回到輔存上去，以保證信息的一致性。 操作系統(tǒng)接到此中斷信號(hào)后 ,就調(diào)用 缺頁(yè)中斷處理程序 ,根據(jù)頁(yè)表中給出的外存地址 ,將該頁(yè)調(diào)入內(nèi)存 ,使作業(yè)繼續(xù)運(yùn)行下去。直到該頁(yè)裝入主存再將其喚醒。 當(dāng)重新執(zhí)行時(shí) ,由于要訪問(wèn)的頁(yè)已在主存 ,因此就可以正常地執(zhí)行下去。 若此時(shí)內(nèi)存中沒(méi)有空閑塊 ， 則要 淘汰某頁(yè) ， 若該頁(yè)在內(nèi)存期間被修改過(guò) ， 則要將其寫(xiě)回外存 。 大多數(shù)程序都有一個(gè)這樣的特定點(diǎn) 試驗(yàn)分析表明：對(duì)所有程序來(lái)說(shuō) ， 要使其有效地工作 ，它在主存中的頁(yè)面數(shù)應(yīng)不低于它的總頁(yè)面數(shù)的一半 01000202130004000500060007000800090001000024 32 48 64 80 96 112 128 160 192主存大小M （ KB ）缺頁(yè)次數(shù) F存儲(chǔ)容量與缺頁(yè)中斷次數(shù)的關(guān)系 理想淘汰算法 — 最佳頁(yè)面算法（ OPT） 淘汰 以后不再需要 的或 最遠(yuǎn)的將來(lái) 才會(huì)用到的頁(yè)面 先進(jìn)先出頁(yè)面淘汰算法 （ FIFO） 最簡(jiǎn)單 的算法是先進(jìn)先出淘汰算法 。為此 ,操作系統(tǒng)維護(hù)一張當(dāng)前頁(yè)表 。 另外設(shè)置一個(gè)指針指向最早進(jìn)入的頁(yè) 。 FIFO算法 較易實(shí)現(xiàn)，但會(huì)出現(xiàn) 抖動(dòng) 。 先進(jìn)先出頁(yè)面淘汰算法（ FIFO） FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 4 4 1 1 1 5 5 5 5 5 5 頁(yè) 2 3 3 3 4 4 4 4 4 2 2 2 頁(yè) 3 2 2 2 3 3 3 3 3 1 1 x x x x x x x v v x x v 共缺頁(yè)中斷 9次 命中率 =3/12*100%=25% FIFO算法雖然易于實(shí)現(xiàn)，但出現(xiàn)抖動(dòng)外，還會(huì)有一種 異?，F(xiàn)象 。這種奇怪的現(xiàn)象就叫做 Belady異常 。某作業(yè)有 5個(gè)頁(yè)面，執(zhí)行時(shí)引用的頁(yè)序列為： 0,1,2,3,0,1,4,0,1,2,3,4。下圖給出該作業(yè)的頁(yè)面蹤跡 。 圖中 (b)是 4個(gè)主存塊 時(shí)卻產(chǎn)生了 10次中斷 。 先進(jìn)先出頁(yè)面淘汰算法（ FIFO） 先進(jìn)先出頁(yè)面淘汰算法（ FIFO） 圖 采用 FIFO的 Belady異常 . 0 1 2 3 0 1 4 0 1 2 3 4 x x x x x x x v v x x v 4 4 4 4 4 3 3 3 0 0 0 4 2 2 3 3 2 1 0 1 0 1 0 1 0 1 0 2 1 2 1 2 1 （ a)分配三個(gè)內(nèi)存塊時(shí)，缺頁(yè) 9次。它是根據(jù)程序執(zhí)行時(shí)所具有的局部性原理考慮的。 LRU算法 是較好的一個(gè)算法 。 最近最少使用的頁(yè)面淘汰算法 (LRU) 多少 ?有無(wú) 最近最久未使用頁(yè)面淘汰算法 仍然難以實(shí)現(xiàn) 現(xiàn)在一般采用近擬 LRU算法 最近最少使用的頁(yè)面淘汰算法 (LRU) 例 2：計(jì)算缺頁(yè)次數(shù) 某程序在內(nèi)存中分配三個(gè)頁(yè)面 ,初始為空 ,頁(yè)面走向?yàn)?4,3,2,1,4,3,5,4,3,2,1,5。在時(shí)間 T內(nèi)，訪問(wèn)過(guò)的頁(yè)其訪問(wèn)位為 1，反之為 0，淘汰為 0 的頁(yè)。 太小 ，訪問(wèn)位為 0的頁(yè)相當(dāng)多，所選的不一定是最久未用的。 練習(xí) 某程序在內(nèi)存中分配 四 個(gè)塊，訪問(wèn)頁(yè)的走向?yàn)?4， 2， 3， 2， 4， 5， 2， 4， 2， 3，1， 4，按 LRU 、 FIFO、 OPT算法分別計(jì)算缺頁(yè)次數(shù) ,假設(shè)開(kāi)始時(shí)所有頁(yè)均不在內(nèi)存。這種現(xiàn)象稱為 顛簸 或 抖動(dòng) 原因： ?頁(yè)面淘汰算法不合理 ?分配給進(jìn)程的物理頁(yè)面數(shù)太少 顛簸（抖動(dòng)） 請(qǐng)求頁(yè)式存貯管理 段式存儲(chǔ)管理 1 段式存儲(chǔ)管理基本思想 用戶程序劃分 按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè) 段號(hào) 。 段式存儲(chǔ)管理 2 段地址映射 1) 地址映射數(shù)據(jù)結(jié)構(gòu) 段地址映射的數(shù)據(jù)結(jié)構(gòu)有 段表 、 段表首址指針和段表的長(zhǎng)度 。 段表 一般包括有 段的長(zhǎng)度 、段的首址 和 存取狀態(tài) 等信息 。 段號(hào) 0 1 2 段首址 段長(zhǎng)度 58K 20K 100K 110K 260K 140K 2 段地址映射 2)段地址變換 :段地址變換由硬件地址變換機(jī)構(gòu)完成 L B 段表長(zhǎng) 段表地址 段 表 寄存器 + s d 段號(hào) 段內(nèi)地址 邏輯地址 段長(zhǎng) 內(nèi)存始址 1K 500 6 K 10 K 段表 … … … + d m ? 訪內(nèi)地址 10K 內(nèi)存 段長(zhǎng) Y N 地址越界，發(fā)生中斷 說(shuō)明 段地址映射過(guò)程為： 程序地址字送入虛地址寄存器 VR中 。 根據(jù)段表首址指針找到段表 ， 查找段號(hào)為 s的表目 ， 得到該段的首地址 。 3）快表 同頁(yè)地址變換一樣 ， 在段地址變換過(guò)程中 ，也有兩次訪問(wèn)內(nèi)存的問(wèn)題 。 2 段地址映射 地址映射及存儲(chǔ)保護(hù)機(jī)制 地址越界 比較 比較 b + d 段 表 快表 物理地址 L b . . . S L b 地址越界 d=L d=L S= Cl + Cl Cb 段號(hào) S 段內(nèi)地址 d 段表始址寄存器 段表長(zhǎng)度寄存器 邏輯地址 地址越界 比較 具有快表的段地址映射 3 分段與分頁(yè)技術(shù)的比較 分段與分頁(yè)主要有以下差別： 段是依據(jù)程序的邏輯結(jié)構(gòu)劃分的 ， 頁(yè)是按內(nèi)存線性空間物理劃分的 。 段是面向用戶的 ， 頁(yè)對(duì)用戶而言是透明的 。面頁(yè)長(zhǎng)是由系統(tǒng)決定的，各頁(yè)的長(zhǎng)度必須相等。 4 段式存儲(chǔ)管理方案小結(jié) 優(yōu)點(diǎn)： 便于動(dòng)態(tài)申請(qǐng)內(nèi)存 管理和使用統(tǒng)一化 便于共享 便于動(dòng)態(tài)鏈接 缺點(diǎn)： 產(chǎn)生碎片 段頁(yè)式存儲(chǔ)管理方式 產(chǎn)生背景 : 結(jié)合頁(yè)式段式優(yōu)點(diǎn) ,克服二者的缺點(diǎn) 1 段頁(yè)式存儲(chǔ)管理基本思想 用戶程序劃分 按段式劃分（對(duì)用戶來(lái)講，按段的邏輯關(guān)系進(jìn)行劃分；對(duì)系統(tǒng)講，按頁(yè)劃分每一段） 邏輯地址 內(nèi)存劃分 : 按頁(yè)式存儲(chǔ)管理方案 內(nèi)存分配 : 以頁(yè)為單位進(jìn)行分配 段號(hào) 段內(nèi)地址 頁(yè)號(hào) 頁(yè)內(nèi)地址 段表 ：記錄了每一段的頁(yè)表始址和頁(yè)表長(zhǎng)度 頁(yè)表 ：記錄了邏輯頁(yè)號(hào)與內(nèi)存塊號(hào)的對(duì)應(yīng)關(guān)系(每一段有一個(gè) ,一個(gè)程序可能有多個(gè)頁(yè)表 ) 內(nèi)存分配管理 ：同頁(yè)式管理 2 地址映射 段頁(yè)式存儲(chǔ)管理方式 2 地址映射 0123段表寄存器＞＋ 段表始址 段表長(zhǎng)度段超長(zhǎng) 段號(hào) s 頁(yè)號(hào) p 頁(yè)內(nèi)地址0123段表＋頁(yè)表b 塊號(hào) b 塊內(nèi)地址頁(yè)表長(zhǎng)度 頁(yè)表始址段頁(yè)式存儲(chǔ)管理的優(yōu)點(diǎn) ： ?提供了虛存的功能 ?無(wú)緊縮問(wèn)題，也沒(méi)有頁(yè)外碎片的存在 ?便于處理變化的數(shù)據(jù)結(jié)構(gòu) ?便于共享和控制存取訪問(wèn)權(quán)限。 3 段頁(yè)式存儲(chǔ)管理的優(yōu)缺點(diǎn) 作業(yè) 1. 解釋下列概念：物理地址，邏輯地址，邏輯地址空間、內(nèi)存空間。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如右表所示：則邏輯地址0A5C(H)所對(duì)應(yīng)的物理地址是什么 ?要求 :寫(xiě)出主要計(jì)算過(guò)程。當(dāng)內(nèi)存塊數(shù)量分別為 3和 4時(shí) ,試問(wèn) LRU、 FIFO、 OPT這 3種置換算法的缺頁(yè)次數(shù)各是多少 (假定所有內(nèi)存塊起初為空 )?