上海網(wǎng)站推廣服務(wù)公司網(wǎng)絡(luò)推廣電話銷售技巧和話術(shù)
?
目錄
數(shù)據(jù)結(jié)構(gòu)之動態(tài)內(nèi)存管理機制
占用塊和空閑塊
系統(tǒng)的內(nèi)存管理
可利用空間表
分配存儲空間的方式
空間分配與回收過程產(chǎn)生的問題
邊界標識法管理動態(tài)內(nèi)存
分配算法
回收算法
伙伴系統(tǒng)管理動態(tài)內(nèi)存
可利用空間表中結(jié)點構(gòu)成
分配算法
回收算法
總結(jié)
無用單元收集（垃圾回收機制）
總結(jié)
內(nèi)存緊縮（內(nèi)存碎片化處理）
分配內(nèi)存空間
回收算法
總結(jié)
數(shù)據(jù)結(jié)構(gòu)之動態(tài)內(nèi)存管理機制
通過前面的學習，介紹很多具體的數(shù)據(jù)結(jié)構(gòu)的存儲以及遍歷的方式，過程中只是很表面地介紹了數(shù)據(jù)的存儲，而沒有涉及到更底層的有關(guān)的存儲空間的分配與回收，從本節(jié)開始將做更深入地介紹。
在使用早期的計算機上編寫程序時，有關(guān)數(shù)據(jù)存儲在什么位置等這樣的問題都是需要程序員自己來給數(shù)據(jù)分配內(nèi)存。而現(xiàn)在的高級語言，大大的減少了程序員的工作，不需要直接和存儲空間打交道，程序在編譯時由編譯程序去合理地分配空間。
本章重點解決的問題是：
- 對于用戶向系統(tǒng)提出的申請空間的請求，系統(tǒng)如何分配內(nèi)存？
- 當用戶不在使用之前申請的內(nèi)存空間后，系統(tǒng)又如何回收？
這里的用戶，不是普通意義上的用戶，可能是一個普通的變量，一個應(yīng)用程序，一個命令等等。只要是向系統(tǒng)發(fā)出內(nèi)存申請的，都可以稱之為用戶。
占用塊和空閑塊
對于計算機中的內(nèi)存來說，稱已經(jīng)分配給用戶的的內(nèi)存區(qū)統(tǒng)稱為“占用塊”；還未分配出去的內(nèi)存區(qū)統(tǒng)稱為“空閑塊”或者“可利用空間塊”。
系統(tǒng)的內(nèi)存管理
對于初始狀態(tài)下的內(nèi)存來說，整個空間都是一個空閑塊（在編譯程序中稱為“堆”）。但是隨著不同的用戶不斷地提出存儲請求，系統(tǒng)依次分配。
整個內(nèi)存區(qū)就會分割成兩個大部分：低地址區(qū)域會產(chǎn)生很多占用塊；高地址區(qū)域還是空閑塊。如圖 1 所示：
?
圖 1 動態(tài)分配過程中的內(nèi)存狀態(tài)
但是當某些用戶運行結(jié)束，所占用的內(nèi)存區(qū)域就變成了空閑塊，如圖 2 所示：
?
圖 2 動態(tài)分配過程中的內(nèi)存變化
此時，就形成了占用塊和空閑塊犬牙交錯的狀態(tài)。當后續(xù)用戶請求分配內(nèi)存時，系統(tǒng)有兩種分配方式：
?
- 系統(tǒng)繼續(xù)利用高地址區(qū)域的連續(xù)空閑塊分配給用戶，不去理會之前分配給用戶的內(nèi)存區(qū)域的狀態(tài)。直到分配無法進行，也就是高地址的空閑塊不能滿足用戶的需求時，系統(tǒng)才會去回收之前的空閑塊，重新組織繼續(xù)分配；
- 當用戶運行一結(jié)束，系統(tǒng)馬上將其所占空間進行回收。當有新的用戶請求分配內(nèi)存時，系統(tǒng)遍歷所有的空閑塊，從中找出一個合適的空閑塊分配給用戶。
合適的空閑塊指的是能夠滿足用戶要求的空閑塊，具體的查找方式有多種，后續(xù)會介紹。
可利用空間表
當采用第 2 種方式時，系統(tǒng)需要建立一張記錄所有空閑塊信息的表。表的形式有兩種：目錄表和鏈表。各自的結(jié)構(gòu)如圖 3 所示：
?
圖 3 目錄表和鏈表
目錄表：表中每一行代表一個空閑塊，由三部分組成：
?
- 初始地址：記錄每個空閑塊的起始地址。
- 空閑塊大小：記錄每個空閑塊的內(nèi)存大小。
- 使用情況：記錄每個空閑塊是否存儲被占用的狀態(tài)。
鏈表：表中每個結(jié)點代表一個空閑塊，每個結(jié)點中需要記錄空閑塊的使用情況、大小和連接下一個空閑塊的指針域。
由于鏈表中有指針的存在，所以結(jié)點中不需要記錄各內(nèi)存塊的起始地址。
系統(tǒng)在不同的環(huán)境中運行，根據(jù)用戶申請空間的不同，存儲空閑塊的可利用空間表有以下不同的結(jié)構(gòu)：
?
- 如果每次用戶請求的存儲空間大小相同，對于此類系統(tǒng)中的內(nèi)存來說，在用戶運行初期就將整個內(nèi)存存儲塊按照所需大小進行分割，然后通過鏈表鏈接。當用戶申請空間時，從鏈表中摘除一個結(jié)點歸其使用；用完后再鏈接到可利用空間表上。
- 每次如果用戶申請的都是若干種大小規(guī)格的存儲空間，針對這種情況可以建立若干個可利用空間表，每一個鏈表中的結(jié)點大小相同。當用戶申請某一規(guī)格大小的存儲空間時，就從對應(yīng)的鏈表中摘除一個結(jié)點供其使用；用完后鏈接到相同規(guī)格大小的鏈表中。
- 用戶申請的內(nèi)存的大小不固定，所以造成系統(tǒng)分配的內(nèi)存塊的大小也不確定，回收時，鏈接到可利用空間表中每個結(jié)點的大小也各不一樣。
第 2 種情況下容易面臨的問題是：如果同用戶申請空間大小相同的鏈表中沒有結(jié)點時，就需要找結(jié)點更大的鏈表，從中取出一個結(jié)點，一部分給用戶使用，剩余部分插入到相應(yīng)大小的鏈表中；回收時，將釋放的空閑塊插入到大小相同的鏈表中去。如果沒有比用戶申請的內(nèi)存空間相等甚至更大的結(jié)點時，就需要系統(tǒng)重新組織一些小的連續(xù)空間，然后給用戶使用。
分配存儲空間的方式
通常情況下系統(tǒng)中的可利用空間表是第 3 種情況。如圖 3(C) 所示。由于鏈表中各結(jié)點的大小不一，在用戶申請內(nèi)存空間時，就需要從可利用空間表中找出一個合適的結(jié)點，有三種查找的方法：
?
- 首次擬合法：在可利用空間表中從頭開始依次遍歷，將找到的第一個內(nèi)存不小于用戶申請空間的結(jié)點分配給用戶，剩余空間仍留在鏈表中；回收時只要將釋放的空閑塊插入在鏈表的表頭即可。
- 最佳擬合法：和首次擬合法不同，最佳擬合法是選擇一塊內(nèi)存空間不小于用戶申請空間，但是卻最接近的一個結(jié)點分配給用戶。為了實現(xiàn)這個方法，首先要將鏈表中的各個結(jié)點按照存儲空間的大小進行從小到大排序，由此，在遍歷的過程中只需要找到第一塊大于用戶申請空間的結(jié)點即可進行分配；用戶運行完成后，需要將空閑塊根據(jù)其自身的大小插入到鏈表的相應(yīng)位置。
- 最差擬合法：和最佳擬合法正好相反，該方法是在不小于用戶申請空間的所有結(jié)點中，篩選出存儲空間最大的結(jié)點，從該結(jié)點的內(nèi)存空間中提取出相應(yīng)的空間給用戶使用。為了實現(xiàn)這一方法，可以在開始前先將可利用空間表中的結(jié)點按照存儲空間大小從大到小進行排序，第一個結(jié)點自然就是最大的結(jié)點。回收空間時，同樣將釋放的空閑塊插入到相應(yīng)的位置上。
以上三種方法各有所長：
?
- 最佳擬合法由于每次分配相差不大的結(jié)點給用戶使用，所以會生成很多存儲空間特別小的結(jié)點，以至于根本無法使用，使用過程中，鏈表中的結(jié)點存儲大小發(fā)生兩極分化，大的很大，小的很小。該方法適用于申請內(nèi)存大小范圍較廣的系統(tǒng)
- 最差擬合法，由于每次都是從存儲空間最大的結(jié)點中分配給用戶空間，所以鏈表中的結(jié)點大小不會起伏太大。依次適用于申請分配內(nèi)存空間較窄的系統(tǒng)。
- 首次擬合法每次都是隨機分配。在不清楚用戶申請空間大小的情況下，使用該方法分配空間。
同時，三種方法中，最佳擬合法相比于其它兩種方式，無論是分配過程還是回收過程，都需要遍歷鏈表，所有最費時間。
空間分配與回收過程產(chǎn)生的問題
無論使用以上三種分配方式中的哪一種，最終內(nèi)存空間都會成為一個一個特別小的內(nèi)存空間，對于用戶申請的空間的需求，單獨拿出任何一個結(jié)點都不能夠滿足。
但是并不是說整個內(nèi)存空間就不夠用戶使用。在這種情況下，就需要系統(tǒng)在回收的過程考慮將地址相鄰的空閑塊合并。
邊界標識法管理動態(tài)內(nèi)存
在使用邊界標識法的系統(tǒng)管理內(nèi)存時，可利用空間表中的結(jié)點的構(gòu)成如圖 1：
?
圖 1 結(jié)構(gòu)構(gòu)成
每個結(jié)點中包含 3 個區(qū)域，head 域、foot 域?和?space 域：
?
- space 域表示為該內(nèi)存塊的大小，它的大小通過 head 域中的 size 值表示。
- head 域中包含有 4 部分：llink?和?rlink?分別表示指向當前內(nèi)存塊結(jié)點的直接前驅(qū)和直接后繼。tag 值用于標記當前內(nèi)存塊的狀態(tài)，是占用塊（用 1 表示）還是空閑塊（用 0 表示）。size?用于記錄該內(nèi)存塊的存儲大小。
- foot 域中包含有 2 部分：uplink?是指針域，用于指向內(nèi)存塊本身，通過 uplink 就可以獲取該內(nèi)存塊所在內(nèi)存的首地址。tag?同 head 域中的 tag 相同，都是記錄內(nèi)存塊狀態(tài)的。
注意：head 域和 foot 域在本節(jié)中都假設(shè)只占用當前存儲塊的 1 個存儲單位的空間，對于該結(jié)點整個存儲空間來說，可以忽略不計。也就是說，在可利用空間表中，知道下一個結(jié)點的首地址，該值減 1 就可以找到當前結(jié)點的 foot 域。
使用邊界標識法的可利用空間表本身是雙向循環(huán)鏈表，每個內(nèi)存塊結(jié)點都有指向前驅(qū)和后繼結(jié)點的指針域。
所以，邊界標識法管理的內(nèi)存塊結(jié)點的代碼表示為：
- typedef struct WORD{
- union{
- struct WORD *llink;//指向直接前驅(qū)
- struct WORD *uplink;//指向結(jié)點本身
- };
- int tag;//標記域,0表示為空閑塊；1表示為占用塊
- int size;//記錄內(nèi)存塊的存儲大小
- struct WORD *rlink;//指向直接后繼
- OtherType other;//內(nèi)存塊可能包含的其它的部分
- }WORD,head,foot,*Space;
通過以上介紹的結(jié)點結(jié)構(gòu)構(gòu)建的可利用空間表中，任何一個結(jié)點都可以作為該鏈表的頭結(jié)點（用 pav 表示頭結(jié)點），當頭結(jié)點為 NULL 時，即可利用空間表為空，無法繼續(xù)分配空間。
分配算法
當用戶申請空間時，系統(tǒng)可以采用 3 種分配方法中的任何一種。但在不斷地分配的過程中，會產(chǎn)生一些容量極小以至無法利用的空閑塊，這些不斷生成的小內(nèi)存塊就會減慢遍歷分配的速度。
3 種分配方法分別為：首部擬合法、最佳擬合法和最差擬合法。
針對這種情況，解決的措施是：
- 選定一個常量 e，每次分配空間時，判斷當前內(nèi)存塊向用戶分配空間后，如果剩余部分的容量比 e 小，則將整個內(nèi)存塊全部分配給用戶。
- 采用頭部擬合法進行分配時，如果每次都從 pav 指向的結(jié)點開始遍歷，在若干次后，會出現(xiàn)存儲量小的結(jié)點密集地分布在 pav 結(jié)點附近的情況，嚴重影響遍歷的時間。解決辦法就是：在每次分配空間后，讓 pav 指針指向該分配空間結(jié)點的后繼結(jié)點，然后從新的 pav 指向的結(jié)點開始下一次的分配。
分配算法的具體實現(xiàn)代碼為（采用首部擬合法）
- Space AllocBoundTag(Space *pav,int n){
- Space p,f;
- int e=10;//設(shè)定常亮 e 的值
- //如果在遍歷過程，當前空閑塊的在存儲容量比用戶申請空間 n 值小，在該空閑塊有右孩子的情況下直接跳過
- for (p=(*pav); p&&p->size<n&&p->rlink!=(*pav); p=p->rlink);
- //跳出循環(huán)，首先排除p為空和p指向的空閑塊容量小于 n 的情況
- if (!p ||p->size<n) {
- return NULL;
- }else{
- //指針f指向p空閑塊的foot域
- f=FootLoc(p);
- //調(diào)整pav指針的位置，為下次分配做準備
- (*pav)=p->rlink;
- //如果該空閑塊的存儲大小比 n 大，比 n+e 小，負責第一種情況，將 p 指向的空閑塊全部分配給用戶
- if (p->size-n <= e) {
- if ((*pav)==p) {
- pav=NULL;
- }
- else{
- //全部分配用戶，即從可利用空間表中刪除 p 空閑塊
- (*pav)->llink=p->llink;
- p->llink->rlink=(*pav);
- }
- //同時調(diào)整head域和foot域中的tag值
- p->tag=f->tag=1;
- }
- //否則，從p空閑塊中拿出 大小為 n 的連續(xù)空間分配給用戶，同時更新p剩余存儲塊中的信息。
- else{
- //更改分配塊foot域的信息
- f->tag=1;
- p->size-=n;
- //f指針指向剩余空閑塊 p 的底部
- f=FootLoc(p);
- f->tag=0; f->uplink=p;
- p=f+1;//p指向的是分配給用戶的塊的head域，也就是該塊的首地址
- p->tag=1; p->size=n;
- }
- return p;
- }
- }
回收算法
在用戶活動完成，系統(tǒng)需要立即回收被用戶占用的存儲空間，以備新的用戶使用。回收算法中需要解決的問題是：在若干次分配操作后，可利用空間塊中會產(chǎn)生很多存儲空間很小以致無法使用的空閑塊。但是經(jīng)過回收用戶釋放的空間后，可利用空間表中可能含有地址相鄰的空閑塊，回收算法需要將這些地址相鄰的空閑塊合并為大的空閑塊供新的用戶使用。
合并空閑塊有 3 種情況：
- 該空閑塊的左邊有相鄰的空閑塊可以進行合并；
- 該空閑塊的右邊用相鄰的空閑塊可以進行合并；
- 該空閑塊的左右兩側(cè)都有相鄰的空閑塊可以進行合并；
判斷當前空閑塊左右兩側(cè)是否為空閑塊的方法是：對于當前空閑塊 p ，p-1 就是相鄰的低地址處的空閑塊的 foot 域，如果 foot 域中的 tag 值為 0 ，表明其為空閑塊； p+p->size 表示的是高地址處的塊的 head 域，如果 head 域中的 tag 值為 0，表明其為空閑塊。
如果當前空閑塊的左右兩側(cè)都不是空閑塊，而是占用塊，此種情況下只需要將新的空閑塊按照相應(yīng)的規(guī)則（頭部擬合法隨意插入，其它兩種方法在對應(yīng)位置插入）插入到可利用空間表中即可。實現(xiàn)代碼為：
- //設(shè)定p指針指向的為用戶釋放的空閑塊
- p->tag=0;
- //f指針指向p空閑塊的foot域
- Space f=FootLoc(p);
- f->uplink=p;
- f->tag=0;
- //如果pav指針不存在，證明可利用空間表為空，此時設(shè)置p為頭指針，并重新建立雙向循環(huán)鏈表
- if (!pav) {
- pav=p->llink=p->rlink=p;
- }else{
- //否則，在p空閑塊插入到pav指向的空閑塊的左側(cè)
- Space q=pav->llink;
- p->rlink=pav;
- p->llink=q;
- q->rlink=pav->llink=p;
- pav=p;
- }
如果該空閑塊的左側(cè)相鄰的塊為空閑塊，右側(cè)為占用塊，處理的方法是：只需要更改左側(cè)空閑塊中的 size 的大小，并重新設(shè)置左側(cè)空閑塊的 foot 域即可（如圖 2）。
?
圖 2 空閑塊合并（當前塊，左側(cè)內(nèi)存塊）
實現(xiàn)代碼為：
- //常量 n 表示當前空閑塊的存儲大小
- int n=p->size;
- Space s=(p-1)->uplink;//p-1 為當前塊的左側(cè)塊的foot域，foot域中的uplink指向的就是左側(cè)塊的首地址，s指針代表的是當前塊的左側(cè)存儲塊
- s->size+=n;//設(shè)置左側(cè)存儲塊的存儲容量
- Space f=p+n-1;//f指針指向的是空閑塊 p 的foot域
- f->uplink=s;//這是foot域的uplink指針重新指向合并后的存儲空間的首地址
- f->tag=0;//設(shè)置foot域的tag標記為空閑塊
如果用戶釋放的內(nèi)存塊的相鄰左側(cè)為占用塊，右側(cè)為空閑塊，處理的方法為：將用戶釋放掉的存儲塊替換掉右側(cè)的空閑塊，同時更改存儲塊的 size 和右側(cè)空閑塊的 uplink 指針的指向（如圖 3 所示）。
?
圖 3 空閑塊合并（當前塊、右側(cè)內(nèi)存塊）
實現(xiàn)代碼為：
- Space t=p+p->size;//t指針指向右側(cè)空閑塊的首地址
- p->tag=0;//初始化head域的tag值為0
- //找到t右側(cè)空閑塊的前驅(qū)結(jié)點和后繼結(jié)點，用當前釋放的空閑塊替換右側(cè)空閑塊
- Space q=t->llink;
- p->llink=q; q->rlink=p;
- Space q1=t->rlink;
- p->rlink=q1; q1->llink=p;
- //更新釋放塊的size的值
- p->size+=t->size;
- //更改合并后的foot域的uplink指針的指向
- Space f=FootLoc(t);
- f->uplink=p;
如果當前用戶釋放掉的空閑塊，物理位置上相鄰的左右兩側(cè)的內(nèi)存塊全部為空閑塊，需要將 3 個空閑塊合并為一個更大的塊，操作的過程為：更新左側(cè)空閑塊的 size 的值，同時在可利用空間表中摘除右側(cè)空閑塊，最后更新合并后的大的空閑塊的 foot 域。
此情況和只有左側(cè)有空閑塊的情況雷同，唯一的不同點是多了一步摘除右側(cè)相鄰空閑塊結(jié)點的操作。
實現(xiàn)代碼為：
純文本復制
- int n=p->size;
- Space s=(p-1)->uplink;//找到釋放內(nèi)存塊物理位置相鄰的低地址的空閑塊
- Space t=p+p->size;//找到物理位置相鄰的高地址處的空閑塊
- s->size+=n+t->size;//更新左側(cè)空閑塊的size的值
- //從可利用空間表中摘除右側(cè)空閑塊
- Space q=t->llink;
- Space q1=t->rlink;
- q->rlink=q1;
- q1->llink=q;
- //更新合并后的空閑塊的uplink指針的指向
- Space f=FootLoc(t);
- f->uplink=s;
伙伴系統(tǒng)管理動態(tài)內(nèi)存
伙伴系統(tǒng)本身是一種動態(tài)管理內(nèi)存的方法，和邊界標識法的區(qū)別是：使用伙伴系統(tǒng)管理的存儲空間，無論是空閑塊還是占用塊，大小都是 2 的 n 次冪（n 為正整數(shù)）。
例如，系統(tǒng)中整個存儲空間為 2m?個字。那么在進行若干次分配與回收后，可利用空間表中只可能包含空間大小為：20、21、22、…、2m?的空閑塊。
字是一種計量單位，由若干個字節(jié)構(gòu)成，不同位數(shù)的機器，字所包含的字節(jié)數(shù)不同。例如，8 位機中一個字由 1 個字節(jié)組成；16 位機器一個字由 2 個字節(jié)組成。
可利用空間表中結(jié)點構(gòu)成
伙伴系統(tǒng)中可利用空間表中的結(jié)點構(gòu)成如圖 1 所示：
?
圖 1 結(jié)點構(gòu)成
header 域表示為頭部結(jié)點，由 4 部分構(gòu)成：
- llink 和 rlink 為結(jié)點類型的指針域，分別用于指向直接前驅(qū)和直接后繼結(jié)點。
- tag 值：用于標記內(nèi)存塊的狀態(tài)，是占用塊（用 1 表示）還是空閑塊（用 0 表示）
- kval ：記錄該存儲塊的容量。由于系統(tǒng)中各存儲塊都是 2 的 m 冪次方，所以 kval 記錄 m 的值。
代碼表示為：
- typedef struct WORD_b{
- struct WORD_b *llink;//指向直接前驅(qū)
- int tag;//記錄該塊是占用塊還是空閑塊
- int kval;//記錄該存儲塊容量大小為2的多少次冪
- struct WORD_b *rlink;//指向直接后繼
- OtherType other;//記錄結(jié)點的其它信息
- }WORD_b,head;
在伙伴系統(tǒng)中，由于系統(tǒng)會不斷地接受用戶的內(nèi)存申請的請求，所以會產(chǎn)生很多大小不同但是都是容量為 2m?的內(nèi)存塊，所以為了在分配的時候查找方便，系統(tǒng)采用將大小相同的各自建立一個鏈表。對于初始容量為 2m?的一整塊存儲空間來說，形成的鏈表就有可能有 m+1 個，為了更好的對這些鏈表進行管理，系統(tǒng)將這 m+1 個鏈表的表頭存儲在數(shù)組中，就類似于鄰接表的結(jié)構(gòu)，如圖 2。
?
圖 2 伙伴系統(tǒng)的初始狀態(tài)
可利用空間表的代碼表示為：
- #define m 16//設(shè)定m的初始值
- typedef struct HeadNode {
- int nodesize;//記錄該鏈表中存儲的空閑塊的大小
- WORD_b * first;//相當于鏈表中的next指針的作用
- }FreeList[m+1];//一維數(shù)組
分配算法
伙伴系統(tǒng)的分配算法很簡單。假設(shè)用戶向系統(tǒng)申請大小為 n 的存儲空間，若 2k-1?< n <= 2k，此時就需要查看可利用空間表中大小為 2k?的鏈表中有沒有可利用的空間結(jié)點：
- 如果該鏈表不為 NULL，可以直接采用頭插法從頭部取出一個結(jié)點，提供給用戶使用；
- 如果大小為 2k?的鏈表為 NULL，就需要依次查看比 2k?大的鏈表，找到后從鏈表中刪除，截取相應(yīng)大小的空間給用戶使用，剩余的空間，根據(jù)大小插入到相應(yīng)的鏈表中。
例如，用戶向系統(tǒng)申請一塊大小為 7 個字的空間，而系統(tǒng)總的內(nèi)存為 24?個字，則此時按照伙伴系統(tǒng)的分配算法得出：22?< 7 < 23，所以此時應(yīng)查看可利用空間表中大小為 23?的鏈表中是否有空閑結(jié)點：
- 如果有，則從該鏈表中摘除一個結(jié)點，直接分配給用戶使用；
- 如果沒有，則需依次查看比 23?大的各個鏈表中是否有空閑結(jié)點。假設(shè)，在大小 24?的鏈表中有空閑塊，則摘除該空閑塊，分配給用戶 23?個字的空間，剩余 23?個字，該剩余的空閑塊添加到大小為 23?的鏈表中。
（A）分配前?????????????????????? （B）分配后
圖 3 伙伴系統(tǒng)分配過程
回收算法
無論使用什么內(nèi)存管理機制，在內(nèi)存回收的問題上都會面臨一個共同的問題：如何把回收的內(nèi)存進行有效地整合，伙伴系統(tǒng)也不例外。
當用戶申請的內(nèi)存塊不再使用時，系統(tǒng)需要將這部分存儲塊回收，回收時需要判斷是否可以和其它的空閑塊進行合并。
在尋找合并對象時，伙伴系統(tǒng)和邊界標識法不同，在伙伴系統(tǒng)中每一個存儲塊都有各自的“伙伴”，當用戶釋放存儲塊時只需要判斷該內(nèi)存塊的伙伴是否為空閑塊，如果是則將其合并，然后合并的新的空閑塊還需要同其伙伴進行判斷整合。反之直接將存儲塊根據(jù)大小插入到可利用空間表中即可。
判斷一個存儲塊的伙伴的位置時，采用的方法為：如果該存儲塊的起始地址為 p，大小為 2k，則其伙伴所在的起始地址為：
?
?
例如，當大小為 28?，起始地址為 512 的伙伴塊的起始地址的計算方式為：
由于 512 MOD 29=0，所以，512+28=768，及如果該存儲塊回收時，只需要查看起始地址為 768 的存儲塊的狀態(tài)，如果是空閑塊則兩者合并，反之直接將回收的釋放塊鏈接到大小為 28?的鏈表中。
總結(jié)
使用伙伴系統(tǒng)進行存儲空間的管理過程中，在用戶申請空間時，由于大小不同的空閑塊處于不同的鏈表中，所以分配完成的速度會更快，算法相對簡單。
回收存儲空間時，對于空閑塊的合并，不是取決于該空閑塊的相鄰位置的塊的狀態(tài)；而是完全取決于其伙伴塊。
所以即使其相鄰位置的存儲塊時空閑塊，但是由于兩者不是伙伴的關(guān)系，所以也不會合并。這也就是該系統(tǒng)的缺點之一：由于在合并時只考慮伙伴，所以容易產(chǎn)生存儲的碎片。
無用單元收集（垃圾回收機制）
通過前幾節(jié)對可利用空間表進行動態(tài)存儲管理的介紹，運行機制可以概括為：
- 當用戶發(fā)出申請空間的請求后，系統(tǒng)向用戶分配內(nèi)存；
- 用戶運行結(jié)束釋放存儲空間后，系統(tǒng)回收內(nèi)存。
這兩部操作都是在用戶給出明確的指令后，系統(tǒng)對存儲空間進行有效地分配和回收。
但是在實際使用過程中，有時會因為用戶申請了空間，但是在使用完成后沒有向系統(tǒng)發(fā)出釋放的指令，導致存儲空間既沒有被使用也沒有被回收，變?yōu)榱?strong>無用單元或者會產(chǎn)生懸掛訪問的問題。
什么是無用單元？簡單來講，無用單元是一塊用戶不再使用，但是系統(tǒng)無法回收的存儲空間。例如在C語言中，用戶可以通過 malloc 和 free 兩個功能函數(shù)來動態(tài)申請和釋放存儲空間。當用戶使用 malloc 申請的空間使用完成后，沒有使用 free 函數(shù)進行釋放，那么該空間就會成為無用單元。
懸掛訪問也很好理解：假設(shè)使用 malloc 申請了一塊存儲空間，有多個指針同時指向這塊空間，當其中一個指針完成使命后，私自將該存儲空間使用 free 釋放掉，導致其他指針處于懸空狀態(tài)，如果釋放掉的空間被再分配后，再通過之前的指針訪問，就會造成錯誤。數(shù)據(jù)結(jié)構(gòu)中稱這種訪問為懸掛訪問。
?
圖 1 含有共享子表的廣義表
在含有共享子表的廣義表中，也可能會產(chǎn)生無用單元。例如圖 1 中，L1、L2 和 L3 分別為三個廣義表的表頭指針，L4 為 L1 和 L2 所共享，L3 是 L2 的子表，L5 為 L1、L2 和 L3 三個廣義表所共享。
在圖 1 的基礎(chǔ)上，假設(shè)表 L1 不再使用，而 L2 和 L3 還在使用，若釋放表 L1，L1 中的所有結(jié)點所占的存儲空間都會被釋放掉，L2 和 L3 中由于同樣包含 L1 中的結(jié)點，兩個表會被破壞，某些指針會產(chǎn)生懸掛訪問的錯誤；
而如果 L1 表使用完成后不及時釋放，L1 中獨自占用的結(jié)點由于未被釋放，系統(tǒng)也不會回收，就會成為無用單元。
解決存儲空間可能成為無用單元或者產(chǎn)生懸掛訪問的方法有兩個：
- 每個申請的存儲空間設(shè)置一個計數(shù)域，這個計數(shù)域記錄的是指向該存儲空間的指針數(shù)目，只有當計數(shù)域的值為 0 時，該存儲空間才會被釋放。
- 在程序運行時，所有的存儲空間無論是處于使用還是空閑的狀態(tài)，一律不回收，當系統(tǒng)中的可利用空間表為空時，將程序中斷，對當前不在使用狀態(tài)的存儲空間一律回收，全部鏈接成一個新的可利用空間表后，程序繼續(xù)執(zhí)行。
第一種方法非常簡單，下面主要介紹第二種方法的具體實現(xiàn)。
第二種方法中，在程序運行過程中很難找出此時哪些存儲空間是空閑的。解決這個問題的辦法是：找當前正在被占用的存儲空間，只需要從當前正在工作的指針變量出發(fā)依次遍歷，就可以找到當前正在被占用的存儲空間，剩余的自然就是此時處于空閑狀態(tài)的存儲空間。
如果想使用第二種方式，可以分為兩步進行：
- 對所有當前正在使用的存儲空間加上被占用的標記（對于廣義表來說，可以在每個結(jié)點結(jié)構(gòu)的基礎(chǔ)上，添加一個 mark 的標志域。在初始狀態(tài)下，所有的存儲空間全部標志為 0，被占用時標記為 1）；
- 依次遍歷所有的存儲空間，將所有標記為 0 的存儲空間鏈接成一個新的可利用空間表。
對正在被占用的存儲空間進行標記的方法有三種：
- 從當前正在工作的指針變量開始，采用遞歸算法依次將所有表中的存儲結(jié)點中的標志域全部設(shè)置為 1；
- 第一種方法中使用遞歸算法實現(xiàn)的遍歷。而遞歸底層使用的棧的存儲結(jié)構(gòu)，所以也可以直接使用棧的方式進行遍歷；
- 以上兩種方法都是使用棧結(jié)構(gòu)來記錄遍歷時指針所走的路徑，便于在后期可以沿原路返回。所以第三種方式就是使用其他的方法代替棧的作用。
遞歸和非遞歸方式在前面章節(jié)做過詳細介紹，第三種實現(xiàn)方式中代替棧的方法是：添加三個指針，p 指針指向當前遍歷的結(jié)點，t 指針永遠指向 p 的父結(jié)點，q 指向 p 結(jié)點的表頭或者表尾結(jié)點。在遍歷過程遵循以下原則：
當 q 指針指向 p 的表頭結(jié)點時，可能出現(xiàn) 3 種情況：
- p 結(jié)點的表頭結(jié)點只是一個元素結(jié)點，沒有表頭或者表尾，這時只需要對該表頭結(jié)點打上標記后即 q 指向 p 的表尾；
- p 結(jié)點的表頭結(jié)點是空表或者是已經(jīng)做過標記的子表，這時直接令 q 指針指向 p 結(jié)點的表尾即可；
- p 結(jié)點的表頭是未添加標記的子表，這時就需要遍歷子表，令 p 指向 q，q 指向 q 的表頭結(jié)點。同時 t 指針相應(yīng)地往下移動，但是在移動之前需要記錄 t 指針的移動軌跡。記錄的方法就是令 p 結(jié)點的 hp 域指向 t，同時設(shè)置 tag 值為 0。
當 q 指針指向 p 的表尾結(jié)點時，可能出現(xiàn) 2 種情況：
- p 指針的表尾是未加標記的子表，就需要遍歷該子表，和之前的類似，令 p 指針和 t 指針做相應(yīng)的移動，在移動之前記錄 t 指針的移動路徑，方法是：用 p 結(jié)點的 tp 域指向 t 結(jié)點，然后在 t 指向 p，p 指向 q。
- p 指針的表尾如果是空表或者已經(jīng)做過標記的結(jié)點，這時 p 結(jié)點和 t 結(jié)點都回退到上一個位置。
由于 t 結(jié)點的回退路徑分別記錄在結(jié)點的 hp 域或者 tp 域中，在回退時需要根據(jù) tag 的值來判斷：如果 tag 值為 0 ，t 結(jié)點通過指向自身 hp 域的結(jié)點進行回退；反之，t 結(jié)點通過指向其 tp 域的結(jié)點進行回退。
圖 2 待遍歷的廣義表
例如，圖 2 中為一個待遍歷的廣義表，其中每個結(jié)點的結(jié)構(gòu)如圖 3 所示：
?
圖 3 廣義表中各結(jié)點的結(jié)構(gòu)
在遍歷如圖 2 中的廣義表時，從廣義表的 a 結(jié)點開始，則 p 指針指向結(jié)點 a，同時 a 結(jié)點中 mark 域設(shè)置為 1，表示已經(jīng)遍歷過，t 指針為 nil，q 指針指向 a 結(jié)點的表頭結(jié)點，初始狀態(tài)如圖 4 所示：
?
圖 4 遍歷廣義表的初始狀態(tài)
由于 q 指針指向的結(jié)點 b 的 tag 值為 1，表示該結(jié)點為表結(jié)構(gòu)，所以此時 p 指向 q，q 指向結(jié)點 c，同時 t 指針下移，在 t 指針指向結(jié)點 a 之前，a 結(jié)點中的 hp 域指向 t，同時 a 結(jié)點中 tag 值設(shè)為 0。效果如圖 5 所示：
?
圖 5 遍歷廣義表（2）
?
通過 q 指針指向的結(jié)點 c 的 tag=1，判斷該結(jié)點為表結(jié)點，同樣 p 指針指向 c，q 指針指向 d，同時 t 指針繼續(xù)下移，在 t 指針指向 結(jié)點 b 之前，b 結(jié)點的 tag 值更改為 0，同時 hp 域指向結(jié)點 a，效果圖如圖 6 所示：
?
圖 6 遍歷廣義表（3）
通過 q 指針指向的結(jié)點 d 的 tag=0，所以，該結(jié)點為原子結(jié)點，此時根據(jù)遵循的原則，只需要將 q 指針指向的結(jié)點 d 的 mark 域標記為 1，然后讓 q 指針直接指向 p 指針指向結(jié)點的表尾結(jié)點，效果圖如圖 7 所示：
?
圖 7 遍歷廣義表（4）
?
當 q 指針指向 p 指針的表尾結(jié)點時，同時 q 指針為空，這種情況的下一步操作為 p 指針和 t 指針全部上移動，即 p 指針指向結(jié)點 b，同時 t 指針根據(jù) b 結(jié)點的 hp 域回退到結(jié)點 a。同時由于結(jié)點 b 的tag 值為 0，證明之前遍歷的是表頭，所以還需要遍歷 b 結(jié)點的表尾結(jié)點，同時將結(jié)點 b 的 tag 值改為 1。效果圖如圖 8 所示：
?
圖 8 遍歷廣義表（5）
?
由于 q 指針指向的 e 結(jié)點為表結(jié)點，根據(jù) q 指針指向的 e 結(jié)點是 p 指針指向的 b 結(jié)點的表尾結(jié)點，所以所做的操作為：p 指針和 t 指針在下移之前，令 p 指針指向的結(jié)點 b 的 tp 域指向結(jié)點 a，然后給 t 賦值 p，p 賦值 q。q 指向 q 的表頭結(jié)點 f。效果如圖 9 所示：
?
圖 9 遍歷廣義表（6）
由于 q 指針指向的結(jié)點 f 為原子結(jié)點，所以直接 q 指針的 mark 域設(shè)為 1 后，直接令 q 指針指向 p 指針指向的 e 結(jié)點的表尾結(jié)點。效果如圖 10 所示：
?
圖 10 遍歷廣義表（7）
?
由于 p 指針指向的 e 結(jié)點的表尾結(jié)點為空，所以 p 指針和 t 指針都回退。由于 p 指針指向的結(jié)點 b 的 tag 值為 1，表明表尾已經(jīng)遍歷完成，所以 t 指針和 p 指針繼續(xù)上移，最終遍歷完成。
總結(jié)
無用單元的收集可以采用以上 3 中算法中任何一種。無論使用哪種算法，無用單元收集本身都是很費時間的，所以無用單元的收集不適用于實時處理的情況中使用。
內(nèi)存緊縮（內(nèi)存碎片化處理）
前邊介紹的有關(guān)動態(tài)內(nèi)存管理的方法，無論是邊界標識法還是伙伴系統(tǒng)，但是以將空閑的存儲空間鏈接成一個鏈表，即可利用空間表，對存儲空間進行分配和回收。
本節(jié)介紹另外一種動態(tài)內(nèi)存管理的方法，使用這種方式在整個內(nèi)存管理過程中，不管哪個時間段，所有未被占用的空間都是地址連續(xù)的存儲區(qū)。
這些地址連續(xù)的未被占用的存儲區(qū)在編譯程序中稱為堆。
圖 1 存儲區(qū)狀態(tài)
假設(shè)存儲區(qū)的初始狀態(tài)如圖 1 所示，若采用本節(jié)介紹的方法管理這塊存儲區(qū)，當 B 占用塊運行完成同時所占的存儲空間釋放后，存儲區(qū)的狀態(tài)應(yīng)如圖 2 所示：
?
圖 2 更新后的存儲區(qū)狀態(tài)
分配內(nèi)存空間
在分配內(nèi)存空間時，每次都從可利用空間中選擇最低（或者最高）的地址進行分配。具體的實現(xiàn)辦法為：設(shè)置一個指針（稱為堆指針），每次用戶申請存儲空間時，都是堆的最低（或者最高）地址進行分配。假設(shè)當用戶申請 N 個單位的存儲空間時，堆指針向高地址（或者低地址）移動 N 個存儲單位，這 N 個存儲單位即為分配給用戶使用的空閑塊，空閑塊的起始地址為堆指針移動之前所在的地址。
例如，某一時間段有四個用戶（A、B、C、D）分別申請 12 個單位、6 個單位、10 個單位和 8 個單位的存儲空間，假設(shè)此時堆指針的初值為 0。則分配后存儲空間的效果為：
回收算法
由于系統(tǒng)中的可利用空間始終都是一個連續(xù)的存儲空間，所以回收時必須將用戶釋放的存儲塊合并到這個堆上才能夠重新使用。
存儲緊縮有兩種做法：
- 其一是一旦用戶釋放所占空間就立即進行回收緊縮；
- 另外一種是在程序執(zhí)行過程中不立即回收用戶釋放的存儲塊，而是等到可利用空間不夠分配或者堆指針指向了可利用存儲區(qū)的最高地址時才進行存儲緊縮。
具體的實現(xiàn)過程是：
- 計算占用塊的新地址。設(shè)立兩個指針隨巡查向前移動，分別用于指示占用塊在緊縮之前和之后的原地址和新地址。因此，在每個占用塊的第一個存儲單位中，除了存儲該占用塊的大小和標志域之外，還需要新增一個新地址域，用于存儲占用塊在緊縮后應(yīng)有的新地址，即建立一張新、舊地址的對照表。
- 修改用戶的出事變量表，保證在進行存儲緊縮后，用戶還能找到自己的占用塊。
- 檢查每個占用塊中存儲的數(shù)據(jù)。如果有指向其它存儲塊的指針，則需作相應(yīng)修改。
- 將所有占用塊遷移到新地址去，即進行數(shù)據(jù)的傳遞。
最后，還要將堆指針賦以新的值。
總結(jié)
存儲緊縮較之無用單元收集更為復雜，是一個系統(tǒng)的操作，如果不是非不得已不建議使用。