操作系統(tǒng)實驗首次適應(yīng)算法與循環(huán)首次適應(yīng)算法

1、學(xué)號P71514032 專業(yè)計算機科學(xué)與技術(shù) 姓名 實驗日期 教師簽字 成績實驗報告【實驗名稱】首次適應(yīng)算法和循環(huán)首次適應(yīng)算法【實驗?zāi)康摹繉W(xué)會主存空間分配與回收的基本方法首次適應(yīng)算法和循環(huán)首次適應(yīng)算法。【實驗原理】理解在連續(xù)分區(qū)動態(tài)的存儲管理方式下，如何實現(xiàn)貯存空間的分配與回收。采用可變式分區(qū)管理，使用最佳適應(yīng)算法實現(xiàn)主存空間的分配與回收。采用可變式分區(qū)管理，使用最壞適應(yīng)算法實現(xiàn)主存空間的分配與回收。數(shù)據(jù)結(jié)構(gòu)：1、bool ROMN; /定義主存信息，如果內(nèi)存被占用，則標(biāo)記為1，否則標(biāo)記為0，設(shè)置內(nèi)存單元為10242、pcb num20;/定義作業(yè)數(shù)組，最大支持20個作業(yè)3、typedef s

2、truct Pcb /定義作業(yè)結(jié)構(gòu)體，包括名稱，開始時間，大小，是否執(zhí)行狀態(tài) char name10; int start; int size; int state=0; pcb;typedef struct Free_rom /空閑區(qū)結(jié)構(gòu)體 int num; int start; int end; int space; Free_room;Free_rom free_rom100;/設(shè)置空閑區(qū)數(shù)組為100個主要函數(shù)void init()；/初始化信息，包括初始化內(nèi)存信息，和初始化作業(yè)隊列void insert_pcb1(pcb &a)；插入作業(yè)函數(shù)，首次適應(yīng)算法，如果有適合的就插入，無合適輸

3、出插入失敗void insert_pcb1(pcb &a)；插入作業(yè)函數(shù)，循環(huán)首次適應(yīng)算法，如果有適合的就插入，無合適輸出插入失敗void Delete(pcb &a)/刪除作業(yè)信息，包括修改內(nèi)存狀態(tài)修改作業(yè)狀態(tài)并對作業(yè)進(jìn)行初始化void show();/顯示信息void find_free_rom() /尋找空閑區(qū)算法流程圖首次適應(yīng)算法循環(huán)首次適應(yīng)算法程序代碼及截圖：#include#include#define N 1024bool ROMN;/設(shè)置內(nèi)存塊int p=0;/循環(huán)首次使用需要標(biāo)記當(dāng)前的空閑區(qū)塊typedef struct Pcb/作業(yè)數(shù)據(jù)結(jié)構(gòu) char name10; int

4、 start; int size; int state=0; pcb;int free_rom_counter=0;pcb num20; /作業(yè)隊列typedef struct Free_rom /空閑區(qū)結(jié)構(gòu)體 int num; int start; int end; int space; Free_room;Free_rom free_rom100;/設(shè)置空閑區(qū)數(shù)組為100個void find_free_rom() /尋找空閑區(qū) free_rom_counter=0; int i,j,p; for(i=0; iN; i+) if(ROMi=0) p=i; for(j=i; jN; j+) i

5、f(ROMj=0) i=j; continue; if(ROMj=1)/找到空閑區(qū) free_rom_counter+; free_rom free_rom_counter.num= free_rom_counter; free_rom free_rom_counter.start=p; free_rom free_rom_counter.end=j-1; free_rom free_rom_counter.space=j-p; i=j+1; break; if(j=N&ROMj-1=0)/對最后一個內(nèi)存進(jìn)行特殊操作 free_rom_counter+; free_rom free_rom_c

6、ounter.num= free_rom_counter;/對空閑區(qū)進(jìn)行處理 free_rom free_rom_counter.start=p; free_rom free_rom_counter.end=j-1; free_rom free_rom_counter.space=j-p; void init()/初始化 for(int i=0; iN; i+) ROMi=0;void show() printf(空閑區(qū)名t開始地址tt大小tt結(jié)束地址ttn); for (int i=1; i= free_rom_counter; i+) printf(%dtt%dttt%dtt%dttn,f

7、ree_rom i.num,free_rom i.start, free_rom i.space,free_rom i.end);void insert_pcb1(pcb &a)/首次適應(yīng)算法來實現(xiàn)作業(yè)調(diào)度 int i,j,k; for(i=0; iN; i+) if(ROMi=0) for(j=i; j=(i+a.size)&jN; j+)/查詢第一個空閑區(qū)，并判斷是否適合插入作業(yè) if(ROMj=1) i=j+1; break; if(j=i+a.size+1) a.start=i;/設(shè)置作業(yè)的開始內(nèi)存 a.state=1;/標(biāo)記作業(yè)在內(nèi)存中 for(k=i; ki+a.size&jN;

8、k+) ROMk=1; printf(插入成功，進(jìn)程%s 的初始地址為%d,結(jié)束地址為%dn,,a.start,a.start+a.size-1); return; if(i=N)/未查詢到合適的區(qū)域 printf(插入失敗，無可用空間n);void insert_pcb2(pcb &a)/循環(huán)首次適應(yīng)算法來實現(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.size)&jN; j+) if(ROMj=1) i=j+1; break; if(j=i+a.size+1)/

9、找到合適的空閑區(qū) a.start=i; a.state=1; for(k=i; ki+a.size&jN; k+) ROMk=1; printf(插入成功，進(jìn)程%s 的初始地址為%d,結(jié)束地址為%dn,,a.start,a.start+a.size-1); p=i+a.size; return; for(i=0; ip; i+)/當(dāng)未找到時，從第一個空閑區(qū)開始查詢，結(jié)束條件為小于所標(biāo)記的P if(ROMi=0) for(j=i; j=(i+a.size)&jp; j+) if(ROMj=1) i=j+1; break; if(j=i+a.size+1)/成功找到結(jié)束，并標(biāo)記當(dāng)前P為

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

11、刪除成功n);int main() init(); int count=0; int choose1,choose; char name10; pcb a; printf(1、首次適應(yīng)算法n); printf(2、循環(huán)首次適應(yīng)算法n); scanf(%d,&choose1); do printf(nn1、插入進(jìn)程n); printf(2、刪除進(jìn)程n); printf(3、顯示進(jìn)程的信息n); printf(4、顯示空閑區(qū)n); scanf(%d,&choose); if(choose=1) printf(輸入進(jìn)程名n); scanf(%s,&); printf(輸入進(jìn)程大小n);

12、scanf(%d,&a.size); if(choose1=1) insert_pcb1(a); else insert_pcb2(a); numcount+=a; else if(choose=2) printf(輸入刪除進(jìn)程的名字n); scanf(%s,&name); for(int i=0; icount; i+) if( !strcmp(,name) Delete(numi); else if(choose=3) printf(進(jìn)程名tt開始地址tt大小tt結(jié)束地址ttn);/輸出內(nèi)存信息 for(int i=0; icount-1; i+) for(int j=i

13、; jnumj+1.start) a=numj; numj=numj+1; numj+1=a; for(int i=0; icount; i+) if(numi.state!=0) printf(%stt%dttt%dtt%dttn,,numi.start,numi.size,numi.size+numi.start-1); else if(choose=4) find_free_rom(); show(); else break; while(1); return 0;首次適應(yīng)算法：本實驗共采用1024個內(nèi)存進(jìn)行模擬，首先對內(nèi)存初始化，得到一個大的空閑區(qū)：相繼插入3個進(jìn)程：

14、分別插入進(jìn)程A B C,大小分別為100,200,300此時查詢進(jìn)程信息和查詢空閑區(qū)信息有一塊大小為424 起始地址為600的空閑區(qū)在進(jìn)行插入D刪除B此時有兩塊空閑區(qū)插入一個150大小的進(jìn)程，他的起始地址應(yīng)為100此時空閑區(qū)只有2塊，一塊大小為50，刪除C進(jìn)程，構(gòu)造一塊大空閑區(qū)再插入一個進(jìn)程為100大小,此時兩塊空閑區(qū)都滿足，此時應(yīng)從第一塊插入再插入一個大于兩塊空閑區(qū)大小的進(jìn)程，此時無可用空間首次適應(yīng)算法完成。循環(huán)首次適應(yīng)算法此時有三塊空閑區(qū)，由于先前插入的是E進(jìn)程，此時空閑區(qū)指針指向3，插入一個小于15的內(nèi)存，會插入到3空間，再插入一個5的內(nèi)存，由于采用循環(huán)首次適應(yīng)，此時插入的也是3再插入一個小于200的進(jìn)程，此時掃描到最后，沒找到，轉(zhuǎn)而從低地址開始查找循環(huán)首次適應(yīng)算法正確【小結(jié)或討論】1、 首次適應(yīng)算法傾向于利用內(nèi)存中低地址部分的空閑區(qū)域，從而保留了高地址部分的大空閑區(qū)，這為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。其缺點是低地址部分不斷被劃分，會留下許多難以利用的、很小的空閑分區(qū)碎片。每次查找都是從低地址部分開始的，這樣會增加查找可用空閑分區(qū)的開銷。2、 為了避免低地址部分留下的許多很小的空閑分區(qū)以及減少查找可用空間區(qū)的開銷，循環(huán)首次適應(yīng)算法在為作業(yè)分配時，從上次找到的空閑區(qū)的下一個空閑區(qū)開始查找，找不到再從頭