【正文】 部性原理考慮的。所謂 局部性原理 ，是指在一段時(shí)間，進(jìn)程集中在一組子程序或循環(huán)中執(zhí)行，導(dǎo)致所有的存貯器訪問(wèn)局限于進(jìn)程地址空間的一個(gè)固定子集。 LRU算法 是較好的一個(gè)算法 。 但為實(shí)現(xiàn) LRU，系統(tǒng)的開銷太大 。 最近最少使用的頁(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。 LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 4 4 1 1 1 5 5 5 2 2 2 頁(yè) 2 3 3 3 4 4 4 4 4 4 1 1 頁(yè) 3 2 2 2 3 3 3 3 3 3 5 x x x x x x x v v x x x 共缺頁(yè)中斷 10次 命中率 =2/12*100%=% 最近最少使用的頁(yè)面淘汰算法 (LRU) LRU近似算法 ： 在頁(yè)表中增加一 訪問(wèn)位 ，每當(dāng)訪問(wèn)一頁(yè)時(shí)，將該頁(yè)的訪問(wèn)位由硬件置 1，軟件周期（ T）性地將所有訪問(wèn)位置 0。在時(shí)間 T內(nèi)，訪問(wèn)過(guò)的頁(yè)其訪問(wèn)位為 1，反之為 0，淘汰為 0 的頁(yè)。 缺點(diǎn)： T難定 。 太小 ，訪問(wèn)位為 0的頁(yè)相當(dāng)多，所選的不一定是最久未用的。 太大 ，所有頁(yè)的引用位可能都為 1，找不到合適的淘汰頁(yè)。 練習(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è)開始時(shí)所有頁(yè)均不在內(nèi)存。 在虛存中，頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(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) 。段號(hào)從 0開始，每一段段內(nèi)也從 0開始編址，段內(nèi)地址是連續(xù)的 邏輯地址 段號(hào) 段內(nèi)地址 1 段式存儲(chǔ)管理基本思想 內(nèi)存劃分 內(nèi)存空間被動(dòng)態(tài)地劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，稱為 物理段 ，每個(gè) 物理段 由 起始地址 和 長(zhǎng)度確定 內(nèi)存分配 以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)連續(xù)空間 (內(nèi)存隨機(jī)分割，需要多少分配多少 )，但各段之間可以不連續(xù)存放。 段式存儲(chǔ)管理 2 段地址映射 1) 地址映射數(shù)據(jù)結(jié)構(gòu) 段地址映射的數(shù)據(jù)結(jié)構(gòu)有 段表 、 段表首址指針和段表的長(zhǎng)度 。 段表首址指針和段表長(zhǎng)度 存放在進(jìn)程自己的 PCB中 。 段表 一般包括有 段的長(zhǎng)度 、段的首址 和 存取狀態(tài) 等信息 。 每一進(jìn)程有一個(gè)段表 ， 程序的每一個(gè)段在段表中占用一個(gè)表目 。 段號(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中 。 取出段號(hào) s和段內(nèi)位移 d。 根據(jù)段表首址指針找到段表 ， 查找段號(hào)為 s的表目 ， 得到該段的首地址 。 把段首地址與段內(nèi)位移 d相加 ， 形成內(nèi)存地址送入 MR中 ， 并以此地址訪問(wèn)內(nèi)存 。 3）快表 同頁(yè)地址變換一樣 ， 在段地址變換過(guò)程中 ，也有兩次訪問(wèn)內(nèi)存的問(wèn)題 。 為了加快訪問(wèn)內(nèi)存的速度也可采用快速存儲(chǔ)器組成快表 。 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)存線性空間物理劃分的 。 段式技術(shù)中程序地址空間是二維的 ， 分頁(yè)技術(shù)中程序地址空間是一維的 。 段是面向用戶的 ， 頁(yè)對(duì)用戶而言是透明的 。 段長(zhǎng)由用戶決定，且各段的大小一般不相等，唯一的限制是最大長(zhǎng)度。面頁(yè)長(zhǎng)是由系統(tǒng)決定的，各頁(yè)的長(zhǎng)度必須相等。 段的共享比頁(yè)的共享更容易。 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)限。 缺點(diǎn) ： ?增加了軟件的復(fù)雜性和管理開銷 ?需要更多的硬件支持 ?各種表格要占用一定的存儲(chǔ)空間 ?存在著系統(tǒng)抖動(dòng)現(xiàn)象 ?存在著頁(yè)內(nèi)碎片的問(wèn)題。 3 段頁(yè)式存儲(chǔ)管理的優(yōu)缺點(diǎn) 作業(yè) 1. 解釋下列概念：物理地址，邏輯地址，邏輯地址空間、內(nèi)存空間。 2. 什么叫重定位？區(qū)分靜態(tài)重定位和動(dòng)態(tài)重定位的根據(jù)是什么？ 3. 什么是虛擬存儲(chǔ)器？它有哪些基本特征？ 4. 什么是分頁(yè)？什么是分段？二者有何區(qū)別？ 作業(yè) 5. 某虛擬存儲(chǔ)器的用戶編程空間共 32個(gè)頁(yè)面 ,每頁(yè)為 1KB,內(nèi)存為16KB。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如右表所示：則邏輯地址0A5C(H)所對(duì)應(yīng)的物理地址是什么 ?要求 :寫出主要計(jì)算過(guò)程。 頁(yè)號(hào) 物理塊號(hào) 0 3 1 7 2 11 3 8 6. 考慮頁(yè)面走向 :4,3,2,1,4,3,5,4,3,2,1,5。當(dāng)內(nèi)存塊數(shù)量分別為 3和 4時(shí) ,試問(wèn) LRU、 FIFO、 OPT這 3種置換算法的缺頁(yè)次數(shù)各是多少 (假定所有內(nèi)存塊起初為空 )?