动态记忆体管理.PPTVIP

楊正宏 編著 全華科技圖書股份有限公司 印行 第十一章 動態記憶體管理(1/2) 11-1 前言 11-2 記憶體分配方法 11-3 邊界標識法(Boundary Tag Method) 11-3-1 可利用空間串列的結構 11-3-2 分配演算法 11-3-3 回收演算法 11-4 夥伴系統(Buddy System) 11-4-1 可利用空間串列的結構 11-4-2 分配演算法 11-4-3 回收演算法 第十一章 動態記憶體管理(2/2) 11-5 費氏夥伴系統(Fibonacci Buddy System) 11-6 廢置單元收集 11-7 廢置單元收集的改良 11-8 記憶體壓縮 前言(1/2) 透過作業系統取得所需記憶體(memory)，並在執行完成後將所佔記憶體歸還作業系統，此項管理工作便稱為「動態記憶體管理」。 動態記憶體管理的基本工作是系統如何因應使用者提出的記憶體分配需求，以及如何回收(釋放)記憶體，以便當新的請求產生時，重新進行分配。 前言(2/2) 系統執行初期 系統執行若干時間之後 記憶體分配方法(1/2) 常用的三種方法包括： 最先合適法(First-Fit) 最佳合適法(Best-Fit) 最差合適法(Worst-Fit) 根據可利用閒置串列的多寡可分： 單一區段 多區段 記憶體分配方法(2/2) 最先合適法(First-Fit)： 自可供利用空間區段中，找到第一塊大於n的閒置區段，將其中一部份分配給使用者；回收時，只要將釋放的閒置區段插入在鏈結串列的開頭即可。 最佳合適法(Best-Fit)： 自可供利用空間區段中，找出一塊大小最接近n的閒置區段分配給使用者。為避免搜尋浪費的時間，先將區段自小到大排序。分配時，只需找到第一個大於n的閒置區段即可分配；回收時，必須將釋放的閒置區段插入到合適的位置上去。 最差合適法(Worst-Fit)： 自可供利用閒置區段中，找出最大的閒置區段分配給使用者。將閒置區段由大到小排序。每次分配時，只需將第一個區段的其中一部份分配給使用者即可；回收時，亦需將釋放的閒置區段插入到適當位置上去。 三種分配方法的比較圖 邊界標識法(Boundary Tag Method) (1/8) 是一種作業系統中用以進行動態分區分配的記憶體管理方法 配合最先合適法來管理記憶體，可減少搜尋時間。 特點： 在於每個記憶體區段的開頭部份和尾部兩個邊界上分別設有標籤，以標識該區域為占用區段或閒置區段，使得在回收使用者釋放的閒置區段時，易於判別物理位置上與其相鄰的記憶體區域是否為閒置區段，以便將所有位址中連續的閒置記憶體區組合成一個大的閒置區段。 邊界標識法(2/8) 起始狀態 執行若干時間後 進行再分配後的狀態 邊界標識法(3/8) 分配演算法規定： 假設所找到的閒置區段的容量為m個字組(包括頭部和底部)，而每次分配只是從中分配n個字組給使用者，剩餘m-n個字組大小的節點仍留在鏈結串列中，則在若干次分配之後，鏈給串列中會出現一些容量極小而分配不出去的閒置區段，這就大大減慢了分配(搜尋)的速度。 彌補的辦法是：選定一個適當的常量e，當m-n≦e時，將容量為m的閒置區段整塊分配給使用者；反之，只分配其中n個字的記憶體。同時，為了避免修改指標，約定將該節點中位址較大部份分配給使用者。 邊界標識法(4/8) 分配演算法規定： 如果每次分配都從同一個節點開始搜尋的話，勢必造成記憶體小的節點集中在開頭指標 pav所指節點附近，反而增加查詢較大閒置區段的時間。反之，如果每次分配從不同的節點開始進行搜尋，使分配後剩餘的小區段均勻地分布在鏈結串列中，則可避免上述弊病。 可行的方法是每次分配之後，令指標pav指向剛進行過分配的節點的後繼節點。 邊界標識法(5/8) 回收演算法 釋放區段的左、右鄰區均為佔用區段的情況 只要作簡單插入即可。由於在按最先合適法進行分配時邊界標識法對可利用空間串列的結構並沒有任何要求，則新的閒置區段插入在串列中任何位置均可。 簡單的做法就是插入在pav指標所指節點之前(或之後)。 邊界標識法(6/8) 回收演算法 釋放區段約左鄰區為閒置區段，而右鄰區為佔用區段的情況 由於釋放區段的開頭部份和左鄰閒置區段的尾部毗鄰，因此只要改變左鄰閒置區段的節點，增加節點size欄的值，且更新設置節點的尾部即可。 邊界標識法(7/8) 回收演算法 釋放區段的右鄰區為閒置區段，左鄰區為佔用區段 由於釋放區段的尾部和右鄰閒置區段的開頭部份毗鄰，當串列中節點由原來右約有鄰閒置區段變成合併後的大閒置區段時，區段的尾部指標位置不變，但開頭的指標位置要移動，因此，鏈結串列中的指標也必須要移動。 邊界標識法(8/8)