【正文】 高地址空間有較大的空閑區(qū)。 50 2022/8/17 第六章 存儲管理 ? 分配：當進程申請一個存儲區(qū)時，系統(tǒng)從表頭開始查找，當找到第一個滿足要求的空閑區(qū)時，停止查找，并且這個空閑區(qū)是最佳的空閑區(qū)。 51 2022/8/17 第六章 存儲管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 （ 隊列 ） ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ， 把釋放區(qū)作為一個空閑區(qū)插入空閑區(qū)表 （ 隊列 ） 。 52 2022/8/17 第六章 存儲管理 分析 優(yōu)點： ? 在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū) ，必定會被選中 ， 而首次適應(yīng)法則不一定 。 缺點： ? 空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。 53 2022/8/17 第六章 存儲管理 最壞適應(yīng)法 ? 要求空閑區(qū)按 大小遞減 的順序組織空閑區(qū)表（或隊列）。 若空閑區(qū)小于 SIZE， 則分配失??；否則從空閑區(qū)中分配 SIZE的存儲區(qū)給用戶，然后修改和調(diào)整空閑區(qū)表。 ? 分配和回收后要對空閑區(qū)表 （ 隊列 ） 重新排序 。 ? 另一方面每次僅作一次查詢工作。 ? 對于某一作業(yè)序列來說 ， 某種算法能將該作業(yè)序列中所有作業(yè)安置完畢 ， 那么我們說 該算法對這一作業(yè)序列是合適的 。 58 2022/8/17 第六章 存儲管理 舉例 ? 例 1：有作業(yè)序列：作業(yè) A要求 18K； 作業(yè) B要求 25K， 作業(yè)C要求 30K。 59 2022/8/17 第六章 存儲管理 練習 ? 有作業(yè)序列：作業(yè) A要求 21K； 作業(yè) B要求 30K， 作業(yè)C要求 25K。 ? 這種不能被任何用戶使用的極小的空閑區(qū)稱為 碎片 。 61 2022/8/17 第六章 存儲管理 在分區(qū)存儲管理中解決碎片的辦法 ? 規(guī)定門限值 （ 由操作系統(tǒng)規(guī)定 ， 如 1K） ， 分割空閑區(qū)時 ， 若剩余部分小于門限值 ， 則不再分割此空閑區(qū) 。 62 2022/8/17 第六章 存儲管理 分頁存儲管理 ? 分頁存儲管理基本思想 ? 頁地址映射 ? 頁式存儲管理方案小結(jié) 63 2022/8/17 第六章 存儲管理 分頁存儲管理基本思想 ? 在分區(qū)存儲管理中 ， 不論采用什么辦法都會出現(xiàn)碎片問題 ， 從而降低了內(nèi)存的利用率 。 ? 分頁技術(shù)是由曼徹斯特大學提出 ， 并于 1960年前后在 Atlas計算機上實現(xiàn) 。 64 2022/8/17 第六章 存儲管理 ? 用戶程序劃分 把用戶程序按邏輯頁劃分成大小相等的部分 ， 稱為 頁 （ page） 。一般，一頁的大小為 2的整數(shù)次冪，因此，地址的高位部分為 頁號 ，低位部分為 頁內(nèi)地址 頁號 頁內(nèi)地址 0 11 12 31 頁號 P 頁內(nèi)位移量 W 編號 0~1048575 相對地址 0~4095 66 2022/8/17 第六章 存儲管理 ? 內(nèi)存空間 按頁的大小劃分為大小相等的區(qū)域，稱為 塊或內(nèi)存塊（物理頁面，頁框） 67 2022/8/17 第六章 存儲管理 ? 內(nèi)存分配 以頁為單位進行分配，并按作業(yè)的頁數(shù)多少來分配。 ? 這樣的數(shù)據(jù)結(jié)構(gòu)稱為 頁表 。 ? 占用處理機的現(xiàn)行進程的頁表必須駐留在內(nèi)存 ， 其首地址和長度由地址映射機構(gòu)的 頁表起址和長度寄存器 指示 。 ? 塊號：登記相應(yīng)的頁所對應(yīng)的內(nèi)存塊號 ? 其它：登記與存儲信息保護有關(guān)的信息 。 74 2022/8/17 第六章 存儲管理 頁大小的選擇 ? 太大：浪費；太?。喉摫磉^長 。 75 2022/8/17 第六章 存儲管理 頁地址映射 ? 分頁中的地址映射其實與通常的地址映射的概念是一樣的 ， 即把 程序地址轉(zhuǎn)換成內(nèi)存地址 ， 這個轉(zhuǎn)換過程是在程序執(zhí)行過程中完成的 ， 是 動態(tài)地址映射 。 76 2022/8/17 第六章 存儲管理 例 ? 設(shè)頁長為 1K， 程序地址字長為 16位 ， 用戶程序空間和頁表如圖 。 ? 當然我們通過計算可以得到 P=2， W=452。 ? 將 VR中的 W的值 452復(fù)制到 MR的低 10位中 ， 從而形成內(nèi)存地址 。 79 2022/8/17 第六章 存儲管理 計算時要注意： 若給出的地址字為 16進制 ， 則將其轉(zhuǎn)換為二進制 ， 然后 ， 根據(jù)頁長及程序地址字的長度 ，分別取出程序地址字的高幾位和低幾位就得到頁號及頁內(nèi)地址 。 80 2022/8/17 第六章 存儲管理 若給出的地址字為 10進制 ， 則用公式： 程序地址字 /頁長 商為頁號 ， 余數(shù)為頁內(nèi)地址 。 81 2022/8/17 第六章 存儲管理 分頁存儲管理中的信息保護 分頁存儲管理中的存儲信息保護從兩個方面來實現(xiàn) 。 82 2022/8/17 第六章 存儲管理 二 、 在頁表中增加用于存取控制和存儲保護的信息 ， 當要訪問某頁時系統(tǒng)要根據(jù)該頁的存取控制和存儲保護信息檢查訪問是否合法 。 ? 若不解決這一問題是不能令人忍受的 。 我們把這種快速存儲器組成的頁表稱為 快表 ， 把存放在內(nèi)存中的頁表稱為慢表 。 ? 快速存儲器是非常非常昂貴的。 ? 硬件根據(jù)需要將頁表中當前需要的少量表目讀入快表 ， 其它表目仍留在內(nèi)存的頁表中 ， 當需要時讀入新的表目 ， 并淘汰適當?shù)谋砟?。也就是說訪問頁表的速度大致相當了訪問快表的速度，考慮到快表的速度是內(nèi)存速度的數(shù)倍或數(shù)十倍，那么相對于內(nèi)存速度，訪問頁表的時間可以忽略不計。 89 2022/8/17 第六章 存儲管理 兩級頁表和多級頁表 ? 當頁表項很多時 ， 僅采用一級頁表需要大片邊續(xù)空間 ， 可將頁表也分頁 ， 并對頁表所占的空間進行索引形成外層頁表 。 ? 更進一步可形成多級頁表。段號從 0開始，每一段段內(nèi)也從 0開始編址，段內(nèi)地址是連續(xù)的 ? 邏輯地址 段號 段內(nèi)地址 95 2022/8/17 第六章 存儲管理 ? 內(nèi)存劃分 內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定 ? 內(nèi)存分配 以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少）， 但各段之間可以不連續(xù)存放 96 2022/8/17 第六章 存儲管理 . . . 0 S 工作區(qū)段 [B] 主程序段 [M] . . . . . . 0 E P 子程序段 [X] 0 K . . . CALL [X] [E] . . . . . . . . . CALL [Y] [F] CALL [A] 116 . . . . . . 0 F L 子程序段 [Y] 0 116 N 數(shù)組 [A] 12345 . . . 97 2022/8/17 第六章 存儲管理 操作系統(tǒng) . . . . . B 0 S A 0 N Y 0 L X 0 P M 0 K 邏輯段號 0 1 2 3 4 作業(yè) 1的地址空間 1000 3200 5000 6000 8000 P K S L N 主存 K 3200 P 1500 L 6000 N 8000 S 5000 段號 段地址 0 1 2 3 4 操作系統(tǒng) 98 2022/8/17 第六章 存儲管理 段地址映射 地址映射數(shù)據(jù)結(jié)構(gòu) 段地址映射的數(shù)據(jù)結(jié)構(gòu)有 段表 、 段表首址指針和段表的長度 。 段表一般包括有段的長度 、 段的首址和存取狀態(tài)等信息 。 段號 0 1 2 段首址 段長度 58K 20K 100K 110K 260K 140K 99 2022/8/17 第六章 存儲管理 內(nèi)存的分配 ? 空閑塊管理 空閑塊表（隊列） ? 內(nèi)存分配算法（三種） 首次 最佳 最壞 與動態(tài)分區(qū)管理相同 100 2022/8/17 第六章 存儲管理 段地址變換 段地址變換由硬件地址變換機構(gòu)完成 101 2022/8/17 第六章 存儲管理 說明 段地址映射過程為： ? 程序地址字送入虛地址寄存器 VR中 。 ? 根據(jù)段表首址指針找到段表 ， 查找段號為 S的表目 ， 得到該段的首地址 。 102 2022/8/17 第六章 存儲管理 快表 ? 同頁地址變換一樣 ， 在段地址變換過程中 ，也有兩次訪問內(nèi)存的問題 。 103 2022/8/17 第六章 存儲管理 Cl Cb + 段號 S 段內(nèi)地址 d 比較 比較 b + d 段 表 S= Cl 快表 物理地址 段表始址寄存器 段表長度寄存器 邏輯地址 L b . . . S L b 地址越界 d=L d=L 地址映射及存儲保護機制 地址越界 地址越界 比較 104 2022/8/17 第六章 存儲管理 分段與分頁技術(shù)的比較 分段與分頁主要有以下差別： ? 段是依據(jù)程序的邏輯結(jié)構(gòu)劃分的 ， 頁是按內(nèi)存線性空間物理劃分的 。 ? 段是面向用戶的 ， 頁對用戶而言是透明的 。面頁長是由系統(tǒng)決定的，各頁的長度必須相等。 106 2022/8/17 第六章 存儲管理 段式存儲管理方案小結(jié) 優(yōu)點： 便于動態(tài)申請內(nèi)存 管理和使用統(tǒng)一化 便于共享 便于動態(tài)鏈接 缺點：產(chǎn)生碎片 思考：與可變分區(qū)存儲管理方案的相同點與不同點？ 107 2022/8/17 第六章 存儲管理 段頁式存儲管理方式 產(chǎn)生背景 : 結(jié)合頁式段式優(yōu)點，克服二者的缺點 ? 段頁式存儲管理基本思想 ? 地址映射 108 2022/8/17 第六章 存儲管理 段頁式存儲管理基本思想 ? 用戶程序劃分 按段式劃分（對用戶來講，按段的邏輯關(guān)系進行劃分；對系統(tǒng)講，按頁劃分每一段） ? 邏輯地址 ? 內(nèi)存劃分 按頁式存儲管理方案 ? 內(nèi)存分配 以頁為單位進行分配 段號 段內(nèi)地址 頁號 頁內(nèi)地址 109 2022/8/17 第六章 存儲管理 ? 段表：記錄了每一段的頁表始址和頁表長度 ? 頁表：記錄了邏輯頁號與內(nèi)存塊號的對應(yīng)關(guān)系（每一段有一個，一個程序可能有多個頁表） ? 內(nèi)存分配管理：同頁式管理 地址映射 110 2022/8/17 第六章 存儲管理 圖示 111 2022/8/17 第六章 存儲管理 思考 ? 在具有快表的段頁式存儲管理方案中，如何實現(xiàn)地址變換？ 112 2022/8/17 第六章 存儲管理 覆蓋技術(shù)與交換技術(shù) 、為什么引入？ 在多道環(huán)境下擴充內(nèi)存的方法，用以解決在較小的存儲空間中運行較大程序時遇到的矛