張蒙用首次適應(yīng)算法模擬內(nèi)存的分配和回收

1、 采用首次適應(yīng)算法實(shí)現(xiàn)主存的分配和回收一、目的在計(jì)算機(jī)系統(tǒng)中，為了提高內(nèi)存區(qū)的利用率，必須給電腦內(nèi)存區(qū)進(jìn)行合理的分配。本實(shí)驗(yàn)通過(guò)對(duì)內(nèi)存區(qū)分配方法首次適應(yīng)算法的使用，來(lái)了解內(nèi)存分配的模式。在熟練掌握計(jì)算機(jī)分區(qū)存儲(chǔ)管理方式的原理的基礎(chǔ)上，編程模擬實(shí)現(xiàn)操作系統(tǒng)的可變分區(qū)存儲(chǔ)管理的功能，一方面加深對(duì)原理的理解，另一方面提高根據(jù)已有原理通過(guò)編程解決實(shí)際問(wèn)題的能力，為進(jìn)行系統(tǒng)軟件開發(fā)和針對(duì)實(shí)際問(wèn)題提出高效的軟件解決方案打下基礎(chǔ)。二、實(shí)驗(yàn)內(nèi)容與數(shù)據(jù)結(jié)構(gòu)：(1) 可變式分區(qū)管理是指在處理作業(yè)過(guò)程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的需要，并且分區(qū)的個(gè)數(shù)是可以調(diào)整的。當(dāng)需要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的貯存量，查

2、看是否有足夠的空閑空間，若有，則按需求量分割一部分給作業(yè)；若無(wú)，則作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分割成許多大大小小的分區(qū)。有的分區(qū)被分配作業(yè)占用，有的分區(qū)空閑，例如，某時(shí)刻主存空間占用情況如圖所示：為了說(shuō)明哪些分區(qū)是空閑的，可以用來(lái)裝入新作業(yè)，必須要有一張空閑區(qū)說(shuō)明表，如下圖所示。(2) 當(dāng)有一個(gè)新作業(yè)要求裝入貯存時(shí)，必須查空閑區(qū)說(shuō)明表，從中找出一個(gè)足夠大的空閑區(qū)。有時(shí)找到的空閑區(qū)可能大于作業(yè)的需求量，這時(shí)應(yīng)將空閑區(qū)一分為二。一個(gè)分給作業(yè)，另一個(gè)仍作為空閑區(qū)留在空閑區(qū)表中。為了盡量減少由于分割造成的碎片，盡可能分配地地址部分的空閑區(qū)，將較大的空閑區(qū)留在高地址端，以利于大作業(yè)的裝入。

3、為此在空閑區(qū)表中，按空閑區(qū)首地址從低到高進(jìn)行登記。(3) 當(dāng)一個(gè)作業(yè)執(zhí)行完成時(shí)，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。在歸還時(shí)，要考慮相鄰空間區(qū)合并問(wèn)題。作業(yè)的釋放區(qū)與空閑區(qū)的鄰接分以下4種情況考慮：A、 釋放區(qū)下鄰空閑區(qū)；B、 釋放區(qū)上鄰空閑區(qū)；C、 釋放區(qū)上下都與空閑區(qū)鄰接；D、 釋放區(qū)上鄰空閑區(qū)不鄰接；一、 實(shí)驗(yàn)要求1. 內(nèi)存大小初始化2. 可以對(duì)內(nèi)存區(qū)進(jìn)行動(dòng)態(tài)分配，采用首次適應(yīng)算法來(lái)實(shí)現(xiàn)3. 可以對(duì)已分配的內(nèi)存塊進(jìn)行回收，并合并相鄰的空閑內(nèi)存塊。二、 實(shí)驗(yàn)內(nèi)容把一個(gè)作業(yè)裝入內(nèi)存，按照首次適應(yīng)算法對(duì)內(nèi)存區(qū)進(jìn)行分配，作業(yè)結(jié)束，回收已分配給該作業(yè)的內(nèi)存塊，并合并相鄰的空閑內(nèi)存塊。三、 實(shí)驗(yàn)結(jié)果運(yùn)行效

4、果：1.初始化內(nèi)存區(qū)大小，并添加作業(yè)，選擇1添加作業(yè)2.當(dāng)作業(yè)大小超過(guò)存儲(chǔ)塊大小時(shí)，分配失敗。3.選擇3，可查看內(nèi)存分配情況4. 選擇2回收內(nèi)存5. 選擇1添加新作業(yè)6. 回收C作業(yè)，相鄰的空閑內(nèi)存塊合并。五、程序流程圖：六、實(shí)驗(yàn)源代碼：/ FirstFit.cpp : 可變分區(qū)用首次適應(yīng)算法來(lái)模擬內(nèi)存回收#include <STDIO.H>#include <STDLIB.H>int MAX_SEGMENT=10;/最大碎片值struct Partition/分區(qū)表目int Par_Size;/分區(qū)大小int Par_No;/分區(qū)序號(hào)或者名字int Addr;/分區(qū)地

5、址int IsUse;/分區(qū)使用情況,0表示空閑，1表示使用Partition *pri;/前向指針Partition *next;/后向指針;Partition * Int()/函數(shù)，返回Partition類型指針/初始化空閑分區(qū)表Partition *list,*H,*H1;list=(struct Partition *)malloc(sizeof(struct Partition);list->next=NULL;H=list;if(!list)printf("n錯(cuò)誤,內(nèi)存初始化分配失敗！程序結(jié)束");exit(1);H1=(struct Partition

6、*)malloc(sizeof(struct Partition);printf("請(qǐng)預(yù)先輸入分區(qū)總大小(以KB為單位)：");scanf("%d",&H1->Par_Size);H1->Addr=0;H1->Par_No=0;H1->IsUse=0;H1->pri=H;H1->next=NULL;H->next=H1;/list->H1return list;Partition * InitFP()/初始化已分配分區(qū)表Partition *FP,*F,*H;int i;FP=(struct Par

7、tition *)malloc(sizeof(struct Partition);FP->next=NULL;H=FP;for(i=0;i<10;i+)/已分配區(qū)先暫定分配十個(gè)表目F=(struct Partition *)malloc(sizeof(struct Partition);if(!F)printf("n錯(cuò)誤,內(nèi)存分配失??！程序結(jié)束");exit(1);F->Par_Size=0;F->Addr=0;F->Par_No=0;F->IsUse=0;F->next=NULL;H->next=F;F->pri=H;

8、H=H->next;return FP;Partition * New_Process( Partition *list, Partition *FP)/為新的進(jìn)程分配資源Partition *H,*P,*H1;int Size,Name,L;H=list;H1=FP->next;H=H->next;printf("請(qǐng)輸入新作業(yè)的名稱和大小(整數(shù)):");scanf("%d %d",&Name,&Size);while(H)if(!H)/表目已查完，無(wú)法分配printf("n已無(wú)空閑分區(qū),本次無(wú)法分配!&quo

9、t;);return list;elseif(H->IsUse=0)/空表目/if(H->Par_Size>=Size)/大小滿足,空閑分區(qū)大小要分配的大小if(H->Par_Size>=Size)/大小滿足,bool temp=false;if(H->Par_Size-Size)<=MAX_SEGMENT)/空閑分區(qū)大小-要分配的大小<碎片值,會(huì)產(chǎn)生碎片,將整塊內(nèi)存大小分配出去，Size=H->Par_Size;/分配的大小為整塊內(nèi)存temp=true;/會(huì)產(chǎn)生碎片/其他情況就分配大小為請(qǐng)求大小，不會(huì)產(chǎn)生碎片，L=H->Addr;/

10、保存空閑分地址if(temp)printf("該次內(nèi)存分配會(huì)產(chǎn)生碎片,將整塊內(nèi)存大小%d分配出去!",Size);elseprintf("該次內(nèi)存分配不會(huì)產(chǎn)生碎片");break; H=H->next;/否則，繼續(xù)往下查找if(H)if(H->Par_Size>Size)/大小滿足,空閑分區(qū)大小要分配的大小P=(struct Partition *)malloc(sizeof(struct Partition);/分配新的表目，處理一條數(shù)據(jù)，分配一次內(nèi)存P->IsUse=1;P->Addr=L;/指向空閑分區(qū)地址P->

11、next=H;/修改指針H->pri->next=P;P->pri=H->pri;H->pri=P;P->Par_Size=Size;/分配大小為要請(qǐng)求分配的大小P->Par_No=Name;/名稱H->Par_Size-=Size;/修改空閑分區(qū),H所指區(qū)塊大小減SizeH->Addr+=Size;/H所指區(qū)塊地址加SizeelseH->IsUse=1;/大小相等的，把當(dāng)前表項(xiàng)設(shè)置空表目while(H1)if(H1->IsUse=0)H1->Par_No=Name;H1->Par_Size=Size;H1->

12、Addr=L;/保存已分配地址H1->IsUse=1;/在已分配表中設(shè)置為已分配break;H1=H1->next;elseprintf("所申請(qǐng)資源已大過(guò)系統(tǒng)所擁有的,請(qǐng)重新輸入!n");return list;Partition *Reclaim( Partition *list, Partition *FP)/結(jié)束作業(yè),資源回收,No為作業(yè)名，回收內(nèi)存 Partition * H1,*H2,*H3,*HF;/H1為釋放區(qū)，H2為后分區(qū)，H3為前分區(qū)int No;/作業(yè)名H1=list;HF=FP;/可有可無(wú)？H1=H1->next;HF=FP->

13、;next;printf("請(qǐng)輸入您想結(jié)束的作業(yè)名:");scanf("%D",&No);while(HF)/對(duì)已分配表進(jìn)行操作if(HF->Par_No=No)HF->IsUse=0;/標(biāo)志為空表目break;/這時(shí)保存著HF所指分區(qū)的信息HF=HF->next;if(!HF)/如果找不到該作業(yè)，則提示出錯(cuò)printf("所輸入的作業(yè)名稱不正確,請(qǐng)重新輸入!");elsewhile(H1)/對(duì)空閑表進(jìn)行操作if(H1->Par_No=No)H1->IsUse=0;/標(biāo)志為空表目printf(&q

14、uot;內(nèi)存回收成功");break;H1=H1->next;H2=H1->next;/后分區(qū)H3=H1->pri;/前分區(qū)if(H2&&H2->IsUse=0)/后接分區(qū)為空閑if(H2->next=NULL)/判斷后接分區(qū)是否為尾結(jié)點(diǎn)H1->Par_Size+=H2->Par_Size;/把H2合并到H1H1->next=NULL;free(H2);printf("已回收%d大小內(nèi)存",H1->Par_Size);else/后分區(qū)不為空閑，表示已經(jīng)被使用H1->Par_Size+=H2

15、->Par_Size;H1->next=H2->next;H2->next->pri=H1;free(H2);printf("已回收%d大小內(nèi)存",H1->Par_Size);if(H3&&H3->IsUse=0)/前分區(qū)為空閑分區(qū)，則合并去前分區(qū)H3->Par_Size+=H1->Par_Size;H3->next=H1->next;if(H1->next!=NULL)/若H1為尾結(jié)點(diǎn)H1->next->pri=H3;free(H1);printf("已回收%d大

16、小內(nèi)存",H1->Par_Size);return list;void Print( Partition *list, Partition *FP)/輸出已分配分區(qū)和空閑分區(qū) Partition *H1,*H2;H1=list->next;H2=FP;H2=H2->next;printf("*已分配分區(qū)表*n");printf("分區(qū)序號(hào)大小始址 狀態(tài)n");while(H2)printf("%d%d%d",H2->Par_No,H2->Par_Size,H2->Addr);if(H2-&

17、gt;IsUse=1)printf("已分配n");elseprintf("空表目n");H2=H2->next;printf("*n");printf("*總的空閑分區(qū)表*n");printf("分區(qū)序號(hào)大小始址 狀態(tài)n");while(H1)printf("%d%d%d",H1->Par_No,H1->Par_Size,H1->Addr);if(H1->IsUse=1)printf("已分配n");elseprintf(&

18、quot;空表目n");H1=H1->next;printf("*n");void Main_Print( Partition *list, Partition *FP)/主入口函數(shù)，進(jìn)行菜單選擇int op;while(1)printf("n主菜單n");printf("1.申請(qǐng)新的作業(yè),分配內(nèi)存n");printf("2.結(jié)束作業(yè),回收內(nèi)存n");printf("3.查看內(nèi)存表n");printf("4.退出系統(tǒng)n");printf("n請(qǐng)選擇:");scanf("%d",&op);switch(op)/根據(jù)輸入,選擇分支方向case 1: New_Process(list,FP);break;case 2: Reclaim(list,FP);break;case 3:Print(list,FP);break;case 4:break