【正文】 022/8/17 第六章 存儲(chǔ)管理 頁大小的選擇 ? 太大：浪費(fèi)；太?。喉摫磉^長 。 ? 占用處理機(jī)的現(xiàn)行進(jìn)程的頁表必須駐留在內(nèi)存 ， 其首地址和長度由地址映射機(jī)構(gòu)的 頁表起址和長度寄存器 指示 。一般，一頁的大小為 2的整數(shù)次冪，因此，地址的高位部分為 頁號(hào) ，低位部分為 頁內(nèi)地址 頁號(hào) 頁內(nèi)地址 0 11 12 31 頁號(hào) P 頁內(nèi)位移量 W 編號(hào) 0~1048575 相對(duì)地址 0~4095 66 2022/8/17 第六章 存儲(chǔ)管理 ? 內(nèi)存空間 按頁的大小劃分為大小相等的區(qū)域，稱為 塊或內(nèi)存塊（物理頁面，頁框） 67 2022/8/17 第六章 存儲(chǔ)管理 ? 內(nèi)存分配 以頁為單位進(jìn)行分配，并按作業(yè)的頁數(shù)多少來分配。 ? 分頁技術(shù)是由曼徹斯特大學(xué)提出 ， 并于 1960年前后在 Atlas計(jì)算機(jī)上實(shí)現(xiàn) 。 61 2022/8/17 第六章 存儲(chǔ)管理 在分區(qū)存儲(chǔ)管理中解決碎片的辦法 ? 規(guī)定門限值 （ 由操作系統(tǒng)規(guī)定 ， 如 1K） ， 分割空閑區(qū)時(shí) ， 若剩余部分小于門限值 ， 則不再分割此空閑區(qū) 。 59 2022/8/17 第六章 存儲(chǔ)管理 練習(xí) ? 有作業(yè)序列：作業(yè) A要求 21K； 作業(yè) B要求 30K， 作業(yè)C要求 25K。 ? 對(duì)于某一作業(yè)序列來說 ， 某種算法能將該作業(yè)序列中所有作業(yè)安置完畢 ， 那么我們說 該算法對(duì)這一作業(yè)序列是合適的 。 ? 分配和回收后要對(duì)空閑區(qū)表 （ 隊(duì)列 ） 重新排序 。 53 2022/8/17 第六章 存儲(chǔ)管理 最壞適應(yīng)法 ? 要求空閑區(qū)按 大小遞減 的順序組織空閑區(qū)表（或隊(duì)列）。 52 2022/8/17 第六章 存儲(chǔ)管理 分析 優(yōu)點(diǎn)： ? 在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū) ，必定會(huì)被選中 ， 而首次適應(yīng)法則不一定 。 50 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)一個(gè)存儲(chǔ)區(qū)時(shí)，系統(tǒng)從表頭開始查找，當(dāng)找到第一個(gè)滿足要求的空閑區(qū)時(shí)，停止查找，并且這個(gè)空閑區(qū)是最佳的空閑區(qū)。 48 2022/8/17 第六章 存儲(chǔ)管理 分析 ? 注意：每次分配和回收后空閑區(qū)表或空閑區(qū)隊(duì)列都要按首址遞增的次序排序。 43 2022/8/17 第六章 存儲(chǔ)管理 三種放置策略 ? 空閑區(qū)表或隊(duì)列的排序 ? 首次適應(yīng)法 ? 最佳適應(yīng)法 ? 最壞適應(yīng)法 ? 三種策略比較 44 2022/8/17 第六章 存儲(chǔ)管理 空閑區(qū)表或隊(duì)列的排序 ? 按空閑區(qū) 首址 遞增的次序歸類組織空閑區(qū)表或空閑區(qū)隊(duì)列 ? 按空閑區(qū) 大小 的遞增或遞減次序組織空閑區(qū)表或隊(duì)列 45 2022/8/17 第六章 存儲(chǔ)管理 首次適應(yīng)法 ? 要求空閑區(qū)按 首址遞增 的次序組織空閑區(qū)表（隊(duì)列）。 其首址仍為前空閑區(qū)首址 ， 大小為釋放區(qū)大小與空閑區(qū)大小之和 。 將一個(gè)空閑區(qū)分成二部分有兩種辦法： 一是從空閑區(qū)的上部開始劃出 SIZE大小的空閑區(qū)給用戶； 二是從空閑區(qū)的底部開始向上劃出 SIZE大小的空閑區(qū)給用戶 。 以空閑區(qū)表為例 ， 當(dāng)用戶要求一個(gè)大小為 SIZE的存儲(chǔ)空間時(shí) ， 系統(tǒng)查詢空閑區(qū)表 ， 找一個(gè)大于或等于SIZE的空閑區(qū) 。 ? 系統(tǒng)還要設(shè)置了 等待分區(qū)隊(duì)列 ， 當(dāng)系統(tǒng)中無空閑區(qū)或無滿足要求的空閑區(qū)時(shí) ， 則把申請(qǐng)者送入等待隊(duì)列中 ， 等待別的進(jìn)程釋放內(nèi)存之后再喚醒隊(duì)列中的進(jìn)程 。 是一種較為實(shí)用的存儲(chǔ)管理方法 。 在這種情況下分區(qū)的大小選擇與作業(yè)大小相當(dāng) ， 這樣內(nèi)存的使用效率較高 。 分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出 ， 并給出 分區(qū)說明表 。 ? 由于程序在執(zhí)行時(shí) ， 在一段時(shí)間內(nèi)一般僅使用它的程序的一部分 （ 或一小部分 ） ， 所以程序僅有部分裝入內(nèi)存完全能夠正確執(zhí)行 。 這種面向編程的存儲(chǔ)器稱為 虛擬存儲(chǔ)器 。 由于內(nèi)存有限 ，系統(tǒng)中不可能容納所有進(jìn)程 ， 有些進(jìn)程的映像可以存放在外存 ， 當(dāng)要運(yùn)行這些進(jìn)程時(shí) ， 必須把它們調(diào)入內(nèi)存 。 20 2022/8/17 第六章 存儲(chǔ)管理 引起內(nèi)存分配和回收的原因 ? 進(jìn)程的開始的結(jié)束 。 ? 目前有請(qǐng)調(diào)和預(yù)調(diào)兩種 17 2022/8/17 第六章 存儲(chǔ)管理 放置策略 ? 用戶程序調(diào)入內(nèi)存時(shí) ， 確定將其放置在何處的策略 。 ? 便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼 。 ? 地址轉(zhuǎn)換機(jī)構(gòu)把 VR和 BR中的內(nèi)容相加，并將結(jié)果送入 MR中，作為實(shí)際訪問的地址。 11 2022/8/17 第六章 存儲(chǔ)管理 映射方法 ? 最簡單的硬件機(jī)構(gòu) 是重定位寄存器 。 ? 例如，程序裝入內(nèi)存的首地址為 1000，則裝配程序就按 MR=1000+VR對(duì)程序中所有地址部分進(jìn)行修改，修改后指令 Load A， 200就變?yōu)?Load A， 1200 9 2022/8/17 第六章 存儲(chǔ)管理 優(yōu)缺點(diǎn) ? 優(yōu)點(diǎn)：不需要硬件的支持。 。 ? 內(nèi)存地址的集合稱為 內(nèi)存空間（或物理地址空間） 。 4 2022/8/17 第六章 存儲(chǔ)管理 ? 要求用戶用內(nèi)存地址編程是非常困難的，尤其是在多道程序設(shè)計(jì)的環(huán)境中。 1200 物理地址空間 Load A data1 data1 3456 源程序 Load A 200 3456 0 100 200 編譯 連接 邏輯地址空間 BA=1000 6 2022/8/17 第六章 存儲(chǔ)管理 地址映射的方式 ? 我們把 用戶程序裝入內(nèi)存時(shí)對(duì)有關(guān)指令的地址部分的修改定義為從程序地址到內(nèi)存地址的 地址映射 ，或稱為 地址重定位 。 ? 缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間；一旦程序裝入后不能移動(dòng)。 ? 在地址重定位機(jī)構(gòu)中 ， 有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器 VR， 一個(gè)內(nèi)存地址寄存器 MR。 14 2022/8/17 第六章 存儲(chǔ)管理 動(dòng)態(tài)地址映射的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： ? 程序占用的內(nèi)存空間是動(dòng)態(tài)可變的 ， 當(dāng)程序從某個(gè)存儲(chǔ)區(qū)移到另一個(gè)區(qū)域時(shí) ， 只需要修改相應(yīng)的寄存器 BR的內(nèi)容即可 。 動(dòng)態(tài)地址重定位的代價(jià)： ? 需要硬件的支持 。 18 2022/8/17 第六章 存儲(chǔ)管理 置換策略 ? 當(dāng)需要將某個(gè)用戶程序調(diào)入內(nèi)存而內(nèi)存空間又不夠時(shí) ， 就要確定哪個(gè)或哪些程序可以從內(nèi)存中移走 。 ? 進(jìn)程運(yùn)行的過程中 ， 它所占用的內(nèi)存也可能發(fā)生變化 。 ? 系統(tǒng)為了充分利用內(nèi)存空間，有時(shí)可能對(duì)內(nèi)存空間進(jìn)行調(diào)整。 由虛存構(gòu)成的存儲(chǔ)空間稱為虛存空間 。 ? 要由操作系統(tǒng)結(jié)合相關(guān)硬件來完成上述工件，這樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為 虛擬存儲(chǔ)器 。 ? 早期的 IBM的 OS/360MFT（ 具有固定任務(wù)數(shù)的多道程序系統(tǒng) ） 采用了這種固定分區(qū)的方法 。 ? 但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí) ， 勢(shì)必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn) ， 這樣就會(huì)造成存儲(chǔ)空間的浪費(fèi) ， 從而影響整個(gè)系統(tǒng)的效率 。 35 2022/8/17 第六章 存儲(chǔ)管理 實(shí)現(xiàn)動(dòng)態(tài)分區(qū)需要的數(shù)據(jù)結(jié)構(gòu) ? 在動(dòng)態(tài)分區(qū)存儲(chǔ)管理中 ， 要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來登記空閑區(qū)的說明信息 ， 它包括空閑區(qū)的大小和位置 。 36 2022/8/17 第六章 存儲(chǔ)管理 空閑區(qū)表和空閑區(qū)隊(duì)列舉例 37 2022/8/17 第六章 存儲(chǔ)管理 動(dòng)態(tài)分區(qū)的分配和回收 分區(qū)的分配 在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中 ， 系統(tǒng)初啟后 。 38 2022/8/17 第六章 存儲(chǔ)管理 分配時(shí)的三種情況 ? 其一是系統(tǒng)中無滿足要求的空閑區(qū) ， 則分配失敗 。 一般常采用第二種辦法 ， 因?yàn)檫@樣劃分時(shí) ，余下的部分在空閑區(qū)表中的首地址不變 ， 只需要修改一下大小就行了 。 ? 釋放區(qū)與前后兩個(gè)空閑區(qū)相鄰：將這三個(gè)區(qū)合為一個(gè)空閑區(qū) ， 其首址為前空閑區(qū)首址 ， 大小為這三個(gè)區(qū)大小之和 ， 并取消原后空閑區(qū)表目 。 46 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE的內(nèi)存時(shí) ， 系統(tǒng)從空閑區(qū)表的第一個(gè)表目開始查詢 ， 直到首次找到等于或大于 SIZE的空閑區(qū) 。 首次適應(yīng)法的優(yōu)點(diǎn)： ? 釋放某一存儲(chǔ)區(qū)時(shí) ， 若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去 ， 這種情況并不改變?cè)搮^(qū)在表中的位置 ， 只要修改其大小或首址 。 ? 所謂最佳即選中的空閑區(qū)是滿足要求的最小空閑區(qū)。 ? 若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū) ， 則選中的空閑區(qū)是滿足要求的最小空閑區(qū) ， 而不致于毀掉較大的空閑區(qū) 。 54 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：進(jìn)程申請(qǐng)一個(gè)大小為 SIZE的存儲(chǔ)區(qū)時(shí)，總是檢查空閑區(qū)表的第一個(gè)空閑區(qū)的大小是否大于或等于 SIZE。 56 2022/8/17 第六章 存儲(chǔ)管理 分析 最壞適應(yīng)法看起來公似乎有些荒唐 ， 但在更加嚴(yán)密地考察后 ， 還是有它的優(yōu)點(diǎn)： ? 當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后 ， 剩下的空閑區(qū)還可能相當(dāng)大 ， 還能裝下較大的程序 。 ? 對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則 這一算法對(duì)該作業(yè)序列是不合適的 。 60 2022/8/17 第六章 存儲(chǔ)管理 碎片問題 ? 由于空閑區(qū)的大小與申請(qǐng)內(nèi)存的大小相等的情況是很少的 ， 絕大多數(shù)情況是從一個(gè)空閑區(qū)中切去一塊 ， 剩下的部分作為一個(gè)空閑區(qū)仍留在空閑區(qū)表中 ， 隨著時(shí)間的推移 ， 空閑區(qū)的發(fā)展趨勢(shì)是越來越小 ， 直至不能滿足任何用戶要求 。 ? 定期壓縮存儲(chǔ)空間，將所有空閑區(qū)集中到內(nèi)存的一端，但這種方法的系統(tǒng)開銷太大。 這種技術(shù)對(duì)操作系統(tǒng)的發(fā)展產(chǎn)生了深遠(yuǎn)影響 。邏輯上相鄰的頁，物理上不一定相鄰 68 2022/8/17 第六章 存儲(chǔ)管理 . . . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 作業(yè)的 地址空間 頁框 （物理塊） 頁號(hào) 頁表 主存中頁框（物理塊） . . . . 69 2022/8/17 第六章 存儲(chǔ)管理 頁地址映射 ? 頁表 ? 頁大小的選擇 ? 頁地址映射 ? 分頁存儲(chǔ)管理中的信息保護(hù) ? 快表和聯(lián)想存儲(chǔ)器 ? 兩級(jí)頁表和多級(jí)頁表 70 2022/8/17 第六章 存儲(chǔ)管理 頁表 ? 將頁號(hào)和頁內(nèi)地址轉(zhuǎn)換成內(nèi)存地址 ， 必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu) ， 用來登記頁號(hào)和塊的對(duì)應(yīng)關(guān)系和有關(guān)信息 。 72 2022/8/17 第六章 存儲(chǔ)管理 頁表內(nèi)容 ? 頁表包含以下幾個(gè)表項(xiàng)： ? 頁號(hào)：登記程序地址空間的頁號(hào) 。 ? IBM AS/400 VAX NS32032 ： 512字節(jié) ? Intel 80386 Motorola 68030 4096字節(jié) 頁的大小是 2K ， k： 912。 77 2022/8/17 第六章 存儲(chǔ)管理 說明 ? 在執(zhí)行指令 MOV r1， [2500]時(shí) ， 地址轉(zhuǎn)換步驟如下： ? 取出程序地址字 250