【正文】 2/17 145 本節(jié)主要內容： 請求分頁中的硬件支持 內存分配策略和分配算法 調頁策略 本節(jié)學習目標： 掌握請求分頁中的硬件支持； 了解內存分配策略和分配算法； 掌握調頁策略 返回 2022/2/17 146 在請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結構，仍然是頁表。 若太少，會頻繁地出現(xiàn)缺頁中斷，降低了系統(tǒng)的吞吐量； 若太多，必然使內存中駐留的進程數(shù)目減少，造成資源 空閑。 例子： 求 :缺頁次數(shù)、缺頁率及置換次數(shù) 2022/2/17 163 最佳（ Optimal）置換算法 發(fā)生了 6次面置換， 9次缺頁中斷 ,。 隨著分配的主存塊數(shù)的增加 ，缺頁中斷次數(shù)不但沒有降低 ， 反而增加了 。 缺頁次數(shù)： 8 置換次數(shù)： 4 2022/2/17 174 2. LRU置換算法的硬件支持 1)寄存器 R=Rn1…R1R0 說明 :系統(tǒng)為每個在 內存 中的頁面配置一個移位寄存器 , 當進程訪問某物理塊時 ,將相應寄存器的 Rn1位置成 1. 2) 棧 基本思想：每當進程訪問某頁時，便將該頁面的頁面號 從棧中移出，將它壓入棧頂。 思想 : 概 述 2022/2/17 186 本節(jié)主要內容： 請求分段中的硬件支持 分段的共享與保護 本節(jié)學習目標： 了解請求分段中的硬件支持； 了解分段的共享與保護 返回 2022/2/17 187 請求分段中的硬件支持 段名 段長 段的 基址 存取 方式 訪 問 字段 A 修 改 字段 M 存在 位 P 增補位 外存 起址 只執(zhí)行、只讀、讀寫 記錄該段被訪問的頻繁程度 是否被修改過，換頁時參考 指示本段是否已調入內存 在運行過程中是否進行過動態(tài)增長 2022/2/17 188 越界中斷處理 進程在執(zhí)行過程中，有時需要擴大分段，如數(shù)據(jù)段。若內存中沒有足夠大的空閑分區(qū)，則考慮進行段的緊湊或將某段或某些段淘汰出去。 2022/2/17 171 LRU算法演示過程（ m=3） 約定：每一輪訪存進行排序，將要置換的頁放 在下面 1 2 3 4 1 2 5 1 2 3 4 5 1 2 2 1 3 3 4 4 1 1 1 2 2 5 5 √ √ √ √ √ √ √ 2 1 2 1 5 3 3 4 4 5 2 3 √ √ 1 2 3 4 1 2 √ 2022/2/17 172 ? 【 例 3】 設 m=3， 采用 LRU算法 ， 缺頁中斷次數(shù)及缺頁率如圖所示 。 2022/2/17 168 ?設 m=4， 仍采用 FIFO算法 ， 缺頁中斷次數(shù)及缺頁率 如下圖 所示 。但是，可把它作為一種評價 標準，比較其他實用方法的優(yōu)劣，所以，最優(yōu)算法 只具有理論上的意義。 若系統(tǒng)為某進程所分配的物理塊數(shù)少于此值時， 進程將無法運行，這取決于指令的格式、功能 和尋址方式。 對換性 對換性是指允許在作業(yè)地運行過程中換進、換出 換進、換出能有效地提高內存利用率 虛擬性 虛擬性是指能夠從邏輯上擴充內存容量 虛擬性是虛擬存儲器所表現(xiàn)出來的最重要的特征。 定 義 2022/2/17 135 虛擬存儲器的邏輯容量由內存容量和外存容量之和決定， 其運行速度接近于內存速度，而成本接近于外存。 內存分配 以頁為單位離散分配，無外碎片，所以也無緊縮問題 以段為單位離散分配，類同可變分區(qū)，會產(chǎn)生許多分散的小自由分區(qū) —— 外碎片，造成主存利用率低，需采用緊縮解決碎片問題，但緊縮需花費機時 分頁和分段比較： 2022/2/17 121 分 頁 分 段共享和存取訪問控制在同一頁面中包含共享的程序和私用的數(shù)據(jù)，使共享和存取訪問控制困難；便于共享段邏輯上完整信息共享有價值 , 提高主存利用率；便于控制存取訪問，段是邏輯上完整信息可根據(jù)各段信息決定存取訪問權動態(tài)連接不能動態(tài)連接；提供動態(tài)連接的便利，運行中不用的模塊可以不連接調入，節(jié)省內存空間動態(tài)增長不能動態(tài)增長 便于處理變化的數(shù)據(jù)結構段，可動態(tài)增長分頁和分段比較 2022/2/17 122 信息共享 例子 : 有一個多用戶系統(tǒng) ,可同時接納 40個用戶 ,它們都執(zhí)行一 個文本編輯程序 .如果文本編輯程序含有 160KB的代碼 和 40KB的數(shù)據(jù)區(qū) ,若不允許共享，則總共需要 : 8MB的內存空間 . 如果代碼是可重入的 ,則總共需要 : 40 40+160=1760KB. 又稱為純代碼，允許多個進程同時訪問 2022/2/17 123 分頁與分段共享比較 : 進程 1 進程 2 ed1 ed40 d1 d10 頁表 頁表 21 60 61 70 71 80 21 60 21 60 2022/2/17 124 段頁式存儲管理方式 段號 (S) 段內頁號 (P) 頁內地址 (W) 地址結構 2022/2/17 125 基本思想： 用戶程序劃分：按段式劃分（對用戶來講，按段的邏輯關系進行劃分；對系統(tǒng)講，按頁劃分每一段） 邏輯地址： 內存劃分：按頁式存儲管理方案 內存分配：以頁為單位進行分配 段號 段內地址 頁號 頁內地址 2022/2/17 126 ：記錄了每一段的頁表始址和頁表長度 ：記錄了邏輯頁號與內存塊號的對應關系（每一段有一個，一個程序可能有多個頁表） ：同頁式管理 返回 2022/2/17 127 虛擬存儲器的基本概念 P141 前面的存儲器管理方式存在下列情況： （ 1）有的作業(yè)很大，不能被全部裝入內存 （ 2）有大量作業(yè)要求運行，但由于內存容量不足以 容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內存讓它們 先運行，而將其它大量的作業(yè)留在外存上等待。 2022/2/17 114 段表： 它記錄了段號，段的首（地）址和長度之間的關系 每一個程序設置一個段表，放在內存 屬于進程的現(xiàn)場信息 段號 0 1 2 段首址 段長度 58K 20K 100K 110K 260K 140K 2022/2/17 115 段號 段長 基址 0 1 2 3 30K 40K 20K 80K 15K 120K 10K 150K 段 表 作業(yè)空間 (MAIN)=0 0 30 (X)=1 0 20 (D)=2 0 15 30K 20K 15K 40 80 120 內存空間 2022/2/17 116 首次適應； 最佳適應； 最壞適應 內存的分配算法： 2022/2/17 117 3. 地址變換機構 控制寄存器 段表始址 段表長度 2 100 有效地址 段號 S 位移量 W 越界 + 2 500 8K + 8292 物理地址 8K 8292 8792 8 1024+100 2022/2/17 118 優(yōu)點： 便于動態(tài)申請內存 管理和使用統(tǒng)一化 便于共享 便于動態(tài)鏈接 缺點：產(chǎn)生碎片 課后思考題：與可變分區(qū)存儲管理方案的相同 點與不同點？ 2022/2/17 119 相同點： 都采用離散分配方式，都通過地址映射機構 來實現(xiàn)地址變換。 2022/2/17 102 兩級頁表機制 31 22 21 12 11 0 外層頁表 頁表 物理地址 外層頁號 p1 外層頁內地址 p2 頁內地址 d 外層頁表寄存器 + + b d 邏輯地址結構 2022/2/17 103 頁目錄地址 目錄位移 頁表位移 頁位移 邏輯地址 頁表地址 . . . 頁目錄（每進程一個） 塊號 . . . 頁表 代碼或數(shù)據(jù) . . . 內存塊 二級頁表結構及地址映射 + + 2022/2/17 104 兩級頁表機制圖 第 0頁頁表（物理塊號 10） 內 存 0 1 0 ┇ 1 1023 2 第 1頁頁表（物理塊號 25） 0 1 ┇ 1023 第 N頁頁表（物理塊號 120） 0 1 外層頁 表 ┇ 1023 10 25 120 12 14 32 35 151 152 0 1 …… 12 13 14 …… 32 33 34 35 …… 151 152 …… 返回 2022/2/17 105 基本分段存儲管理方式 P135 分頁存儲管理的主要動力，是提高內存利用率； 分段存儲管理方式的引入，則為了滿足用戶在編程和使用上多方面的要求。 ? 若是，則直接讀出該頁所對應的物理塊號，送入物理地址寄存器； ? 若在快表中未找到對應的頁表項，則需再訪問內存中的頁表，找到后，把從頁表中讀出的頁表項存入快表中的一個寄存器單元中，以取代一個舊的頁表項。 ?頁表大多駐留內存。 頁面的大小一般為 512B~8KB 2)頁面大小 但 另一方面 ，也會使每個進程要求較多的頁面，從而 導致頁表過長，占用大量內存；此外，還會降低頁面 換進換出的效率。目的是為了支持虛擬存儲系統(tǒng)。 2022/2/17 60 最壞適應算法的空閑分區(qū)鏈表組織形式 2022/2/17 61 (5) ? 前面的幾種算法稱為順序搜索法。 2022/2/17 52 基于首次適應算法的動態(tài)分區(qū)分配過程： 38KB 60KB 40KB 例 1 假設作業(yè)需要 36KB的存儲空間 空閑分區(qū)鏈以地址遞增的次序鏈接 例 2 假設作業(yè)需要 58KB的存儲空間 46KB 10 2KB 2022/2/17 53 首次適應算法的空閑分區(qū)鏈表組織形式 2022/2/17 54 2)循環(huán)首次適應算法（ next fit) 在為進程分配內存空間時，不再每次從鏈首開始查找， 而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查 找，直至能找到第一個能滿足要求的空閑分區(qū) 。 內存分配續(xù) : （ 2）動態(tài)存儲分配 2022/2/17 40 內存分配 連續(xù)分配方