【文章內(nèi)容簡介】 其內(nèi)存分配圖及分配后空閑分區(qū)表如下： 存儲 管理 51 區(qū)號 大小 起址 1 194k 317k 2 120k 60k 3 32k 20k 4 8k 52k (2)該算法分配后的空閑分區(qū)表 3 0k 20k 52k 60k 180k 511k (1)內(nèi)存分配圖 20K 52K 60K 280K 310K 317K ?算法特點 總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有大作業(yè)到來時，其存儲空間的申請往往會得不到滿足。 存儲 管理 52 ⑤ 快速適應(yīng)算法（分類搜索法） ? 算法要求 將空閑分區(qū)根據(jù)其容量大小進行分類，每一類相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表 ，同時在內(nèi)存中設(shè)立一張 管理索引表 ，每一表項對應(yīng)了一種空閑分區(qū)類型，并記錄頭指針。進程根據(jù)自己的長度，尋找能容納它的最小空閑區(qū)鏈表，取下第一塊進行分配即可。 存儲 管理 53 ? 最先適應(yīng)法： 按分區(qū)的先后次序 ， 從頭查找 ， 找到符合要求的第一個分區(qū) – 該算法的分配和釋放的 時間性能 較好 ， 空閑 較大的分區(qū) 可以被保留在內(nèi)存高端 。 – 但隨著低端分區(qū)不斷劃分而產(chǎn)生較多 小分區(qū) ， 每次分配時查找時間開銷會增大 。 ? 最佳適應(yīng)法： 找到其大小與要求相差最小的空閑分區(qū) – 從個別來看 ， 外碎片 較小 ， 但從整體來看 ， 會形成較多外碎片 。 較大的空閑分區(qū) 可以被保留 。 ? 最壞適應(yīng)法： 找到最大的空閑分區(qū) – 基本不留 小空閑分區(qū) ， 但 較大的空閑分區(qū) 不被保留 。 幾種分配算法的比較 存儲 管理 54 例題：分區(qū)存儲管理算法題 ? 假定主存中按地址順序依次有五個空閑區(qū)?？臻e區(qū)大小依次為： 32k,10k,15k,228k,J1,J2,J3,J4,J5。 他們各需要主存 1k,10k,128k,28k,115k。 ? 判斷用最先適應(yīng)分配算法，最壞適應(yīng)分配算法，最佳分配適應(yīng)算法能否將這五個作業(yè)順序裝入？ 存儲 管理 55 OS 32K 10K 15K 228K 100K 示意圖： 存儲 管理 56 起始地址 長度 標(biāo)志位 100K 32K 0 200K 10K 0 300K 15K 0 400K 228K 0 700K 100K 0 起始地址 長度 標(biāo)志位 30K 70K ZS 已分配區(qū)表 空閑區(qū)表 存儲 管理 57 最先適應(yīng)分配算法 (空閑區(qū)按地址遞增順序排列 ) 作業(yè)依次請求空間 1k,10k,128k,28k,115k。 32K 228K 10K 100K 15K 空閑鏈 首指針 (1)作業(yè) J1請求 1K空間 31K 228K 10K 100K 15K 空閑鏈 首指針 (2)作業(yè) J2請求 10K空間 21K 100K 10K 100K 15K 空閑 (3)作業(yè) J3請求 128K空間 (4)作業(yè) J4請求 28K空間 (5)作業(yè) J5請求 115K空間 所有空間均不能滿足作業(yè) J5請求 存儲 管理 58 最壞適應(yīng)分配算法 (空閑區(qū)按長度遞減順序排列 ) 作業(yè)依次請求空間 1k,10k,128k,28k,115k。 228K 15K 100K 10K 32K 空閑鏈 首指針 (1)作業(yè) J1請求 1K空間 227K 15K 100K 10K 32K 空閑鏈 首指針 (2)作業(yè) J2請求 10K空間 217K 15K 100K 10K 32K 空閑鏈 首指針 100K 15K 89K 10K 32K 空閑鏈 首指針 89K 15K 72K 10K 32K 空閑鏈 首指針 (3)作業(yè) J3請求 128K空間 (4)作業(yè) J4請求 28K空間 (5)作業(yè) J5請求 115K空間 所有空間均不能滿足作業(yè) J5請求 存儲 管理 59 最優(yōu)適應(yīng)分配算法 (空閑區(qū)按長度遞增順序排列 ) 作業(yè)依次請求空間 1k,10k,128k,28k,115k。 10K 100K 15K 228K 32K 空閑鏈 首指針 (1)作業(yè) J1請求 1K空間 9K 100K 15K 228K 32K 空閑鏈 首指針 (2)作業(yè) J2請求 10K空間 5K 100K 9K 228K 32K 空閑鏈 首指針 5K 100K 9K 100K 32K 空閑鏈 首指針 4K 100K 5K 100K 9K 空閑鏈 首指針 (3)作業(yè) J3請求 128K空間 (4)作業(yè) J4請求 28K空間 (5)作業(yè) J5請求 115K空間 所有空間均不能滿足作業(yè) J5請求 存儲 管理 60 （ 2）回收內(nèi)存 當(dāng)作業(yè)執(zhí)行結(jié)束時，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息。 ? 回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種 ： 1） 回收分區(qū)上鄰接一個空閑分區(qū) ,合并后首地址為空閑分區(qū)的首地址 ,大小為二者之和。 2） 回收分區(qū)下鄰接一個空閑分區(qū) ,合并后首地址為回收分區(qū)的首地址 ,大小為二者之和。 3） 回收分區(qū)上下鄰接空閑分區(qū) ,合并后首地址為上空閑分區(qū)的首地址 ,大小為三者之和。 4） 回收分區(qū)不鄰接空閑分區(qū) ，這時在空閑分區(qū)表中新建一表項，并填寫分區(qū)大小等信息。 存儲 管理 61 M1回收區(qū)M2回收M1空白區(qū)M2( a )M1回收區(qū)M2回收M1M2( b)M1回收區(qū)M2回收M1M2( c )M1回收區(qū)M2回收 M1( d)(a) M M2都非空 (b) M1為空、 M2非空 (c) M1為非空、 M2空 (d) M M2都為空 ? 回收內(nèi)存空間，關(guān)鍵是修改兩個表。 存儲 管理 62 在動態(tài)分區(qū)分配中， 消除了固定分區(qū)管理造成的“內(nèi)碎片”， 但是不可避免的在內(nèi)存空間造成“外碎片”。 多個無法利用的小分區(qū)所形成的“碎片”是一種很大的資源浪費。 如圖（ a）所示， 空閑分區(qū)之和為 10 KB，但是無法裝入一個 8 KB的程序。 系統(tǒng)區(qū)程序 A5 K B程序 B3 K B程序 C2 K B緊湊系統(tǒng)區(qū)程序 A程序 B程序 C10 K B( a ) ( b)存儲 管理 63 ?內(nèi)存擴充 ? 消除了固定分區(qū)管理造成的“ 內(nèi)碎片 ”，但是不可避免的在內(nèi)存空間造成“ 外碎片 ”。 ? 采用移動（緊縮）技術(shù)。定時的或在內(nèi)存緊張時，將內(nèi)存中所有作業(yè)移到內(nèi)存的一端，使其相鄰。 存儲 管理 64 ? 經(jīng)過緊縮后的進程在內(nèi)存中的位置發(fā)生了變化，若不對程序和數(shù)據(jù)的地址進行修改，在進程就無法運行。 ? 要使其運行，必須進行“ 動態(tài)重定位 ” 存儲 管理 65 可重定位分區(qū)分配 1. 動態(tài)重定位的引入 在分區(qū)存儲管理方式中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。 例 ： 如圖所示系統(tǒng)中有四個小空閑分區(qū)，不相鄰，但總?cè)萘繛?90KB，如果現(xiàn)有一作業(yè)要求分配 40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于 40KB，故此作業(yè)無法裝入內(nèi)存。 這種內(nèi)存中無法被利用的存儲空間稱為 “零頭”或“碎片”。 根據(jù)碎片出現(xiàn)的情況分為以下兩種： 操作系統(tǒng) 作業(yè) A 20KB 作業(yè) B 30KB 作業(yè) C 15KB 作業(yè) D 25KB 存儲 管理 66 系統(tǒng)中的碎片 os 用戶程序 p4 p1 p2 0k 20k 56k 65k 125k 135k 內(nèi)部碎片 內(nèi)部碎片 內(nèi)部碎片 25KB 作業(yè) D 15KB 作業(yè) C 30KB 作業(yè) B 20KB 作業(yè) A 操作系統(tǒng) 外部碎片 外部碎片 外部碎片 外部碎片 內(nèi)部碎片 外部碎片 ?內(nèi)部碎片 ： 指分配給作業(yè)的存儲空間中未被利用的部分。如固定分區(qū)中存在的碎片。 ?外部碎片 ： 指系統(tǒng)中無法利用的小的空閑分區(qū)。 如動態(tài)分區(qū)中存在的碎片。 存儲 管理 67 碎片問題的解決方法 ? 拼接或緊湊或緊縮技術(shù) 將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對其地址加以修改或變換即稱為 重定位 ），使本來分散的多個小空閑分區(qū)連成一個大的空閑區(qū)。如圖所示。 這種通過移動作業(yè)從把多個分散的小分區(qū)拼接成一個大分區(qū)的方法稱為 拼接 或 緊湊 或 緊縮 。 拼接時機：分區(qū)回收時；當(dāng)找不到足夠大的空閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時。 操作系統(tǒng) 作業(yè) A 作業(yè) B 作業(yè) C 作業(yè) D 20KB 30KB 90KB 15KB 25KB 存儲 管理 68 2. 動態(tài)重定位的實現(xiàn) 動態(tài)重定位可使程序不加任何修改就裝入內(nèi)存，但是它需要硬件 —重定位寄存器 的支持。對每一個有效地址都要加上重定位寄存器中的內(nèi)容，以形成絕對地址。 0 3456 . . . . . . LOAD 1 200 . . . . . . 0 100 200 300 . . . . . . . . . LOAD 1 200 3456 邏輯地址空間 1100 1200 1300 物理地址空間 200 有效地址 + 1000 BR 1000 存儲 管理 69 動態(tài)重定位分區(qū)分配算法流程圖 有大于 x的 空閑分區(qū)嗎？ 返回分區(qū)號 空閑分區(qū) 總和大于 x嗎？ 拼接并修改 相應(yīng)數(shù)據(jù)結(jié)構(gòu) 返回 修改有關(guān) 數(shù)據(jù)結(jié)構(gòu) 按動態(tài)分區(qū) 分配方式進行分配 Y Y N N 無法分配，返回 請求分配一個 大小為 x的分區(qū) 3. 動態(tài)重定位分區(qū)分配算法 在動態(tài)分區(qū)分配算法中 增加拼接功能 ，在找不到足夠大的空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時，進行拼接。 存儲 管理 70 可重定位分區(qū)分配方式主要特點 可以充分利用存儲區(qū)中的 “ 零頭 /碎片 ” ，提高主存的利用率。 但若 “ 零頭 /碎片 ” 過多，則 拼接頻率過高會使系統(tǒng)開銷加大 。 存儲 管理 71 覆蓋技術(shù)與交換技術(shù) ? 引入：其目標(biāo)是在較小的可用內(nèi)存中 運行較大的程序 。常用于多道程序系統(tǒng)，與分區(qū)存儲管理配合使用。 ? 原理：一個程序的幾個代碼段或數(shù)據(jù)段，按照 時間 先后來 占用公共的內(nèi)存空間。 – 將程序的 必要部分 （常用功能）的代碼和數(shù)據(jù) 常駐內(nèi)存 ； – 可選部分 （不常用功能）在其他程序模塊中實現(xiàn)，平時存放在外存中（覆蓋文件），在需要用到時才裝入到內(nèi)存； – 不存在調(diào)用關(guān)系 的模塊不必同時裝入到內(nèi)存，從而 可以相互覆蓋 。 (即 不同時用的模塊可共用一個分區(qū) ) ? 缺點： – 編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度 。 – 從外存裝入覆蓋文件，以 時間延長來換取空間節(jié)省 。