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

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

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

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

4、 start; int size; int state=0; pcb;int free_rom_counter=0;pcb num20; /作業(yè)隊列typedef struct Free_rom /空閑區(qū)結構體 int num; int start; int end; int space; Free_room;Free_rom free_rom100;/設置空閑區(qū)數組為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)/對最后一個內存進行特殊操作 free_rom_counter+; free_rom free_rom_c

6、ounter.num= free_rom_counter;/對空閑區(qū)進行處理 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結束地址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è)調度 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;/設置作業(yè)的開始內存 a.state=1;/標記作業(yè)在內存中 for(k=i; ki+a.size&jN;

8、k+) ROMk=1; printf(插入成功，進程%s 的初始地址為%d,結束地址為%dn,,a.start,a.start+a.size-1); return; if(i=N)/未查詢到合適的區(qū)域 printf(插入失敗，無可用空間n);void insert_pcb2(pcb &a)/循環(huán)首次適應算法來實現作業(yè)調度 int i,j,k; for(i=p; iN; i+)/從所標記的當前區(qū)域開始查詢，查詢到末內存 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(插入成功，進程%s 的初始地址為%d,結束地址為%dn,,a.start,a.start+a.size-1); p=i+a.size; return; for(i=0; ip; i+)/當未找到時，從第一個空閑區(qū)開始查詢，結束條件為小于所標記的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)/成功找到結束，并標記當前P為

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

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

12、scanf(%d,&a.size); if(choose1=1) insert_pcb1(a); else insert_pcb2(a); numcount+=a; else if(choose=2) printf(輸入刪除進程的名字n); scanf(%s,&name); for(int i=0; icount; i+) if( !strcmp(,name) Delete(numi); else if(choose=3) printf(進程名tt開始地址tt大小tt結束地址ttn);/輸出內存信息 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;首次適應算法：本實驗共采用1024個內存進行模擬，首先對內存初始化，得到一個大的空閑區(qū)：相繼插入3個進程：

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