操作系統(tǒng)試驗(yàn)四主存空間的分配與回收-首次適應(yīng)算法和循環(huán)首次適應(yīng)算法

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 首次適應(yīng)算法和循環(huán)首次適應(yīng)算法【實(shí)驗(yàn)?zāi)康摹坷斫庠谶B續(xù)分區(qū)動(dòng)態(tài)的存儲(chǔ)治理方式下,如何實(shí)現(xiàn)主存空間的分配與回收.【實(shí)驗(yàn)原理】首次適應(yīng)(first fit, FF)算法FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接.在分配內(nèi)存時(shí),從鏈?zhǔn)组_ 始順序查找,直至找到一個(gè)大小能滿足要求的空閑分區(qū)即可. 然后再根據(jù)作業(yè)的 大小,從該分區(qū)中劃出一塊內(nèi)存空間,分配給請(qǐng)求者,余下的空閑分區(qū)仍留在空 閑鏈中.假設(shè)從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū),那么說明系統(tǒng)中已經(jīng)沒有足夠大的內(nèi)存分配給該進(jìn)程,內(nèi)存分配失敗,返回.循環(huán)首次適應(yīng)(next fit, NF)算法為防止低址局部留下許多很小的空閑分區(qū)

2、, 以及減少查找可用空閑分區(qū)的開 銷,循環(huán)首次適應(yīng)算法在為進(jìn)程分配內(nèi)存空間時(shí), 不再是每次都從鏈?zhǔn)组_始查找, 而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找,直至找到一個(gè)能滿足要 求的空閑分區(qū),從中劃出一塊玉請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè).【實(shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)主存空間的分配與回收：1. 采用可變式分區(qū)治理,使用首次適應(yīng)算法實(shí)現(xiàn)主存空間的分配與回收；2. 采用可變式分區(qū)治理,使用循環(huán)首次適應(yīng)算法實(shí)現(xiàn)主存空間的分配與回 收.數(shù)據(jù)結(jié)構(gòu)和符號(hào)說明：typedef struct PCB/® 程限制塊(char ProgressName10; 進(jìn)程名稱int Startaddress;int P

3、rogressSize;int ProgressState = 0;；typedef struct FREE(int Free_num;int Startaddress;int Endaddress;int Free_Space;一進(jìn)程開始地址進(jìn)程大小進(jìn)程狀態(tài)空閑區(qū)結(jié)構(gòu)體空閑區(qū)名稱空閑區(qū)開始地址空閑區(qū)結(jié)束地址空閑區(qū)大小算法流程圖:首次適應(yīng)算法循環(huán)首次適應(yīng)算法開始/進(jìn)程名稱進(jìn)程開始地址/進(jìn)程大小/進(jìn)程狀態(tài)空閑區(qū)結(jié)構(gòu)體空閑區(qū)名稱空閑區(qū)開始地址空閑區(qū)結(jié)束地址空閑區(qū)大小程序代碼及截圖:#include<stdio.h>#include<string.h>#include <

4、;stdlib.h> #include <io.h>#define N 1024typedef struct PCB/ 進(jìn)程限制塊char ProgressName10;int Startaddress;int ProgressSize;int ProgressState = 0;typedef struct FREEint Free_num;int Startaddress;int Endaddress;int Free_Space;int count = 0; /當(dāng)前內(nèi)存中進(jìn)程個(gè)數(shù)bool ROMN;/設(shè)置內(nèi)存塊int p = 0;/循環(huán)首次使用需要標(biāo)記當(dāng)前的空閑區(qū)塊FR

5、EE FREE100;/設(shè)置空閑區(qū)數(shù)組為100個(gè)int FREE_counter = 0;/ 空閑區(qū)的個(gè)數(shù)PCB num20;作業(yè)隊(duì)列void init()/初始化操作 for(int i=0; i<N; i+) ROMi = 0; void showProgress(PCB &a) printf("n");printf("進(jìn)程名tt開始地址tt大小tt結(jié)束地址n");/輸出內(nèi)存信息 printf("n");for(int i=0; i<count-1; i+) for(int j=i; j<count-1;

6、 j+) if(numj.Startaddress>numj+1.Startaddress) a = numj; numj = numj+1; numj+1 = a; for(int i=0; i<count; i+) if(numi.ProgressState!=0)printf("%stt%dttt%dtt%dttn,numi.ProgressName,numi.Startaddress,numi.ProgressSiz e,numi.ProgressSize+numi.Startaddress-1); printf("n");void showF

7、ree()/打印空閑區(qū)的情況 printf("n");printf(" 空閑區(qū)名t|開始地址t| 大小 t| 結(jié)束地址n");printf("n");for (int i=1; i<= FREE_counter; i+) printf("t%1dt%8dt%11dt%dn",FREEi.Free_num,FREEi.Startaddress,FREEi.Free_Space,FREEi.Endaddress); printf("n");void find_FREE()/尋找空閑區(qū)(int

8、i,j,p;/計(jì)數(shù)值FREE_counter = 0;/預(yù)設(shè)空閑區(qū)數(shù)為 0 for(i = 0; i < N; i+) if(ROMi = 0) ( p = i;for(j = i; j < N; j+) (if(ROMj=0)/未找到空閑區(qū),那么將 j賦值給i后繼續(xù)循環(huán) (i = j;continue;if(ROMj=1)/找到空閑區(qū) (FREE_counter+;/ 空閑區(qū)個(gè)數(shù) +1;FREEFREE_counter.Free_num = FREE_counter;/ 設(shè)置空閑區(qū)編號(hào) FREEFREE_counter.Startaddress = p;FREEFREE_coun

9、ter.Endaddress = j-1; FREEFREE_counter.Free_Space = j-p; i=j+1;break; if(j = N && ROMj-1 = 0)/對(duì)最后一個(gè)內(nèi)存進(jìn)行特殊操作(FREE_counter+;FREE FREE_counter.Free_num = FREE_counter;/ 對(duì)空閑區(qū)進(jìn)行處理 FREE FREE_counter.Startaddress = p;FREE FREE_counter.Endaddress =j-1; FREE FREE_counter.Free_Space = j-p; void First_

10、Fit(PCB &a)/ 首次適應(yīng)算法 int i,j,k;for(i=0; i<N; i+) if(ROMi=0) (for(j=i; j<=(i+a.ProgressSize)&&j<N; j+)/查詢第一個(gè)空閑區(qū),并判斷是否適合插入作業(yè)if(ROMj=1) (i = j + 1; break; if(j=i+a.ProgressSize+1)(a.Startaddress = i;/設(shè)置作業(yè)的開始地址 a.ProgressState = 1;/標(biāo)記作業(yè)在內(nèi)存中 for(k=i; k<i+a.ProgressSize&&j&l

11、t;N; k+) ROMk=1;printf("進(jìn)程%s插入成功,進(jìn)程%s的初始地址為d,結(jié)束地址 為 dn,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);return;if(i=N)/未查詢到適宜的區(qū)域 printf("插入失敗,無可用空間！ n");void Next_Fit(PCB &a)/循環(huán)首次適應(yīng)算法來實(shí)現(xiàn)作業(yè)調(diào)度(int i,j,k;for(i=p; i<N; i+)/從所標(biāo)記的當(dāng)前區(qū)域開始查詢,查詢到末內(nèi)存(if(ROMi=0

12、)(for(j=i; j<=(i+a.ProgressSize)&&j<N; j+) if(ROMj=1) (i = j+1; break;if(j=i+a.ProgressSize+1)/ 找到適宜的空閑區(qū)(a.Startaddress=i;a.ProgressState=1;for(k=i; k<i+a.ProgressSize&&j<N; k+)ROMk=1;printf("插入成功,進(jìn)程s的初始地址為d,結(jié)束地址 為 dn,a.ProgressName,a.Startaddress,a.Startaddress+a.Pr

13、ogressSize-1);p=i+a.ProgressSize;return;for(i=0; i<p; i+)/當(dāng)未找到時(shí),從第一個(gè)空閑區(qū)開始查詢,結(jié)束條件為小于所標(biāo)記的Pif(ROMi=0) for(j=i; j<=(i+a.ProgressSize)&&j<p; j+)if(ROMj=1) i=j+1;break;if(j=i+a.ProgressSize+1)/成功找到結(jié)束,并標(biāo)記當(dāng)前P為現(xiàn)在的作業(yè)的尾部a.Startaddress=i;a.ProgressState=1;for(k=i; k<i+a.ProgressSize&&

14、;j<p; k+)ROMk=1;printf(" 插入成功,進(jìn)程 %s 的初始地址 為 %dn",a.ProgressName,a.Startaddress);p=i+a.ProgressSize;break; if(i=p)/查詢兩局部都未找到適宜的區(qū)域,輸出插入失敗語(yǔ)句 printf(-插入失敗,無可用空間n");void Delete(PCB &a)/刪除作業(yè),修改內(nèi)存信息和初始化該作業(yè)信息int i;for(i=a.Startaddress; i<a.Startaddress+a.ProgressSize; i+)ROMi=0;a.Pr

15、ogressState=0;/l犬態(tài)標(biāo)記為未使用printf("進(jìn)程 %s 刪除成功 n",a.ProgressName);int main()(int choose1,choose;char ProgressName10;PCB a;init();printf("t主存空間的分配與回收n");printf("n");printf("t1、首次適應(yīng)算法n");printf("t2、循環(huán)首次適應(yīng)算法n");printf("n");printf(-請(qǐng)選擇分配算法：");

16、scanf("%d,&choose1);system("cls");while(1)(w:system("cls");printf(-當(dāng)前分配算法:");if(choose1 = 1)printf("首次適應(yīng)算法n");elseprintf("循環(huán)首次適應(yīng)算法n");printf("n");printf("t1、插入進(jìn)程 n");printf("t2、刪除進(jìn)程 n");printf("t3、顯示進(jìn)程的信息n"

17、);printf("t4、顯示空閑區(qū) n");printf("n");printf("請(qǐng)輸入：");scanf("%d",&choose);system("cls");switch(choose)(case 1:printf(-請(qǐng)輸入進(jìn)程名:");scanf("%s,&a.ProgressName);printf(-請(qǐng)輸入進(jìn)程的大小：");scanf("%d,&a.ProgressSize);for(int i = 0; i <

18、; count; i+)if(strcmp(numi.ProgressName,a.ProgressName)=0) (printf("已存在同名進(jìn)程,無法插入.n");system("pause");goto w;if(choose1=1)/首次適應(yīng)算法First_Fit(a);elseNext_Fit(a);/循環(huán)首次適應(yīng)算法 numcount+=a;break;case 2:if(count = 0)(printf("當(dāng)前沒有進(jìn)程在內(nèi)存中,無法刪除！n");system("pause");goto w;printf(-輸入刪除的進(jìn)程名字：");scanf("%s,&ProgressName);for(int i=0; i<count; i+)if(!strcmp(numi.ProgressName,ProgressName) Delete(numi);elseprintf(-沒有找到對(duì)應(yīng)進(jìn)程,請(qǐng)重新輸入.n");break;case 3:showProgress(a);break;case 4:find_FREE();showFree();break;default:printf("n 無效的輸入.n"