操作系統(tǒng)實(shí)驗(yàn)四主存空間的分配與回收

1、實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)名稱】 首次適應(yīng)算法和循環(huán)首次適應(yīng)算法【實(shí)驗(yàn)?zāi)康摹坷斫庠谶B續(xù)分區(qū)動態(tài)的存儲管理方式下，如何實(shí)現(xiàn)主存空間的分配與回收?！緦?shí)驗(yàn)原理】首次適應(yīng)（first fit，F(xiàn)F）算法FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_ 始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)即可。 然后再按照作業(yè)的 大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請求者，余下的空閑分區(qū)仍留在空 閑鏈中。若從鏈?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ū)，從中劃出一塊玉請求大小相等的內(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)和符號說明：typedef struct PCB/進(jìn)程控制塊char ProgressName10; 進(jìn)程名稱int Startaddress;int ProgressSi

3、ze;int ProgressState = 0;；typedef struct FREEint Free_ num;int Startaddress;int En daddress;int Free_Space; 一/進(jìn)程開始地址/進(jìn)程大小/進(jìn)程狀態(tài)/空閑區(qū)結(jié)構(gòu)體/空閑區(qū)名稱空閑區(qū)開始地址/空閑區(qū)結(jié)束地址/空閑區(qū)大小否空閑區(qū)指針指向下 一個(gè)空閑區(qū)否是否為最后一個(gè)空閑區(qū)?開始1空閑區(qū)登記1F插入作業(yè)F空閑區(qū)指一個(gè)空針指向第:閑區(qū)首次適應(yīng)算法f前空閑區(qū)是否滿足要求?插入失敗插入作業(yè)，修改內(nèi) 存信息和作業(yè)信息表是結(jié)束循環(huán)首次適應(yīng)算法算法流程圖:開始程序代碼及截圖:#in clude#in clud

4、e#in elude #i nclude #defi ne N 1024typedef struct PCB 進(jìn)程控制塊 char ProgressName10;int Startaddress;int ProgressSize;int ProgressState = 0; ;typedef struct FREEint Free_ num;int Startaddress;int En daddress;int Free_Space;/進(jìn)程名稱進(jìn)程開始地址/進(jìn)程大小/進(jìn)程狀態(tài)/空閑區(qū)結(jié)構(gòu)體/空閑區(qū)名稱/空閑區(qū)開始地址/空閑區(qū)結(jié)束地址/空閑區(qū)大小;int count = 0; /當(dāng)前內(nèi)存中進(jìn)程

5、個(gè)數(shù)bool ROMN;設(shè)置內(nèi)存塊int p = 0;/循環(huán)首次使用需要標(biāo)記當(dāng)前的空閑區(qū)塊FREE FREE100;設(shè)置空閑區(qū)數(shù)組為 100個(gè)int FREE_counter = 0;/ 空閑區(qū)的個(gè)數(shù)PCB num20;作業(yè)隊(duì)列void init()初始化操作for(int i=0; iN; i+)ROMi = 0;void showProgress(PCB &a)printf(”n);printf(”進(jìn)程名tt開始地址tt大小tt結(jié)束地址n”);/輸出內(nèi)存信息printf(”n);for(i nt i=0; ico un t-1; i+)for(i nt j=i; jnu mj+1.Star

6、taddress)a = nu mj;nu mj = nu mj+1;nu mj+1 = a;for(i nt i=0; ico unt; i+)if(nu mi. ProgressState!=0)prin tf(%stt%dttt%dtt%dtt n, numi.ProgressName ,n umi.Startaddress, nu mi.ProgressSiz e,nu mi.ProgressSize+nu mi.Startaddress-1);printf(”n);void showFree()/打印空閑區(qū)的情況printf(”n);printf(空閑區(qū)名t|開始地址t|大小 t|結(jié)

7、束地址n);printf(”n);for (int i=1; i= FREE_co un ter; i+)prin tf(t%1dt%8dt%11dt%dn,FREEi.Free_num,FREEi.Startaddress,FREEi.Free_Space,FREEi.E ndaddress);printf(”n ”)；void fin d_FREE()尋找空閑區(qū)int i,j,p;計(jì)數(shù)值FREE_cou nter = 0;/預(yù)設(shè)空閑區(qū)數(shù)為 0for(i = 0; i N; i+)if(ROMi = 0)p = i;for(j = i; j N; j+)if(ROMj=0)/未找到空閑區(qū)，則

8、將 j賦值給i后繼續(xù)循環(huán)i = j;con ti nue;if(ROMj=1)/找到空閑區(qū)FREE_counter+; 空閑區(qū)個(gè)數(shù) +1 ；FREEFREE_counter.Free_num = FREE_counter;/ 設(shè)置空閑區(qū)編號FREEFREE_cou nter.Startaddress = p;FREEFREE_cou nter.E ndaddress = j-1;FREEFREE_co un ter.Free_Space = j-p;i=j+1;break;if(j = N & ROMj-1 = 0)/對最后一個(gè)內(nèi)存進(jìn)行特殊操作FREE_co un ter+;FREE FREE

9、_counter.Free_num = FREE_counter;/ 對空閑區(qū)進(jìn)行處理FREE FREE_cou nter.Startaddress = p;FREE FREE_cou nter.E ndaddress =j-1;FREE FREE_co un ter.Free_Space = j-p;void First_Fit(PCB &a)/ 首次適應(yīng)算法int i,j,k;for(i=0; iN; i+)if(ROMi=0)for(j=i; j=(i+a.ProgressSize )&jN; j+)查詢第一個(gè)空閑區(qū)，并判斷是否適合插入作業(yè)if(ROMj=1)i = j + 1;brea

10、k;if(j=i+a.ProgressSize+1)a.Startaddress = i;設(shè)置作業(yè)的開始地址a.ProgressState = 1;/標(biāo)記作業(yè)在內(nèi)存中for(k=i; ki+a.ProgressSize&jN; 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_Fi

11、t(PCB &a)/循環(huán)首次適應(yīng)算法來實(shí)現(xiàn)作業(yè)調(diào)度int i,j,k;for(i=p; iN; i+)/從所標(biāo)記的當(dāng)前區(qū)域開始查詢，查詢到末內(nèi)存if(ROMi=0)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; ki+a.ProgressSize&jN; k+)R0Mk=1;printf(”插入成功，進(jìn)程%s的初始地址為d,結(jié)束地址為 dn ,a.Progress

12、Name,a.Startaddress,a.Startaddress+a.ProgressSize-1);p=i+a.ProgressSize;return;for(i=0; ip; i+)/當(dāng)未找到時(shí)，從第一個(gè)空閑區(qū)開始查詢，結(jié)束條件為小于所標(biāo)記的Pif(ROMi=0)for(j=i; j=(i+a.ProgressSize )&jp; 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; ki+a.Progress

13、Size&jp; k+)ROMk=1;printf(”插入成功，進(jìn)程 %s 的初始地址為 dn ,a.ProgressName,a.Startaddress);p=i+a.ProgressSize;break;if(i=p)查詢兩部分都未找到合適的區(qū)域，輸出插入失敗語句printf(插入失敗，無可用空間n);void Delete(PCB &a)刪除作業(yè)，修改內(nèi)存信息和初始化該作業(yè)信息int i;for(i=a.Startaddress; ia.Startaddress+a.ProgressSize; i+)ROMi=O;a.ProgressState=0;/狀態(tài)標(biāo)記為未使用printf(進(jìn)程

14、 %s 刪除成功 n,a.ProgressName);int mai n()int choose1,choose;char ProgressName10;PCB a;ini t();printf(t主存空間的分配與回收n);printf(”-n ”);printf(t1、首次適應(yīng)算法n);printf(t2、循環(huán)首次適應(yīng)算法n);printf(-n ”);printf(請選擇分配算法：”)；scan f(%d,&choose1);system(cls);while(1)w:system(cls);printf(當(dāng)前分配算法：);if(choose1 = 1)printf(首次適應(yīng)算法n);el

15、seprintf(循環(huán)首次適應(yīng)算法n);printf(n);printf(t1、插入進(jìn)程 n);printf(t2、刪除進(jìn)程 n);printf(t3、顯示進(jìn)程的信息n);printf(t4、顯示空閑區(qū) n);printf(n);printf(請輸入:);scan f(%d, &choose);system(cls);switch(choose)case 1:printf(請輸入進(jìn)程名:);scan f(%s, &a.P rogressName);printf(請輸入進(jìn)程的大?。?;scan f(%d,&a.P rogressSize);for(i nt i = 0; i count; i+)

16、if(strcmp( nu mi.ProgressName,a.ProgressName)=0) printf(已存在同名進(jìn)程，無法插入。n);system(pause);goto w;if(choose仁=1)/首次適應(yīng)算法First_Fit(a);elseNext_Fit(a);循環(huán)首次適應(yīng)算法nu mco un t+=a;break;case 2:if(co unt = 0)printf(當(dāng)前沒有進(jìn)程在內(nèi)存中，無法刪除！n);system(pause);goto w;printf(輸入刪除的進(jìn)程名字：);scan f(%s,&ProgressName);for(i nt i=0; ico unt; i+)if(!strcmp( nu mi .P rogressName,ProgressName) Delete( nu mi);elseprintf(”沒有找到對應(yīng)進(jìn)程，請重新輸入。n);break;case 3:showProgress(a);break;case 4:fin d_FREE();showFree();break;default:printf(n 無效的輸入。n”);system(pause);return 0;主界面:首次適應(yīng)算法，初始空閑區(qū):插入進(jìn)程:E;l啟如=1I