【正文】 則分配失敗 。 ? 其二是空閑區(qū)大小與 SIZE相等 ， 則修改空閑區(qū)表相應(yīng)表目 ， 向用戶返回該空閑區(qū)首址 ，表示此空閑區(qū)已分給了要求的用戶 。 39 2022/8/17 第六章 存儲(chǔ)管理 ? 其三是空閑區(qū)大于 SIZE， 這時(shí)將空閑區(qū)一分為二 。 將一個(gè)空閑區(qū)分成二部分有兩種辦法： 一是從空閑區(qū)的上部開(kāi)始劃出 SIZE大小的空閑區(qū)給用戶； 二是從空閑區(qū)的底部開(kāi)始向上劃出 SIZE大小的空閑區(qū)給用戶 。 一般常采用第二種辦法 ， 因?yàn)檫@樣劃分時(shí) ，余下的部分在空閑區(qū)表中的首地址不變 ， 只需要修改一下大小就行了 。 40 2022/8/17 第六章 存儲(chǔ)管理 分區(qū)的回收 當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí) ， 系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰 ， 若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去 ， 否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置 。 41 2022/8/17 第六章 存儲(chǔ)管理 釋放區(qū)與空閑區(qū)相鄰的四種情況 42 2022/8/17 第六章 存儲(chǔ)管理 說(shuō)明 ? 釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū) 。 其首址仍為前空閑區(qū)首址 ， 大小為釋放區(qū)大小與空閑區(qū)大小之和 。 ? 釋放區(qū)與前后兩個(gè)空閑區(qū)相鄰：將這三個(gè)區(qū)合為一個(gè)空閑區(qū) ， 其首址為前空閑區(qū)首址 ， 大小為這三個(gè)區(qū)大小之和 ， 并取消原后空閑區(qū)表目 。 ? 釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑 ，首地址為釋放區(qū)首地址 ， 大小為二者大小之和 。 ? 釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置。 43 2022/8/17 第六章 存儲(chǔ)管理 三種放置策略 ? 空閑區(qū)表或隊(duì)列的排序 ? 首次適應(yīng)法 ? 最佳適應(yīng)法 ? 最壞適應(yīng)法 ? 三種策略比較 44 2022/8/17 第六章 存儲(chǔ)管理 空閑區(qū)表或隊(duì)列的排序 ? 按空閑區(qū) 首址 遞增的次序歸類(lèi)組織空閑區(qū)表或空閑區(qū)隊(duì)列 ? 按空閑區(qū) 大小 的遞增或遞減次序組織空閑區(qū)表或隊(duì)列 45 2022/8/17 第六章 存儲(chǔ)管理 首次適應(yīng)法 ? 要求空閑區(qū)按 首址遞增 的次序組織空閑區(qū)表（隊(duì)列）。 46 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE的內(nèi)存時(shí) ， 系統(tǒng)從空閑區(qū)表的第一個(gè)表目開(kāi)始查詢 ， 直到首次找到等于或大于 SIZE的空閑區(qū) 。 從該區(qū)中劃出大小為 SIZE的分區(qū)分配給進(jìn)程 ， 余下的部分仍作為一個(gè)空閑區(qū)留在空閑區(qū)表中 ，但要修改其首址和大小 。 47 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ，把釋放區(qū)作為一個(gè)空閑區(qū) ， 將其大小和首址按照首地址大小遞增 的順序插入到空閑區(qū)表的適當(dāng)位置 。 48 2022/8/17 第六章 存儲(chǔ)管理 分析 ? 注意：每次分配和回收后空閑區(qū)表或空閑區(qū)隊(duì)列都要按首址遞增的次序排序。 首次適應(yīng)法的優(yōu)點(diǎn)： ? 釋放某一存儲(chǔ)區(qū)時(shí) ， 若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去 ， 這種情況并不改變?cè)搮^(qū)在表中的位置 ， 只要修改其大小或首址 。 ? 這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。 49 2022/8/17 第六章 存儲(chǔ)管理 最佳適應(yīng)法 ? 要求按 空閑區(qū)大小從小到大 的次序組成空閑區(qū)表（隊(duì)列）。 50 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)一個(gè)存儲(chǔ)區(qū)時(shí)，系統(tǒng)從表頭開(kāi)始查找，當(dāng)找到第一個(gè)滿足要求的空閑區(qū)時(shí)，停止查找，并且這個(gè)空閑區(qū)是最佳的空閑區(qū)。 ? 所謂最佳即選中的空閑區(qū)是滿足要求的最小空閑區(qū)。 51 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 （ 隊(duì)列 ） ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ， 把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表 （ 隊(duì)列 ） 。 ? 分配和回收后要對(duì)空閑區(qū)表 （ 隊(duì)列 ） 重新排序 。 52 2022/8/17 第六章 存儲(chǔ)管理 分析 優(yōu)點(diǎn)： ? 在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū) ，必定會(huì)被選中 ， 而首次適應(yīng)法則不一定 。 ? 若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū) ， 則選中的空閑區(qū)是滿足要求的最小空閑區(qū) ， 而不致于毀掉較大的空閑區(qū) 。 缺點(diǎn)： ? 空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來(lái)的空閑區(qū)一般情況下是很小的，以致無(wú)法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來(lái)越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。 53 2022/8/17 第六章 存儲(chǔ)管理 最壞適應(yīng)法 ? 要求空閑區(qū)按 大小遞減 的順序組織空閑區(qū)表（或隊(duì)列）。 54 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：進(jìn)程申請(qǐng)一個(gè)大小為 SIZE的存儲(chǔ)區(qū)時(shí)，總是檢查空閑區(qū)表的第一個(gè)空閑區(qū)的大小是否大于或等于 SIZE。 若空閑區(qū)小于 SIZE， 則分配失敗；否則從空閑區(qū)中分配 SIZE的存儲(chǔ)區(qū)給用戶，然后修改和調(diào)整空閑區(qū)表。 55 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 （ 隊(duì)列 ） ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ， 把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表 （ 隊(duì)列 ） 。 ? 分配和回收后要對(duì)空閑區(qū)表 （ 隊(duì)列 ） 重新排序 。 56 2022/8/17 第六章 存儲(chǔ)管理 分析 最壞適應(yīng)法看起來(lái)公似乎有些荒唐 ， 但在更加嚴(yán)密地考察后 ， 還是有它的優(yōu)點(diǎn)： ? 當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后 ， 剩下的空閑區(qū)還可能相當(dāng)大 ， 還能裝下較大的程序 。 ? 另一方面每次僅作一次查詢工作。 57 2022/8/17 第六章 存儲(chǔ)管理 三種策略比較 ? 上述三種放置策略各有利弊 ， 到底哪種最好不能一概而論 ， 而應(yīng)針對(duì)具體作業(yè)序列來(lái)分析 。 ? 對(duì)于某一作業(yè)序列來(lái)說(shuō) ， 某種算法能將該作業(yè)序列中所有作業(yè)安置完畢 ， 那么我們說(shuō) 該算法對(duì)這一作業(yè)序列是合適的 。 ? 對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則 這一算法對(duì)該作業(yè)序列是不合適的 。 58 2022/8/17 第六章 存儲(chǔ)管理 舉例 ? 例 1：有作業(yè)序列：作業(yè) A要求 18K； 作業(yè) B要求 25K， 作業(yè)C要求 30K。 系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列 ? 經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的 ， 而其它兩種對(duì)該作業(yè)序列是不合適的 。 59 2022/8/17 第六章 存儲(chǔ)管理 練習(xí) ? 有作業(yè)序列：作業(yè) A要求 21K； 作業(yè) B要求 30K， 作業(yè)C要求 25K。 60 2022/8/17 第六章 存儲(chǔ)管理 碎片問(wèn)題 ? 由于空閑區(qū)的大小與申請(qǐng)內(nèi)存的大小相等的情況是很少的 ， 絕大多數(shù)情況是從一個(gè)空閑區(qū)中切去一塊 ， 剩下的部分作為一個(gè)空閑區(qū)仍留在空閑區(qū)表中 ， 隨著時(shí)間的推移 ， 空閑區(qū)的發(fā)展趨勢(shì)是越來(lái)越小 ， 直至不能滿足任何用戶要求 。 ? 這種不能被任何用戶使用的極小的空閑區(qū)稱為 碎片 。 碎片的出現(xiàn)造成了存儲(chǔ)空間的浪費(fèi) 。 61 2022/8/17 第六章 存儲(chǔ)管理 在分區(qū)存儲(chǔ)管理中解決碎片的辦法 ? 規(guī)定門(mén)限值 （ 由操作系統(tǒng)規(guī)定 ， 如 1K） ， 分割空閑區(qū)時(shí) ， 若剩余部分小于門(mén)限值 ， 則不再分割此空閑區(qū) 。 ? 定期壓縮存儲(chǔ)空間，將所有空閑區(qū)集中到內(nèi)存的一端，但這種方法的系統(tǒng)開(kāi)銷(xiāo)太大。 62 2022/8/17 第六章 存儲(chǔ)管理 分頁(yè)存儲(chǔ)管理 ? 分頁(yè)存儲(chǔ)管理基本思想 ? 頁(yè)地址映射 ? 頁(yè)式存儲(chǔ)管理方案小結(jié) 63 2022/8/17 第六章 存儲(chǔ)管理 分頁(yè)存儲(chǔ)管理基本思想 ? 在分區(qū)存儲(chǔ)管理中 ， 不論采用什么辦法都會(huì)出現(xiàn)碎片問(wèn)題 ， 從而降低了內(nèi)存的利用率 。雖然采用壓縮存儲(chǔ)區(qū)的方法可以解決碎片問(wèn)題 ， 但系統(tǒng)開(kāi)銷(xiāo)太大 ， 而無(wú)實(shí)用價(jià)值 ， 必須尋求新的技術(shù)來(lái)解決這一問(wèn)題 ， 于是分頁(yè)技術(shù)產(chǎn)生了 。 ? 分頁(yè)技術(shù)是由曼徹斯特大學(xué)提出 ， 并于 1960年前后在 Atlas計(jì)算機(jī)上實(shí)現(xiàn) 。 這種技術(shù)對(duì)操作系統(tǒng)的發(fā)展產(chǎn)生了深遠(yuǎn)影響 。 64 2022/8/17 第六章 存儲(chǔ)管理 ? 用戶程序劃分 把用戶程序按邏輯頁(yè)劃分成大小相等的部分 ， 稱為 頁(yè) （ page） 。 從 0開(kāi)始編制頁(yè)號(hào) ，頁(yè)內(nèi)地址是相對(duì)于 0編址 65 2022/8/17 第六章 存儲(chǔ)管理 ? 邏輯地址 用戶程序的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。一般，一頁(yè)的大小為 2的整數(shù)次冪，因此，地址的高位部分為 頁(yè)號(hào) ，低位部分為 頁(yè)內(nèi)地址 頁(yè)號(hào) 頁(yè)內(nèi)地址 0 11 12 31 頁(yè)號(hào) P 頁(yè)內(nèi)位移量 W 編號(hào) 0~1048575 相對(duì)地址 0~4095 66 2022/8/17 第六章 存儲(chǔ)管理 ? 內(nèi)存空間 按頁(yè)的大小劃分為大小相等的區(qū)域，稱為 塊或內(nèi)存塊（物理頁(yè)面，頁(yè)框） 67 2022/8/17 第六章 存儲(chǔ)管理 ? 內(nèi)存分配 以頁(yè)為單位進(jìn)行分配，并按作業(yè)的頁(yè)數(shù)多少來(lái)分配。邏輯上相鄰的頁(yè)，物理上不一定相鄰 68 2022/8/17 第六章 存儲(chǔ)管理 . . . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 作業(yè)的 地址空間 頁(yè)框 （物理塊） 頁(yè)號(hào) 頁(yè)表 主存中頁(yè)框（物理塊） . . . . 69 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)地址映射 ? 頁(yè)表 ? 頁(yè)大小的選擇 ? 頁(yè)地址映射 ? 分頁(yè)存儲(chǔ)管理中的信息保護(hù) ? 快表和聯(lián)想存儲(chǔ)器 ? 兩級(jí)頁(yè)表和多級(jí)頁(yè)表 70 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)表 ? 將頁(yè)號(hào)和頁(yè)內(nèi)地址轉(zhuǎn)換成內(nèi)存地址 ， 必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu) ， 用來(lái)登記頁(yè)號(hào)和塊的對(duì)應(yīng)關(guān)系和有關(guān)信息 。 ? 這樣的數(shù)據(jù)結(jié)構(gòu)稱為 頁(yè)表 。 71 2022/8/17 第六章 存儲(chǔ)管理 ? 系統(tǒng)為 每個(gè)進(jìn)程建立一個(gè)頁(yè)表 ， 頁(yè)表的長(zhǎng)度和首地址存放在該進(jìn)程的進(jìn)程控制塊 （ PCB） 中 。 ? 占用處理機(jī)的現(xiàn)行進(jìn)程的頁(yè)表必須駐留在內(nèi)存 ， 其首地址和長(zhǎng)度由地址映射機(jī)構(gòu)的 頁(yè)表起址和長(zhǎng)度寄存器 指示 。 72 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)表內(nèi)容 ? 頁(yè)表包含以下幾個(gè)表項(xiàng)： ? 頁(yè)號(hào)：登記程序地址空間的頁(yè)號(hào) 。 ? 塊號(hào)：登記相應(yīng)的頁(yè)所對(duì)應(yīng)的內(nèi)存塊號(hào) ? 其它：登記與存儲(chǔ)信息保護(hù)有關(guān)的信息 。 頁(yè)號(hào) 塊號(hào) 其它 0 5 … 1 65 … 2 13 … 73 2022/8/17 第六章 存儲(chǔ)管理 例 ? 如圖 ， 作業(yè) 1有 2頁(yè)分別裝入內(nèi)存的第 6塊；作業(yè) 2有 3頁(yè)裝入內(nèi)存的第 7塊；作業(yè) 3有 1 頁(yè)裝入內(nèi)存的第 8塊 。 74 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)大小的選擇