第一篇：實驗三 存儲器的分配與回收算法實現(xiàn)(二維數(shù)組)
實驗三 存儲器的分配與回收算法
◆實驗名稱：存儲器的分配與回收算法實驗 ◆儀器、設(shè)備：計算機(jī)
◆參考資料：操作系統(tǒng)實驗指導(dǎo)書 ◆實驗?zāi)康模?/p>
設(shè)計一個存儲器的分配與回收算法管理方案，并編寫模擬程序?qū)崿F(xiàn)?！魧嶒瀮?nèi)容：
1.模擬操作系統(tǒng)的主存分配，運用可變分區(qū)的存儲管理算法設(shè)計主存分配和回收程序，并不實際啟動裝入作業(yè)。
2.采用最先適應(yīng)法、最佳適應(yīng)法、最壞適應(yīng)法分配主存空間。
3.當(dāng)一個新作業(yè)要求裝入主存時，必須查空閑區(qū)表，從中找出一個足夠大的空閑區(qū)。若找到的空閑區(qū)大于作業(yè)需要量，這是應(yīng)把它分成二部分，一部分為占用區(qū)，加一部分又成為一個空閑區(qū)。
4.當(dāng)一個作業(yè)撤離時，歸還的區(qū)域如果與其他空閑區(qū)相鄰，則應(yīng)合并成一個較大的空閑區(qū)，登在空閑區(qū)表中。
5.運行所設(shè)計的程序，輸出有關(guān)數(shù)據(jù)結(jié)構(gòu)表項的變化和內(nèi)存的當(dāng)前狀態(tài)?！魧嶒炓螅?/p>
1． 詳細(xì)描述實驗設(shè)計思想、程序結(jié)構(gòu)及各模塊設(shè)計思路； 2． 詳細(xì)描述程序所用數(shù)據(jù)結(jié)構(gòu)及算法； 3． 明確給出測試用例和實驗結(jié)果；
4． 為增加程序可讀性，在程序中進(jìn)行適當(dāng)注釋說明；
5． 認(rèn)真進(jìn)行實驗總結(jié)，包括：設(shè)計中遇到的問題、解決方法與收獲等； 6． 實驗報告撰寫要求結(jié)構(gòu)清晰、描述準(zhǔn)確邏輯性強(qiáng)；
實驗過程中，同學(xué)之間可以進(jìn)行討論互相提高，但絕對禁止抄襲。◆實驗過程記錄（源程序、測試用例、測試結(jié)果及心得體會等
實驗代碼如下：
#include
int work[10][2];
//作業(yè)名字 大小
int idle[10][2];
//空閑區(qū)大小 地址
int free[10][3];
//已分配區(qū)域的名字 地址 大小
int num=0,b=1,d,ch1,ch2;void init(){
idle[0][0]=1;idle[0][1]=100;
free[0][0]=0;free[1][1]=0;free[1][2]=0;
work[0][0]=0;work[0][1]=0;
for(int i=1;i <=9;i++){ //初始化數(shù)組
idle[i][0]=0;idle[i][1]=0;
free[i][0]=0;free[i][1]=0;free[i][2]=0;
work[i][0]=0;work[i][1]=0;
} }
void jishu(){ //求空閑單元數(shù)
for(int i=0;i <9;i++)
if(idle[i][1]!=0)
num++;}
void jishu1(){ //求作業(yè)數(shù)
for(int i=0;i <9;i++)
if(work[i][1]!=0)
b++;
}
void zuixian(){ //最先適應(yīng)法
jishu();
for(int i=0;i for(int j=i;j if(idle[j][0]>idle[j+1][0]){ int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } } void zuijia(){ //最佳適應(yīng)法 num=0; jishu(); for(int i=0;i for(int j=i;j if(idle[j][1]>idle[j+1][1]){ int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } } void zuihuai(){ //最壞適應(yīng)法 num=0; jishu(); for(int i=0;i for(int j=i;j if(idle[j][1] int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } } void huishou(int name){ //回收進(jìn)程函數(shù) num=0; b=0; jishu(); jishu1(); int c=-1; for(int k=0;k <=b;k++){ if(free[k][0]==name){ c=k; break; } } if(c==-1)cout <<“要回收的作業(yè)不存在！” < else{ for(int i=0;i //將空閑單元排序{不包括新回收的} for(int j=i;j if(idle[j][0]>idle[j+1][0]){ int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } for(int q=0;q if(free[c][1] <=idle[q][0]){ for(int j=num;j>=q;j--){ idle[j+1][0]=idle[j][0]; idle[j+1][1]=idle[j][1]; } idle[j][0]=free[c][1]; idle[j][1]=free[c][2]; b++; if(idle[j+1][0]==idle[j][0]+idle[j][1]){ idle[j][1]=idle[j][1]+idle[j+1][1]; for(int m=j+1;m <=num;m++){ idle[m][0]=idle[m+1][0]; idle[m][1]=idle[m+1][1]; } idle[m][0]=0; idle[m][1]=0; b--; } if(idle[j-1][0]==idle[j][0]){ idle[j-1][1]=idle[j-1][1]+idle[j][1]; for(int n=j;j <=num;j++){ idle[n][0]=idle[n+1][0]; idle[n][1]=idle[n+1][1]; } idle[n][0]=0; idle[n][1]=0; b--; } break; } } if(ch2==1)zuixian(); if(ch2==2)zuijia(); if(ch2==3)zuihuai(); for(int p=c;c free[c][0]=free[c+1][0]; free[c][1]=free[c+1][1]; free[c][2]=free[c+1][2]; work[c][0]=work[c+1][0]; work[c][1]=work[c+1][1]; } cout<<“該進(jìn)程已被成功回收！”< } } void fp(){ int tag=0;//判斷空閑區(qū)與請求區(qū)大小 num=0; b=0; jishu(); jishu1(); for(int j=0;j if(work[b][1] free[b][0]=work[b][0]; free[b][1]=idle[j][0]; free[b][2]=work[b][1]; idle[j][0]=idle[j][0]+work[b][1]; idle[j][1]=idle[j][1]-work[b][1]; tag=1; break; } else if(work[b][1]==idle[j][1]){ free[b][0]=work[b][0]; free[b][1]=idle[j][0]; free[b][2]=work[b][1]; tag=1; for(int i=j;i <=num-1;i++){ idle[i][0]=idle[i+1][0]; idle[i][1]=idle[i+1][1];} break;} else tag=0;} if(tag==0)cout <<“作業(yè)過大沒有足夠存儲空間！” < void print(){ num=0; b=1; jishu(); jishu1(); cout <<“已分配表為:” < for(int i=0;i <=b;i++) if(free[i][2]!=0) cout <<“作業(yè)名:” < cout < cout <<“空閑區(qū)表為:” < for(int j=0;j if(idle[j][1]!=0) cout <<“起始地址:” < cout < void main(){ //主函數(shù)運行上面定義的函數(shù) init(); int n; cout <<“1.分配空間；2.回收空間；” < cin>>ch1; cout < cout <<“1.最先適應(yīng)法；2.最佳適應(yīng)法；3.最壞適應(yīng)法；” < cin>>ch2; cout < cout <<“請輸入要分配內(nèi)存的作業(yè)名及占用內(nèi)存大小:”; cin>>work[b][0]>>work[b][1]; cout < if(ch2==1){ zuixian(); fp(); } else if(ch2==2){ zuijia(); fp();} else if(ch2==3){ zuihuai(); fp();} print();} cout <<“輸入要回收的作業(yè)名：” < cin>>n; huishou(n); } 實驗截圖： 成功回收時： 回收失敗時： 實驗體會： 本次實驗的難度較大，尤其是回收進(jìn)程，主要編寫幾個算法和回收程序，最佳，最優(yōu)，最壞算法和回收算法，我用的是數(shù)組，有工作數(shù)組，空閑數(shù)組，已分配數(shù)組。最后再編寫算法，但是回收算法現(xiàn)在還是有些不清晰，需要進(jìn)一步研究！ 實驗報告 【實驗名稱】 首次適應(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(“插入失敗，無可用空間?。躰“); } 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：第二篇：操作系統(tǒng)實驗四主存空間的分配與回收首次適應(yīng)算法和循環(huán)首次適應(yīng)算法
點擊咨詢 