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

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

2、、typedef struct 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ū)數(shù)組為100個主要函數(shù)void init()；/初始化信息，包括初始化內存信息，和初始化作業(yè)隊列void insert_pcb1(pcb &a)；插入作業(yè)函數(shù)，首次適應算法，

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

4、需要標記當前的空閑區(qū)塊typedef struct Pcb/作業(yè)數(shù)據結構 char name10; int 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ū)數(shù)組為100個void find_free_rom() /尋找空閑區(qū) free_rom_counter=0; int i,j,p

5、; for(i=0; i<N; i+) if(ROMi=0) p=i; for(j=i; j<N; j+) if(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&a

6、mp;&ROMj-1=0)/對最后一個內存進行特殊操作 free_rom_counter+; free_rom free_rom_counter.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; i<N; i+) ROMi=0;void show() printf("空閑區(qū)名t開始地址tt

7、大小tt結束地址ttn"); for (int i=1; i<= free_rom_counter; i+) printf("%dtt%dttt%dtt%dttn",free_rom i.num,free_rom i.start, free_rom i.space,free_rom i.end);void insert_pcb1(pcb &a)/首次適應算法來實現(xiàn)作業(yè)調度 int i,j,k; for(i=0; i<N; i+) if(ROMi=0) for(j=i; j<=(i+a.size)&&j<N; j+)/

8、查詢第一個空閑區(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; k<i+a.size&&j<N; k+) ROMk=1; printf("插入成功，進程%s 的初始地址為%d,結束地址為%dn",,a.start,a.start+a.size-1); return; if(i=N)/未查詢到合適的區(qū)域 printf("插入失敗，無可用空間n");void

9、insert_pcb2(pcb &a)/循環(huán)首次適應算法來實現(xiàn)作業(yè)調度 int i,j,k; for(i=p; i<N; i+)/從所標記的當前區(qū)域開始查詢，查詢到末內存 if(ROMi=0) for(j=i; j<=(i+a.size)&&j<N; j+) if(ROMj=1) i=j+1; break; if(j=i+a.size+1)/找到合適的空閑區(qū) a.start=i; a.state=1; for(k=i; k<i+a.size&&j<N; k+) ROMk=1; printf("插入成功，進程%s 的

10、初始地址為%d,結束地址為%dn",,a.start,a.start+a.size-1); p=i+a.size; return; for(i=0; i<p; i+)/當未找到時，從第一個空閑區(qū)開始查詢，結束條件為小于所標記的P if(ROMi=0) for(j=i; j<=(i+a.size)&&j<p; j+) if(ROMj=1) i=j+1; break; if(j=i+a.size+1)/成功找到結束，并標記當前P為現(xiàn)在的作業(yè)的尾部 a.start=i; a.state=1; for(k=i; k<i+a.size&

11、;&j<p; 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; i<a.start+a.size; i+) ROMi=0; a.state=0;/狀態(tài)標記為未使用 printf("刪除

12、成功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&

13、quot;); scanf("%d",&choose); if(choose=1) printf("輸入進程名n"); scanf("%s",&); printf("輸入進程大小n"); scanf("%d",&a.size); if(choose1=1) insert_pcb1(a); else insert_pcb2(a); numcount+=a; else if(choose=2) printf("輸入刪除進程的名字n"); sca

14、nf("%s",&name); for(int i=0; i<count; i+) if( !strcmp(,name) Delete(numi); else if(choose=3) printf("進程名tt開始地址tt大小tt結束地址ttn");/輸出內存信息 for(int i=0; i<count-1; i+) for(int j=i; j<count-1; j+) if(numj.start>numj+1.start) a=numj; numj=numj+1; numj+1=a; for(in

15、t i=0; i<count; 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個進程：分別插入進程A B C,大小分別為100,200,300此時查詢進程信息和查

16、詢空閑區(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è)分配時