實驗報告
【實驗名稱】
首次適應(yīng)算法和循環(huán)首次適應(yīng)算法
【實驗?zāi)康摹?/p>
理解在連續(xù)分區(qū)動態(tài)的存儲管理方式下，如何實現(xiàn)主存空間的分配與回收。
【實驗原理】
首次適應(yīng)（first
fit，F(xiàn)F）算法
FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)即可。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€能滿足要求的分區(qū)，則表明系統(tǒng)中已經(jīng)沒有足夠大的內(nèi)存分配給該進(jìn)程，內(nèi)存分配失敗，返回。
循環(huán)首次適應(yīng)（next
fit，NF）算法
為避免低址部分留下許多很小的空閑分區(qū)，以及減少查找可用空閑分區(qū)的開銷，循環(huán)首次適應(yīng)算法在為進(jìn)程分配內(nèi)存空間時，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至找到一個能滿足要求的空閑分區(qū)，從中劃出一塊玉請求大小相等的內(nèi)存空間分配給作業(yè)。
【實驗內(nèi)容】
實現(xiàn)主存空間的分配與回收：
1.采用可變式分區(qū)管理，使用首次適應(yīng)算法實現(xiàn)主存空間的分配與回收；
2.采用可變式分區(qū)管理，使用循環(huán)首次適應(yīng)算法實現(xiàn)主存空間的分配與回收。
數(shù)據(jù)結(jié)構(gòu)和符號說明：
typedef
struct
PCB//進(jìn)程控制塊
{
char
ProgressName[10];
//進(jìn)程名稱
int
Startaddress;
//進(jìn)程開始地址
int
ProgressSize;
//進(jìn)程大小
int
ProgressState
=
0;
//進(jìn)程狀態(tài)
};
typedef
struct
FREE
//空閑區(qū)結(jié)構(gòu)體
{
int
Free_num;
//空閑區(qū)名稱
int
Startaddress;
//空閑區(qū)開始地址
int
Endaddress;
//空閑區(qū)結(jié)束地址
int
Free_Space;
//空閑區(qū)大小
};
算法流程圖：
首次適應(yīng)算法
循環(huán)首次適應(yīng)算法
程序代碼及截圖：
#include
#include
#include
#include
#define
N
1024
typedef
struct
PCB//進(jìn)程控制塊
{
char
ProgressName[10];
//進(jìn)程名稱
int
Startaddress;
//進(jìn)程開始地址
int
ProgressSize;
//進(jìn)程大小
int
ProgressState
=
0;
//進(jìn)程狀態(tài)
};
typedef
struct
FREE
//空閑區(qū)結(jié)構(gòu)體
{
int
Free_num;
//空閑區(qū)名稱
int
Startaddress;
//空閑區(qū)開始地址
int
Endaddress;
//空閑區(qū)結(jié)束地址
int
Free_Space;
//空閑區(qū)大小
};
int
count
=
0;
//當(dāng)前內(nèi)存中進(jìn)程個數(shù)
bool
ROM[N];//設(shè)置內(nèi)存塊
int
p
=
0;//循環(huán)首次使用需要標(biāo)記當(dāng)前的空閑區(qū)塊
FREE
FREE[100];//設(shè)置空閑區(qū)數(shù)組為100個
int
FREE_counter
=
0;//空閑區(qū)的個數(shù)
PCB
num[20];
//作業(yè)隊列
void
init()//初始化操作
{
for(int
i=0;
i i++) ROM[i] = 0; } void showProgress(PCB &a) { printf(“----------------------------------------------------------------------＼n“); printf(“進(jìn)程名＼t＼t開始地址＼t＼t大?。躷＼t結(jié)束地址＼n“);//輸出內(nèi)存信息 printf(“----------------------------------------------------------------------＼n“); for(int i=0; i i++) for(int j=i; j j++) if(num[j].Startaddress>num[j+1].Startaddress) { a = num[j]; num[j] = num[j+1]; num[j+1] = a; } for(int i=0; i i++) if(num[i].ProgressState!=0) printf(“%s＼t＼t%d＼t＼t＼t%d＼t＼t%d＼t＼t＼n“,num[i].ProgressName,num[i].Startaddress,num[i].ProgressSize,num[i].ProgressSize+num[i].Startaddress-1); printf(“----------------------------------------------------------------------＼n“); } void showFree()//打印空閑區(qū)的情況 { printf(“----------------------------------------------------------------------＼n“); printf(“ 空閑區(qū)名＼t| 開始地址＼t| 大小 ＼t| 結(jié)束地址＼n“); printf(“----------------------------------------------------------------------＼n“); for (int i=1; i<= FREE_counter; i++) { printf(“＼t%1d＼t%8d＼t%11d＼t %d＼n“,FREE[i].Free_num,FREE[i].Startaddress,FREE[i].Free_Space,FREE[i].Endaddress); printf(“----------------------------------------------------------------------＼n“); } } void find_FREE() //尋找空閑區(qū) { int i,j,p; //計數(shù)值 FREE_counter = 0;//預(yù)設(shè)空閑區(qū)數(shù)為0 for(i = 0; i N; i++) if(ROM[i] == 0) { p = i; for(j = i; j N; j++) { if(ROM[j]==0)//未找到空閑區(qū)，則將j賦值給i后繼續(xù)循環(huán) { i = j; continue; } if(ROM[j]==1)//找到空閑區(qū) { FREE_counter++;//空閑區(qū)個數(shù)+1； FREE[FREE_counter].Free_num = FREE_counter;//設(shè)置空閑區(qū)編號 FREE[FREE_counter].Startaddress = p; FREE[FREE_counter].Endaddress = j-1; FREE[FREE_counter].Free_Space = j-p; i=j+1; break; } } if(j == N && ROM[j-1] == 0)//對最后一個內(nèi)存進(jìn)行特殊操作 { FREE_counter++; FREE[ FREE_counter].Free_num = FREE_counter;//對空閑區(qū)進(jìn)行處理 FREE[ FREE_counter].Startaddress = p; FREE[ FREE_counter].Endaddress =j-1; FREE[ FREE_counter].Free_Space = j-p; } } } void First_Fit(PCB &a)//首次適應(yīng)算法 { int i,j,k; for(i=0; i i++) if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++)//查詢第一個空閑區(qū)，并判斷是否適合插入作業(yè) if(ROM[j]==1) { i = j + 1; break; } if(j==i+a.ProgressSize+1) { a.Startaddress = i;//設(shè)置作業(yè)的開始地址 a.ProgressState = 1;//標(biāo)記作業(yè)在內(nèi)存中 for(k=i; k k++) ROM[k]=1; printf(“進(jìn)程%s插入成功，進(jìn)程%s的初始地址為%d,結(jié)束地址為%d＼n“,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); return; } } if(i==N)//未查詢到合適的區(qū)域 printf(“插入失敗，無可用空間！＼n“); } void Next_Fit(PCB &a)//循環(huán)首次適應(yīng)算法來實現(xiàn)作業(yè)調(diào)度 { int i,j,k; for(i=p; i i++)//從所標(biāo)記的當(dāng)前區(qū)域開始查詢，查詢到末內(nèi)存 { if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++) if(ROM[j]==1) { i = j+1; break; } if(j==i+a.ProgressSize+1)//找到合適的空閑區(qū) { a.Startaddress=i; a.ProgressState=1; for(k=i; k k++) ROM[k]=1; printf(“插入成功，進(jìn)程%s的初始地址為%d,結(jié)束地址為%d＼n“,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); p=i+a.ProgressSize; return; } } } for(i=0; i i++)//當(dāng)未找到時，從第一個空閑區(qū)開始查詢，結(jié)束條件為小于所標(biāo)記的P if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++) if(ROM[j]==1) { i=j+1; break; } if(j==i+a.ProgressSize+1)//成功找到結(jié)束，并標(biāo)記當(dāng)前P為現(xiàn)在的作業(yè)的尾部 { a.Startaddress=i; a.ProgressState=1; for(k=i; k ROM[k]=1; printf(“插入成功，進(jìn)程%s的初始地址為%d＼n“,a.ProgressName,a.Startaddress); p=i+a.ProgressSize; break; } } if(i==p)//查詢兩部分都未找到合適的區(qū)域，輸出插入失敗語句 printf(“插入失敗，無可用空間＼n“); } void Delete(PCB &a)//刪除作業(yè)，修改內(nèi)存信息和初始化該作業(yè)信息 { int i; for(i=a.Startaddress; i i++) ROM[i]=0; a.ProgressState=0;//狀態(tài)標(biāo)記為未使用 printf(“進(jìn)程%s刪除成功＼n“,a.ProgressName); } int main() { int choose1,choose; char ProgressName[10]; PCB a; init(); printf(“＼t主存空間的分配與回收＼n“); printf(“---------------------------------------＼n“); printf(“＼t1、首次適應(yīng)算法＼n“); printf(“＼t2、循環(huán)首次適應(yīng)算法＼n“); printf(“---------------------------------------＼n“); printf(“請選擇分配算法：“); scanf(“%d“,&choose1); system(“cls“); while(1) { w:system(“cls“); printf(“當(dāng)前分配算法：“); if(choose1 == 1) printf(“首次適應(yīng)算法＼n“); else printf(“循環(huán)首次適應(yīng)算法＼n“); printf(“---------------------------------------＼n“); printf(“＼t1、插入進(jìn)程＼n“); printf(“＼t2、刪除進(jìn)程＼n“); printf(“＼t3、顯示進(jìn)程的信息＼n“); printf(“＼t4、顯示空閑區(qū)＼n“); printf(“---------------------------------------＼n“); printf(“請輸入：“); scanf(“%d“,&choose); system(“cls“); switch(choose) { case 1: printf(“請輸入進(jìn)程名:“); scanf(“%s“,&a.ProgressName); printf(“請輸入進(jìn)程的大小：“); scanf(“%d“,&a.ProgressSize); for(int i = 0; i count; i++) if(strcmp(num[i].ProgressName,a.ProgressName)==0) { printf(“已存在同名進(jìn)程，無法插入。＼n“); system(“pause“); goto w; } if(choose1==1)//首次適應(yīng)算法 First_Fit(a); else Next_Fit(a);//循環(huán)首次適應(yīng)算法 num[count++]=a; break; case 2: if(count == 0) { printf(“當(dāng)前沒有進(jìn)程在內(nèi)存中，無法刪除?。躰“); system(“pause“); goto w; } printf(“輸入刪除的進(jìn)程名字：“); scanf(“%s“,&ProgressName); for(int i=0; i i++) if(!strcmp(num[i].ProgressName,ProgressName)) Delete(num[i]); else printf(“沒有找到對應(yīng)進(jìn)程，請重新輸入。＼n“); break; case 3: showProgress(a); break; case 4: find_FREE(); showFree(); break; default: printf(“＼n無效的輸入。＼n“); } system(“pause“); } return 0; } 主界面： 首次適應(yīng)算法，初始空閑區(qū)： 插入進(jìn)程： 插入3個進(jìn)程： 空閑區(qū)信息： 刪除進(jìn)程2： 刪除后空閑區(qū)狀況： 再插入一個進(jìn)程，可以看到其其初始地址為100： 循環(huán)首次適應(yīng)算法,插入3個進(jìn)程 刪除進(jìn)程2后： 再插入進(jìn)程A，發(fā)現(xiàn)其從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，其初始地址為750而不是200：
點擊咨詢