【正文】 34 ★ 單一連續(xù)分配主要是指：內(nèi)存只供 一個(gè) 用戶進(jìn)程使用 。 系統(tǒng)區(qū) 用戶區(qū) 空閑區(qū) 圖 單一連續(xù)區(qū)管理時(shí)的內(nèi)存劃分 35 ★ 單一連續(xù)分配方式主要采用 靜態(tài)分配 方式 ， 即：作業(yè)或進(jìn)程一旦進(jìn)入內(nèi)存后 ， 就要等到該作業(yè)或進(jìn)程執(zhí)行結(jié)束后才能釋放內(nèi)存 。 如 圖 。 ★ 缺點(diǎn) ： （ 1） 由于進(jìn)程或作業(yè)所要求的存儲(chǔ)量不會(huì)正好等于內(nèi)存可用存儲(chǔ)區(qū)容量 ， 因而總有一部分空閑存儲(chǔ)區(qū) 得不到 利用 。 37 （ 3） 單一連續(xù)分配管理方式限制了用戶程序和系統(tǒng)程序的可重入性 。 因?yàn)橄到y(tǒng)只允許每次對(duì)一個(gè)作業(yè)或進(jìn)程進(jìn)行內(nèi)存分配 。 改進(jìn) —— 38 分區(qū)存儲(chǔ)管理 ★ 分區(qū)管理是在單一連續(xù)管理的基礎(chǔ)上發(fā)展起來(lái)的一種存儲(chǔ)管理方法 ， 是 滿足多道 程序運(yùn)行的 最簡(jiǎn)單 的存儲(chǔ)管理方案 。 ★ 按分區(qū)的時(shí)機(jī) ， 分區(qū)管理分為 固定 分區(qū)和 可變 分區(qū) 。 ★ 分區(qū)一旦劃分結(jié)束 ， 在整個(gè)執(zhí)行過(guò)程中每個(gè)分區(qū)的 長(zhǎng)度 和內(nèi)存的總分區(qū) 個(gè)數(shù) 將 保持不變 。 ★ 內(nèi)存的分配釋放 、 存儲(chǔ)保護(hù)以及地址變換等 都 通過(guò)分區(qū)說(shuō)明表進(jìn)行 。 41 ★ 固定分區(qū)的地址重定位采取 靜態(tài)地址 重定位方法； ★ 固定分區(qū)的存儲(chǔ)保護(hù)采用 上 、 下界寄存器 保護(hù)方式 。 而且當(dāng)用戶作業(yè)的地址空間小于分區(qū)的存儲(chǔ)空間時(shí) ， 浪費(fèi) 了一些存儲(chǔ)空間 。 42 可變分區(qū) 法 ★ 與固定分區(qū)法相比 ， 可變分區(qū)法在作業(yè)執(zhí)行 前 并 不建立 分區(qū) ， ★ 而是在作業(yè) 裝入 內(nèi)存時(shí) 建立 分區(qū) ， 使分區(qū)的大小正好與作業(yè)要求的存儲(chǔ)空間 相等 ， ★ 能有效 解決 固定式分區(qū)的 內(nèi)部碎片 問(wèn)題 ， 是一種 較為實(shí)用 的存儲(chǔ)管理方法 。 43 0k 40k 256k1 操作系統(tǒng) 空 閑 分 區(qū) （ a） 可變式分區(qū)運(yùn)行開(kāi)始 0k 40k 86k 118k 156k 196k 256k1 操作系統(tǒng) 作業(yè) 1(46k) 作業(yè) 2(32k) 作業(yè) 3(38k) 作業(yè) 4(40k) 空閑 （ 60k） （ b） 作業(yè) 4進(jìn)入內(nèi)存 0k 40k 86k 118k 156k 196k 256k1 操作系統(tǒng) 空閑 1(46k) 作業(yè) 2(32k) 空閑 2(38k) 作業(yè) 4(40k) 空閑 3(60k) （ c） 作業(yè) 3釋放后內(nèi)存 圖 可變式分區(qū)內(nèi)存使用情況示意圖 44 ★ 如 圖 ， 假設(shè)某系統(tǒng)采用 可變式分區(qū) 存儲(chǔ)管理 ， 在系統(tǒng)運(yùn)行的開(kāi)始 ， 存儲(chǔ)區(qū)被分為操作系統(tǒng)分區(qū) （ 40kb） 和可分給用戶的空閑區(qū) （ 216kb） 。 ★ 此時(shí) ， 作業(yè) 5進(jìn)入系統(tǒng) ， 要求分配 36k內(nèi)存 ， 如何 為作業(yè) 5分配內(nèi)存呢 ？ 45 ★ 如 圖 （ c） 所示 ， 此時(shí) ， 有 三種 方法可給作業(yè) 5分配內(nèi)存： ① 從作業(yè) 1釋放的 46k中 ， 分 36k給作業(yè) 5， 即 分配空閑區(qū) 1； ② 從作業(yè) 3釋放的 38k中 ， 分 36k給作業(yè) 5， 即 分配空閑區(qū) 2； ③ 從空閑的 60k中 ， 分 36k給作業(yè) 5， 即 分配空閑區(qū) 3。 46 1. 空閑分區(qū)的組織形式 ★ 在可變式分區(qū)存儲(chǔ)管理中 ， 常把空閑區(qū)組成 空閑分區(qū)表或 空閑分區(qū)鏈表 的形式 。 ★ 采用空閑分區(qū)表要占用一定數(shù)量的存儲(chǔ)單元存放此表 ? 增加 了系統(tǒng)的開(kāi)銷 。 ★ 系統(tǒng)中用一個(gè) 固定 單元作為空閑分區(qū)鏈表的 鏈表頭指針 ，指向 第一塊 空閑分區(qū) 首 地址 ， 最后一塊 空閑分區(qū)的鏈表指針 存放鏈尾標(biāo)志 。 ★ 所以 使用比較廣泛 的是空閑分區(qū)的鏈表組織形式 。 ★ 若系統(tǒng)中所有空閑區(qū)都 小于 Xk， 則無(wú)法分配 。 ★ 若該空閑區(qū) 大于 Xk， 則將空閑區(qū)一分為二 ， 一個(gè)為 Xk， 分給用戶 ， 另一個(gè)為余下部分 ， 仍留在空閑區(qū)鏈表中 ， 修改相應(yīng)鏈表指針?biāo)赶虻牡刂泛涂臻e區(qū)大小 。 應(yīng)該 檢查 回收區(qū)與內(nèi)存中前后空閑區(qū) 是否 相鄰 ， ★ 若 相鄰 ， 則應(yīng)進(jìn)行 合并 ， 形成一個(gè)較大的空閑區(qū) ， 并對(duì)相應(yīng)的鏈表指針進(jìn)行修改； ★ 若 不相鄰 ， 應(yīng)將空閑區(qū) 插入 到空閑區(qū)鏈表的適當(dāng)位置 。 ★ 最 先 適應(yīng)算法 ★ 最 佳 適應(yīng)算法 ★ 最 差 適應(yīng)算法 51 （ 1） 最先適應(yīng)算法 ★ 思想是 : 把空閑分區(qū)按其所在存儲(chǔ)空間中 地址遞增 的順序連接在一起 。 ★ 算法 如 圖 。 53 （ 2）最佳適應(yīng)算法 ★ 這種算法把空閑分區(qū)鏈表按 分區(qū)大小 由小到大 進(jìn)行組織 。 ★ 此算法 最節(jié)約空間 ， 因?yàn)樗M量不分割大的空閑區(qū) 。 30 k 100 40 k 80 50 k ^ 50 50 100 80 54 （ 3）最差適應(yīng)算法 ★ 這種算法要求把空閑區(qū)按分區(qū) 大小遞 減 的順序組織成空閑區(qū)鏈表 。 30 k 100 5 40 k 80 30 k ^ 70 70 100 80 55 ★ 該算法的 優(yōu) 點(diǎn)是：可以避免形成碎片； ★ 缺 點(diǎn)是：分割大的空閑區(qū)后 ， 再遇到較大的申請(qǐng)時(shí) ，無(wú)法滿足的可能性較大 。 56 4. 地址重定位和存儲(chǔ)保護(hù) 可變分區(qū)法的： 地址重定位：采用 靜態(tài) 重定位 ， 也可采用 動(dòng)態(tài) 重定位 。 57 5. 碎片處理 ★ 所謂 碎片 是指：內(nèi)存中出現(xiàn)的一些零散的小空閑區(qū)域 。 ★ 如果內(nèi)存中碎片 很多 ， 會(huì)造成 嚴(yán)重 的存儲(chǔ)資源浪費(fèi) 。 這一過(guò)程稱為 緊湊 （ 拼接 ） ， 這一技術(shù)就是 緊湊技術(shù) （ 拼接技術(shù) ） 。 58 6. 可變分區(qū)存儲(chǔ)管理的主要優(yōu)缺點(diǎn) 優(yōu)點(diǎn) ： 有效地 解決 了固定式分區(qū)的 內(nèi)部碎片 問(wèn)題 ， 較有效地利用主存空間 ， 提高了多個(gè)作業(yè)或進(jìn)程對(duì)內(nèi)存的共享 。 59 課堂練習(xí) P123124： 912 60 純 分頁(yè)存儲(chǔ)管理 ★ 目前已討論了單道存儲(chǔ)管理和分區(qū)式存儲(chǔ)管理方法 。 ★ 再者 ， 分區(qū)式管理時(shí) ， 由于各作業(yè)或進(jìn)程對(duì)應(yīng)于不同的分區(qū)以及在分區(qū)內(nèi)各作業(yè)或進(jìn)程連續(xù)存放 ， 進(jìn)程的大小仍受分區(qū)大小或內(nèi)存可用空間的 限制 。 61 ★ 頁(yè)式 管理正是為了 減少碎片 ， 以及為了只在內(nèi)存存放那些反復(fù)執(zhí)行或即將執(zhí)行的程序段與數(shù)據(jù)部分 ， 而把那些不經(jīng)常執(zhí)行的程序段和數(shù)據(jù)存放在外存待執(zhí)行時(shí)調(diào)入 ， 以提高內(nèi)存利用率 而提出來(lái)的 。 ★ 內(nèi)存的所有物理塊從 0開(kāi)始編號(hào) ， 稱作 物理塊號(hào) 或 內(nèi)存塊號(hào) 。 物理塊 0 物理塊 1 物理塊 2 …… 63 ★ 系統(tǒng)將用戶程序的 邏輯空間 按照 同樣大小 也劃分成若干頁(yè)面 ， 稱為 邏輯頁(yè)面 ， 有時(shí)也簡(jiǎn)稱為 頁(yè) 。 2. 邏輯地址空間劃分 頁(yè) 0 頁(yè) 1 頁(yè) 2 …… 64 ★ 對(duì)用戶程序地址空間的分頁(yè)是 系統(tǒng) 自動(dòng)進(jìn)行的 ， 即對(duì)用戶是 透明 的 。 ★ 例如 ， 圖 ， 機(jī)器地址長(zhǎng)為 20位 ， 若頁(yè)面長(zhǎng)度為 210， 則地址的 10～ 19位表示頁(yè)號(hào) ， 最多擁有 210 =1024個(gè) 邏輯頁(yè) ， 0～ 9位表示頁(yè)內(nèi)地址 ， 即頁(yè)長(zhǎng)為 210 =1K。 3. 頁(yè)面大小 ★ 頁(yè)面尺寸一般取 2的整數(shù)次冪 ，如 29， 210， 211等。 4. 內(nèi)存分配 頁(yè) 0 頁(yè) 1 頁(yè) 2 物理塊 0 物理塊 1 物理塊 2 物理塊 3 物理塊 4 物理塊 5 物理塊 6 物理塊 7 物理塊 8 …… 邏輯空間 內(nèi)存空間 67 ★ 如果把一個(gè)作業(yè)的所有頁(yè)面 一次全部裝入 到內(nèi)存塊中 ，就把這種分頁(yè)稱之為 純分頁(yè) 存儲(chǔ)管理 。 ★ 本節(jié) 先討論 純 分頁(yè)存儲(chǔ)管理 。 ★ 用戶程序的地址空間有多少頁(yè) ， 該頁(yè)表里就登記多少行 ，且按邏輯頁(yè)的 順序排列 。 頁(yè)號(hào) 塊號(hào) 0 2 1 6 2 8 圖 頁(yè)表示意圖 69 2. 建立空閑頁(yè)面表 系統(tǒng) 中設(shè)立 一張 內(nèi)存空閑頁(yè)面表 ， 記錄內(nèi)存物理頁(yè)面空閑情況 ， 用于內(nèi)存分配和回收 。 （ 1） 頁(yè)表始址寄存器 ★ 用于保存 正在運(yùn)行 進(jìn)程的頁(yè)表在內(nèi)存的 首地址 。 （ 2） 頁(yè)表長(zhǎng)度寄存器 ★ 用于保存 正在運(yùn)行 進(jìn)程的 頁(yè)表的長(zhǎng)度 。 4. 硬件支持 72 5. 地址映射 8644 頁(yè)號(hào) 0 1 2 頁(yè)表始址寄存器 頁(yè)表長(zhǎng)度寄存器 H L ＋ ＜ 邏輯地址 頁(yè)號(hào) 2 頁(yè)內(nèi)地址 452 塊號(hào) 2 6 8 8 452 LOAD 1,2500 12345 內(nèi)存 2148 頁(yè)號(hào) ≥L 越界 物理地址 圖 頁(yè)式存儲(chǔ)管理的地址映射 頁(yè)表 73 具體步驟說(shuō)明如下： （ 1） 地址映射機(jī)構(gòu)把 CPU給出的 邏輯地址分為兩部分 ， 如執(zhí)行指令 LOAD 1， 2500時(shí) ， 邏輯地址 2500＝ 2 1024＋ 452，因此頁(yè)號(hào) p＝ 2， 頁(yè)內(nèi)地址 d＝ 452。 74 （ 3） 根據(jù)頁(yè)表始址得到頁(yè)表在內(nèi)存的首地址 ， 并根據(jù)邏輯頁(yè)號(hào) p在頁(yè)表中找到對(duì)應(yīng)的物理頁(yè)號(hào) 。 （ 4） 把 物理頁(yè)號(hào)與邏輯地址中的頁(yè)內(nèi)地址 d拼在一起 ，形 成 訪 問(wèn) 內(nèi) 存 的 物 理 地 址 。 75 快表 從地址映射過(guò)程中可以看出 ， 共需 兩次 訪問(wèn)內(nèi)存： ★ 第一次 訪問(wèn)頁(yè)表 ， 得到數(shù)據(jù)的物理地址 。 ?增加了訪問(wèn)時(shí)間 。 ★ 一般稱這樣的寄存器組為 快表 或 聯(lián)想存儲(chǔ)器 。 77 具有快表的地址映射過(guò)程： 當(dāng)處理機(jī)給出邏輯地址 （ p， w） 時(shí) ， 分頁(yè)機(jī)構(gòu) : ★ 一方面 取出頁(yè)號(hào) p， 并根據(jù) p從 頁(yè)表中查找 相應(yīng)的內(nèi)存塊號(hào) b； ★ 另一方面 自動(dòng)把頁(yè)號(hào) p送入快表 ， 并和快表各單元進(jìn)行比較 ， 78 如 與某單元頁(yè)號(hào) 相符 ， 則 ★ 輸出對(duì)應(yīng)塊號(hào) b ， 并與頁(yè)內(nèi)地址 w形成物理地址進(jìn)行訪問(wèn) ， ★ 停止查找頁(yè)表的工作 ， ★ 由于快表采用的是高速緩存 ， 其訪問(wèn)速度比訪問(wèn)頁(yè)表要快得多 。 79 物理地址 頁(yè)表 頁(yè)號(hào) 塊號(hào) p b 邏輯地址 p w 聯(lián)想存儲(chǔ)器 頁(yè)號(hào) 塊號(hào) p b a + b w 頁(yè)表始址寄存器 ① 利用快表查找 ② 利用頁(yè)表查找 ③利用頁(yè)表中查找到的頁(yè)號(hào)、塊號(hào)更新快表 圖 采用快表和頁(yè)表相結(jié)合的分頁(yè)地址變換過(guò)程示意圖 1 2 2 3 1 物理地址頁(yè)表頁(yè)號(hào) 塊號(hào)邏輯地址聯(lián)想存儲(chǔ)器頁(yè)號(hào) 塊號(hào)頁(yè)表始址寄存器① 利用快表查找 ② 利用頁(yè)表查找③利用頁(yè)表中查找到的頁(yè)號(hào)、塊號(hào)更新快表圖 采用快表和頁(yè)表相結(jié)合的分頁(yè)地址變換過(guò)程示意圖80 存儲(chǔ)保護(hù) 頁(yè)式管理可以為內(nèi)存提供 兩種 方式的保護(hù) : ★ 地址越界保護(hù)： 可由地址變換機(jī)構(gòu)中的控制寄存器的值（ 頁(yè)表長(zhǎng)度 ） ， 和所要訪問(wèn)的 邏輯地址 相 比較 完成 。 即：在 頁(yè)表中增加相應(yīng)的保護(hù)位 即可 。 ★ 缺點(diǎn) ：采用動(dòng)態(tài)地址變換機(jī)制 ， 既增加硬件成本也降低了處理機(jī)速度 。 ★ 一般情況下 ， 用戶 希望： 按邏輯關(guān)系對(duì)作業(yè)分段 ，并能根據(jù)名字來(lái)訪問(wèn)程序段和數(shù)據(jù)段 。 84 1. 基本原理 ★ 內(nèi)存 空間被 動(dòng)態(tài) 地 劃分 為 若干 個(gè) 長(zhǎng)度不相同 的區(qū)域 ，每個(gè)區(qū)域稱作一個(gè) 物理段 。 ★ 將物理 段中 的所有單元從 0開(kāi)始 依次編址 。 ★ 例如：主程序 、 子程序 、 數(shù)據(jù)等可各成一段 ， 每段對(duì)應(yīng)于一個(gè)過(guò)程 、 一個(gè)程序模塊或一個(gè)數(shù)據(jù)集合 。 ★ 整個(gè)地址空間就構(gòu)成了 二維地址空間 。 物理段 0 …… 物理段 1 物理段 2 …… 邏輯段 0 邏輯段 1 邏輯段 2 87 實(shí)現(xiàn)方法 1. 建立段表 ★ 系統(tǒng)為 每個(gè)用戶程序 建立 一張 段表 ， 用于記錄用戶程序的 邏輯段 與內(nèi)存 物理段 之間的 對(duì)應(yīng)關(guān)系 ， 包括 邏輯段號(hào) ，內(nèi)存首地址 和 物理段長(zhǎng)度 三項(xiàng)內(nèi)容 。 ★ 段表存放在 內(nèi)存系統(tǒng)區(qū)