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

操作系統(tǒng)實(shí)驗(yàn)-首次適應(yīng)算法與循環(huán)首次適應(yīng)算法首次適應(yīng)算法開始空閑區(qū)登記插入作業(yè)信息空閑區(qū)指針指向第一個(gè)空閑區(qū)當(dāng)前空閑區(qū)是否是否為最后一是否滿足個(gè)空閑區(qū)是否插入當(dāng)前作業(yè)，修空閑區(qū)指針指向下改內(nèi)存信息和作業(yè)作業(yè)插入失敗一個(gè)空閑區(qū)信息表信息是繼續(xù)插入？否整理輸出結(jié)束循環(huán)首次適應(yīng)算法開始是否為最后一空閑區(qū)登記個(gè)空閑區(qū)是空閑區(qū)指針指向第一個(gè)空閑區(qū)，空閑區(qū)指針加一標(biāo)記當(dāng)前空閑區(qū)P否當(dāng)前空閑區(qū)是插入作業(yè)信息否滿足是當(dāng)前空閑區(qū)是 否否滿足是插入當(dāng)前作業(yè)，修改內(nèi)存信息和作業(yè)信息表信息空閑區(qū)指針指向下是一個(gè)空閑區(qū)，標(biāo)記繼續(xù)插入？作業(yè)插入失敗當(dāng)前空閑區(qū)P輸出信息結(jié)束

否空閑區(qū)指針指向第一個(gè)空閑區(qū)是否小于所標(biāo)記的空閑區(qū)P是是 當(dāng)前指針?biāo)赶騾^(qū)域是否滿足否空閑區(qū)指針指向下一個(gè)空閑區(qū)

否否程序代碼及截圖：#include<stdio.h>#include<string.h>#defineN1024boolROM[N];// 設(shè)置內(nèi)存塊intp=0;// 循環(huán)首次使用需要標(biāo)記當(dāng)前的空閑區(qū)塊typedefstructPcb//{

作業(yè)數(shù)據(jù)結(jié)構(gòu)charname[10];intstart;intsize;intstate=0;}pcb;intfree_rom_counter=0;pcbnum[20];// 作業(yè)隊(duì)列typedefstructFree_rom//空閑區(qū)結(jié)構(gòu)體{intnum;intstart;intend;intspace;}Free_room;Free_romfree_rom[100];//設(shè)置空閑區(qū)數(shù)組為100個(gè)voidfind_free_rom()//尋找空閑區(qū){free_rom_counter=0;inti,j,p;for(i=0;i<N;i++)if(ROM[i]==0){p=i;for(j=i;j<N;j++){if(ROM[j]==0){i=j;continue;}if(ROM[j]==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&&ROM[j-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;}}}voidinit()// 初始化{for(inti=0;i<N;i++)ROM[i]=0;}voidshow(){printf(" 空閑區(qū)名\t 開始地址\t\t

大小\t\t

結(jié)束地址\t\t\n");for(inti=1;i<=free_rom_counter;i++)printf("%d\t\t%d\t\t\t%d\t\t%d\t\t\n",free_rom[

i].num,free_rom[

i].start,free_rom[i].space,free_rom[i].end);}voidinsert_pcb1(pcb&a)// 首次適應(yīng)算法來(lái)實(shí)現(xiàn)作業(yè)調(diào)度{inti,j,k;for(i=0;i<N;i++)if(ROM[i]==0){for(j=i;j<=(i+a.size)&&j<N;j++)// 查詢第一個(gè)空閑區(qū)，并判斷是否適合插入作業(yè)if(ROM[j]==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++)ROM[k]=1;printf(" 插入成功，進(jìn)程%s的初始地址為%d,結(jié)束地址為%d\n",,a.start,a.start+a.size-1);return;}}if(i==N)// 未查詢到合適的區(qū)域printf(" 插入失敗，無(wú)可用空間 \n");}voidinsert_pcb2(pcb&a)// 循環(huán)首次適應(yīng)算法來(lái)實(shí)現(xiàn)作業(yè)調(diào)度{inti,j,k;for(i=p;i<N;i++)// 從所標(biāo)記的當(dāng)前區(qū)域開始查詢，查詢到末內(nèi)存{if(ROM[i]==0){for(j=i;j<=(i+a.size)&&j<N;j++)if(ROM[j]==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++)ROM[k]=1;printf(" 插入成功，進(jìn)程%s的初始地址為%d,結(jié)束地址為%d\n",,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)記的

Pif(ROM[i]==0){for(j=i;j<=(i+a.size)&&j<p;j++)if(ROM[j]==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&&j<p;k++)ROM[k]=1;printf(" 插入成功，進(jìn)程%s的初始地址為%d\n",,a.start);p=i+a.size;break;}}if(i==p)// 查詢兩部分都未找到合適的區(qū)域，輸出插入失敗語(yǔ)句printf(" 插入失敗，無(wú)可用空間 \n");}voidDelete(pcb&a)// 刪除作業(yè)，修改內(nèi)存信息和初始化該作業(yè)信息{inti;for(i=a.start;i<a.start+a.size;i++)ROM[i]=0;a.state=0;// 狀態(tài)標(biāo)記為未使用printf(" 刪除成功\n");}intmain(){init();intcount=0;intchoose1,choose;charname[10];pcba;printf("1 、首次適應(yīng)算法\n");printf("2 、循環(huán)首次適應(yīng)算法\n");scanf("%d",&choose1);do{printf("\n\n1 、插入進(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");scanf("%d",&a.size);if(choose1==1)insert_pcb1(a);else insert_pcb2(a);num[count++]=a;}else if(choose==2){printf(" 輸入刪除進(jìn)程的名字\n");scanf("%s",&name);for(inti=0;i<count;i++)if(!strcmp(num[i].name,name))Delete(num[i]);}else if(choose==3){printf(" 進(jìn)程名\t\t 開始地址\t\t 大小\t\t 結(jié)束地址\t\t\n");// 輸出內(nèi)存信息for(inti=0;i<count-1;i++)for(intj=i;j<count-1;j++)if(num[j].start>num[j+1].start){a=num[j];num[j]=num[j+1];num[j+1]=a;}for(inti=0;i<count;i++)if(num[i].state!=0)printf("%s\t\t%d\t\t\t%d\t\t%d\t\t\n",num[i].name,num[i].start,num[i].size,num[i].size+num[i].start-1);}elseif(choose==4){find_free_rom();show();}elsebreak;}while(1);return0;}首次適應(yīng)算法：本實(shí)驗(yàn)共采用1024個(gè)內(nèi)存進(jìn)行模擬，首先對(duì)內(nèi)存初始化，得到一個(gè)大的空閑區(qū)：相繼插入3個(gè)進(jìn)程：分別插入進(jìn)程ABC,大小分別為100,200,300此時(shí)查詢進(jìn)程信息和查詢空閑區(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í)無(wú)可用空間首次適應(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í)掃描到最后，沒(méi)找到，轉(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í)， 從上次找到的空閑區(qū)的下一個(gè)空閑區(qū)開始查找，找不到再?gòu)念^開始查找，實(shí)