?

目錄

數(shù)據(jù)結(jié)構(gòu)之動(dòng)態(tài)內(nèi)存管理機(jī)制

占用塊和空閑塊

系統(tǒng)的內(nèi)存管理

可利用空間表

分配存儲空間的方式

空間分配與回收過程產(chǎn)生的問題

邊界標(biāo)識法管理動(dòng)態(tài)內(nèi)存

分配算法

回收算法

伙伴系統(tǒng)管理動(dòng)態(tài)內(nèi)存

可利用空間表中結(jié)點(diǎn)構(gòu)成

分配算法

回收算法

總結(jié)

無用單元收集（垃圾回收機(jī)制）

總結(jié)

內(nèi)存緊縮（內(nèi)存碎片化處理）

分配內(nèi)存空間

回收算法

總結(jié)

數(shù)據(jù)結(jié)構(gòu)之動(dòng)態(tài)內(nèi)存管理機(jī)制

通過前面的學(xué)習(xí)，介紹很多具體的數(shù)據(jù)結(jié)構(gòu)的存儲以及遍歷的方式，過程中只是很表面地介紹了數(shù)據(jù)的存儲，而沒有涉及到更底層的有關(guān)的存儲空間的分配與回收，從本節(jié)開始將做更深入地介紹。

在使用早期的計(jì)算機(jī)上編寫程序時(shí)，有關(guān)數(shù)據(jù)存儲在什么位置等這樣的問題都是需要程序員自己來給數(shù)據(jù)分配內(nèi)存。而現(xiàn)在的高級語言，大大的減少了程序員的工作，不需要直接和存儲空間打交道，程序在編譯時(shí)由編譯程序去合理地分配空間。

本章重點(diǎn)解決的問題是：

• 對于用戶向系統(tǒng)提出的申請空間的請求，系統(tǒng)如何分配內(nèi)存？
• 當(dāng)用戶不在使用之前申請的內(nèi)存空間后，系統(tǒng)又如何回收？

這里的用戶，不是普通意義上的用戶，可能是一個(gè)普通的變量，一個(gè)應(yīng)用程序，一個(gè)命令等等。只要是向系統(tǒng)發(fā)出內(nèi)存申請的，都可以稱之為用戶。

占用塊和空閑塊

對于計(jì)算機(jī)中的內(nèi)存來說，稱已經(jīng)分配給用戶的的內(nèi)存區(qū)統(tǒng)稱為“占用塊”；還未分配出去的內(nèi)存區(qū)統(tǒng)稱為“空閑塊”或者“可利用空間塊”。

系統(tǒng)的內(nèi)存管理

對于初始狀態(tài)下的內(nèi)存來說，整個(gè)空間都是一個(gè)空閑塊（在編譯程序中稱為“堆”）。但是隨著不同的用戶不斷地提出存儲請求，系統(tǒng)依次分配。

整個(gè)內(nèi)存區(qū)就會(huì)分割成兩個(gè)大部分：低地址區(qū)域會(huì)產(chǎn)生很多占用塊；高地址區(qū)域還是空閑塊。如圖 1 所示：
?

圖 1 動(dòng)態(tài)分配過程中的內(nèi)存狀態(tài)

但是當(dāng)某些用戶運(yùn)行結(jié)束，所占用的內(nèi)存區(qū)域就變成了空閑塊，如圖 2 所示：
?

圖 2 動(dòng)態(tài)分配過程中的內(nèi)存變化

此時(shí)，就形成了占用塊和空閑塊犬牙交錯(cuò)的狀態(tài)。當(dāng)后續(xù)用戶請求分配內(nèi)存時(shí)，系統(tǒng)有兩種分配方式：
?

1. 系統(tǒng)繼續(xù)利用高地址區(qū)域的連續(xù)空閑塊分配給用戶，不去理會(huì)之前分配給用戶的內(nèi)存區(qū)域的狀態(tài)。直到分配無法進(jìn)行，也就是高地址的空閑塊不能滿足用戶的需求時(shí)，系統(tǒng)才會(huì)去回收之前的空閑塊，重新組織繼續(xù)分配；
2. 當(dāng)用戶運(yùn)行一結(jié)束，系統(tǒng)馬上將其所占空間進(jìn)行回收。當(dāng)有新的用戶請求分配內(nèi)存時(shí)，系統(tǒng)遍歷所有的空閑塊，從中找出一個(gè)合適的空閑塊分配給用戶。

合適的空閑塊指的是能夠滿足用戶要求的空閑塊，具體的查找方式有多種，后續(xù)會(huì)介紹。

可利用空間表

當(dāng)采用第 2 種方式時(shí)，系統(tǒng)需要建立一張記錄所有空閑塊信息的表。表的形式有兩種：目錄表和鏈表。各自的結(jié)構(gòu)如圖 3 所示：
?

圖 3 目錄表和鏈表

目錄表：表中每一行代表一個(gè)空閑塊，由三部分組成：
?

• 初始地址：記錄每個(gè)空閑塊的起始地址。
• 空閑塊大?。河涗浢總€(gè)空閑塊的內(nèi)存大小。
• 使用情況：記錄每個(gè)空閑塊是否存儲被占用的狀態(tài)。

鏈表：表中每個(gè)結(jié)點(diǎn)代表一個(gè)空閑塊，每個(gè)結(jié)點(diǎn)中需要記錄空閑塊的使用情況、大小和連接下一個(gè)空閑塊的指針域。

由于鏈表中有指針的存在，所以結(jié)點(diǎn)中不需要記錄各內(nèi)存塊的起始地址。

系統(tǒng)在不同的環(huán)境中運(yùn)行，根據(jù)用戶申請空間的不同，存儲空閑塊的可利用空間表有以下不同的結(jié)構(gòu)：
?

1. 如果每次用戶請求的存儲空間大小相同，對于此類系統(tǒng)中的內(nèi)存來說，在用戶運(yùn)行初期就將整個(gè)內(nèi)存存儲塊按照所需大小進(jìn)行分割，然后通過鏈表鏈接。當(dāng)用戶申請空間時(shí)，從鏈表中摘除一個(gè)結(jié)點(diǎn)歸其使用；用完后再鏈接到可利用空間表上。
2. 每次如果用戶申請的都是若干種大小規(guī)格的存儲空間，針對這種情況可以建立若干個(gè)可利用空間表，每一個(gè)鏈表中的結(jié)點(diǎn)大小相同。當(dāng)用戶申請某一規(guī)格大小的存儲空間時(shí)，就從對應(yīng)的鏈表中摘除一個(gè)結(jié)點(diǎn)供其使用；用完后鏈接到相同規(guī)格大小的鏈表中。
3. 用戶申請的內(nèi)存的大小不固定，所以造成系統(tǒng)分配的內(nèi)存塊的大小也不確定，回收時(shí)，鏈接到可利用空間表中每個(gè)結(jié)點(diǎn)的大小也各不一樣。

第 2 種情況下容易面臨的問題是：如果同用戶申請空間大小相同的鏈表中沒有結(jié)點(diǎn)時(shí)，就需要找結(jié)點(diǎn)更大的鏈表，從中取出一個(gè)結(jié)點(diǎn)，一部分給用戶使用，剩余部分插入到相應(yīng)大小的鏈表中；回收時(shí)，將釋放的空閑塊插入到大小相同的鏈表中去。如果沒有比用戶申請的內(nèi)存空間相等甚至更大的結(jié)點(diǎn)時(shí)，就需要系統(tǒng)重新組織一些小的連續(xù)空間，然后給用戶使用。

分配存儲空間的方式

通常情況下系統(tǒng)中的可利用空間表是第 3 種情況。如圖 3(C) 所示。由于鏈表中各結(jié)點(diǎn)的大小不一，在用戶申請內(nèi)存空間時(shí)，就需要從可利用空間表中找出一個(gè)合適的結(jié)點(diǎn)，有三種查找的方法：
?

• 首次擬合法：在可利用空間表中從頭開始依次遍歷，將找到的第一個(gè)內(nèi)存不小于用戶申請空間的結(jié)點(diǎn)分配給用戶，剩余空間仍留在鏈表中；回收時(shí)只要將釋放的空閑塊插入在鏈表的表頭即可。
• 最佳擬合法：和首次擬合法不同，最佳擬合法是選擇一塊內(nèi)存空間不小于用戶申請空間，但是卻最接近的一個(gè)結(jié)點(diǎn)分配給用戶。為了實(shí)現(xiàn)這個(gè)方法，首先要將鏈表中的各個(gè)結(jié)點(diǎn)按照存儲空間的大小進(jìn)行從小到大排序，由此，在遍歷的過程中只需要找到第一塊大于用戶申請空間的結(jié)點(diǎn)即可進(jìn)行分配；用戶運(yùn)行完成后，需要將空閑塊根據(jù)其自身的大小插入到鏈表的相應(yīng)位置。
• 最差擬合法：和最佳擬合法正好相反，該方法是在不小于用戶申請空間的所有結(jié)點(diǎn)中，篩選出存儲空間最大的結(jié)點(diǎn)，從該結(jié)點(diǎn)的內(nèi)存空間中提取出相應(yīng)的空間給用戶使用。為了實(shí)現(xiàn)這一方法，可以在開始前先將可利用空間表中的結(jié)點(diǎn)按照存儲空間大小從大到小進(jìn)行排序，第一個(gè)結(jié)點(diǎn)自然就是最大的結(jié)點(diǎn)。回收空間時(shí)，同樣將釋放的空閑塊插入到相應(yīng)的位置上。

以上三種方法各有所長：
?

• 最佳擬合法由于每次分配相差不大的結(jié)點(diǎn)給用戶使用，所以會(huì)生成很多存儲空間特別小的結(jié)點(diǎn)，以至于根本無法使用，使用過程中，鏈表中的結(jié)點(diǎn)存儲大小發(fā)生兩極分化，大的很大，小的很小。該方法適用于申請內(nèi)存大小范圍較廣的系統(tǒng)
• 最差擬合法，由于每次都是從存儲空間最大的結(jié)點(diǎn)中分配給用戶空間，所以鏈表中的結(jié)點(diǎn)大小不會(huì)起伏太大。依次適用于申請分配內(nèi)存空間較窄的系統(tǒng)。
• 首次擬合法每次都是隨機(jī)分配。在不清楚用戶申請空間大小的情況下，使用該方法分配空間。

同時(shí)，三種方法中，最佳擬合法相比于其它兩種方式，無論是分配過程還是回收過程，都需要遍歷鏈表，所有最費(fèi)時(shí)間。

空間分配與回收過程產(chǎn)生的問題

無論使用以上三種分配方式中的哪一種，最終內(nèi)存空間都會(huì)成為一個(gè)一個(gè)特別小的內(nèi)存空間，對于用戶申請的空間的需求，單獨(dú)拿出任何一個(gè)結(jié)點(diǎn)都不能夠滿足。

但是并不是說整個(gè)內(nèi)存空間就不夠用戶使用。在這種情況下，就需要系統(tǒng)在回收的過程考慮將地址相鄰的空閑塊合并。

邊界標(biāo)識法管理動(dòng)態(tài)內(nèi)存

在使用邊界標(biāo)識法的系統(tǒng)管理內(nèi)存時(shí)，可利用空間表中的結(jié)點(diǎn)的構(gòu)成如圖 1：
?

圖 1 結(jié)構(gòu)構(gòu)成

每個(gè)結(jié)點(diǎn)中包含 3 個(gè)區(qū)域，head 域、foot 域?和?space 域：
?

• space 域表示為該內(nèi)存塊的大小，它的大小通過 head 域中的 size 值表示。
• head 域中包含有 4 部分：llink?和?rlink?分別表示指向當(dāng)前內(nèi)存塊結(jié)點(diǎn)的直接前驅(qū)和直接后繼。tag 值用于標(biāo)記當(dāng)前內(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è)只占用當(dāng)前存儲塊的 1 個(gè)存儲單位的空間，對于該結(jié)點(diǎn)整個(gè)存儲空間來說，可以忽略不計(jì)。也就是說，在可利用空間表中，知道下一個(gè)結(jié)點(diǎn)的首地址，該值減 1 就可以找到當(dāng)前結(jié)點(diǎn)的 foot 域。

使用邊界標(biāo)識法的可利用空間表本身是雙向循環(huán)鏈表，每個(gè)內(nèi)存塊結(jié)點(diǎn)都有指向前驅(qū)和后繼結(jié)點(diǎn)的指針域。

所以，邊界標(biāo)識法管理的內(nèi)存塊結(jié)點(diǎn)的代碼表示為：

1. typedef struct WORD{
2. union{
3. struct WORD *llink;//指向直接前驅(qū)
4. struct WORD *uplink;//指向結(jié)點(diǎn)本身
5. };
6. int tag;//標(biāo)記域,0表示為空閑塊；1表示為占用塊
7. int size;//記錄內(nèi)存塊的存儲大小
8. struct WORD *rlink;//指向直接后繼
9. OtherType other;//內(nèi)存塊可能包含的其它的部分
10. }WORD,head,foot,*Space;

通過以上介紹的結(jié)點(diǎn)結(jié)構(gòu)構(gòu)建的可利用空間表中，任何一個(gè)結(jié)點(diǎn)都可以作為該鏈表的頭結(jié)點(diǎn)（用 pav 表示頭結(jié)點(diǎn)），當(dāng)頭結(jié)點(diǎn)為 NULL 時(shí)，即可利用空間表為空，無法繼續(xù)分配空間。

分配算法

當(dāng)用戶申請空間時(shí)，系統(tǒng)可以采用 3 種分配方法中的任何一種。但在不斷地分配的過程中，會(huì)產(chǎn)生一些容量極小以至無法利用的空閑塊，這些不斷生成的小內(nèi)存塊就會(huì)減慢遍歷分配的速度。

3 種分配方法分別為：首部擬合法、最佳擬合法和最差擬合法。

針對這種情況，解決的措施是：

1. 選定一個(gè)常量 e，每次分配空間時(shí)，判斷當(dāng)前內(nèi)存塊向用戶分配空間后，如果剩余部分的容量比 e 小，則將整個(gè)內(nèi)存塊全部分配給用戶。
2. 采用頭部擬合法進(jìn)行分配時(shí)，如果每次都從 pav 指向的結(jié)點(diǎn)開始遍歷，在若干次后，會(huì)出現(xiàn)存儲量小的結(jié)點(diǎn)密集地分布在 pav 結(jié)點(diǎn)附近的情況，嚴(yán)重影響遍歷的時(shí)間。解決辦法就是：在每次分配空間后，讓 pav 指針指向該分配空間結(jié)點(diǎn)的后繼結(jié)點(diǎn)，然后從新的 pav 指向的結(jié)點(diǎn)開始下一次的分配。

分配算法的具體實(shí)現(xiàn)代碼為（采用首部擬合法）

1. Space AllocBoundTag(Space *pav,int n){
2. Space p,f;
3. int e=10;//設(shè)定常亮 e 的值
4. //如果在遍歷過程，當(dāng)前空閑塊的在存儲容量比用戶申請空間 n 值小，在該空閑塊有右孩子的情況下直接跳過
5. for (p=(*pav); p&&p->size<n&&p->rlink!=(*pav); p=p->rlink);
6. //跳出循環(huán)，首先排除p為空和p指向的空閑塊容量小于 n 的情況
7. if (!p ||p->size<n) {
8. return NULL;
9. }else{
10. //指針f指向p空閑塊的foot域
11. f=FootLoc(p);
12. //調(diào)整pav指針的位置，為下次分配做準(zhǔn)備
13. (*pav)=p->rlink;
14. //如果該空閑塊的存儲大小比 n 大，比 n+e 小，負(fù)責(zé)第一種情況，將 p 指向的空閑塊全部分配給用戶
15. if (p->size-n <= e) {
16. if ((*pav)==p) {
17. pav=NULL;
18. }
19. else{
20. //全部分配用戶，即從可利用空間表中刪除 p 空閑塊
21. (*pav)->llink=p->llink;
22. p->llink->rlink=(*pav);
23. }
24. //同時(shí)調(diào)整head域和foot域中的tag值
25. p->tag=f->tag=1;
26. }
27. //否則，從p空閑塊中拿出 大小為 n 的連續(xù)空間分配給用戶，同時(shí)更新p剩余存儲塊中的信息。
28. else{
29. //更改分配塊foot域的信息
30. f->tag=1;
31. p->size-=n;
32. //f指針指向剩余空閑塊 p 的底部
33. f=FootLoc(p);
34. f->tag=0; f->uplink=p;
35. p=f+1;//p指向的是分配給用戶的塊的head域，也就是該塊的首地址
36. p->tag=1; p->size=n;
37. }
38. return p;
39. }
40. }

回收算法

在用戶活動(dòng)完成，系統(tǒng)需要立即回收被用戶占用的存儲空間，以備新的用戶使用。回收算法中需要解決的問題是：在若干次分配操作后，可利用空間塊中會(huì)產(chǎn)生很多存儲空間很小以致無法使用的空閑塊。但是經(jīng)過回收用戶釋放的空間后，可利用空間表中可能含有地址相鄰的空閑塊，回收算法需要將這些地址相鄰的空閑塊合并為大的空閑塊供新的用戶使用。

合并空閑塊有 3 種情況：

• 該空閑塊的左邊有相鄰的空閑塊可以進(jìn)行合并；
• 該空閑塊的右邊用相鄰的空閑塊可以進(jìn)行合并；
• 該空閑塊的左右兩側(cè)都有相鄰的空閑塊可以進(jìn)行合并；

判斷當(dāng)前空閑塊左右兩側(cè)是否為空閑塊的方法是：對于當(dāng)前空閑塊 p ，p-1 就是相鄰的低地址處的空閑塊的 foot 域，如果 foot 域中的 tag 值為 0 ，表明其為空閑塊； p+p->size 表示的是高地址處的塊的 head 域，如果 head 域中的 tag 值為 0，表明其為空閑塊。

如果當(dāng)前空閑塊的左右兩側(cè)都不是空閑塊，而是占用塊，此種情況下只需要將新的空閑塊按照相應(yīng)的規(guī)則（頭部擬合法隨意插入，其它兩種方法在對應(yīng)位置插入）插入到可利用空間表中即可。實(shí)現(xiàn)代碼為：

1. //設(shè)定p指針指向的為用戶釋放的空閑塊
2. p->tag=0;
3. //f指針指向p空閑塊的foot域
4. Space f=FootLoc(p);
5. f->uplink=p;
6. f->tag=0;
7. //如果pav指針不存在，證明可利用空間表為空，此時(shí)設(shè)置p為頭指針，并重新建立雙向循環(huán)鏈表
8. if (!pav) {
9. pav=p->llink=p->rlink=p;
10. }else{
11. //否則，在p空閑塊插入到pav指向的空閑塊的左側(cè)
12. Space q=pav->llink;
13. p->rlink=pav;
14. p->llink=q;
15. q->rlink=pav->llink=p;
16. pav=p;
17. }

如果該空閑塊的左側(cè)相鄰的塊為空閑塊，右側(cè)為占用塊，處理的方法是：只需要更改左側(cè)空閑塊中的 size 的大小，并重新設(shè)置左側(cè)空閑塊的 foot 域即可（如圖 2）。

?

圖 2 空閑塊合并（當(dāng)前塊，左側(cè)內(nèi)存塊）

實(shí)現(xiàn)代碼為：

1. //常量 n 表示當(dāng)前空閑塊的存儲大小
2. int n=p->size;
3. Space s=(p-1)->uplink;//p-1 為當(dāng)前塊的左側(cè)塊的foot域，foot域中的uplink指向的就是左側(cè)塊的首地址，s指針代表的是當(dāng)前塊的左側(cè)存儲塊
4. s->size+=n;//設(shè)置左側(cè)存儲塊的存儲容量
5. Space f=p+n-1;//f指針指向的是空閑塊 p 的foot域
6. f->uplink=s;//這是foot域的uplink指針重新指向合并后的存儲空間的首地址
7. f->tag=0;//設(shè)置foot域的tag標(biāo)記為空閑塊

如果用戶釋放的內(nèi)存塊的相鄰左側(cè)為占用塊，右側(cè)為空閑塊，處理的方法為：將用戶釋放掉的存儲塊替換掉右側(cè)的空閑塊，同時(shí)更改存儲塊的 size 和右側(cè)空閑塊的 uplink 指針的指向（如圖 3 所示）。

?

圖 3 空閑塊合并（當(dāng)前塊、右側(cè)內(nèi)存塊）

實(shí)現(xiàn)代碼為：

1. Space t=p+p->size;//t指針指向右側(cè)空閑塊的首地址
2. p->tag=0;//初始化head域的tag值為0
3. //找到t右側(cè)空閑塊的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，用當(dāng)前釋放的空閑塊替換右側(cè)空閑塊
4. Space q=t->llink;
5. p->llink=q; q->rlink=p;
6. Space q1=t->rlink;
7. p->rlink=q1; q1->llink=p;
8. //更新釋放塊的size的值
9. p->size+=t->size;
10. //更改合并后的foot域的uplink指針的指向
11. Space f=FootLoc(t);
12. f->uplink=p;

如果當(dāng)前用戶釋放掉的空閑塊，物理位置上相鄰的左右兩側(cè)的內(nèi)存塊全部為空閑塊，需要將 3 個(gè)空閑塊合并為一個(gè)更大的塊，操作的過程為：更新左側(cè)空閑塊的 size 的值，同時(shí)在可利用空間表中摘除右側(cè)空閑塊，最后更新合并后的大的空閑塊的 foot 域。

此情況和只有左側(cè)有空閑塊的情況雷同，唯一的不同點(diǎn)是多了一步摘除右側(cè)相鄰空閑塊結(jié)點(diǎn)的操作。

實(shí)現(xiàn)代碼為：

純文本復(fù)制

1. int n=p->size;
2. Space s=(p-1)->uplink;//找到釋放內(nèi)存塊物理位置相鄰的低地址的空閑塊
3. Space t=p+p->size;//找到物理位置相鄰的高地址處的空閑塊
4. s->size+=n+t->size;//更新左側(cè)空閑塊的size的值
5. //從可利用空間表中摘除右側(cè)空閑塊
6. Space q=t->llink;
7. Space q1=t->rlink;
8. q->rlink=q1;
9. q1->llink=q;
10. //更新合并后的空閑塊的uplink指針的指向
11. Space f=FootLoc(t);
12. f->uplink=s;

伙伴系統(tǒng)管理動(dòng)態(tài)內(nèi)存

伙伴系統(tǒng)本身是一種動(dòng)態(tài)管理內(nèi)存的方法，和邊界標(biāo)識法的區(qū)別是：使用伙伴系統(tǒng)管理的存儲空間，無論是空閑塊還是占用塊，大小都是 2 的 n 次冪（n 為正整數(shù)）。

例如，系統(tǒng)中整個(gè)存儲空間為 2m?個(gè)字。那么在進(jìn)行若干次分配與回收后，可利用空間表中只可能包含空間大小為：20、21、22、…、2m?的空閑塊。

字是一種計(jì)量單位，由若干個(gè)字節(jié)構(gòu)成，不同位數(shù)的機(jī)器，字所包含的字節(jié)數(shù)不同。例如，8 位機(jī)中一個(gè)字由 1 個(gè)字節(jié)組成；16 位機(jī)器一個(gè)字由 2 個(gè)字節(jié)組成。

可利用空間表中結(jié)點(diǎn)構(gòu)成

伙伴系統(tǒng)中可利用空間表中的結(jié)點(diǎn)構(gòu)成如圖 1 所示：
?

圖 1 結(jié)點(diǎn)構(gòu)成

header 域表示為頭部結(jié)點(diǎn)，由 4 部分構(gòu)成：

• llink 和 rlink 為結(jié)點(diǎn)類型的指針域，分別用于指向直接前驅(qū)和直接后繼結(jié)點(diǎn)。
• tag 值：用于標(biāo)記內(nèi)存塊的狀態(tài)，是占用塊（用 1 表示）還是空閑塊（用 0 表示）
• kval ：記錄該存儲塊的容量。由于系統(tǒng)中各存儲塊都是 2 的 m 冪次方，所以 kval 記錄 m 的值。

代碼表示為：

1. typedef struct WORD_b{
2. struct WORD_b *llink;//指向直接前驅(qū)
3. int tag;//記錄該塊是占用塊還是空閑塊
4. int kval;//記錄該存儲塊容量大小為2的多少次冪
5. struct WORD_b *rlink;//指向直接后繼
6. OtherType other;//記錄結(jié)點(diǎn)的其它信息
7. }WORD_b,head;

在伙伴系統(tǒng)中，由于系統(tǒng)會(huì)不斷地接受用戶的內(nèi)存申請的請求，所以會(huì)產(chǎn)生很多大小不同但是都是容量為 2m?的內(nèi)存塊，所以為了在分配的時(shí)候查找方便，系統(tǒng)采用將大小相同的各自建立一個(gè)鏈表。對于初始容量為 2m?的一整塊存儲空間來說，形成的鏈表就有可能有 m+1 個(gè)，為了更好的對這些鏈表進(jìn)行管理，系統(tǒng)將這 m+1 個(gè)鏈表的表頭存儲在數(shù)組中，就類似于鄰接表的結(jié)構(gòu)，如圖 2。

?

圖 2 伙伴系統(tǒng)的初始狀態(tài)

可利用空間表的代碼表示為：

1. #define m 16//設(shè)定m的初始值
2. typedef struct HeadNode {
3. int nodesize;//記錄該鏈表中存儲的空閑塊的大小
4. WORD_b * first;//相當(dāng)于鏈表中的next指針的作用
5. }FreeList[m+1];//一維數(shù)組

分配算法

伙伴系統(tǒng)的分配算法很簡單。假設(shè)用戶向系統(tǒng)申請大小為 n 的存儲空間，若 2k-1?< n <= 2k，此時(shí)就需要查看可利用空間表中大小為 2k?的鏈表中有沒有可利用的空間結(jié)點(diǎn)：

• 如果該鏈表不為 NULL，可以直接采用頭插法從頭部取出一個(gè)結(jié)點(diǎn)，提供給用戶使用；
• 如果大小為 2k?的鏈表為 NULL，就需要依次查看比 2k?大的鏈表，找到后從鏈表中刪除，截取相應(yīng)大小的空間給用戶使用，剩余的空間，根據(jù)大小插入到相應(yīng)的鏈表中。

例如，用戶向系統(tǒng)申請一塊大小為 7 個(gè)字的空間，而系統(tǒng)總的內(nèi)存為 24?個(gè)字，則此時(shí)按照伙伴系統(tǒng)的分配算法得出：22?< 7 < 23，所以此時(shí)應(yīng)查看可利用空間表中大小為 23?的鏈表中是否有空閑結(jié)點(diǎn)：

• 如果有，則從該鏈表中摘除一個(gè)結(jié)點(diǎn)，直接分配給用戶使用；
• 如果沒有，則需依次查看比 23?大的各個(gè)鏈表中是否有空閑結(jié)點(diǎn)。假設(shè)，在大小 24?的鏈表中有空閑塊，則摘除該空閑塊，分配給用戶 23?個(gè)字的空間，剩余 23?個(gè)字，該剩余的空閑塊添加到大小為 23?的鏈表中。

（A）分配前?????????????????????? （B）分配后
圖 3 伙伴系統(tǒng)分配過程

回收算法

無論使用什么內(nèi)存管理機(jī)制，在內(nèi)存回收的問題上都會(huì)面臨一個(gè)共同的問題：如何把回收的內(nèi)存進(jìn)行有效地整合，伙伴系統(tǒng)也不例外。

當(dāng)用戶申請的內(nèi)存塊不再使用時(shí)，系統(tǒng)需要將這部分存儲塊回收，回收時(shí)需要判斷是否可以和其它的空閑塊進(jìn)行合并。

在尋找合并對象時(shí)，伙伴系統(tǒng)和邊界標(biāo)識法不同，在伙伴系統(tǒng)中每一個(gè)存儲塊都有各自的“伙伴”，當(dāng)用戶釋放存儲塊時(shí)只需要判斷該內(nèi)存塊的伙伴是否為空閑塊，如果是則將其合并，然后合并的新的空閑塊還需要同其伙伴進(jìn)行判斷整合。反之直接將存儲塊根據(jù)大小插入到可利用空間表中即可。

判斷一個(gè)存儲塊的伙伴的位置時(shí)，采用的方法為：如果該存儲塊的起始地址為 p，大小為 2k，則其伙伴所在的起始地址為：

?

?

例如，當(dāng)大小為 28?，起始地址為 512 的伙伴塊的起始地址的計(jì)算方式為：
由于 512 MOD 29=0，所以，512+28=768，及如果該存儲塊回收時(shí)，只需要查看起始地址為 768 的存儲塊的狀態(tài)，如果是空閑塊則兩者合并，反之直接將回收的釋放塊鏈接到大小為 28?的鏈表中。

總結(jié)

使用伙伴系統(tǒng)進(jìn)行存儲空間的管理過程中，在用戶申請空間時(shí)，由于大小不同的空閑塊處于不同的鏈表中，所以分配完成的速度會(huì)更快，算法相對簡單。

回收存儲空間時(shí)，對于空閑塊的合并，不是取決于該空閑塊的相鄰位置的塊的狀態(tài)；而是完全取決于其伙伴塊。

所以即使其相鄰位置的存儲塊時(shí)空閑塊，但是由于兩者不是伙伴的關(guān)系，所以也不會(huì)合并。這也就是該系統(tǒng)的缺點(diǎn)之一：由于在合并時(shí)只考慮伙伴，所以容易產(chǎn)生存儲的碎片。

無用單元收集（垃圾回收機(jī)制）

通過前幾節(jié)對可利用空間表進(jìn)行動(dòng)態(tài)存儲管理的介紹，運(yùn)行機(jī)制可以概括為：

1. 當(dāng)用戶發(fā)出申請空間的請求后，系統(tǒng)向用戶分配內(nèi)存；
2. 用戶運(yùn)行結(jié)束釋放存儲空間后，系統(tǒng)回收內(nèi)存。

這兩部操作都是在用戶給出明確的指令后，系統(tǒng)對存儲空間進(jìn)行有效地分配和回收。

但是在實(shí)際使用過程中，有時(shí)會(huì)因?yàn)橛脩羯暾埩丝臻g，但是在使用完成后沒有向系統(tǒng)發(fā)出釋放的指令，導(dǎo)致存儲空間既沒有被使用也沒有被回收，變?yōu)榱?strong>無用單元或者會(huì)產(chǎn)生懸掛訪問的問題。

什么是無用單元？簡單來講，無用單元是一塊用戶不再使用，但是系統(tǒng)無法回收的存儲空間。例如在C語言中，用戶可以通過 malloc 和 free 兩個(gè)功能函數(shù)來動(dòng)態(tài)申請和釋放存儲空間。當(dāng)用戶使用 malloc 申請的空間使用完成后，沒有使用 free 函數(shù)進(jìn)行釋放，那么該空間就會(huì)成為無用單元。

懸掛訪問也很好理解：假設(shè)使用 malloc 申請了一塊存儲空間，有多個(gè)指針同時(shí)指向這塊空間，當(dāng)其中一個(gè)指針完成使命后，私自將該存儲空間使用 free 釋放掉，導(dǎo)致其他指針處于懸空狀態(tài)，如果釋放掉的空間被再分配后，再通過之前的指針訪問，就會(huì)造成錯(cuò)誤。數(shù)據(jù)結(jié)構(gòu)中稱這種訪問為懸掛訪問。
?

圖 1 含有共享子表的廣義表

在含有共享子表的廣義表中，也可能會(huì)產(chǎn)生無用單元。例如圖 1 中，L1、L2 和 L3 分別為三個(gè)廣義表的表頭指針，L4 為 L1 和 L2 所共享，L3 是 L2 的子表，L5 為 L1、L2 和 L3 三個(gè)廣義表所共享。

在圖 1 的基礎(chǔ)上，假設(shè)表 L1 不再使用，而 L2 和 L3 還在使用，若釋放表 L1，L1 中的所有結(jié)點(diǎn)所占的存儲空間都會(huì)被釋放掉，L2 和 L3 中由于同樣包含 L1 中的結(jié)點(diǎn)，兩個(gè)表會(huì)被破壞，某些指針會(huì)產(chǎn)生懸掛訪問的錯(cuò)誤；

而如果 L1 表使用完成后不及時(shí)釋放，L1 中獨(dú)自占用的結(jié)點(diǎn)由于未被釋放，系統(tǒng)也不會(huì)回收，就會(huì)成為無用單元。

解決存儲空間可能成為無用單元或者產(chǎn)生懸掛訪問的方法有兩個(gè)：

1. 每個(gè)申請的存儲空間設(shè)置一個(gè)計(jì)數(shù)域，這個(gè)計(jì)數(shù)域記錄的是指向該存儲空間的指針數(shù)目，只有當(dāng)計(jì)數(shù)域的值為 0 時(shí)，該存儲空間才會(huì)被釋放。
2. 在程序運(yùn)行時(shí)，所有的存儲空間無論是處于使用還是空閑的狀態(tài)，一律不回收，當(dāng)系統(tǒng)中的可利用空間表為空時(shí)，將程序中斷，對當(dāng)前不在使用狀態(tài)的存儲空間一律回收，全部鏈接成一個(gè)新的可利用空間表后，程序繼續(xù)執(zhí)行。

第一種方法非常簡單，下面主要介紹第二種方法的具體實(shí)現(xiàn)。

第二種方法中，在程序運(yùn)行過程中很難找出此時(shí)哪些存儲空間是空閑的。解決這個(gè)問題的辦法是：找當(dāng)前正在被占用的存儲空間，只需要從當(dāng)前正在工作的指針變量出發(fā)依次遍歷，就可以找到當(dāng)前正在被占用的存儲空間，剩余的自然就是此時(shí)處于空閑狀態(tài)的存儲空間。

如果想使用第二種方式，可以分為兩步進(jìn)行：

• 對所有當(dāng)前正在使用的存儲空間加上被占用的標(biāo)記（對于廣義表來說，可以在每個(gè)結(jié)點(diǎn)結(jié)構(gòu)的基礎(chǔ)上，添加一個(gè) mark 的標(biāo)志域。在初始狀態(tài)下，所有的存儲空間全部標(biāo)志為 0，被占用時(shí)標(biāo)記為 1）；
• 依次遍歷所有的存儲空間，將所有標(biāo)記為 0 的存儲空間鏈接成一個(gè)新的可利用空間表。

對正在被占用的存儲空間進(jìn)行標(biāo)記的方法有三種：

• 從當(dāng)前正在工作的指針變量開始，采用遞歸算法依次將所有表中的存儲結(jié)點(diǎn)中的標(biāo)志域全部設(shè)置為 1；
• 第一種方法中使用遞歸算法實(shí)現(xiàn)的遍歷。而遞歸底層使用的棧的存儲結(jié)構(gòu)，所以也可以直接使用棧的方式進(jìn)行遍歷；
• 以上兩種方法都是使用棧結(jié)構(gòu)來記錄遍歷時(shí)指針?biāo)叩穆窂?，便于在后期可以沿原路返回。所以第三種方式就是使用其他的方法代替棧的作用。

遞歸和非遞歸方式在前面章節(jié)做過詳細(xì)介紹，第三種實(shí)現(xiàn)方式中代替棧的方法是：添加三個(gè)指針，p 指針指向當(dāng)前遍歷的結(jié)點(diǎn)，t 指針永遠(yuǎn)指向 p 的父結(jié)點(diǎn)，q 指向 p 結(jié)點(diǎn)的表頭或者表尾結(jié)點(diǎn)。在遍歷過程遵循以下原則：

當(dāng) q 指針指向 p 的表頭結(jié)點(diǎn)時(shí)，可能出現(xiàn) 3 種情況：

• p 結(jié)點(diǎn)的表頭結(jié)點(diǎn)只是一個(gè)元素結(jié)點(diǎn)，沒有表頭或者表尾，這時(shí)只需要對該表頭結(jié)點(diǎn)打上標(biāo)記后即 q 指向 p 的表尾；
• p 結(jié)點(diǎn)的表頭結(jié)點(diǎn)是空表或者是已經(jīng)做過標(biāo)記的子表，這時(shí)直接令 q 指針指向 p 結(jié)點(diǎn)的表尾即可；
• p 結(jié)點(diǎn)的表頭是未添加標(biāo)記的子表，這時(shí)就需要遍歷子表，令 p 指向 q，q 指向 q 的表頭結(jié)點(diǎn)。同時(shí) t 指針相應(yīng)地往下移動(dòng)，但是在移動(dòng)之前需要記錄 t 指針的移動(dòng)軌跡。記錄的方法就是令 p 結(jié)點(diǎn)的 hp 域指向 t，同時(shí)設(shè)置 tag 值為 0。

當(dāng) q 指針指向 p 的表尾結(jié)點(diǎn)時(shí)，可能出現(xiàn) 2 種情況：

• p 指針的表尾是未加標(biāo)記的子表，就需要遍歷該子表，和之前的類似，令 p 指針和 t 指針做相應(yīng)的移動(dòng)，在移動(dòng)之前記錄 t 指針的移動(dòng)路徑，方法是：用 p 結(jié)點(diǎn)的 tp 域指向 t 結(jié)點(diǎn)，然后在 t 指向 p，p 指向 q。
• p 指針的表尾如果是空表或者已經(jīng)做過標(biāo)記的結(jié)點(diǎn)，這時(shí) p 結(jié)點(diǎn)和 t 結(jié)點(diǎn)都回退到上一個(gè)位置。

由于 t 結(jié)點(diǎn)的回退路徑分別記錄在結(jié)點(diǎn)的 hp 域或者 tp 域中，在回退時(shí)需要根據(jù) tag 的值來判斷：如果 tag 值為 0 ，t 結(jié)點(diǎn)通過指向自身 hp 域的結(jié)點(diǎn)進(jìn)行回退；反之，t 結(jié)點(diǎn)通過指向其 tp 域的結(jié)點(diǎn)進(jìn)行回退。

圖 2 待遍歷的廣義表

例如，圖 2 中為一個(gè)待遍歷的廣義表，其中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)如圖 3 所示：
?

圖 3 廣義表中各結(jié)點(diǎn)的結(jié)構(gòu)

在遍歷如圖 2 中的廣義表時(shí)，從廣義表的 a 結(jié)點(diǎn)開始，則 p 指針指向結(jié)點(diǎn) a，同時(shí) a 結(jié)點(diǎn)中 mark 域設(shè)置為 1，表示已經(jīng)遍歷過，t 指針為 nil，q 指針指向 a 結(jié)點(diǎn)的表頭結(jié)點(diǎn)，初始狀態(tài)如圖 4 所示：
?

圖 4 遍歷廣義表的初始狀態(tài)

由于 q 指針指向的結(jié)點(diǎn) b 的 tag 值為 1，表示該結(jié)點(diǎn)為表結(jié)構(gòu)，所以此時(shí) p 指向 q，q 指向結(jié)點(diǎn) c，同時(shí) t 指針下移，在 t 指針指向結(jié)點(diǎn) a 之前，a 結(jié)點(diǎn)中的 hp 域指向 t，同時(shí) a 結(jié)點(diǎn)中 tag 值設(shè)為 0。效果如圖 5 所示：
?

圖 5 遍歷廣義表（2）
?

通過 q 指針指向的結(jié)點(diǎn) c 的 tag=1，判斷該結(jié)點(diǎn)為表結(jié)點(diǎn)，同樣 p 指針指向 c，q 指針指向 d，同時(shí) t 指針繼續(xù)下移，在 t 指針指向 結(jié)點(diǎn) b 之前，b 結(jié)點(diǎn)的 tag 值更改為 0，同時(shí) hp 域指向結(jié)點(diǎn) a，效果圖如圖 6 所示：
?

圖 6 遍歷廣義表（3）

通過 q 指針指向的結(jié)點(diǎn) d 的 tag=0，所以，該結(jié)點(diǎn)為原子結(jié)點(diǎn)，此時(shí)根據(jù)遵循的原則，只需要將 q 指針指向的結(jié)點(diǎn) d 的 mark 域標(biāo)記為 1，然后讓 q 指針直接指向 p 指針指向結(jié)點(diǎn)的表尾結(jié)點(diǎn)，效果圖如圖 7 所示：
?

圖 7 遍歷廣義表（4）
?

當(dāng) q 指針指向 p 指針的表尾結(jié)點(diǎn)時(shí)，同時(shí) q 指針為空，這種情況的下一步操作為 p 指針和 t 指針全部上移動(dòng)，即 p 指針指向結(jié)點(diǎn) b，同時(shí) t 指針根據(jù) b 結(jié)點(diǎn)的 hp 域回退到結(jié)點(diǎn) a。同時(shí)由于結(jié)點(diǎn) b 的tag 值為 0，證明之前遍歷的是表頭，所以還需要遍歷 b 結(jié)點(diǎn)的表尾結(jié)點(diǎn)，同時(shí)將結(jié)點(diǎn) b 的 tag 值改為 1。效果圖如圖 8 所示：
?

圖 8 遍歷廣義表（5）
?

由于 q 指針指向的 e 結(jié)點(diǎn)為表結(jié)點(diǎn)，根據(jù) q 指針指向的 e 結(jié)點(diǎn)是 p 指針指向的 b 結(jié)點(diǎn)的表尾結(jié)點(diǎn)，所以所做的操作為：p 指針和 t 指針在下移之前，令 p 指針指向的結(jié)點(diǎn) b 的 tp 域指向結(jié)點(diǎn) a，然后給 t 賦值 p，p 賦值 q。q 指向 q 的表頭結(jié)點(diǎn) f。效果如圖 9 所示：
?

圖 9 遍歷廣義表（6）

由于 q 指針指向的結(jié)點(diǎn) f 為原子結(jié)點(diǎn)，所以直接 q 指針的 mark 域設(shè)為 1 后，直接令 q 指針指向 p 指針指向的 e 結(jié)點(diǎn)的表尾結(jié)點(diǎn)。效果如圖 10 所示：
?

圖 10 遍歷廣義表（7）
?

由于 p 指針指向的 e 結(jié)點(diǎn)的表尾結(jié)點(diǎn)為空，所以 p 指針和 t 指針都回退。由于 p 指針指向的結(jié)點(diǎn) b 的 tag 值為 1，表明表尾已經(jīng)遍歷完成，所以 t 指針和 p 指針繼續(xù)上移，最終遍歷完成。

總結(jié)

無用單元的收集可以采用以上 3 中算法中任何一種。無論使用哪種算法，無用單元收集本身都是很費(fèi)時(shí)間的，所以無用單元的收集不適用于實(shí)時(shí)處理的情況中使用。

內(nèi)存緊縮（內(nèi)存碎片化處理）

前邊介紹的有關(guān)動(dòng)態(tài)內(nèi)存管理的方法，無論是邊界標(biāo)識法還是伙伴系統(tǒng)，但是以將空閑的存儲空間鏈接成一個(gè)鏈表，即可利用空間表，對存儲空間進(jìn)行分配和回收。

本節(jié)介紹另外一種動(dòng)態(tài)內(nèi)存管理的方法，使用這種方式在整個(gè)內(nèi)存管理過程中，不管哪個(gè)時(shí)間段，所有未被占用的空間都是地址連續(xù)的存儲區(qū)。

這些地址連續(xù)的未被占用的存儲區(qū)在編譯程序中稱為堆。

圖 1 存儲區(qū)狀態(tài)

假設(shè)存儲區(qū)的初始狀態(tài)如圖 1 所示，若采用本節(jié)介紹的方法管理這塊存儲區(qū)，當(dāng) B 占用塊運(yùn)行完成同時(shí)所占的存儲空間釋放后，存儲區(qū)的狀態(tài)應(yīng)如圖 2 所示：

?

圖 2 更新后的存儲區(qū)狀態(tài)

分配內(nèi)存空間

在分配內(nèi)存空間時(shí)，每次都從可利用空間中選擇最低（或者最高）的地址進(jìn)行分配。具體的實(shí)現(xiàn)辦法為：設(shè)置一個(gè)指針（稱為堆指針），每次用戶申請存儲空間時(shí)，都是堆的最低（或者最高）地址進(jìn)行分配。假設(shè)當(dāng)用戶申請 N 個(gè)單位的存儲空間時(shí)，堆指針向高地址（或者低地址）移動(dòng) N 個(gè)存儲單位，這 N 個(gè)存儲單位即為分配給用戶使用的空閑塊，空閑塊的起始地址為堆指針移動(dòng)之前所在的地址。

例如，某一時(shí)間段有四個(gè)用戶（A、B、C、D）分別申請 12 個(gè)單位、6 個(gè)單位、10 個(gè)單位和 8 個(gè)單位的存儲空間，假設(shè)此時(shí)堆指針的初值為 0。則分配后存儲空間的效果為：

回收算法

由于系統(tǒng)中的可利用空間始終都是一個(gè)連續(xù)的存儲空間，所以回收時(shí)必須將用戶釋放的存儲塊合并到這個(gè)堆上才能夠重新使用。

存儲緊縮有兩種做法：

1. 其一是一旦用戶釋放所占空間就立即進(jìn)行回收緊縮；
2. 另外一種是在程序執(zhí)行過程中不立即回收用戶釋放的存儲塊，而是等到可利用空間不夠分配或者堆指針指向了可利用存儲區(qū)的最高地址時(shí)才進(jìn)行存儲緊縮。

具體的實(shí)現(xiàn)過程是：

1. 計(jì)算占用塊的新地址。設(shè)立兩個(gè)指針隨巡查向前移動(dòng)，分別用于指示占用塊在緊縮之前和之后的原地址和新地址。因此，在每個(gè)占用塊的第一個(gè)存儲單位中，除了存儲該占用塊的大小和標(biāo)志域之外，還需要新增一個(gè)新地址域，用于存儲占用塊在緊縮后應(yīng)有的新地址，即建立一張新、舊地址的對照表。
2. 修改用戶的出事變量表，保證在進(jìn)行存儲緊縮后，用戶還能找到自己的占用塊。
3. 檢查每個(gè)占用塊中存儲的數(shù)據(jù)。如果有指向其它存儲塊的指針，則需作相應(yīng)修改。
4. 將所有占用塊遷移到新地址去，即進(jìn)行數(shù)據(jù)的傳遞。

最后，還要將堆指針賦以新的值。

總結(jié)

存儲緊縮較之無用單元收集更為復(fù)雜，是一個(gè)系統(tǒng)的操作，如果不是非不得已不建議使用。文章來源地址http://www.zghlxwxcb.cn/news/detail-660916.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之動(dòng)態(tài)內(nèi)存管理機(jī)制的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！