采用首次適應(yīng)算法的動態(tài)分區(qū)分配模擬課程設(shè)計實驗報告

1需求分析1）本程序要求實現(xiàn)對內(nèi)存的動態(tài)分配與回收的模擬，同時，在內(nèi)存的分配時還必須使用首次適應(yīng)算法，最后，還要顯示內(nèi)存塊分配和回收后空閑內(nèi)存分區(qū)鏈的情況。2）要實現(xiàn)對作業(yè)的內(nèi)存分配，首先要有一個對作業(yè)進行創(chuàng)建和分配內(nèi)存的模塊，其中，該模塊在分配內(nèi)存時要使用首次適應(yīng)算法；要實現(xiàn)對內(nèi)存的回收，要有一個內(nèi)存回收的模塊，其中，該模塊在回收內(nèi)存時要考慮內(nèi)存回收的四種情況；最后，還要有一個能顯示內(nèi)存空閑分區(qū)鏈的情況的模塊。2概要設(shè)計1）首次適應(yīng)算法的結(jié)構(gòu)如圖1：圖1首次適應(yīng)算法的結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)structFq{intsize,o,no;Fq*before,*next;};其中，F(xiàn)q表示結(jié)構(gòu)體的名字(類型)，size表示分區(qū)的可用空間大小，o表示該分區(qū)的狀態(tài)(是否已分配)，no表示該分區(qū)中的作業(yè)標志，*before表示該結(jié)點的向前指針，*next表示該結(jié)點的向后指針。各種函數(shù)說明：\voidalloc(intb,intno,Fq*p)；對作業(yè)no進行內(nèi)存分配的功能函數(shù)；其中，參數(shù)b表示需求的內(nèi)存大小，參數(shù)no表示作業(yè)的編號，參數(shù)*p表示空閑分區(qū)鏈的第一個非空結(jié)點的指針；voidfree(Fq*c)；將地址為c的分區(qū)的內(nèi)存回收；其中，參數(shù)*c表示要回收內(nèi)存的結(jié)點；voidcreate(Fq*head)；創(chuàng)建新作業(yè)的子函數(shù)；其中，參數(shù)*head表示空閑分區(qū)鏈的鏈首指針；要配合函數(shù)alloc()使用；voidcha(Fq*head)；查看內(nèi)存中的空閑分區(qū)鏈的子函數(shù)；其中，參數(shù)*head表示空閑分區(qū)鏈的鏈首指針；#voidhui(Fq*head)；回收內(nèi)存的子函數(shù)；其中，參數(shù)*head表示空閑分區(qū)鏈的鏈首指針；要配合函數(shù)free()使用；3運行環(huán)境操作系統(tǒng)：WindowsXP(32位/DirectX11)電腦:X86兼容臺式電腦處理器：英特爾Pentium（奔騰）雙核E5300@內(nèi)存:2GB4開發(fā)工具和編程語言1） 開發(fā)工具：VisualC++；2） 編程語言：C++語言；5詳細設(shè)計1）程序結(jié)構(gòu)如圖2：圖2程序結(jié)構(gòu)圖2）?主菜單模塊：voidmain（）//主函數(shù){Fq*head=newFq;head->next=newFq;head->next->size=MAXSIZE;head->next->o=0;head->next->next=NULL;intchoice=0;docout<〈"請選擇你要進行的操作："〈〈endl；回收內(nèi)存空間0、cout<<"1、創(chuàng)建新作業(yè)2、查看空閑分區(qū)鏈回收內(nèi)存空間0、退出"<<endl；cin>>choice；switch(choice){case1:create(head)；break；case2:cha(head)；break；case3:hui(head)；break；(case0:break；default：cout<<"輸入錯誤！"<<endl；}}while(choice!=0)；}?創(chuàng)建新作業(yè)模塊：voidcreate(Fq*head)//創(chuàng)建作業(yè)子函數(shù){Fq*p=head->next；p->before=head；intno=0,b=0；cout<<"請輸入要創(chuàng)建的作業(yè)的編號："；cin>>no；cout<<"請輸入作業(yè)的需求空間大?。?；cin>>b；alloc(b,no,p)；//此處調(diào)用功能函數(shù)alloc()}?查看空閑分區(qū)鏈模塊：voidcha(Fq*head)//查看內(nèi)存中的空閑分區(qū)鏈的子函數(shù)Fq*p=head->next;p->before=head;inti=0;cout<<"空閑分區(qū)鏈的情況為："〈〈endl；while(p!=NULL){if(p->o==0){cout〈〈"空閑分區(qū)"〈〈++i〈〈" "〈〈p->size〈〈"K"〈〈endl；}p=p->next；}}?回收內(nèi)存空間模塊：voidhui(Fq*head)//回收內(nèi)存的子函數(shù){)Fq*p=head->next；p->before=head；intno=0；cout<〈"請輸入要回收內(nèi)存的作業(yè)號："；cin>>no；while(p!=NULL){if(p->no==no){free(p);//此處調(diào)用功能函數(shù)free()cout<<"作業(yè)"<50<<"的內(nèi)存已回收！"<<endl；return；elsep=p->next;}?內(nèi)存分配功能函數(shù)模塊：voidalloc(intb,intno,Fq*p)//對作業(yè)no進行內(nèi)存分配的子函數(shù)}{while(p!=NULL){if(p->o==1){p=p->next;}else{if(p->size>b){if(p->size-b<=min_size){p->o=1;p->no=no;}else{Fq*q=newFq;Fq*r;r=p->before;r->next=q;q->before=r;q->next=p;p->before=q;q->size=b;p->size=p->size-b;q->no=no;q->o=1;}cout〈＜"內(nèi)存分配成功！"〈〈endl；return;}elsep=p->next；}}cout〈〈"內(nèi)存分配失?。?〈〈endl；}?內(nèi)存回收功能函數(shù)模塊：)voidfree(Fq*c)//將地址為c的分區(qū)內(nèi)存回收{(diào)if(c->before->o==0&&c->next->o==0){Fq*r=c->before,*s=c->next->next；r->size=(r->size+c->size+c->next->size)；r->next=s；if(s!=NULL)s->before=r；%}if(c->before->o==0&&c->next->o!=0){c->before->size=c->before->size+c->size；c->before->next=c->next；c->next->before=c->before；}if(c->next->o==0&&c->before->o!=0){Fq*r=c->next->next；c->size=c->size+c->next->size;c->next=c->next->next;if（r!=NULL）r->before=c;c->o=0;}elsec->o=0;}6調(diào)試分析1）內(nèi)存分配功能函數(shù)模塊：剛開始對作業(yè)分配內(nèi)存時，只是將空閑分區(qū)的大小以及前后向指針進行修改，而沒有對分配給作業(yè)的內(nèi)存進行設(shè)置；這樣，盡管內(nèi)存的空閑分區(qū)大小已經(jīng)變小，但是，以后卻無法對已分配的內(nèi)存空間以及作業(yè)進行修改；于是，我經(jīng)過思考后，決定將分配給作業(yè)的內(nèi)存空間也設(shè)置為一個分區(qū)，只不過不是空閑的分區(qū)，通過狀態(tài)標識符。來與空閑分區(qū)進行區(qū)別。2） 回收內(nèi)存空間模塊：剛開始編寫此模塊的代碼時，我有一種無從下手的感覺；因為，如果要回收某個作業(yè)的內(nèi)存，那么必須知道該作業(yè)所在的內(nèi)存中的位置；但是，剛開始我用的數(shù)據(jù)結(jié)構(gòu)中只有表示內(nèi)存狀態(tài)的屬性（分區(qū)可用空間大小，狀態(tài)標識符，前后向指針），這樣就不能對特定的作業(yè)進行操作；最后，我經(jīng)過思考決定在內(nèi)存的數(shù)據(jù)結(jié)構(gòu)中增加一項，即作業(yè)標識符，用來保存分區(qū)中的作業(yè)信息，從而達到查找特定作業(yè)所在內(nèi)存分區(qū)的目的。3） 在編寫代碼的過程中，我還遇到了一些小的問題；比如，對鏈表進行操作時，老是出現(xiàn)錯誤，不能對鏈表進行正確的操作等；這些問題與我對鏈表的認識不夠深入和準確有關(guān)，不過，通過這次程序的編寫，進一步加深了我對鏈表的理解，對鏈表的運用也變得得心應(yīng)手了。7測試結(jié)果1）測試數(shù)據(jù)：作業(yè)1申請130KB；作業(yè)2申請60KB；作業(yè)3申請100KB；作業(yè)2釋放60KB；作業(yè)4申請200KB；作業(yè)3釋放100KB；作業(yè)1釋放130KB；作業(yè)5申請140KB；作業(yè)6申請60KB；作業(yè)7申請50KB；作業(yè)6釋放60KB2）程序運行結(jié)果如圖3、4所示：圖3程序運行結(jié)果圖*乍;\￡++輸出、采用首次適匝諄袪的動?xùn)朔謪^(qū)分配、采用首次適應(yīng)臬袪的動譽分區(qū)分配.睛說擇你罵進行的操啊1、創(chuàng)建篩業(yè)2.舌看空閑分區(qū)鏈2空用分區(qū)鏈的情況為：空閑分區(qū)i640K睛選和你曇進行的操低1、創(chuàng)建篩業(yè)2.舌看空閑分區(qū)鏈3.可反內(nèi)存空間0，退出3.可反內(nèi)存空間0，退出區(qū)要惣建的保業(yè)的編號：1認作業(yè)的需乗空間大小:130附配成咖屛你署進行的操苗劃建胡F業(yè)2,古看空鬧疔區(qū)鏈認要您建的幣業(yè)的編號：2認作業(yè)的需乗空間大小:60附配威功!屛你鷲進行的操低劃建審乍業(yè)2.魯看空鬧分區(qū)鏈3、可枝內(nèi)存空間0.退出3.可收內(nèi)存空間0.退出睛樹入妾倉!建的隹業(yè)対騙轉(zhuǎn)3f|A作業(yè)的需親空同大卜108肉存弁配成功I請迭洋禰瞬進行的操毎仁創(chuàng)建髀業(yè)2.魯看空閑分區(qū)鏈33.可收內(nèi)存空間0.退出1ffi三角D黒郭內(nèi)存的作業(yè)弓；2恢兩內(nèi)存已回憶 的操年2.備看空閑兮區(qū)鏈創(chuàng)建新3.可收內(nèi)存空間0.退出牧筍蠶零空離足200三分配成功I圖4程序運行結(jié)果圖150K蘿丁粵操逵著空閑分區(qū)鏈3150K蘿丁粵操逵著空閑分區(qū)鏈3、回收內(nèi)存空間進行的操企：匸業(yè)2、卷看空閑分區(qū)鏈3、回收內(nèi)存空間回收內(nèi)存的作業(yè)號：3勺存己回妝！鷲逬行的操企：1、創(chuàng)建薪祜業(yè)2、卷看空閑分區(qū)鏈3、回收內(nèi)存空間1語選擇你鴦逬行的操企：-創(chuàng)建薪祜業(yè)2、卷看空閑分區(qū)鏈3、回收內(nèi)存空間請強入妾創(chuàng)建的企業(yè)的編號：14(3誼卷△住坐耳需求空間大?。赫埼航B爾鴦逬行的操企：14(3-創(chuàng)建薪祜業(yè)2、卷看空閑分區(qū)鏈3、回收內(nèi)存空間請?zhí)腿腈獎?chuàng)建的