蒲曉蓉操作系統(tǒng)原理—第31章存儲管理-資料下載頁
2025-01-12 09:16本頁面
【正文】 空閑分區(qū)也是外零頭了 。 例如 ? 當(dāng)系統(tǒng)進(jìn)行到如圖 (c)所示的情形時 ，若有一個進(jìn)程 P7申請大小為 16MB的存儲空間 。 ? 分別采用上述 4種算法進(jìn)行分配 ， 如圖所示 ， 分析結(jié)果 。 圖 動態(tài)劃分的 4種分配算法 (a)FFA 或 WFA 24MB 10MB OS 8MB P7 16MB P2 10MB P4 10MB P6 10MB 20MB 10MB (b)NFA 24MB 10MB OS 8MB P7 16MB P2 10MB P4 10MB P6 10MB 20MB 10MB 此次分 配位置 上次分 配位置 (c)BFA 10MB OS 8MB P2 10MB P7 16MB P4 10MB P6 10MB 10MB 40MB 4MB 伙伴系統(tǒng) (Buddy System) ? 靜態(tài)劃分方案限制了系統(tǒng)中活躍進(jìn)的數(shù)目。并且，只能運(yùn)行不超過分區(qū)大小的進(jìn)程，如果進(jìn)程遠(yuǎn)遠(yuǎn)小于分區(qū)大小，則內(nèi)存空間的利用率非常低。 ? 動態(tài)劃分方案使存儲管理復(fù)雜化，并且需要系統(tǒng)付出緊湊外零頭的額外開銷。 ? 伙伴系統(tǒng)：綜合靜態(tài)劃分技術(shù)和動態(tài)劃分技術(shù)的優(yōu)點(diǎn) ? 伙伴系統(tǒng)內(nèi)存的用戶可用空間為 2u 。 ? 系統(tǒng)總是為進(jìn)程分配大小為 2i的一個空閑分區(qū)。其中 m≤i≤U， 2m是系統(tǒng)允許的最小分區(qū)尺寸。 ? 如果進(jìn)程申請的存儲空間大小為 k，且 2 i1 ＜ k ≤ 2i,則將整個 2i大小的分區(qū)分配給它。 ? 否則，該分區(qū)被分割成大小相等（ 2i1 ）的兩個分區(qū)。再判斷 k是否滿足條件： 2i2k≤2i1,若滿足條件，則將兩個伙伴中的任何一個分配給進(jìn)程； ? 否則，將其中一個伙伴又平均分成兩個分區(qū)。此過程一直繼續(xù)進(jìn)行，直到產(chǎn)生的分區(qū)大于或等于 k，將其分配進(jìn)程。 伙伴系統(tǒng)的存儲分配 進(jìn)程申請大小為 k的空間 ， 系統(tǒng)為之分配一個 2i的空閑分區(qū) ， 其中 ， 2 i1 ＜ k ≤ 2i ? 若 k ＞ 2u ， 即進(jìn)程 內(nèi)存空間 ， 失??； ? 若當(dāng)前無尺寸為 2i的空閑分區(qū) ， 則： (1) 將 i變?yōu)?i+1， 查找一個尺寸為 2 i+1的空閑分區(qū) 。若存在 ， 轉(zhuǎn) (2)執(zhí)行 。否則 ， 繼續(xù)執(zhí)行 (1)； ⑵ 等分 2 i+1空閑分區(qū) :產(chǎn)生兩個 2i的伙伴分區(qū)； ⑶ 把其中一個 2i的伙伴分區(qū)作為空閑分區(qū)； (4) 另一個 2i 空閑分區(qū)分配給進(jìn)程 ， 結(jié)束 。 伙伴系統(tǒng)存儲空間的回收 當(dāng)進(jìn)程執(zhí)行完畢 ， 釋放一個尺寸為 2i的分區(qū)時 ，系統(tǒng)用下面的算法回收該分區(qū)： ? 如果被回收分區(qū)的伙伴分區(qū)非空閑，那么保留該分區(qū)為一個獨(dú)立的空閑分區(qū)，否則 [1] 合并回收分區(qū)及其伙伴分區(qū) ， 從而得到一個尺寸為 2 i+1的空閑分區(qū)； [2] 系統(tǒng)再次調(diào)用本算法回收上一步得到的尺寸為 2 i+1 的空閑分區(qū)。 例如 ? 有進(jìn)程 P P P P P5相繼申請、釋放空間。 ? 系統(tǒng)分配、回收（合并）伙伴分區(qū)的過程如圖所示： P1 申請 100KB P2 申請 200KB P3 申請 120KB P4 申請 300KB 系統(tǒng)初始狀態(tài) P P3結(jié)束 P5 申請 160KB P1執(zhí)行結(jié)束 P5執(zhí)行結(jié)束 P4執(zhí)行結(jié)束 1MB P1 128KB 256KB 512KB P1 128KB P2 512KB P1 P3 P2 512KB P1 P3 P2 P4 P1 128KB 256KB P4 P1 128KB P5 P4 256KB P5 P4 512KB P4 1MB 圖 一個伙伴系統(tǒng)的內(nèi)存分配與回收過程
公司管理相關(guān)推薦
鄂ICP備17016276號-1