【文章內(nèi)容簡介】 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有動態(tài)分區(qū)的管理與組織用到的數(shù)據(jù)結(jié)構(gòu)動態(tài)分區(qū)的管理與組織常用的兩種方法為： 表格法、鏈表法 .表格法： 在表格法中需要用到的數(shù)據(jù)結(jié)構(gòu)為： 可用表 和 請求表區(qū)號 分區(qū)長度 起始地址1 16K 40K2 24K 78K3 9K 100K 進程號 請求大小P1 13KP2 20K 可用表 請求表分區(qū)并非緊密相連制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 分區(qū)的分配與回收 （ 1） 掃描請求表，讀出表中的請求空間的某個進程。 （ 2） 將進程的請求長度與可用表中的每個可用分區(qū)大 小進行比較，找到合適的空閑區(qū)，分配給該進程。 （ 3） 更新可用表 （分區(qū)起始地址和長度更改） 和請求表。 （ 4） 進程釋放空間時，將相鄰的空閑區(qū)進行聯(lián)結(jié)合并， 更新可用表。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有鏈表法 鏈表法是利用每個內(nèi)存空閑區(qū)的頭幾個單元存放 本空閑區(qū)的大小 及 下一個空閑區(qū)的起始地址 ，從而將所有的空閑區(qū)鏈接起來。空閑區(qū)的示意圖如 (a)所示，鏈表如圖 (b)所示?？臻e區(qū) size next(a) (b) 8KB 60KB 32KB 212KB 300KB NULL20KB鏈?zhǔn)字羔樋臻e分區(qū)組成的鏈表制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有分區(qū)的分配與回收 （ 1）掃描請求表，讀出表中的請求空間的某個進程。 （ 2）搜索鏈表，找到合適的空閑區(qū)，分配給該進程。 （ 3）更新鏈表。 （ 4）進程釋放空間時，將相鄰的空閑區(qū)進行聯(lián)結(jié)合并， 更新鏈表。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 在上述分區(qū)分配過程中的步驟 (2)，尋找合適的分區(qū)常用 的方法有以下三種： （ 1）最先適應(yīng)算法 把最先找到的、滿足存儲需要的空閑分區(qū)作為分配的 對象。優(yōu)點：查找時間短，實現(xiàn)簡單；缺點： 容易將大的分區(qū)分割成小塊 ，對大作業(yè)不利。 鏈表按照空間在內(nèi)存中位置的先后順序組織 （ 2）最佳適應(yīng)算法 從當(dāng)前所有空閑區(qū)中找出一個 能夠滿足存儲需求的、 最小 的空閑區(qū) 作為分配的對象。優(yōu)點：保證了大作業(yè)的需求。缺點：容易形成 小的碎片 空閑區(qū)，不容易分配。 鏈表按照空間大?。◤男〉酱螅┙M織 （ 3）最壞適應(yīng)算法 從當(dāng)前所有空閑區(qū)中找出 滿足需求的、 最大 的空閑區(qū) 作為分配對象。優(yōu)點：每次分配剩余空間充足，不留下碎片空閑區(qū)。 鏈表按照空間大?。◤拇蟮叫。┙M織制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有三種策略的評價和比較 P119（ 1）查找速度（ 2）釋放速度（ 3）空閑利用制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有動態(tài)分區(qū)存儲管理的特點：(1)作業(yè)一次性全部裝入到一個連續(xù)的存儲分區(qū)中。(2)分區(qū)是按照作業(yè)對內(nèi)存的需求來劃分的，因此，不 會出現(xiàn) 內(nèi)部碎片 （內(nèi)部碎片就是已經(jīng)被分配出去（能明確指出屬于哪個進程）卻不能被利用的內(nèi)存空間）的問題。(3)有硬件支持，實現(xiàn)指令地址的動態(tài)重定位。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有動態(tài)分區(qū)管理的缺點：(1)沒有解決小內(nèi)存運行大作業(yè)的問題 （仍然是僅僅依賴內(nèi)存） 。(2)雖然避免了內(nèi)部碎片，但是會引起極小的分 區(qū)難以得到利用，形成 外部碎片 （外部碎片指的是還沒有被分配出去（不屬于任何進程），但由于大小太小了無法分配給申請內(nèi)存空間的新進程的內(nèi)存空閑區(qū)域） 。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有分區(qū)管理的優(yōu)點：(1) 現(xiàn)了多個作業(yè)對內(nèi)存的共享，提高了系統(tǒng)的資源利用率。(2) 要求硬件支持少，算法簡單，易實現(xiàn)。缺點：(1) 內(nèi)存利用率不高，內(nèi)存中存在嚴重的碎片。(2) 作業(yè)受分區(qū)大小的限制。(3) 難以實現(xiàn)各分區(qū)的信息共享。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 作業(yè)： 如圖 (a)所示，現(xiàn)在有兩個空閑分區(qū)， 是 111KB161KB， 一個是 231KB256KB。 作業(yè) D到達，提出存儲需求 20KB， 問：如果系統(tǒng)實行最先適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法時，分別應(yīng)該把哪一個空閑區(qū)分配給它？分配后的內(nèi)存情形用圖形標(biāo)出。 (此時內(nèi) 0存空閑區(qū)采用鏈表法管理，空閑區(qū)按照地址遞增順序排列 )。 制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 操作系統(tǒng)作業(yè) A的分區(qū)（ 16K）作業(yè) B的分區(qū)（ 75K） 空閑區(qū)（ 50K） 作業(yè) C的分區(qū)（ 70K） 空閑區(qū)（ 25K）020K36K111K161K231K256K(a) 操作系統(tǒng) 作業(yè) A的分區(qū)（ 16K） 作業(yè) B的分區(qū)（ 75K） 空閑區(qū)（ 30K） 作業(yè) C的分區(qū)（ 70K） 空閑區(qū)（ 25K）020K36K111K161K231K256K(b) 作業(yè) D的分區(qū)（ 20K）131K 操作系統(tǒng) 作業(yè) A的分區(qū)（ 16K） 作業(yè) B的分區(qū)（ 75K） 空閑區(qū)（ 50K） 作業(yè) C的分區(qū)（ 70K） 空閑區(qū)（ 25K）020K36K111K161K231K256K(c) 作業(yè) D的分區(qū)（ 20K）251K制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 答： 當(dāng)系統(tǒng)采取最先適應(yīng)算法時，兩個空閑區(qū)都能滿足作業(yè) D的需求，此時系統(tǒng)按照 空閑區(qū)地址遞增的順序構(gòu)成鏈表 ，則最先搜索到的空閑區(qū)應(yīng)該是大小為 50KB的空閑區(qū)，此時分配后的內(nèi)存 如圖 (b)所示。 當(dāng)系統(tǒng)采取最佳適應(yīng)算法時， 空閑區(qū)鏈表應(yīng)當(dāng)按照空閑區(qū)的大小順序重新排列 ，則搜索到滿足條件的最小的空閑區(qū)應(yīng)該是大小為 25KB的空閑區(qū)，此時分配后的內(nèi)存 如圖 (c)所示。當(dāng)系統(tǒng)采取最壞適應(yīng)算法時，則搜索到滿足條件的最大的空閑區(qū)應(yīng)該是大小為 50KB的空閑區(qū)，此時分配后的內(nèi)存 如圖 (b)所示。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 基本思想 分區(qū)管理存在著嚴重的外部碎片問題，而且作業(yè)的大小受到分區(qū)大小的限制，而分頁管理可以很好的解決這些問題。在分頁存儲管理中，系統(tǒng)將內(nèi)存劃分成 大小相等 的許多分區(qū)，稱為 “ 頁面 ” 。頁面的編號為 0,1,2,… 如圖 (a) 所示。 用戶作業(yè)的地址空間也被劃分成大小與 “ 頁面 ” 相同的分區(qū) ，稱為 “ 頁 ” ， 如圖 (b)所示。此時用戶程序的虛擬地址由兩部分組成：頁號與頁內(nèi)地址， 如圖 (c)所示。這個二維地址可以轉(zhuǎn)換成一維的，具體轉(zhuǎn)換公式為： 一維地址 =頁號 *分頁尺寸 +葉內(nèi)位移量 繼續(xù) 頁式存儲管理制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 操作系統(tǒng) 作業(yè) A（ 第 2頁） 作業(yè) A（ 第 0頁） 作業(yè) A（ 第 1頁）20K24K28K36K40K256K032K ……(a)44K頁面 0~4頁面 5頁面 6頁面 7頁面 8頁面 9頁面 10內(nèi)存 用戶作業(yè)的地址空間0第 0頁4KB8KB12KB第 1頁第 2頁(1,1092) 51881092(b)(c)頁號 頁內(nèi)地址091019 只要內(nèi)存中有足夠多的空閑頁面，用戶作業(yè)中的某一頁裝入哪一個頁面都是可以的。上圖中，作業(yè)裝入了頁面 頁面 8和頁面 10這三個 不連續(xù)的存儲塊 中。因此解決了分區(qū)管理中作業(yè)必須連續(xù)存放的缺陷。 返回制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 靜態(tài)頁面管理 靜態(tài)頁面管理在作業(yè)或進程執(zhí)行之前，把該作業(yè)或進程的程序段和數(shù)據(jù)全部裝入內(nèi)存中的各個頁面，利用頁表和硬件地址變換機構(gòu)實現(xiàn)虛擬地址到物理地址的映射。該存儲管理方法中使用的數(shù)據(jù)結(jié)構(gòu)主要有 “ 頁表” 和 “ 請求表 （確定作業(yè)或進程虛擬空間的各頁在內(nèi)存中的實際位置） ” 。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有 頁表 最簡單的頁表由頁號與頁面號組成，每個進程至少有一個頁表 , 記錄了該進程的頁與頁面的對應(yīng)關(guān)系。如圖 (a)所示： 請求表 請求表記錄了作業(yè)或進程在內(nèi)存中的實際對應(yīng)位置，其表項如 圖 (b)所示：頁號 頁面號0 91 212 22進程號請求頁面數(shù)頁表始址頁表長度狀態(tài)1 20 1024 20 已分配2 34 1044 34 已分配3 18 1078 18 已分配(a) (b)制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計算機學(xué)院版權(quán)所有存儲頁面表（位示圖法）內(nèi)存中劃分一固定區(qū)域，每個單元的每個 比特位 代表一個頁面。 存儲頁面表每個系統(tǒng)一張，每個字位代表一個頁面。若頁面已分配，則對應(yīng)的字位置為 1；反之，置為 0。我們可以按照下面的公式計算出存儲頁面表中的該位代表的頁面號： 1 1 1 1 0 1 0 01 0 0 1 1 1 1 0空閑頁面總數(shù)為： 601234567位號 字節(jié)號01存儲頁面表（空閑頁面鏈）制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計算機學(xué)院 《操作系統(tǒng)》教程 16