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

1、實驗報告實驗名稱 首次適應算法和循環(huán)首次適應算法【實驗目的】理解在連續(xù)分區(qū)動態(tài)的存儲治理方式下,如何實現(xiàn)主存空間的分配與回收.【實驗原理】首次適應(first fit, FF)算法FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接.在分配內存時,從鏈首開 始順序查找,直至找到一個大小能滿足要求的空閑分區(qū)即可. 然后再根據(jù)作業(yè)的 大小,從該分區(qū)中劃出一塊內存空間,分配給請求者,余下的空閑分區(qū)仍留在空 閑鏈中.假設從鏈首直至鏈尾都不能找到一個能滿足要求的分區(qū),那么說明系統(tǒng)中已經沒有足夠大的內存分配給該進程,內存分配失敗,返回.循環(huán)首次適應(next fit, NF)算法為防止低址局部留下許多很小的空閑分區(qū)

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

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

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

5、EE FREE100;/設置空閑區(qū)數(shù)組為100個int FREE_counter = 0;/ 空閑區(qū)的個數(shù)PCB num20;作業(yè)隊列void init()/初始化操作 for(int i=0; i<N; i+) ROMi = 0; void showProgress(PCB &a) printf("n");printf("進程名tt開始地址tt大小tt結束地址n");/輸出內存信息 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| 結束地址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;/計數(shù)值FREE_counter = 0;/預設空閑區(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ū)個數(shù) +1;FREEFREE_counter.Free_num = FREE_counter;/ 設置空閑區(qū)編號 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)/對最后一個內存進行特殊操作(FREE_counter+;FREE FREE_counter.Free_num = FREE_counter;/ 對空閑區(qū)進行處理 FREE FREE_counter.Startaddress = p;FREE FREE_counter.Endaddress =j-1; FREE FREE_counter.Free_Space = j-p; void First_

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

11、t;N; k+) ROMk=1;printf("進程%s插入成功,進程%s的初始地址為d,結束地址 為 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)首次適應算法來實現(xiàn)作業(yè)調度(int i,j,k;for(i=p; i<N; i+)/從所標記的當前區(qū)域開始查詢,查詢到末內存(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("插入成功,進程s的初始地址為d,結束地址 為 dn,a.ProgressName,a.Startaddress,a.Startaddress+a.Pr

13、ogressSize-1);p=i+a.ProgressSize;return;for(i=0; i<p; i+)/當未找到時,從第一個空閑區(qū)開始查詢,結束條件為小于所標記的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)/成功找到結束,并標記當前P為現(xiàn)在的作業(yè)的尾部a.Startaddress=i;a.ProgressState=1;for(k=i; k<i+a.ProgressSize&&

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

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

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

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

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