西安郵電大學(xué)（計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)：內(nèi)存管理專(zhuān)業(yè)名稱(chēng)：軟件工程班級(jí)：學(xué)生姓名：學(xué)號(hào)（8位）：指導(dǎo)教師：實(shí)驗(yàn)日期：12月04日實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境1、實(shí)驗(yàn)環(huán)境Linuxcentos7系統(tǒng)

gcc編譯器gdb調(diào)試2、實(shí)驗(yàn)?zāi)康?1)掌握內(nèi)存分派FF，BF，WF方略及實(shí)現(xiàn)的思路；(2)掌握內(nèi)存回收過(guò)程及實(shí)現(xiàn)思路；(3)參考本程序思路，實(shí)現(xiàn)內(nèi)存的申請(qǐng)、釋放的管理程序，調(diào)試運(yùn)行，總結(jié)程序設(shè)計(jì)中出現(xiàn)的問(wèn)題并找出因素，寫(xiě)出實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容(1)掌握內(nèi)存分派FF，BF，WF方略及實(shí)現(xiàn)的思路；(2)掌握內(nèi)存回收過(guò)程及實(shí)現(xiàn)思路；(3)參考本程序思路，實(shí)現(xiàn)內(nèi)存的申請(qǐng)、釋放的管理程序，調(diào)試運(yùn)行，總結(jié)程序設(shè)計(jì)中出現(xiàn)的問(wèn)題并找出因素，寫(xiě)出實(shí)驗(yàn)報(bào)告。方案設(shè)計(jì)----------------------------------------------------------Memorymanagementexperiment1-Setmemorysize(default=1024)2-Selectmemoryallocationalgorithm3-Newprocess4-killaprocess5-Displaymemoryusage0-Exit----------------------------------------------------------一、初次適應(yīng)算法（FirstFit）：該算法從空閑分區(qū)鏈?zhǔn)组_(kāi)始查找，直至找到一種能滿(mǎn)足其大小規(guī)定的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存分派給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)鏈中。

特點(diǎn)：該算法傾向于使用內(nèi)存中低地址部分的空閑區(qū)，在高地址部分的空閑區(qū)極少被運(yùn)用，從而保存了高地址部分的大空閑區(qū)。顯然為后來(lái)達(dá)成的大作業(yè)分派大的內(nèi)存空間發(fā)明了條件。

缺點(diǎn)：低地址部分不停被劃分，留下許多難以運(yùn)用、很小的空閑區(qū)，而每次查找又都從低地址部分開(kāi)始，會(huì)增加查找的開(kāi)銷(xiāo)。二、循環(huán)初次適應(yīng)算法（NextFit）：該算法是由初次適應(yīng)算法演變而成的。在為進(jìn)程分派內(nèi)存空間時(shí)，不再每次從鏈?zhǔn)组_(kāi)始查找，直至找到一種能滿(mǎn)足規(guī)定的空閑分區(qū)，并從中劃出一塊來(lái)分給作業(yè)。

特點(diǎn)：使內(nèi)存中的空閑分分辨布的更為均勻，減少了查找時(shí)的系統(tǒng)開(kāi)銷(xiāo)。

缺點(diǎn)：缺少大的空閑分區(qū)，從而造成不能裝入大型作業(yè)。三、最佳適應(yīng)算法（BestFit）：該算法總是把既能滿(mǎn)足規(guī)定，又是最小的空閑分分辨配給作業(yè)。為了加速查找，該算法規(guī)定將全部的空閑區(qū)按其大小排序后，以遞增次序形成一種空白鏈。這樣每次找到的第一種滿(mǎn)足規(guī)定的空閑區(qū)，必然是最優(yōu)的。孤立地看，該算法似乎是最優(yōu)的，但事實(shí)上并不一定。由于每次分派后剩余的空間一定是最小的，在存儲(chǔ)器中將留下許多難以運(yùn)用的小空閑區(qū)。同時(shí)每次分派后必須重新排序，這也帶來(lái)了一定的開(kāi)銷(xiāo)。

特點(diǎn)：每次分派給文獻(xiàn)的都是最適宜該文獻(xiàn)大小的分區(qū)。

缺點(diǎn)：內(nèi)存中留下許多難以運(yùn)用的小的空閑區(qū)。四、最壞適應(yīng)算法(WorstFit)：該算法按大小遞減的次序形成空閑區(qū)鏈，分派時(shí)直接從空閑區(qū)鏈的第一種空閑區(qū)中分派（不能滿(mǎn)足需要?jiǎng)t不分派）。很顯然，如果第一種空閑分區(qū)不能滿(mǎn)足，那么再?zèng)]有空閑分區(qū)能滿(mǎn)足需要。這種分派辦法初看起來(lái)不合理，但它也有很強(qiáng)的直觀吸引力：在大空閑區(qū)中放入程序后，剩余的空閑區(qū)經(jīng)常也很大，于是還能裝下一種較大的新程序。

最壞適應(yīng)算法與最佳適應(yīng)算法的排序正好相反，它的隊(duì)列指針總是指向最大的空閑區(qū)，在進(jìn)行分派時(shí)，總是從最大的空閑區(qū)開(kāi)始查尋。

該算法克服了最佳適應(yīng)算法留下的許多小的碎片的局限性，但保存大的空閑區(qū)的可能性減小了，并且空閑區(qū)回收也和最佳適應(yīng)算法同樣復(fù)雜。

特點(diǎn)：給文獻(xiàn)分派分區(qū)后剩余的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對(duì)中小型文獻(xiàn)分派分區(qū)操作有利。

缺點(diǎn)：使存儲(chǔ)器中缺少大的空閑區(qū)，對(duì)大型文獻(xiàn)的分分辨配不利。四．測(cè)試數(shù)據(jù)及運(yùn)行成果五．總結(jié)本次實(shí)驗(yàn)使我受益匪淺，我不僅僅學(xué)習(xí)到了專(zhuān)業(yè)知識(shí)，更重要的是收獲了經(jīng)驗(yàn)與體會(huì)，這些使我一生受用不盡，記下來(lái)與大家共勉：1.多學(xué)多問(wèn)，學(xué)會(huì)虛心討教。在實(shí)驗(yàn)前內(nèi)存管理的最佳適配算法不是很會(huì)計(jì)算，向班級(jí)同窗請(qǐng)教后發(fā)現(xiàn)即使思維上有點(diǎn)繞，但是并不是很難，很快就理解了原理思想。2.善于思考，真正消化知識(shí)。有知到識(shí)，永遠(yuǎn)不是那么簡(jiǎn)樸的事，當(dāng)你真正學(xué)會(huì)去思考時(shí)，別人的知識(shí)才干變成你自己的東西。3.前人鋪路，后人修路。墨守陳規(guī)永遠(yuǎn)不會(huì)有新的建樹(shù)，前人的道路固然重要，但是學(xué)會(huì)創(chuàng)新更為重要。4.獨(dú)立而不孤立。學(xué)會(huì)獨(dú)立思考，獨(dú)立實(shí)驗(yàn)，但要記住與別人的交流也是十分重要的，實(shí)驗(yàn)和實(shí)驗(yàn)事永遠(yuǎn)不是你自己的。5.認(rèn)真認(rèn)真地做好實(shí)驗(yàn)紀(jì)錄。不要當(dāng)你真正用到它時(shí)才知它的重要所在。六．附錄：源代碼（電子版）#include<stdio.h>#include<stdlib.h>#include<ctype.h>#definePROCESS_NAME_LEN32//進(jìn)程名長(zhǎng)度#defineMIN_SLICE10//最小碎片大小#defineDEFAULT_MEM_SIZE1024//內(nèi)存大小#defineDEFAULT_MEM_START0//起始地址//內(nèi)存分派算法#defineMA_FF1#defineMA_BF2#defineMA_WF3//描述每一種空閑塊的數(shù)據(jù)構(gòu)造structfree_block_type{intsize;intstart_addr;structfree_block_type*next;};//每個(gè)進(jìn)程分派到的內(nèi)存塊的描述structallocated_block{intpid;intsize;intstart_addr;charprocess_name[PROCESS_NAME_LEN];structallocated_block*next;};structfree_block_type*free_block;structallocated_block*allocated_block_head=NULL;intmem_size=DEFAULT_MEM_SIZE;//內(nèi)存大小intma_algorithm=MA_FF;//現(xiàn)在分派算法staticintpid=0;//初始pidintflag=0;voiddisplay_menu();voiddo_exit();structfree_block_type*init_free_block(intmem_size);voidset_mem_size();voidset_algorithm();voidnew_process();voidkill_process();voiddisplay_mem_usage();voidrearrange(intchoice);voidrearrage_FF();voidrearrage_BF();voidrearrage_WF();intmain(){charchoice;pid=0;free_block=init_free_block(mem_size);display_menu();while(1){printf("Pleasechoice:");fflush(stdin);choice=getchar();//獲取顧客輸入switch(choice){case'1':set_mem_size();//設(shè)立內(nèi)存大小break;case'2':set_algorithm();//設(shè)立算法flag=1;break;case'3':new_process();//創(chuàng)立新進(jìn)程flag=1;break;case'4':kill_process();//刪除進(jìn)程flag=1;break;case'5':display_mem_usage();//顯示內(nèi)存使用flag=1;break;case'0':do_exit();//釋放鏈表并退出exit(0);default:break;}choice=getchar();}return0;}//緊縮解決voidfree_memory_rearrage(intmemory_reduce_size,intallocated_size){structfree_block_type*p1,*p2;structallocated_block*a1,*a2;if(memory_reduce_size!=0)//分派完尚有小塊空間{p1=free_block;p2=p1->next;p1->start_addr=0;p1->size=memory_reduce_size;p1->next=NULL;mem_size=memory_reduce_size;}else{p2=free_block;free_block=NULL;mem_size=0;}while(p2!=NULL)//釋放節(jié)點(diǎn){p1=p2;p2=p2->next;free(p1);}//allocated_block重新修改鏈接a1=(structallocated_block*)malloc(sizeof(structallocated_block));a1->pid=pid;a1->size=allocated_size;a1->start_addr=memory_reduce_size;//已申請(qǐng)的開(kāi)始地址，從memory_reduce_size開(kāi)始sprintf(a1->process_name,"PROCESS-%02d",pid);a1->next=allocated_block_head;a2=allocated_block_head;allocated_block_head=a1;while(a2!=NULL){a2->start_addr=a1->start_addr+a1->size;a1=a2;a2=a2->next;}}intallocate_mem(structallocated_block*ab){structfree_block_type*fbt,*pre;intrequest_size=ab->size;fbt=pre=free_block;while((pre!=NULL)&&(request_size>pre->size)){fbt=pre;pre=pre->next;}if(!pre){if(mem_size>=request_size){if(mem_size>=request_size+MIN_SLICE)free_memory_rearrage(mem_size-request_size,request_size);elsefree_memory_rearrage(0,mem_size);return0;}elsereturn-1;}else{if((pre->size-request_size)>MIN_SLICE){pre->size=pre->size-request_size;ab->start_addr=pre->start_addr+pre->size;}else{if(pre==fbt){fbt=pre->next;free_block=fbt;}elsefbt->next=pre->next;ab->start_addr=pre->start_addr;ab->size=pre->size;free(pre);}}mem_size-=ab->size;rearrange(ma_algorithm);return1;}//創(chuàng)立新進(jìn)程，分派內(nèi)存voidnew_process(){structallocated_block*ab;intsize;intret;if(mem_size==0){printf("thememoryisallused！nottocreatenewprocess,pleasereleaseprocess！\n");return;}ab=(structallocated_block*)malloc(sizeof(structallocated_block));if(ab==NULL){printf("NoMem!\n");exit(1);}ab->next=NULL;pid++;sprintf(ab->process_name,"PROCESS-%02d",pid);//字符串格式化ab->pid=pid;while(1){printf("Pleaseinputthememoryfor%s(0-%d):",ab->process_name,mem_size);scanf("%d",&size);if(size<=mem_size&&size>0){ab->size=size;break;}printf("Pleaseinputagain！\n");}ret=allocate_mem(ab);if((ret==1)&&(allocated_block_head==NULL))allocated_block_head=ab;elseif(ret==1){ab->next=allocated_block_head;allocated_block_head=ab;}elseif(ret==-1){printf("Allocationfail\n");free(ab);return;}printf("AllocationSuccess!\n");}//尋找已分派的內(nèi)存塊structallocated_block*find_process(intpid){structallocated_block*p;p=allocated_block_head;while(p){if(p->pid==pid)returnp;p=p->next;}returnp;}intfree_mem(structallocated_block*ab){intalgorithm=ma_algorithm;structfree_block_type*fbt,*pre,*work;mem_size+=ab->size;fbt=(structfree_block_type*)malloc(sizeof(structfree_block_type));if(!fbt)return-1;fbt->size=ab->size;fbt->start_addr=ab->start_addr;fbt->next=NULL;rearrange(MA_FF);pre=NULL;work=free_block;while((work!=NULL)&&(fbt->start_addr>work->start_addr)){pre=work;work=work->next;}if(!pre)//插入開(kāi)始位置{if(!work){free_block=fbt;}else{fbt->next=work;free_block=fbt;if(fbt->start_addr+fbt->size==work->start_addr){fbt->next=work->next;fbt->size=fbt->size+work->size;free(work);}}}else{if(!work){pre->next=fbt;if(fbt->start_addr==pre->start_addr+pre->size){pre->next=work;pre->size=fbt->size+pre->size;free(fbt);}}else{fbt->next=work;pre->next=fbt;if((fbt->start_addr==pre->start_addr+pre->size)&&(fbt->start_addr+fbt->size==work->start_addr)){pre->next=work->next;pre->size=pre->size+fbt->size+work->size;free(fbt);free(work);}elseif(fbt->start_addr==pre->start_addr+pre->size){pre->next=work;pre->size=pre->size+fbt->size;free(fbt);}elseif(work->start_addr==fbt->start_addr+fbt->size){fbt->next=work->next;fbt->size=work->size+fbt->size;free(work);}}}rearrange(ma_algorithm);return1;}voiddispose(structallocated_block*free_ab){structallocated_block*pre,*ab;if(free_ab==allocated_block_head){allocated_block_head=free_ab->next;free(free_ab);return;}pre=allocated_block_head;ab=allocated_block_head->next;while(ab!=free_ab){pre=ab;ab=ab->next;}pre->next=ab->next;free(ab);}//終止進(jìn)程，回收內(nèi)存voidkill_process(){structallocated_block*ab;intpid;printf("Killprocess,inputpid=");scanf("%d",&pid);ab=find_process(pid);if(ab!=NULL){free_mem(ab); //釋放ab所示的分派區(qū)dispose(ab); //釋放ab數(shù)據(jù)構(gòu)造節(jié)點(diǎn)printf("KillProcessSuccess!\n");return;}printf("KillProcessFailure!\n");}//顯示現(xiàn)在內(nèi)存的使用狀況，涉及空閑區(qū)的狀況和已經(jīng)分派的狀況voiddisplay_mem_usage(){structfree_block_type*fbt=free_block;structallocated_block*ab=allocated_block_head;/*顯示空閑區(qū)*/printf("----------------------------------------------------------\n");if(fbt==NULL)printf("success!\n");else{printf("FreeMemory:\n");printf("%20s%20s\n","\tstart_addr","size");while(fbt!=NULL){printf("%20d%20d\n",fbt->start_addr,fbt->size);fbt=fbt->next;}}printf("----------------------------------------------------------\n");/*顯示已分派區(qū)*/if(ab==NULL)printf("尚未開(kāi)始分派!\n");else{printf("\nUsedMemory:\n");printf("%10s%20s%10s%10s\n","\tPID","ProcessName","start_addr","size");while(ab!=NULL){printf("%10d%20s%10d%10d\n",ab->pid,ab->process_name,ab->start_addr,ab->size);ab=ab->next;}}printf("----------------------------------------------------------\n");}//最佳適配算法voidrearrage_BF(){structfree_block_type*p,*p1,*p2;structfree_block_type*last_flag;p1=(structfree_block_type*)malloc(sizeof(structfree_block_type));p1->next=free_block;free_block=p1;//不變化p1,free_block指向頭p1if(free_block!=NULL){for(last_flag=NULL;last_flag!=free_block;last_flag=p){for(p=p1=free_block;p1->next!=NULL&&p1->next->next!=NULL&&p1->next->next!=last_flag;p1=p1->next){if(p1->next->size>p1->next->next->size){p2=p1->next->next;p1->next->next=p2->next;//p2->next=p1->next;p1->next=p2;p=p1->next->next;}}}}p1=free_block;free_block=free_block->next;free(p1);p1=NULL;}//最差適配算法voidrearrage_WF(){structfree_block_type*p,*p1,*p2;structfree_block_type*last_flag;p1=(structfree_block_type*)malloc(sizeof(structfree_block_type));p1->next=free_block;free_block=p1;//不變化p1,free_block指向頭p1if(free_block!=NULL){for(last_flag=NULL;last_flag!=free_block;last_flag=p){for(p=p1=free_block;p1->next!=NULL&&p1->next->next!=NULL&&p1->next->next!=last_flag;p1=p1->next){if(p1->next->size<p1->next->next->size){p2=p1->next->next;p1->next->next=p2->next;//p2->next=p1->next;p1->next=p2;p=p1->next->next;}}}}p1=free_block;free_block=free_block->next;free(p1);p1=NULL;}//最快適配算法voidrearrage_FF(){structfree_block_type*p,*p1,*p2;structfree_block_type*last_flag;p1=(structfree_block_type*)malloc(sizeof(structfree_block_type));p1->next=free_block;free_block=p1;//不變化p1,free_block指向頭p1if(free_block!=NULL){for(last_flag=NULL;last_flag!=free_block;last_flag=p){for(p=p1=free_block;p1->next!=NULL&&p1->next->next!=NULL&&p1->next->next!=last_flag;p1=p1->next){if(p1->next->start_addr>p1->next->next->start_addr){p2=p1->next->next;p1->next->next=p2->next;p2->next=p1->next;p1->next=p2;p=p1->next->next;}}}}p1=free_block;free_block=free_block->next;free(p1);p1=NULL;}//初始化空閑塊structfree_block_type*init_free_block(intmem_size){structfree_block_type*fb;fb=(structfree_block_type*)malloc(sizeof(structfree_block_type));if(fb==NULL){printf("NoMem!\n");exit(1);}fb->size=mem_size;fb->start_addr=DEFAULT_MEM_START;fb->next=NULL;returnfb;}voiddisplay_menu(){printf("\n");printf("----------------------------------------------------------\n");printf("Memorymanagementexperiment\n");printf("1-Setme