【文章內(nèi)容簡介】 外部碎片 問題，為解決外部碎片問題，可采用緊湊技術(shù)，但花費大量處理機時間。 59 課堂練習(xí) P123124： 912 60 純 分頁存儲管理 ★ 目前已討論了單道存儲管理和分區(qū)式存儲管理方法 。 ★ 分區(qū) 式管理方式盡管實現(xiàn)方式較為簡單 ， 但存在著嚴重的 碎片 問題 ?內(nèi)存的利用率 不高 。 ★ 再者 ， 分區(qū)式管理時 ， 由于各作業(yè)或進程對應(yīng)于不同的分區(qū)以及在分區(qū)內(nèi)各作業(yè)或進程連續(xù)存放 ， 進程的大小仍受分區(qū)大小或內(nèi)存可用空間的 限制 。 ★ 而且 ， 分區(qū)式管理也 不利于 程序段和數(shù)據(jù)的 共享 。 61 ★ 頁式 管理正是為了 減少碎片 ， 以及為了只在內(nèi)存存放那些反復(fù)執(zhí)行或即將執(zhí)行的程序段與數(shù)據(jù)部分 ， 而把那些不經(jīng)常執(zhí)行的程序段和數(shù)據(jù)存放在外存待執(zhí)行時調(diào)入 ， 以提高內(nèi)存利用率 而提出來的 。 62 基本原理 頁式存儲管理： ★ 將 內(nèi)存 空間劃分成 等長 的若干區(qū)域 ， 每個區(qū)域稱為一個物理塊 ， 有時也稱 內(nèi)存塊 或 塊 。 ★ 內(nèi)存的所有物理塊從 0開始編號 ， 稱作 物理塊號 或 內(nèi)存塊號 。 ★ 每 個物理 塊內(nèi)單元 亦從 0開始依次編址 ， 稱為 塊內(nèi)地址 。 物理塊 0 物理塊 1 物理塊 2 …… 63 ★ 系統(tǒng)將用戶程序的 邏輯空間 按照 同樣大小 也劃分成若干頁面 ， 稱為 邏輯頁面 ， 有時也簡稱為 頁 。 ★ 程序的各個邏輯頁面從 0開始依次編號 ， 稱作 邏輯頁號 或相對頁號 ， ★ 每 個邏輯 頁面內(nèi)單元 也從 0開始編址 ， 稱為 頁內(nèi)地址 。 2. 邏輯地址空間劃分 頁 0 頁 1 頁 2 …… 64 ★ 對用戶程序地址空間的分頁是 系統(tǒng) 自動進行的 ， 即對用戶是 透明 的 。 ★ 由于頁面尺寸選為 2的整數(shù)次冪 ， 故系統(tǒng)可將地址的高位 部分定義成 頁號 ， 低位 部分定義成 頁內(nèi)地址 。 ★ 例如 ， 圖 ， 機器地址長為 20位 ， 若頁面長度為 210， 則地址的 10～ 19位表示頁號 ， 最多擁有 210 =1024個 邏輯頁 ， 0～ 9位表示頁內(nèi)地址 ， 即頁長為 210 =1K。 0 10 9 19 頁號（ P） 頁內(nèi)地址（ W） 圖 邏輯地址空間劃分 65 ★ 頁面大小直接影響地址轉(zhuǎn)換和頁式存儲管理的性能 : ?如果頁面 太大 ， 以至于和作業(yè)地址空間相差無幾 ， 這種方法就變成了可變分區(qū)方法的翻版； ?反之 ， 如果頁面 太小 ， 則增加了系統(tǒng)的開銷 。 3. 頁面大小 ★ 頁面尺寸一般取 2的整數(shù)次冪 ，如 29， 210， 211等。 66 ★ 存儲分配時 ， 以塊為單位 ， 并按用戶程序的頁數(shù)多少進行分配 ， 邏輯上相鄰的頁面在內(nèi)存中不一定相鄰 ， 即 : ★ 分配給用戶程序的內(nèi)存塊不一定連續(xù) 。 4. 內(nèi)存分配 頁 0 頁 1 頁 2 物理塊 0 物理塊 1 物理塊 2 物理塊 3 物理塊 4 物理塊 5 物理塊 6 物理塊 7 物理塊 8 …… 邏輯空間 內(nèi)存空間 67 ★ 如果把一個作業(yè)的所有頁面 一次全部裝入 到內(nèi)存塊中 ，就把這種分頁稱之為 純分頁 存儲管理 。 ★ 如果作業(yè)的所有頁面 并不是一次全部裝入 ， 而是根據(jù)作業(yè)運行時的實際要求裝入 ， 則把這種分頁稱為 虛擬頁式 存儲管理 。 ★ 本節(jié) 先討論 純 分頁存儲管理 。 68 實現(xiàn)方法 1. 建立頁表 ★ 系統(tǒng)為 每個用戶 程序建立 一張 頁表 ， 用于記錄用戶程序邏輯頁面與內(nèi)存物理塊之間的對應(yīng)關(guān)系 。 ★ 用戶程序的地址空間有多少頁 ， 該頁表里就登記多少行 ，且按邏輯頁的 順序排列 。 ★ 頁表存放在 內(nèi)存系統(tǒng)區(qū) 內(nèi) 。 頁號 塊號 0 2 1 6 2 8 圖 頁表示意圖 69 2. 建立空閑頁面表 系統(tǒng) 中設(shè)立 一張 內(nèi)存空閑頁面表 ， 記錄內(nèi)存物理頁面空閑情況 ， 用于內(nèi)存分配和回收 。 70 3. 內(nèi)存分配算法 圖 頁面分配算法流程圖 71 系統(tǒng)提供一對 硬件 寄存器：頁表始址寄存器和頁表長度寄存器 。 （ 1） 頁表始址寄存器 ★ 用于保存 正在運行 進程的頁表在內(nèi)存的 首地址 。 ★ 當(dāng)進程被調(diào)度程序選中投人運行時 ， 系統(tǒng)將其頁表首址從 進程控制塊 中取出送入該寄存器 。 （ 2） 頁表長度寄存器 ★ 用于保存 正在運行 進程的 頁表的長度 。 ★ 當(dāng)進程被選中運行時 ， 系統(tǒng)將它從 進程控制塊 中取出送入該寄存器 。 4. 硬件支持 72 5. 地址映射 8644 頁號 0 1 2 頁表始址寄存器 頁表長度寄存器 H L ＋ ＜ 邏輯地址 頁號 2 頁內(nèi)地址 452 塊號 2 6 8 8 452 LOAD 1,2500 12345 內(nèi)存 2148 頁號 ≥L 越界 物理地址 圖 頁式存儲管理的地址映射 頁表 73 具體步驟說明如下： （ 1） 地址映射機構(gòu)把 CPU給出的 邏輯地址分為兩部分 ， 如執(zhí)行指令 LOAD 1， 2500時 ， 邏輯地址 2500＝ 2 1024＋ 452，因此頁號 p＝ 2， 頁內(nèi)地址 d＝ 452。 這是假設(shè)頁面大小為 210情況下得到的結(jié)果； （ 2） 將 邏輯頁號 p與頁表長度比較 ， 如果 p大于頁表長度 ，則為越界 ， 發(fā)生越界中斷 。 74 （ 3） 根據(jù)頁表始址得到頁表在內(nèi)存的首地址 ， 并根據(jù)邏輯頁號 p在頁表中找到對應(yīng)的物理頁號 。 如果頁號 p＝ 2，則相應(yīng)物理頁號為 8。 （ 4） 把 物理頁號與邏輯地址中的頁內(nèi)地址 d拼在一起 ，形 成 訪 問 內(nèi) 存 的 物 理 地 址 。 在 本 例 中 ， 物理地址＝ 1024 8＋ 452＝ 8644。 75 快表 從地址映射過程中可以看出 ， 共需 兩次 訪問內(nèi)存： ★ 第一次 訪問頁表 ， 得到數(shù)據(jù)的物理地址 。 ★ 第二次才是 存取數(shù)據(jù) 。 ?增加了訪問時間 。 76 為了提高存取速度 , ★ 在分頁地址變化機構(gòu)中 ， 加入一組 高速緩沖存儲器 , ★ 用來存放當(dāng)前作業(yè)的 最常用 的頁號和與之相對應(yīng)的物理塊號 。 ★ 一般稱這樣的寄存器組為 快表 或 聯(lián)想存儲器 。 ★ 快表因硬件成本較高，個數(shù) 不宜太多 ，一般以 8～ 16個單元組成，和頁表具有 并行查找 能力。 77 具有快表的地址映射過程： 當(dāng)處理機給出邏輯地址 （ p， w） 時 ， 分頁機構(gòu) : ★ 一方面 取出頁號 p， 并根據(jù) p從 頁表中查找 相應(yīng)的內(nèi)存塊號 b； ★ 另一方面 自動把頁號 p送入快表 ， 并和快表各單元進行比較 ， 78 如 與某單元頁號 相符 ， 則 ★ 輸出對應(yīng)塊號 b ， 并與頁內(nèi)地址 w形成物理地址進行訪問 ， ★ 停止查找頁表的工作 ， ★ 由于快表采用的是高速緩存 ， 其訪問速度比訪問頁表要快得多 。 如果 在快表中 查找不到 ， ★ 仍繼續(xù)在頁表中查找， ★ 并把查找到的頁號 p和塊號 b放到快表的空閑單元 中，以備下次使用， ★ 如無空閑單元，則通常把最先裝入的那個頁號 淘汰 ，以騰出位置。 79 物理地址 頁表 頁號 塊號 p b 邏輯地址 p w 聯(lián)想存儲器 頁號 塊號 p b a + b w 頁表始址寄存器 ① 利用快表查找 ② 利用頁表查找 ③利用頁表中查找到的頁號、塊號更新快表 圖 采用快表和頁表相結(jié)合的分頁地址變換過程示意圖 1 2 2 3 1 物理地址頁表頁號 塊號邏輯地址聯(lián)想存儲器頁號 塊號頁表始址寄存器① 利用快表查找 ② 利用頁表查找③利用頁表中查找到的頁號、塊號更新快表圖 采用快表和頁表相結(jié)合的分頁地址變換過程示意圖80 存儲保護 頁式管理可以為內(nèi)存提供 兩種 方式的保護 : ★ 地址越界保護： 可由地址變換機構(gòu)中的控制寄存器的值（ 頁表長度 ） ， 和所要訪問的 邏輯地址 相 比較 完成 。 ★ 存取控制保護： 通過頁表 ， 控制對內(nèi)存信息的操作方式 ，以提供保護 。 即：在 頁表中增加相應(yīng)的保護位 即可 。 81 優(yōu)點與缺點 純分頁存儲管理的： ★ 優(yōu)點 ：有效解決了碎片問題 ， 主存利用率高 ， 內(nèi)存分配與回收算法也比較簡單 。 ★ 缺點 ：采用動態(tài)地址變換機制 ， 既增加硬件成本也降低了處理機速度 。 82 課堂練習(xí) P124125： 1416 83 純段式 存儲管理 純 段式 管理的基本思想 ★ 通常情況下 :一個作業(yè) =多個程序段 +多個數(shù)據(jù)段 ， ★ 這要求 鏈接裝配程序 將它們按 一維線性 地址排列 ，從而給程序和數(shù)據(jù)的 共享 帶來 不便 。 ★ 一般情況下 ， 用戶 希望： 按邏輯關(guān)系對作業(yè)分段 ，并能根據(jù)名字來訪問程序段和數(shù)據(jù)段 。 ★ 純段式存儲管理：較好地解決了程序和數(shù)據(jù)的 共享問題以及程序 動態(tài)鏈接 等問題 。 84 1. 基本原理 ★ 內(nèi)存 空間被 動態(tài) 地 劃分 為 若干 個 長度不相同 的區(qū)域 ，每個區(qū)域稱作一個 物理段 。 ★ 每個物理段在 內(nèi)存中 有一個起始地址 ， 稱作 段首址 。 ★ 將物理 段中 的所有單元從 0開始 依次編址 。 物理段 0 物理段 1 物理段 2 …… 85 2. 邏輯地址空間劃分 ★ 用戶程序按 邏輯上 有 完整意義 的段來劃分 ， 稱為 邏輯段 。 ★ 例如：主程序 、 子程序 、 數(shù)據(jù)等可各成一段 ， 每段對應(yīng)于一個過程 、 一個程序模塊或一個數(shù)據(jù)集合 。 ★ 將 一個用戶程序 的所有邏輯段從 0開始 編號 ， 稱為 段號 ； ★ 將 一個邏輯段中 的所有單元從 0開始 編址 ， 稱為 段內(nèi)地址 。 ★ 整個地址空間就構(gòu)成了 二維地址空間 。 段內(nèi)地址（ W） 段號（ S） ★ 用戶程序的 邏輯地址 由段號和段內(nèi)地址 兩部分 組成： 86 3. 內(nèi)存分配 ★ 系統(tǒng)以 段為單位 進行內(nèi)存分配 ， ★ 為每 一個邏輯段 分配 一個連續(xù)的內(nèi)存區(qū) （ 物理段 ） ， ★ 邏輯上連續(xù)的 各個段在內(nèi)存不一定連續(xù) 存放 。 物理段 0 …… 物理段 1 物理段 2 …… 邏輯段 0 邏輯段 1 邏輯段 2 87 實現(xiàn)方法 1. 建立段表 ★ 系統(tǒng)為 每個用戶程序 建立 一張 段表 ， 用于記錄用戶程序的 邏輯段 與內(nèi)存 物理段 之間的 對應(yīng)關(guān)系 ， 包括 邏輯段號 ，內(nèi)存首地址 和 物理段長度 三項內(nèi)容 。 ★ 用戶程序有多少邏輯段 ， 該段表里就登記多少行 ， 且按邏輯段的 順序 的排列 。 ★ 段表存放在 內(nèi)存系統(tǒng)區(qū) 里 。 ★ 段表如 圖 。 88 段號 內(nèi)存首地址 段長 0 660 660 1 240 330 2 100 90 3 1580 123 圖 段表示意圖 89 系統(tǒng) 中設(shè)立 一張 內(nèi)存空閑區(qū)表 ， 記錄內(nèi)存中空閑區(qū)域情況 ，用于為段分配和回收內(nèi)存 。 2. 建立空閑區(qū)表 90 系統(tǒng)提供 一對 寄存器：段表始址寄存器和段表長度寄存器 。 （ 1） 段表始址寄存器 ： ★ 用于保存 正在運行 進程的段表在內(nèi)存的 首地址 。 ★ 當(dāng)進程被調(diào)度程序選中投入運行時 ， 系統(tǒng)將其段表首址從 進程控制塊 中取出送入該寄存器 。 （ 2） 段表長度寄存器 ： ★ 用于保存 正在運行 進程的 段表的長度 。 ★ 當(dāng)進程被選中運行時 ， 系統(tǒng)將它從 進程控制塊 中取出送入該寄存器 。 3. 硬件支持 91 ★ 如 圖 。 ★ 先將邏輯地址中的 段號 與段表長度寄存器中的 段表長度進行 比較 ， ★ 若段號 超過 段表長度 ,則產(chǎn)生 越界中斷 ； ★ 否則 ， 系統(tǒng)將根據(jù)段號和段表始址寄存器中的段表起始地址計算出該段在 段表中的位置 ， ★ 從該位置中將獲得該段存放在 內(nèi)存中的起始地址 。 ★ 然后 ， 檢查 段內(nèi)位移 是否超過 該段的 段長 ， ★ 若 超過 則產(chǎn)生 越界中斷 ； ★ 否則 ， 將該段在內(nèi)存的起始地址與邏輯地址的段內(nèi)位移相加 就可得到要訪問的 物理地址 。 4. 地址映射過程 92 邏輯地址 段表始址寄存器 段表長度寄存器 段表起始地址 段表長度 段號 段長