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

1、學(xué)號(hào)P71514032 專業(yè)計(jì)算機(jī)科學(xué)與技術(shù) 姓名 實(shí)驗(yàn)日期2017.11.16 教師簽字 成績實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)名稱】首次適應(yīng)算法和循環(huán)首次適應(yīng)算法【實(shí)驗(yàn)?zāi)康摹繉W(xué)會(huì)主存空間分配與回收的基本方法首次適應(yīng)算法和循環(huán)首次適應(yīng)算法。【實(shí)驗(yàn)原理】理解在連續(xù)分區(qū)動(dòng)態(tài)的存儲(chǔ)管理方式下，如何實(shí)現(xiàn)貯存空間的分配與回收。采用可變式分區(qū)管理，使用最佳適應(yīng)算法實(shí)現(xiàn)主存空間的分配與回收。采用可變式分區(qū)管理，使用最壞適應(yīng)算法實(shí)現(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個(gè)作業(yè)3

2、、typedef struct Pcb /定義作業(yè)結(jié)構(gòu)體，包括名稱，開始時(shí)間，大小，是否執(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個(gè)主要函數(shù)void init()；/初始化信息，包括初始化內(nèi)存信息，和初始化作業(yè)隊(duì)列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)并對(duì)作業(yè)進(jìn)行初始化void show();/顯示信息void find_free_rom() /尋找空閑區(qū)算法流程圖首次適應(yīng)算法循環(huán)首次適應(yīng)算法程序代碼及截圖：#include<stdio.h>#include<string.h>#define N 1024bool ROMN;/設(shè)置內(nèi)存塊int p=0;/循環(huán)首次使用

4、需要標(biāo)記當(dāng)前的空閑區(qū)塊typedef struct Pcb/作業(yè)數(shù)據(jù)結(jié)構(gòu) char name10; int start; int size; int state=0; pcb;int free_rom_counter=0;pcb num20; /作業(yè)隊(duì)列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個(gè)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)/對(duì)最后一個(gè)內(nèi)存進(jìn)行特殊操作 free_rom_counter+; free_rom free_rom_counter.num= free_rom_counter;/對(duì)空閑區(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; i<N; i+) ROMi=0;void show() printf("空閑區(qū)名t開始地址tt

7、大小tt結(jié)束地址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)/首次適應(yīng)算法來實(shí)現(xiàn)作業(yè)調(diào)度 int i,j,k; for(i=0; i<N; i+) if(ROMi=0) for(j=i; j<=(i+a.size)&&j<N; j+)/

8、查詢第一個(gè)空閑區(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; k<i+a.size&&j<N; 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

9、insert_pcb2(pcb &a)/循環(huán)首次適應(yīng)算法來實(shí)現(xiàn)作業(yè)調(diào)度 int i,j,k; for(i=p; i<N; i+)/從所標(biāo)記的當(dāng)前區(qū)域開始查詢，查詢到末內(nèi)存 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("插入成功，進(jìn)程%s 的

10、初始地址為%d,結(jié)束地址為%dn",,a.start,a.start+a.size-1); p=i+a.size; return; for(i=0; i<p; i+)/當(dāng)未找到時(shí)，從第一個(gè)空閑區(qū)開始查詢，結(jié)束條件為小于所標(biāo)記的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)/成功找到結(jié)束，并標(biāo)記當(dāng)前P為現(xiàn)在的作業(yè)的尾部 a.start=i; a.state=1; for(k=i; k<i+a.size&

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

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

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

14、nf("%s",&name); for(int i=0; i<count; i+) if( !strcmp(,name) Delete(numi); else if(choose=3) printf("進(jìn)程名tt開始地址tt大小tt結(jié)束地址ttn");/輸出內(nèi)存信息 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;首次適應(yīng)算法：本實(shí)驗(yàn)共采用1024個(gè)內(nèi)存進(jìn)行模擬，首先對(duì)內(nèi)存初始化，得到一個(gè)大的空閑區(qū)：相繼插入3個(gè)進(jìn)程：分別插入進(jìn)程A B C,大小分別為100,200,300此時(shí)查詢進(jìn)程信息和查

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