1-概述
動態存儲管理的基本問題是：系統如何按請求分配內存，如何回收內存再利用。提出請求的用戶可能是系統的一個作業，也可能是程序中的一個變量。
空閒塊
未曾分配的地址連續的內存區稱為“空閒塊”。
占用塊
已分配給用戶使用的地址連續的內存區稱為“占用塊”。
系統剛剛啟動時，整個內存可看做一個大的“空閒塊”，隨著用戶請求的進入，系統依次分配相應的內存。
在系統運行過程中，內存被分為兩大部分：低地址區（若干占用塊）和高地址區（空閒塊）。
經過一段時間後，有的程序運行結束，釋放掉它所占用的內存，使之變為空閒塊，這就使整個內存中空閒塊和占用塊之間出現了相互交錯的現象。如下圖：
當系統進入到圖中b），又有新的用戶請求分配內存時，系統該如何處理呢？
方法一：系統繼續從高地址區的空閒塊進行分配，直到無法分配。當剩余的空閒塊不能滿足分配請求時，系統才去回收所有的不再使用的內存區，並重新組織內存，緊湊所有的空閒塊為一個大的空閒塊，以備在分配。
方法二：空閒鏈表。空閒鏈表中包含了所有空閒塊的信息，一個節點對應一個空閒塊。當用戶請求分配時，系統所作的工作就是搜索空閒鏈表，按某種策略找到一個合適的空閒塊進行分配，並刪除對應的節點。當用戶釋放所占用的內存時，系統回收該內存，並將它插入到空閒鏈表中。
空閒鏈表
空閒鏈表三種結構形式：
（1）所有請求的內存大小相同。這是一種最簡單的動態存儲管理方式。
對此，系統通常的做法是：
a）系統啟動時，將內存按大小均分成若干個塊，並形成一個鏈表。
b）分配時，只需將鏈表中第一個節點分配給用戶即可，無需掃描整個鏈表。
c）回收時，將空閒塊插入到鏈表頭即可。
（2）所有請求的內存大小有n種規格。可創建n個（1）情況中的鏈表，分配與回收與（1）類似，不同之處在於：當請求的鏈表為空時，需要在節點大的鏈表上進行分配，取一部分內存給用戶，剩余部分作為一個新節點插入到相應的鏈表中。
（3）所有請求的內存大小是不同的，是不斷發生變化的。這種情況下的分配與回收見下篇。
分配算法和回收
對於內存塊大小不同的空閒鏈表，假如有一個大小為N的內存申請，如果空閒鏈表中大於N的內存只有一塊，假如大小為M，就把M的一部分分配給用戶，同時把剩余的M-N的部分作為一個節點插入到空閒鏈表中。
當大於N的內存有多塊時，我們該如何分配呢？通常有以下三種方法：
（1）最先適配法。顧名思義，順序掃描空閒鏈表，找到第一個大於等於N的空閒塊，把其中的N分配給用戶。因為鏈表不按內存的地址有序，也不按大小有序，所以回收內存塊放到表頭即可。
問題：運行一段時間後，鏈表中將會出現一些非常小的塊，並在這些小塊都在鏈表的前邊。
（2）最優適配法。在空閒鏈表中找到一個不小於N並且最接近N的空閒塊分配給用戶。分配時需要整表掃描。如果鏈表按空閒塊從小到大有序，分配時只需找到第一個大於N的空閒塊，回收時需要插入到鏈表合適的位置上。
（3）最差適配法。將鏈表中不小於N且是鏈表中最大的空閒塊的一部分分配給用戶。鏈表可按空閒塊從大到小的順序排列，分配只需判斷鏈表第一個空閒塊即可，回收時需要插入到鏈表合適的位置上。
對於回收，我們考慮的不僅僅是歸還節點，還要考慮空閒塊的合並問題。這種把物理地址相鄰的空閒塊的合並以取得更大的空閒塊的方法是需要的。空閒鏈表中的空閒塊並不是按物理地址有序的，那又如何快速合並呢？下篇中將討論一種方法：邊界標識法
邊界標識法
原文鏈接：http://blog.csdn.net/hbuxiaoshe/article/details/5994743
就空閒鏈表來說，要確定哪些空閒塊是物理地址相鄰的，確實不太容易，需要整表掃描。
邊界標識法能夠有效的判斷空閒塊的物理相鄰內存塊是否為空閒塊。
所有的空閒塊組成一個雙向循環鏈表，鏈表中每一個節點的結構如下：
llink和rlink分別指向鏈表中的前驅後繼節點。
size表明內存塊的大小。
uplink指向本塊的首地址，圖中箭頭，其作用下面講述。
tag頭和尾中各有一個，作為內存塊邊界的標識，0表空閒塊，1表占用塊。
分配時同樣會在鏈表上產生很多非常小的空閒塊，影響分配的效率，因此，可以定義一個全局的指針p，當不為空時分配，使其始終指向剛進行過分配的節點的後繼節點。
回收時判斷物理相鄰的塊是否為空閒塊的方法：
假設當前回收塊的物理地址為p（下面涉及到的左鄰塊和右鄰塊都是物理地址相鄰的，在循環鏈表中也許不相鄰），
左鄰塊：左鄰塊的尾的地址是p1=p-sizeof(尾)，左鄰塊是否為空閒塊的判斷則為p1->tag是否為0。當為空閒塊時，只需將當前塊合並到左鄰塊中即可，而左鄰塊的地址則需要由uplink來獲得（原因是中間內存塊的大小是不固定的，不能通過偏移來實現），即p1->uplink。修改左鄰塊的size和uplink即可。
右鄰塊：右鄰塊的首的地址為p2=p+sizeof(頭)，右鄰塊是否為空閒塊的判斷則為p2->tag是否為0。當為空閒塊時，與右鄰塊合並，修改p的llink、rlink和size，修改p2的uplink。
你可能會認為，既然鏈表中的塊都是空閒塊，干嗎還要加上tag標識位呢？我的回答是，如果沒有tag，當我們找到右鄰塊的地址時，沒有辦法判斷右鄰塊是不是鏈表中的一個節點，也許它還在被用戶使用著。那為什麼要用兩個tag呢？個人覺得，用一個也可以，但用兩個更容易判斷。
