動(dòng)態(tài)內(nèi)存分配算法試驗(yàn)報(bào)告材料

1、實(shí)用標(biāo)準(zhǔn)文案精彩文檔動(dòng) 態(tài) 內(nèi) 存 分 配算 法 實(shí) 驗(yàn) 報(bào) 告院系:計(jì)算機(jī)與通信工程學(xué)院班級(jí):計(jì)科 08-1 班姓名:胡太祥實(shí)用標(biāo)準(zhǔn)文案精彩文檔學(xué)號(hào):200807010112一、實(shí)驗(yàn)題目：動(dòng)態(tài)內(nèi)存分配算法二、實(shí)驗(yàn)?zāi)康纳钊肓私鈩?dòng)態(tài)分區(qū)存儲(chǔ)管理方式內(nèi)存分配與回收的實(shí)現(xiàn)三、實(shí)驗(yàn)要求熟悉存儲(chǔ)管理中動(dòng)態(tài)分區(qū)的管理方式及Win dowsVC+程序設(shè)計(jì)方法四、實(shí)驗(yàn)內(nèi)容1，確定定內(nèi)存空閑分配表和進(jìn)程內(nèi)存分配表2，采用首次適應(yīng)算法完成內(nèi)存空間的分配3，采用最佳適應(yīng)算法完成內(nèi)存空間的分配4，采用最壞適應(yīng)算法完成內(nèi)存空間的分配5，實(shí)現(xiàn)內(nèi)存回收功能五、實(shí)驗(yàn)結(jié)果環(huán)境下,實(shí)用標(biāo)準(zhǔn)文案精彩文檔XJ-1010你有以下尊法可

2、供選擇:fess應(yīng)應(yīng)應(yīng)適適適次專田直日B B駆退收回回返K K!臺(tái)-.KETT收回i i妝彎配看:籌功分查擇入入成:選需配1313請(qǐng)請(qǐng)請(qǐng)命!e=洋AJ盤大.存區(qū)時(shí)XJfiB BK K *位1 1業(yè)要T T配看隼丙功分查擇入入成；選鞘配請(qǐng)請(qǐng)請(qǐng)分收回回返 B BK4位SISI3士業(yè)要T T配看星而功分查擇入入成=選3 3請(qǐng)請(qǐng)請(qǐng)分ZJ(T1 1業(yè)要配看;需功分查擇入人應(yīng)-請(qǐng)請(qǐng)請(qǐng)分i i業(yè)要配看證持功分查：擇入入成:-擇選藉配1313選注弔注nnnn請(qǐng)介注nnnn乳己1 1 3 3實(shí)用標(biāo)準(zhǔn)文案精彩文檔Free92&67 KB首次適應(yīng)算法結(jié)果、：30 KB慵選擇J丄，議黔礙知 9413圭.并配3

3、=査看返回1：分配J-壬舀2：回收也返向1:分配3：查看3IS區(qū)分的X+益尸2更配S您分查擇：il 3收回回返騒區(qū)大小；26 KB；Free I&KB2：回收0=KB一二11?4S實(shí)用標(biāo)準(zhǔn)文案精彩文檔主存分配情況空閑分區(qū)B BK K2 21 1 8 8口小Z地大區(qū)始區(qū)LiJ2-kJFree 5010 KB分區(qū)號(hào)：Free膽始地址：10B分區(qū)大小；32667 KB已分配分區(qū)B B* Jr口小z地分區(qū)牛2趙始地血=20分反大水=30KB最佳適應(yīng)算法收回回返配看分查1 1 3 3IBIB 位IIIT /Z業(yè)要L.1疔區(qū)大小:實(shí)用標(biāo)準(zhǔn)文案精彩文檔主存分配情況 空閑分區(qū)分區(qū)號(hào)r Free起始地;

4、tL 50分區(qū)大?。?0 MB:Free起始地址：8分區(qū)大水：12 KBFree1003266? KB已分配分區(qū)最壞適應(yīng)算法2：回收0：返向KB14小Z地大分起分l(n0 04-6 4口一小區(qū)地大E始01小Z地大區(qū)地大區(qū)始區(qū)分停實(shí)用標(biāo)準(zhǔn)文案精彩文檔王苻分配情況空閑分區(qū)分區(qū)號(hào)匕Free總始地L 100曲區(qū)大小：32fc67 KB分區(qū)號(hào)=Free起始地51分區(qū)大9 KB已分配分區(qū)iwl：20分図大?。?0 KS六、實(shí)驗(yàn)總結(jié)首次適應(yīng)算法：從表頭指針開始查找課利用空間表， 將找到的第一個(gè) 大小不小于“請(qǐng)求”的空閑塊的一部分分配給用戶。最佳適應(yīng)算法：將可利用空間表中一個(gè)大小不小于“請(qǐng)求”且最接近“請(qǐng)求”

5、的空閑塊的一部分分配給用戶。最壞適應(yīng)算法：將可利用空間表中一個(gè)大小不小于“請(qǐng)求”且是鏈表 中最大的空閑塊的一部分分配給用戶。以上是動(dòng)態(tài)內(nèi)存分配的三種算法思想，算法采用數(shù)據(jù)結(jié)構(gòu)中的雙 向鏈表實(shí)現(xiàn)。e ee er rF F匸I一Z地大一區(qū)始區(qū)分-_E nK小區(qū)始區(qū)分起分-1.BK075 1I_*r區(qū)地大E始區(qū)0 0實(shí)用標(biāo)準(zhǔn)文案精彩文檔附錄（算法代碼）：實(shí)用標(biāo)準(zhǔn)文案精彩文檔#i nclude#i nclude#defi ne Free 0 / 空閑狀態(tài)#defi ne Used 1 /已用狀態(tài)#define OK 1/ 完成#defi ne ERROR 0 / 出錯(cuò)#defi ne MAX_le n

6、gth 32767 /最大內(nèi)存空間為 32767KBtypedef int Status; /typedef 將標(biāo)識(shí)符 Status 定義成一個(gè)數(shù)據(jù)型標(biāo)識(shí)符int n = 0;typedef struct freearea / 定義一個(gè)結(jié)構(gòu)體 freearea,并對(duì)這個(gè)空閑分區(qū)進(jìn)行說明int ID;/分區(qū)號(hào)long size;/分區(qū)大小long address; / 分區(qū)地址int state; /當(dāng)前狀態(tài) ElemType;typedefstructDuLNode /doublelinked list / 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)ElemType data;struct DuLNode *p

7、rior; / 前趨指針struct DuLNode*next; / 后繼指針 DuLNode, *DuL in kList;DuLinkList free_list;/ 空閑鏈表DuLi nkList alloc_list; / 已分配鏈表Status alloc(i nt);/內(nèi)存分配void free_memory(i nt ID, int method); /內(nèi)存回收Status first_fit(i nt ID, i nt size); / 首 次適應(yīng)算法Status best_fit(i nt ID, i nt size); /最佳適應(yīng)算法實(shí)用標(biāo)準(zhǔn)文案精彩文檔Status wor

8、st_fit(intID, int size); /最壞適應(yīng)算法實(shí)用標(biāo)準(zhǔn)文案精彩文檔voidfirst_fit_i nsert(DuLNode*insert); /首次適應(yīng)插入排序voidbest_fit_i nsert(DuLNode*insert);/最佳適應(yīng)插入排序voidworst_fit_i nsert(DuLNode*insert); /最壞適應(yīng)插入排序DuLNode*in depe ndent_no de(DuLNode*node); / 斷開節(jié)點(diǎn) node 與相鄰節(jié)點(diǎn)的聯(lián)系，使其孤立/將節(jié)點(diǎn) node 分割，返回分配的節(jié)點(diǎn) 信息，node 為剩余內(nèi)存信息/node 為雙指針形式

9、，因?yàn)榭赡苄枰?對(duì)node 的值進(jìn)行修改DuLNode *slice_node(DuLNode*no de, int ID, int size);void show(); 查看分配Status In itblock(); 開創(chuàng)空間表Status Initblock()/開創(chuàng)帶頭節(jié)點(diǎn)的內(nèi)存空間鏈表，頭節(jié)點(diǎn)不用alloc_list(DuL in kList)malloc(sizeof(DuLNode);free_list(DuL in kList)malloc(sizeof(DuLNode);/頭節(jié)點(diǎn)不用alloc_list-prioralloc_list- next = NULL; free_l

10、ist-priorfree_list- next = NULL;/空閑列表初始為整個(gè)內(nèi)存大小，放至 U node 節(jié)點(diǎn)中DuLNode*n ode(DuLNode*)malloc(sizeof(DuLNod e);no de-data.address = 0;no de-data.sizeMAX_le ngth;實(shí)用標(biāo)準(zhǔn)文案in sert-prior = free_list;in sert-prior = p;精彩文檔no de-data .ID = 0;no de-data.state = Free;/將 node 節(jié)點(diǎn)放到空閑鏈表中no de-prior = free_list;no de

11、-n ext = NULL;free_list- n ext = no de;return OK;/將所插入節(jié)點(diǎn)按首址從小到大順序插入到空閑鏈表中voidfirst_fit_i nsert(DuLNode*insert) /首次適應(yīng)插入排序DuLNode *p = free_list- next;/按首址從小到大的順序插入節(jié)占八、while (p) /找到插入位置：p 之前if(in sert-data.addressdata.address) in sert- n ext = p;in sert-priorp-prior;p-prior- n extin sert;p-prior = in

12、sert;break;/空閑鏈表為空，則將節(jié)點(diǎn)放到頭節(jié)點(diǎn)后if (p = NULL) free_list- n ext = in sert;插入位置為鏈表尾if (p-n ext = NULL) return;break; /還是提前退實(shí)用標(biāo)準(zhǔn)文案精彩文檔p-n ext = in sert;出循環(huán)的好，不然會(huì)再次進(jìn)入循環(huán)p = p-n ext; /搜索下一個(gè)節(jié)點(diǎn)/最佳適應(yīng)插入排序：/將所插入節(jié)點(diǎn)按空間從小到大插入鏈表voidbest_fit_i nsert(DuLNode*in sert)DuLNode *p = free_list- next;/按空間從小到大插入節(jié)點(diǎn)while (p) /在

13、 p 前插入if(in sert-data.sizedata.size) in sert- n ext = p;in sert-prior=p-prior;p-prior- n ext=in sert;p-prior = in sert;break;/空閑鏈表為空，則插入到頭節(jié)點(diǎn)后if (p = NULL) free_list- n ext = in sert;in sert-prior = free_list;return;插入位置為鏈表尾if (p-n ext = NULL) p-n ext = in sert;in sert-prior = p;break; /還是提前退出循環(huán)的好，不然

14、會(huì)再次進(jìn)入循環(huán)實(shí)用標(biāo)準(zhǔn)文案精彩文檔p = p-n ext; / 搜索下一個(gè)節(jié)點(diǎn)/最壞適應(yīng)插入排序：/將所插入節(jié)點(diǎn)按空間從大到小插入 鏈表voidworst_fit_i nsert(DuLNode*in sert)DuLNode *p = free_list- next;/鏈表為空，則插入到頭節(jié)點(diǎn)后if (p = NULL) free_list- n ext = in sert; insert-prior = free_list; return;/按空間從大到小插入節(jié)點(diǎn)while (p) /在 p 前插入節(jié)點(diǎn)if(in sert-data.size=p-data.size) in sert- n

15、 ext = p;in sert-prior=p-prior;p-prior- n ext=in sert;p-prior = in sert;break;插入位置為鏈表尾if (p-n ext = NULL) p-n ext = in sert;in sert-prior = p;break; /還是提前退出循環(huán)的好，不然會(huì)再次進(jìn)入循環(huán)p = p- next; /搜索下一個(gè)節(jié)點(diǎn)實(shí)用標(biāo)準(zhǔn)文案if (* no de)-data.size = size)精彩文檔/斷開節(jié)點(diǎn) node 與相鄰節(jié)點(diǎn)間的聯(lián) 系，使其孤立/返回孤立后的節(jié)點(diǎn)指針DuLNode*in depe ndent_no de(DuLN

16、ode*no de)if (node != NULL) if (node-prior != NULL) no de-prior- n extno de-n ext;if (node-next != NULL) no de-n ext-priorno de-prior;no de-priorno de-next = NULL;return no de;/將節(jié)點(diǎn) n ode 分片， 其中一片 alloc node為為用戶所分配的內(nèi)存片，/另一片為分配后原 node 節(jié)點(diǎn)所剩余的內(nèi)存片，放到 node 中/若 node 節(jié)點(diǎn)原來大小等于所要開辟的大小，貝 U node 賦值為 NULL/返回分配結(jié)果

17、DuLNode *slice_node(DuLNode*no de, int ID, int size)DuLNode *allocnode = NULL;/node 的大小正好等于所要分配的大小，/則直接將該節(jié)點(diǎn)放到分配鏈表中，node 賦值為 NULL實(shí)用標(biāo)準(zhǔn)文案alloc no de-data.size=method) / 內(nèi)存回收精彩文檔/將node從空閑鏈表中分 出來in depe ndent_no de(* no de);/得到所分配的內(nèi)存片alloc node = (*no de);alloc no de-data .ID = ID;alloc no de-data.state=

18、Used;/沒有剩余空間，這個(gè)地方導(dǎo)致必須用雙重指針(*n ode) = NULL; else if (* no de)-data.size size)/node的大小大于所需的大小，故將 node 分為兩片/ 一片為所分配的內(nèi)存片，分配地址和空間alloc node=(DuLNode*)malloc(sizeof(DuLNode);alloc no de-data.address=(*no de)-data.address;alloc no de-data .ID = ID;alloc no de-data.state=Used;alloc no de-prior=alloc no de-n

19、 ext = NULL;/另一片為分配后剩下的內(nèi) 存片，修改內(nèi)存地址和大小(*no de)-data.address+= size;(*no de)-data.size-=size;/返回分配結(jié)果retur n alloc no de;/按不同的分配方法歸還內(nèi)存void free_memory(i nt ID, int實(shí)用標(biāo)準(zhǔn)文案alloc no de-data.size=method) / 內(nèi)存回收精彩文檔size;實(shí)用標(biāo)準(zhǔn)文案free no de-data.size精彩文檔DuLNode *p, *prior,*n ext,*free no de;p = prior = n ext = f

20、ree node =NULL;/從已分配鏈表中找到所要?dú)w還 的內(nèi)存信息p = alloc_list- n ext;while (p) if (p-dataD = ID) /找到所要?dú)w還的內(nèi)存信息free node = p;free no de-data.state=Free;free no de-data .ID=Free;break;p = p-n ext; / 繼續(xù)查找/將 free node 從已分配鏈表中分離出來in depe ndent_no de(free no de);if (freen ode = NULL) / 沒有所要?dú)w還的內(nèi)存return;/合并空閑內(nèi)存片p = free

21、_list- n ext;while (p) /找到先前合并內(nèi)存節(jié)點(diǎn)priorif (p-data.address +p-data.size=freeno de-data.address) prior = p;elseif實(shí)用標(biāo)準(zhǔn)文案精彩文檔(free no de-data.address+實(shí)用標(biāo)準(zhǔn)文案精彩文檔p-data.address) /找到向后合并內(nèi)存節(jié)點(diǎn) nextn ext = p;/在這兒，如果是首次適 應(yīng)算法 可以直接中斷循環(huán)了p = p-n ext; /繼續(xù)查找/向前合并節(jié)點(diǎn)存在，則進(jìn)行合并if (prior != NULL) in depe ndent_no de(prior

22、);/將 prior 從空閑鏈表中分離出來/freenode與 prior 合并free no de-data.address=prior-data.address;free no de-data.size+=prior-data.size;/釋放 prior 節(jié)點(diǎn)/向后合并節(jié)點(diǎn)存在，則進(jìn)行合并if (next != NULL) in depe ndent_no de( next);/將 next 從空閑鏈表中分離出來/freenode 與 next 合并free no de-data.size+=n ext-data.size;/釋放 next 節(jié)點(diǎn)free( next);/按不同的分配方式

23、， 重新插入合 并后的節(jié)點(diǎn)if (method = 1) first_fit_i nsert(free no de); else if (method = 2) best_fit_i nsert(free no de);實(shí)用標(biāo)準(zhǔn)文案精彩文檔 else if (method = 3) Status alloc(int ch) 分配主存int ID, request;cout ID;cout request;if (request 0 | request = 0)cout 分配數(shù)據(jù)不合適，請(qǐng)重新輸入! endl;return ERROR;if (ch = 1) / 首次適應(yīng)算法if (first_

24、fit(ID, request)=OK) cout 分配成功! en dl; else cout 內(nèi)存不足，分配失敗! endl;return OK; else if (ch = 2) / 選擇最佳適應(yīng)算法if (best_fit(ID, request)=OK) cout 分配成功! en dl; else cout 內(nèi)存不足，分free(prior);worst_fit_in sert(free no de);實(shí)用標(biāo)準(zhǔn)文案精彩文檔配失敗! next;DuLNode *allocnode = NULL;/將 p 分片，返回所要分配的內(nèi) 存信息/由于是按首址從小到大排列空 閑內(nèi)存節(jié)點(diǎn)/故不需再

25、重排剩余內(nèi)存節(jié)點(diǎn)alloc node = slice_ no de(&p, ID,size);DuLNode*q= else if (ch = 3) /最壞適應(yīng)while (p) 算法/找到合適空閑內(nèi)存節(jié)點(diǎn)if (worst_fit(ID,request)if (p-data.size = size) =OK) break;cout 分配成功!n ext;cout 內(nèi)存不足，分配失敗! n ext;/將所分配節(jié)點(diǎn)放到已分配鏈表 頭節(jié)點(diǎn)后if (q != NULL) alloc no de-n ext = q;alloc no de-prior=q-prior;q-prior- n ex

26、t=alloc no de;q-prior = alloc no de; else alloc_list- n ext=alloc no de;alloc no de-prior=alloc_list;return OK;Status best_fit(i nt ID, i nt size) /最佳適應(yīng)算法DuLNode *p = free_list- n ext;DuLNode *allocnode = NULL, *leftnode = NULL;while (p) /找到了合適的內(nèi)存節(jié)點(diǎn)if (p-data.size = size) break;p = p-n ext;if (p = N

27、ULL) /內(nèi)存不足return ERROR;/分片，剩余內(nèi)存片需重新排序alloc node = slice_ no de(&p, ID,實(shí)用標(biāo)準(zhǔn)文案精彩文檔size);left node = p;DuLNode*qalloc_list- n ext;/將所分配節(jié)點(diǎn)放到已分配鏈表 頭節(jié)點(diǎn)后if (q != NULL) alloc no de-n ext = q;alloc no de-prioralloc_list;q-prior- n extalloc no de;q-prior = alloc no de; else alloc_list- n extalloc no de;al

28、loc no de-prioralloc_list;/重新插入剩余內(nèi)存片if (left node != NULL) /分離剩余內(nèi)存片in depe ndent_no de(left no de);插入該片best_fit_i nsert(left no de);return OK;Status worst_fit(i nt ID, int size) / 最壞適應(yīng)算法，直接找第一個(gè)節(jié)點(diǎn)DuLNode *p = free_list- n ext;DuLNode *allocnode = NULL, *leftnode = NULL;if (p = NULL | p-data.size n ext;/將所分配節(jié)點(diǎn)放到已分配鏈表 頭節(jié)點(diǎn)后if (q != NULL) alloc no de-n ext = q;alloc no de-prioralloc_list;q-prior- n extalloc no de;q-prior = alloc no de; else alloc_list- n extalloc no de;alloc_list;/重新插入剩余內(nèi)存片if (left node != NULL) /分離剩余內(nèi)存片in depe ndent_no de(left no de);插入該片worst