第一篇：操作系統(tǒng)課程設(shè)計(jì)_動態(tài)分區(qū)分配存儲管理

操作系統(tǒng)課程設(shè)計(jì)

設(shè)計(jì)題目 動態(tài)分區(qū)分配存儲管理

學(xué)生姓名學(xué)

號 專業(yè)班級 指導(dǎo)教師

呂 霆

20102675 計(jì)算機(jī)10-01班

第一章

課程設(shè)計(jì)概述

1.1 設(shè)計(jì)任務(wù): 動態(tài)分區(qū)分配存儲管理

1.2 設(shè)計(jì)要求

建立描述內(nèi)存分配狀況的數(shù)據(jù)結(jié)構(gòu)； ?建立描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)； ?使用兩種方式產(chǎn)生進(jìn)程：（a）自動產(chǎn)生，（b）手工輸入； ? 在屏幕上顯示內(nèi)存的分配狀況、每個進(jìn)程的執(zhí)行情況； ? 建立分區(qū)的分配與回收算法，支持緊湊算法； ? 時間的流逝可用下面幾種方法模擬：（a）按鍵盤，每按一次可認(rèn)為過一個時間單位；(b)響應(yīng)WM_TIMER；

? 將一批進(jìn)程的執(zhí)行情況存入磁盤文件，以后可以讀出并重放；

? 支持算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法：最壞適應(yīng)算法。

1.3 設(shè)計(jì)目的

旨在讓我們更好的了解動態(tài)分區(qū)管理方面的知識.第二章 原理及算法描述

2.1動態(tài)分區(qū)分配算法原理

首次適應(yīng)算法

* 算法概述：分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，找到滿足的空閑分區(qū)則劃出空間分配，余下的空閑空間仍保留在空閑鏈表中

* 實(shí)現(xiàn)方法：分配時從數(shù)組第一個元素開始比較，若符合條件則將該元素減去對應(yīng)作業(yè)的值

循環(huán)首次適應(yīng)算法

* 算法概述：由首次適應(yīng)算法演變，只是每次分配改為由上一次找到的空閑分區(qū)開始查找

* 實(shí)現(xiàn)方法：在首次適應(yīng)算法的基礎(chǔ)上增加一個值用于記錄找到的空閑分區(qū)的位置

最佳適應(yīng)算法

* 算法概述：每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)

分配給作業(yè)

* 實(shí)現(xiàn)方法：我們決定每次分配先把空閑分區(qū)按從小到大的順序排列，然后將第一個匹配分區(qū)分配給作業(yè)

最壞適應(yīng)算法

* 算法概述：每次為作業(yè)分配內(nèi)存時，總是挑選一個最大的空閑分區(qū)分割給作業(yè)使用

* 實(shí)現(xiàn)方法：算法與最佳適應(yīng)算法幾乎相同，僅在排序時把空閑分區(qū)表按從大到小的順序排列，所以未作詳細(xì)注釋

回收分區(qū)

當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時,系統(tǒng)根據(jù)回收區(qū)的首址,從空閑區(qū)鏈(表)中找到相應(yīng)的插入點(diǎn),此時可能出現(xiàn)以下四種情況之一;1)回收區(qū)與插入點(diǎn)的前一個空閑分區(qū)F1相鄰接,此時應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并,不必為回收區(qū)分配新表項(xiàng),而只需修改其前一分區(qū)F1的大小.2)回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接,此時也可將兩分區(qū)合并,形成新的空閑分區(qū),但用回收區(qū)的首址作為新空閑區(qū)的首址,大小為兩者之和.3)回收區(qū)同時與插入點(diǎn)的前,后兩個分區(qū)鄰接,此時將三個分區(qū)合并,使用F1的表項(xiàng)和F1的首址,取消F2的表項(xiàng),大小為三者之和.4)回收區(qū)既不與F1相鄰接,又不與F2鄰接.這時應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng),填寫回收區(qū)的首址和大小,并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置.緊湊算法

通過移動內(nèi)存中的作業(yè)的位置,以把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法.第三章 開發(fā)環(huán)境

此程序是本人利用c++語言在vs2012的開發(fā)環(huán)境中實(shí)現(xiàn)的第四章 程序?qū)崿F(xiàn)--數(shù)據(jù)結(jié)構(gòu)

#include #include #include using namespace std;ofstream stream;//輸出流對象 int ary1[20][4];//內(nèi)存分配狀態(tài) int ary2[20][3];//空閑分區(qū)狀態(tài) int ary3[10];//進(jìn)程分配狀態(tài)

int recycle;//需要回收的盤塊序號 int id1;//算法選擇號 int m;//內(nèi)存區(qū)數(shù) int n;//空閑區(qū)數(shù) int q;//進(jìn)程數(shù)

int r=0;//循環(huán)首次適應(yīng)算法：對應(yīng)的這次查找到的空閑分區(qū)序號 //打印輸出函數(shù) void vision(){

int i;int j;if(id1==1)stream.open(“first_fit.txt”, ios::app);if(id1==2)stream.open(“nextfirst_fit.txt”, ios::app);if(id1==3)stream.open(“best_fit.txt”,ios::app);if(id1==4)stream.open(“worst_fit.txt”, ios::app);if(id1==5)stream.open(“compact.txt”,ios::app);if(id1==6)stream.open(“huishou.txt”,ios::app);cout<<“-------------內(nèi)存分配狀態(tài)-------------”<

} cout <

} cout <

}

//作業(yè)信息的自動產(chǎn)生 void create_pro(){

}

//作業(yè)的手動生成 void create_zuoye(){ int j;int choice2;int id3=rand()%10;m=id3;//內(nèi)存區(qū)數(shù)量 cout<<“產(chǎn)生”<

} ary3[0]=42;ary3[1]=86;ary3[i]=rand()%100;if(ary3[i]==0){i--;} {

} cout<<“--------------------------”<

}

//內(nèi)存信息的自動產(chǎn)生 void create_apply(){

int k=0;//空閑區(qū)數(shù)量 for(i=0;i

if(ary1[i][3]!=2){ary2[k][0]=ary1[i][0];ary2[k][1]=ary1[i][1];ary2[k][2]=ary1[i][2];k++;} int i;for(i=0;i

} ary1[i][0]=i+1;ary1[i][1]=rand()%100;if(i==0){ } ary1[i][3]=rand()%3;//cout <>choice2;q=choice2;cout<<“輸入想創(chuàng)建的作業(yè)請求大小”<

} cout<<“你創(chuàng)建了”<>j;ary3[i]=j;

}

//內(nèi)存信息的手動生成 int create_fenqu(){

}

//首次適應(yīng)算法 void first_fit()int k,x,y,o=0;int a=0;cout<<“輸入想創(chuàng)建的內(nèi)存分區(qū)塊數(shù) : ”;cin>>k;

cout<<“輸入”<

} cout<<“輸入內(nèi)存塊的分配狀態(tài)”<

} ary1[0][2]=0;ary1[1][2]=ary1[0][1];for(int i=2;i

for(int i=0;i

} n=a;return m,n;if(ary1[i][3]!=2){

} ary2[a][0]=ary1[i][0];ary2[a][1]=ary1[i][1];ary2[a][2]=ary1[i][2];a++;ary1[i][2]=ary1[i-1][2]+ary1[i-1][1];//起始地址 cin>>y;if(y==2){ } ary1[i][3]=y;//狀態(tài) n++;ary1[i][0]=i;//序號 cin>>x;ary1[i][1]=x;//大小 } n=k;//空閑塊數(shù)量

{

vision();int i;int j;int k;int l;int d;//用來保存第k個的值 int id2=0;for(i=0;i

for(j=0;j

if(ary2[j][1]>=ary3[i])//進(jìn)程占用空間小于等于其中一個空閑區(qū)的大小 {

cout<<“[”<

ary1[ary2[j][0]-1][3]=2;for(k=j+1;k

ary2[k-1][0]=ary2[k][0];ary2[k-1][1]=ary2[k][1];ary2[k-1][2]=ary2[k][2];} n--;

}else//否則的話，空閑鏈對應(yīng)的地方盤塊大小小了進(jìn)程占用的大小，并且內(nèi)存分配從對應(yīng)的 {

l=ary2[j][0];d=ary1[l-1][1];//大小 ary1[l-1][1]=ary3[i];ary1[l-1][3]=2;m++;for(k=m;k>ary2[j][0]+1;k--){

ary1[k-1][0]=ary1[k-2][0]+1;ary1[k-1][1]=ary1[k-2][1];ary1[k-1][2]=ary1[k-2][2];ary1[k-1][3]=ary1[k-2][3];那一項(xiàng)開始增加一項(xiàng)

} l=ary2[j][0];

}

}

{ if(ary1[id2][3]!=2)

}

} n=k;} break;} else {

}

cout<<“[”<

{

ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} ary1[l][0]=l+1;ary1[l][1]=d-ary3[i];ary1[l][2]=ary1[l-1][1]+ary1[l-1][2];ary1[l][3]=0;k=0;for(id2=0;id2

//首次循環(huán)適應(yīng)算法 void next_fit(){ vision();int i;int j;int k;int s;int d;int id2;for(i=0;i

{

for(j=r;j

if(ary3[i]<=ary2[j][1]){

cout<<“[”<

{

} else//對應(yīng)的空閑塊大小大于進(jìn)程需要大小 { //-----改變內(nèi)存分配情況-----r=(r+1)%n;//改變第k塊的內(nèi)容 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;//從k+1之后所有向后移一格 m++;//內(nèi)存塊數(shù)增加1 for(s=m-1;s>k;s--){

ary1[s][0]=ary1[s-1][0]+1;ary1[s][1]=ary1[s-1][1];ary1[s][2]=ary1[s-1][2];//---改變內(nèi)存分配---k=ary2[j][0];//得到對應(yīng)空閑塊對應(yīng)內(nèi)存塊的序號 k--;ary1[k][3]=2;//把對應(yīng)內(nèi)存塊標(biāo)志位上改成已分配 //------------------//--改變空閑塊表：把從這塊空閑塊以下的所有空閑塊向上移一格--n--;for(k=j;k

} vision();//------------------break;ary2[k][0]=ary2[k+1][0];ary2[k][1]=ary2[k+1][1];ary2[k][2]=ary2[k+1][2];stream<<“[”<

}

}

//思路：先把空閑列表檢索一遍，選出最佳答案，進(jìn)行分配

void best_fit()//最佳算法--按順序檢索，把與進(jìn)程要求內(nèi)存大小最接近的快分配給進(jìn)程 {

int i;int s;int j=-9999;//用來保存最接近的答案 int e;//用來存放進(jìn)行比較時的中間結(jié)果

}

{ if(ary1[id2][3]!=2)

}

} else{

} cout<<“[”<

{

ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} ary1[s][3]=ary1[s-1][3];} //改變第k+1塊內(nèi)容：對應(yīng)的數(shù)組是ary1[k] ary1[k][0]=ary1[k-1][0]+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];//--------------------------//----改變空閑表分配情況----k=0;for(id2=0;id2

}else { cout<<“[”<

for(s=0;s

} if(j<0){ cout<<“[”<=ary3[i])&&(e>ary2[s][1]))//滿足分配要求 { e=ary2[s][1];} j=s;for(i=0;i

if(ary2[j][1]==ary3[i]){

} else

for(l=k;l

} n--;ary2[l-1][0]=ary2[l][0];ary2[l-1][1]=ary2[l][1];ary2[l-1][2]=ary2[l][2];ary1[k-1][3]=2;k=ary2[j][0];

}

//最壞適應(yīng)算法 void worst_fit()

}

{ if(ary1[id2][3]!=2)

}

} vision();n=k;

} for(k=j+1;k

{

ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} {

//把對應(yīng)的內(nèi)存分配進(jìn)行更改 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;m++;for(l=m;l>ary2[j][0]+1;l--){

} k=ary2[j][0];ary1[k][0]=k+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];ary1[k][3]=0;k=0;ary1[l-1][0]=ary1[l-2][0]+1;ary1[l-1][1]=ary1[l-2][1];ary1[l-1][2]=ary1[l-2][2];ary1[l-1][3]=ary1[l-2][3];for(id2=0;id2

{

}else { cout<<“[”<

int e=-9999;//用來存放進(jìn)行比較時的中間結(jié)果 int k;int l;int d;int id2;vision();{

j=-9999;e=-9999;for(s=0;s

} if(j<0){ cout<<“[”<=ary3[i])&&(e

if(ary2[j][1]==ary3[i]){

k=ary2[j][0];

ary1[k-1][3]=2;

for(l=k;l

{ if(ary1[id2][3]!=2)

}

} vision();n=k;

} for(k=j+1;k

{

ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;}

} else {

//把對應(yīng)的內(nèi)存分配進(jìn)行更改 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;m++;for(l=m;l>ary2[j][0]+1;l--){

}

k=ary2[j][0];ary1[k][0]=k+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];ary1[k][3]=0;k=0;ary1[l-1][0]=ary1[l-2][0]+1;ary1[l-1][1]=ary1[l-2][1];ary1[l-1][2]=ary1[l-2][2];ary1[l-1][3]=ary1[l-2][3];} n--;ary2[l-1][2]=ary2[l][2];for(id2=0;id2

}

//回收內(nèi)存算法： /* 有共計(jì)八種情況，1.（1）回收區(qū)上鄰接著空閑盤塊，下連接著已分配盤塊（2）回收區(qū)下鄰接著空閑盤塊，上鄰接著已分配盤塊(3)回收區(qū)上下連接的都是空閑盤塊（4)空閑區(qū)上下鄰接的都是已分配盤塊

（5）要回收的盤塊就是第一個盤塊，并且向下鄰接著空閑盤塊(6)要回收的盤塊就是第一個盤塊，但是向下鄰接著已分配盤塊(7)要回收的盤塊就是最后一個盤塊，并且向上鄰接的是空閑盤塊(8)要回收的盤塊就是最后一個盤塊，但是向上鄰接的是已分配盤塊 */ void apply_recycle(){

ary1[0][1]=ary1[0][1]+ary1[1][1];ary1[0][3]=0;for(i=1;i

if(recycle==1){ //cout<

if(ary1[1][3]!=2){ cout<<“要回收的盤塊就是第一個盤塊，并且向下鄰接著空閑盤塊”<

} else { ary1[0][3]=0;n++;ary2[0][0]=1;ary2[0][1]=ary1[0][1];ary2[0][2]=ary1[0][2];vision();} stream<<“要回收的盤塊就是第一個盤塊，并且向下鄰接著空閑盤塊”<

ary2[k][0]=ary1[j][0];

ary1[0][3]=0;k=0;for(j=0;j

//cout<<“ary1[j][3]”<

} else{ cout<<“要回收的盤塊就是第一個盤塊，但是向下鄰接著已分配盤塊”<

} n=k;vision();

}

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;

{

} m--;// cout<<“" k=0;vision();//cout<<”ary1[0][3]“<

cout<<”ary1[j][3]“<

} else{ cout<<”要回收的盤塊就是最后一個盤塊，但是向上鄰接的是已分配盤塊“<

} n=k;vision();

}

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;

ary1[recycle-2][3]=0;ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];m--;k=0;for(j=0;j

//cout<<”ary1[j][3]“<

} else if(recycle==m){

if(ary1[recycle-2][3]!=2){ cout<<”要回收的盤塊就是最后一個盤塊，并且向上鄰接的是空閑盤塊“<

} n=k;vision();

}

ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;stream<<”要回收的盤塊就是最后一個盤塊，并且向上鄰接的是空閑盤塊“<

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;

} else{//剩下比較復(fù)雜的四種情況

if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]==2))//回收區(qū)上鄰接著空閑盤塊，下連接著{cout<<”回收區(qū)上鄰接著空閑盤塊，下連接著已分配盤塊“<

}

} n=k;vision();

}

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;

ary1[recycle-1][3]=0;k=0;for(j=0;j

//cout<<”ary1[j][3]“<

stream<<”回收區(qū)上鄰接著空閑盤塊，下連接著已分配盤塊“<

ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];for(i=recycle-1;i

} m--;k=0;for(j=0;j

//cout<<”ary1[j][3]“<

} if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]!=2))//回收區(qū)上下連接的都是空閑盤塊 { cout<<”回收區(qū)上下連接的都是空閑盤塊“<

} vision();

}

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;

} n=k;vision();} if((ary1[recycle][3]!=2)&&(ary1[recycle-2][3]==2))//回收區(qū)下鄰接著空閑盤塊，上鄰接著{ cout<<”回收區(qū)下鄰接著空閑盤塊，上鄰接著已分配盤塊“<

stream<<”回收區(qū)下鄰接著空閑盤塊，上鄰接著已分配盤塊“<

ary1[recycle-2][3]=0;ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];for(i=recycle-1;i

} m--;k=0;for(j=0;j

//cout<<”ary1[j][3]“<

}

}

} if((ary1[recycle-2][3]==2)&&(ary1[recycle][3]==2))//空閑區(qū)上下鄰接的都是已分配盤塊 {

} ary1[recycle-1][3]=0;k=0;for(j=0;j

} vision();//cout<<”ary1[j][3]“<

}

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;cout<<”回收區(qū)上下連接的都是空閑盤塊“<

} m=m-2;k=0;for(j=0;j

} vision();//cout<<”ary1[j][3]“<

}

ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;ary1[recycle-1][0]=ary1[recycle+1][0]-2;ary1[recycle-1][1]=ary1[recycle+1][1];ary1[recycle-1][2]=ary1[recycle+1][2];ary1[recycle-1][3]=ary1[recycle+1][3];n=k;n=k;

}

//緊湊算法 void compact(){

num_avl=0;for(id2=0;id2

int num_avl;//記錄空閑盤塊數(shù)量 int sum_avl=0;//總共空閑區(qū)大小 int num_apl=0;//統(tǒng)計(jì)總共空閑區(qū)有多大 vision();for(id2=0;id2

} //最后一塊空閑塊

ary1[num_apl][0]=num_apl+1;ary1[num_apl][1]=sum_avl;ary1[num_apl][2]=ary1[num_apl-1][1]+ary1[num_apl-1][2];ary1[num_apl][3]=0;m=num_apl+1;//包括最后一個空閑區(qū) if(ary1[id2][3]==2){

} ary1[num_apl][0]=num_apl+1;ary1[num_apl][1]=ary1[id2][1];if(num_apl==0){

} ary1[num_apl][3]=2;num_apl++;//cout<<”num_apl“<

}

//主函數(shù)入口

void main(){

if(choice1==1){

}

num=rand()&10;q=num;int id3=2+rand()%8;m=id3;//內(nèi)存區(qū)數(shù)量 create_apply();create_pro();int i;int j;int num;int choice1;//操作選擇標(biāo)記 int choice2;int flag=1;//標(biāo)記是否再執(zhí)行 while(flag==1){

cout<<”********************************************“<>choice1;

} n=num_avl;vision();

} ary2[num_avl][0]=ary1[id2][0];ary2[num_avl][1]=ary1[id2][1];ary2[num_avl][2]=ary1[id2][2];num_avl++;if(choice1==2){

} vision();

cout<<”**------------------請選擇處理算法----------------------**“<

} }

cout<<”**************************** “<>o;flag=o;

cout<<”**1首次適應(yīng)算法-----2循環(huán)首次適應(yīng)算法-----3最佳適應(yīng)算法 **“<>id1;if(id1==1)if(id1==2)if(id1==3)if(id1==4)if(id1==5)

} {first_fit();} {next_fit();} {best_fit();} {worst_fit();} { compact();} if(id1==6){ cout<<”*******************生成內(nèi)存狀態(tài)******************“<>recycle;if((recycle>m)||(recycle<1)){

} cout<<”錯誤:內(nèi)存中不存在此塊！“<

} if(id2==-9999){ apply_recycle();} if(ary2[i][0]==recycle){

}

cout<<”錯誤：輸入的為空閑盤塊！"<

第二篇：操作系統(tǒng)試驗(yàn)動態(tài)分區(qū)分配

實(shí)

驗(yàn)

報(bào)

告

課程名稱________操作系統(tǒng)試驗(yàn)____________

實(shí)驗(yàn)名稱________

動態(tài)分區(qū)分配___________

實(shí)驗(yàn)類型_________驗(yàn)證型_________________

實(shí)驗(yàn)地點(diǎn)___機(jī)房___實(shí)驗(yàn)日期__2011_

指導(dǎo)教師__________________________

專

業(yè)_計(jì)算機(jī)科學(xué)與技術(shù)_

班

級__________

學(xué)

號______________

姓

名____________

成績________________

XX大學(xué)計(jì)算機(jī)與通信工程學(xué)院

實(shí)驗(yàn)3

動態(tài)分區(qū)分配

一．實(shí)驗(yàn)?zāi)康挠酶呒壵Z言編寫和調(diào)試一個內(nèi)存分配模擬程序，以加深對動態(tài)分區(qū)的概念及內(nèi)存分配原理的理解。

二．實(shí)驗(yàn)原理

可變分區(qū)調(diào)度算法有:最先適應(yīng)分配算法,最優(yōu)適應(yīng)分配算法,最壞適應(yīng)算法。

用戶提出內(nèi)存空間的申請；系統(tǒng)根據(jù)申請者的要求，按照一定的分配策略分析內(nèi)存空間的使用情況，找出能滿足請求的空閑區(qū)，分給申請者；當(dāng)程序執(zhí)行完畢或主動歸還內(nèi)存資源時，系統(tǒng)要收回它所占用的內(nèi)存空間或它歸還的部分內(nèi)存空間。

每當(dāng)一個進(jìn)程被創(chuàng)建時，內(nèi)存分配程序首先要查找空閑內(nèi)存分區(qū)表（鏈），從中尋找一個合適的空閑塊進(jìn)行劃分，并修改空閑內(nèi)存分區(qū)表（鏈）。當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)表（鏈）中找到相應(yīng)的插入點(diǎn)，此時出現(xiàn)如下四種情況：

1)

回收區(qū)與插入點(diǎn)的前一個空閑分區(qū)F1相鄰接，此時可將回收區(qū)直接與F1合并，并修改F1的大??；

2)

回收區(qū)與插入點(diǎn)的后一個空閑分區(qū)F2相鄰接，此時可將回收區(qū)直接與F2合并，并用回收區(qū)的首址最為新空閑區(qū)的首址，大小為二者之和；

3)

回收區(qū)同時與插入點(diǎn)的前、后兩個空閑分區(qū)鄰接，此時需將三者合并；

4)

回收區(qū)不與任何一個空閑區(qū)鄰接，此時應(yīng)建一新的表項(xiàng)。

三．實(shí)驗(yàn)內(nèi)容

編寫并調(diào)試一個模擬的內(nèi)存分配程序。具體做法為：使用一個循環(huán)，根據(jù)提示，由用戶選擇隨時創(chuàng)建一個新的進(jìn)程，并為其分配存儲空間，也隨時可以撤銷一個進(jìn)程，可以根據(jù)需要隨時打印空閑分區(qū)表（鏈）以及打印系統(tǒng)中內(nèi)存使用情況。

四．實(shí)驗(yàn)環(huán)境

軟件環(huán)境:Visual

C++6.0

五．實(shí)驗(yàn)方案

六．實(shí)驗(yàn)步驟

1、流程圖

2、程序源代碼

八．實(shí)驗(yàn)中遇到的問題及解決方法

九．實(shí)驗(yàn)總結(jié)（見封皮）

【實(shí)驗(yàn)總結(jié)】

【指導(dǎo)教師評語及成績】

成績：

指導(dǎo)教師（簽字）：

****年**月**日

第三篇：計(jì)算機(jī)操作系統(tǒng)動態(tài)分區(qū)存儲管理方式下的內(nèi)存空間的分配與回收實(shí)驗(yàn)報(bào)告

計(jì)算機(jī)操作系統(tǒng)

實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)二

實(shí)驗(yàn)題目：存儲器管理

系別：計(jì)算機(jī)科學(xué)與技術(shù)系

班級：

姓名：

學(xué)號：2

一、實(shí)驗(yàn)?zāi)康?/p>

深入理解動態(tài)分區(qū)存儲管理方式下的內(nèi)存空間的分配與回收。

二、實(shí)驗(yàn)內(nèi)容

編寫程序完成動態(tài)分區(qū)存儲管理方式下的內(nèi)存分配和回收的實(shí)現(xiàn)。具體內(nèi)容包括：

確定用來管理內(nèi)存當(dāng)前使用情況的數(shù)據(jù)結(jié)構(gòu)； 采用首次適應(yīng)算法完成內(nèi)存空間的分配； 分情況對作業(yè)進(jìn)行回收；

編寫主函數(shù)對所做工作進(jìn)行測試。

三、實(shí)驗(yàn)原理

分配：動態(tài)分區(qū)存儲管理方式把內(nèi)存除OS占用區(qū)域外的空間看作一個大的空閑區(qū)。當(dāng)作業(yè)要求裝入內(nèi)存時，根據(jù)作業(yè)需要內(nèi)存空間的大小查詢內(nèi)存中各個空閑區(qū)，當(dāng)從內(nèi)存中找到一個大于或等于該作業(yè)大小的內(nèi)存空閑區(qū)時，選擇其中一個空閑區(qū)，按作業(yè)要求劃出一個分區(qū)裝入該作業(yè)。

回收：作業(yè)執(zhí)行完后，它所占用的內(nèi)存空間被收回，成為一個空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個空閑區(qū)。

四、實(shí)驗(yàn)方法

實(shí)現(xiàn)動態(tài)分區(qū)的分配與回收，主要考慮三個問題：

第一、設(shè)計(jì)記錄內(nèi)存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)和作業(yè)占用的區(qū)域(利用結(jié)構(gòu)體類型數(shù)組來保存數(shù)據(jù))；

第二、在設(shè)計(jì)的數(shù)據(jù)表格基礎(chǔ)上設(shè)計(jì)內(nèi)存分配算法（采用首次適應(yīng)算法找合適的分區(qū)（對空閑分區(qū)表進(jìn)行排序），分配時要考慮碎片問題）；

第三、在設(shè)計(jì)的數(shù)據(jù)表格基礎(chǔ)上設(shè)計(jì)內(nèi)存回收算法（分四種情況進(jìn)行回收（上鄰、下鄰、上下鄰和無相鄰分區(qū)）。

五、實(shí)驗(yàn)步驟

第一，設(shè)計(jì)記錄內(nèi)存使用情況的數(shù)據(jù)表格 ? 已分配分區(qū)表：起始地址、長度、標(biāo)志（0表示“空表項(xiàng)”，1表示“已分配”）? 空閑分區(qū)表：

起始地址、長度、標(biāo)志（0表示“空表項(xiàng)”，1表示“未分配”）

struct used_table { float address;

//已分分區(qū)起始地址

float length;

//已分分區(qū)長度，單位為字節(jié)

int flag;

//已分配表區(qū)登記欄標(biāo)志，用0表示空欄目，char zuoyename;};

//已分配區(qū)表

Struct free_table[ { float address;

//空閑分區(qū)起始地址

float length;

//空閑分區(qū)長度，單位為字節(jié)

int flag;

//空閑分區(qū)表登記欄目用0表示空欄目，1表示未配 };//空閑分區(qū)表

第二，在設(shè)計(jì)的表格上進(jìn)行內(nèi)存分配

? 首次適應(yīng)算法：為作業(yè)分配內(nèi)存，要求每次找到一個起始地址最小的適合作業(yè)的分區(qū)（按起始地址遞增排序）。

? 最大碎片size：要求當(dāng)找到的空閑分區(qū)－作業(yè)的大小的值小于或等于size時，將該分區(qū)全部分配給作業(yè)（數(shù)組后面元素向前移）； ? 否則，給作業(yè)分割出一部分空間時，其余部分仍作為新的空閑分區(qū)登記（空閑分區(qū)長度=空閑分區(qū)長度-作業(yè)長度, ? 空閑分區(qū)起始地址=空閑分區(qū)起始地址+作業(yè)長度 第三，在設(shè)計(jì)的表格上進(jìn)行內(nèi)存回收。

1、上鄰：條件:回收作業(yè)的始址=某個空閑區(qū)的始址+長度

操作：空閑區(qū)的長度=空閑區(qū)的長度+作業(yè)的大小

2、下鄰：條件:回收作業(yè)的始址+作業(yè)的長度=某個空閑區(qū)的始址

操作： 空閑區(qū)的始址=回收作業(yè)的始址

空閑區(qū)的長度=空閑區(qū)的長度+作業(yè)的長度

3、上下鄰：條件:1，2條件同時成立

操作：空閑區(qū)的始址=上鄰的始址

空閑區(qū)的長度=上鄰的長度+作業(yè)的長度+下鄰的長度

刪除下鄰

4、無上下鄰：

操作：找flag=0的行

空閑區(qū)的始址=回收作業(yè)的始址

空閑區(qū)的長度=作業(yè)的長度

六、實(shí)驗(yàn)代碼

# include # include #define M 10 //允許的空閑區(qū)表長最大為m #define N 10 //允許的最大作業(yè)數(shù)量為n #define MIN 1 //碎片的最大值

#define SADDRESS 200 //空閑分區(qū)初始的起始地址 #define SLENGTH 150000 //空閑分區(qū)的初始長度 struct used_t{ float address;//已分分區(qū)起始地址

float length;//已分分區(qū)長度

int flag;//已分配表區(qū)登記欄標(biāo)志，用0表示空欄目

}used_table[N];struct free_t{ float address;//空閑分區(qū)起始地址

float length;//空閑分區(qū)長度 int flag;//空閑分區(qū)表登記欄目用0表示空欄目，1表示未分配

}free_table[M];//空閑分區(qū)表

void allocate(char,float);//分配算法子程序 void reclaim(char);//回收算法子程序 void main(){ int i,a;float zyl;char zyn;//空閑分區(qū)表初始化

free_table[0].address=SADDRESS;//空閑分區(qū)表的起始地址

free_table[0].length=SLENGTH;//空閑分區(qū)表的長度 free_table[0].flag=1;//標(biāo)志位置1表示未分配

for(i=1;i

free_table[i].length=0;

free_table[i].flag=0;} //0表示空欄目

//已分分區(qū)表初始化 for(i=0;i

used_table[i].length=0;

used_table[i].flag=0;} while(1){cout<<“請選擇功能項(xiàng)：”<

<<“1-分配主存”<

<<“2-回收主存”<

<<“3-顯示主存”<

<<“0-退出”<

<<“選擇功能項(xiàng)(0-3):”;

cin>>a;switch(a){case 0: //當(dāng)選擇0時退出程序

return;

case 1: { //a=1 分配主存空間

cout<<“n請輸入作業(yè)名zyn和作業(yè)所需長度zyl(作業(yè)名為一個字符，長度zyl要小于”<

cin>>zyn>>zyl;

allocate(zyn,zyl);//為作業(yè)zyn分配主存空間

break;

} case 2:{ // a=2 回收主存空間

cout<<“n請輸入要回收分區(qū)的作業(yè)名：”;

cin>>zyn;

reclaim(zyn);//回收作業(yè)zyn的主存空間

break;} case 3: { //a=3 顯示主存情況，輸出空閑區(qū)表和已分配區(qū)表 cout<<“n輸出空閑區(qū)表：”<

<<“ 起始地址 分區(qū)長度 標(biāo)志”<

for(i=0;i

if(free_table[i].flag!=0)cout<

cin.get();

cout<<“n輸出已分配區(qū)表：”<

<<“ 起始地址 分區(qū)長度 標(biāo)志”<

for(i=0;i

cout<

<

break;}

default:{

cout<<“n沒有該選項(xiàng)！”<

break;

}}} cin.get()}//分配算法子程序

void allocate(char zyn,float zyl){ float ad;int k=-1;int i=0;while(i

if(free_table[i].length>=zyl&&free_table[i].flag==1)

k=i;

i++;} if(k==-1){ //未找到可用空閑區(qū)，返回

cout<<“無可用空閑區(qū)！”<

return;} /*找到可用空閑區(qū)，開始分配：若空閑區(qū)大小與作業(yè)要求分配的空間差小于MIN,則將找到的空閑區(qū)全部分配給該作業(yè)；若空閑區(qū)大小與要求分配的空間的差大于minisize,則從空閑區(qū)劃出一部分分配給作業(yè)。*/ if(free_table[k].length-zyl<=MIN){ free_table[k].flag=0;ad=free_table[k].address;zyl=free_table[k].length;for(i=k;i

free_table[i]=free_table[i+1];} else{ free_table[k].length=free_table[k].length-zyl;ad=free_table[k].address;free_table[k].address=free_table[k].address+zyl;} /*修改已分配區(qū)表*/ i=0;while(used_table[i].flag!=0&&i

s++;//找到作業(yè)zyn在以分配表中的表目s if(s>=N){ cout<<“找不到該作業(yè)！”<

S=used_table[s].address;//取作業(yè)zyn在內(nèi)存中的首地址

L=used_table[s].length;//取作業(yè)zyn所分配到的內(nèi)存的長度

j=-1;k=-1;i=0;//尋找回收分區(qū)的上下鄰空閑區(qū)，上鄰表目k，下鄰表目j while(i

if(free_table[i].address==S+L)j=i;}

i++;} if(k!=-1){ //有上鄰空閑區(qū)

if(j!=-1){ //有下鄰空閑區(qū) 即有上下鄰空閑區(qū)，三項(xiàng)合并

free_table[k].length=free_table[k].length+free_table[j].length+L;

free_table[j].flag=0;} else //上鄰空閑區(qū)，下鄰非空閑區(qū)，與上鄰合并

free_table[k].length=free_table[k].length+L;}//if else { //k==-1 無上鄰空閑區(qū)

if(j!=-1){ //無上鄰空閑區(qū)，有下鄰空閑區(qū)，與下鄰合并 free_table[j].address=S;free_table[j].length=free_table[j].length+L;} else{ //j==-1 上下鄰均為非空閑區(qū)，回收區(qū)域直接填入 t=0;//在空閑區(qū)表中尋找空欄目

while(free_table[t].flag==1&&t=M){ //空閑區(qū)表滿，回收空間失敗，將已分配區(qū)表復(fù)原

cout<<“主存空閑表沒有空間，回收失??！”<

return;

} free_table[t].address=S;

free_table[t].length=L;

free_table[t].flag=1;}} for(i=0;i<=M-1;i++)for(int j=i;jfree_table[j].address){ free_t temp;temp=free_table[i];free_table[i]=free_table[j];free_table[j]=temp;}}

七、實(shí)驗(yàn)結(jié)果

1、總的存儲空間

2、分配空間

3、回收空間（1）有上下鄰

（2）有上鄰

（3）有下鄰

（4）無上下鄰，回收7

八、實(shí)驗(yàn)總結(jié)

1、通過實(shí)驗(yàn)學(xué)會了理解動態(tài)分區(qū)存儲管理方式下的內(nèi)存空間的分配與回收

2、學(xué)會了回收的四種方式

3、實(shí)驗(yàn)過程中遇到了問題，學(xué)會了與同學(xué)探討解決

第四篇：操作系統(tǒng)實(shí)驗(yàn)報(bào)告-可變分區(qū)存儲管理方式的內(nèi)存分配回收

實(shí)驗(yàn)三 可變分區(qū)存儲管理方式的內(nèi)存分配回收

一．實(shí)驗(yàn)?zāi)康?/p>

（1）深入了解可變分區(qū)存儲管理方式的內(nèi)存分配回收的實(shí)現(xiàn)。

二．實(shí)驗(yàn)內(nèi)容

編寫程序完成可變分區(qū)存儲管理方式的內(nèi)存分配回收，要求有內(nèi)存空間分配表，并采用最優(yōu)適應(yīng)算法完成內(nèi)存的分配與回收。

三．實(shí)驗(yàn)原理

在可變分區(qū)模式下，在系統(tǒng)初啟且用戶作業(yè)尚未裝入主存儲器之前，整個用戶區(qū)是一個大空閑分區(qū)，隨著作業(yè)的裝入和撤離，主存空間被分成許多分區(qū)，有的分區(qū)被占用，而有的分區(qū)時空閑的。為了方便主存空間的分配和去配，用于管理的數(shù)據(jù)結(jié)構(gòu)可由兩張表組成：“已分配區(qū)表”和“未分配區(qū)表”。在“未分配表中”將空閑區(qū)按長度遞增順序排列，當(dāng)裝入新作業(yè)時，從未分配區(qū)表中挑選一個能滿足用戶進(jìn)程要求的最小分區(qū)進(jìn)行分配。這時從已分配表中找出一個空欄目登記新作業(yè)的起始地址和占用長度，同時修改未分配區(qū)表中空閑區(qū)的長度和起始地址。當(dāng)作業(yè)撤離時已分配區(qū)表中的相應(yīng)狀態(tài)變?yōu)椤翱铡?，而將收回的分區(qū)登記到未分配區(qū)表中，若有相鄰空閑區(qū)再將其連接后登記。可變分區(qū)的回收算法較為復(fù)雜，當(dāng)一個作業(yè)撤離時，可分為4種情況：其臨近都有作業(yè)（A和B），其一邊有作業(yè)（A或B），其兩邊均為空閑區(qū)。尤其重要的是，在程序中利用“new類型T（初值列表）”申請分配用于存放T類型數(shù)據(jù)的內(nèi)存空間，利用“delete指針名”釋放指針?biāo)赶虻膬?nèi)存空間。

四．實(shí)驗(yàn)部分源程序

#include using namespace std;typedef struct SNode { // Space Node

int start,end;// 起始，結(jié)束

int length;// 長度大小

struct SNode *next;// 指向下一結(jié)點(diǎn)的指針 }* SP;SP Head=(SP)malloc(sizeof(SNode));// 全局變量，內(nèi)存空間頭結(jié) void DispSpace(){ // 顯示內(nèi)存空間分配情況

SP p=Head->next;

cout<<“n 空閑區(qū)說明表 n”

<<“---地址--長度---n”;

while(p)

{

cout<<“

”<

start

<<“

”<

length<

p=p->next;

}

cout<<“----------------n”;}

void Initial(){ // 初始化說明表

SP p,q;

p=(SP)malloc(sizeof(SNode));

q=(SP)malloc(sizeof(SNode));

p->start=14;p->length=12;p->end=26;

q->start=32;q->length=96;q->end=128;// 指導(dǎo)書上的作業(yè)分配

Head->next=p;// 與頭結(jié)點(diǎn)連接

p->next=q;

q->next=NULL;

DispSpace();}

void Allocation(int len){ // 分配內(nèi)存給新作業(yè)

SP p=Head->next,q;

while(p){

if(p->length < len)

p=p->next;

else if(p->length > len)

{

p->start=p->start+len;

p->length=p->length-len;

cout<<“分配成功!n”;

DispSpace();return;

}

else

{//當(dāng)兩者長度相等

q=p->next;

p->next=q->next;

cout<<“分配成功!n”;

DispSpace();return;

}

}

cout<<“分配失敗!n”;

DispSpace();return;}

void CallBack(int sta,int len){ // 回收內(nèi)存

SP p=Head,q=p->next,r;// 開始地址和長度

p->end=0;

int en=sta+len;

while(q){

if(sta == 0){ // 初始地址為0

if(en == q->start){ // 正好回收

q->start=0;

q->length=q->end;

return;

}

else {

r=(SP)malloc(sizeof(SNode));

r->start=sta;r->length=len;r->end=en;

p->next=r;

r->next=q;

return;

}

}

else if((p->end < sta)&&(q->start > en)){ // 上鄰區(qū)

r=(SP)malloc(sizeof(SNode));

r->start=sta;r->length=len;r->end=en;

p->next=r;

r->next=q;

return;

}

else if((p->end < sta)&&(q->start == en)){ // 鄰區(qū)相接

q->start=sta;

q->length=q->end-sta;

return;

}

else if((p->end == sta)&&(q->start < en)){ // 下鄰區(qū)

p->end=en;

p->length=en-p->start;

return;

}

else if(p->end==sta && q->start==en){ // 鄰區(qū)相接

p->end=q->end;

p->length=p->end-p->start;

p->next=q->next;

return;

}

else {

p=p->next;

q=q->next;

}

} } void main(){

Initial();

cout<<“現(xiàn)在分配大小為 6K 的作業(yè) 4 申請裝入主存: ”;

Allocation(6);// 分配時參數(shù)只有長度

//--------指導(dǎo)書測試數(shù)據(jù)演示----------

cout<<“現(xiàn)回收作業(yè) 3(起址10,長度4)n”;

CallBack(10,4);

DispSpace();

cout<<“現(xiàn)回收作業(yè) 2(起址26,長度6)n”;

CallBack(26,6);

DispSpace();

//---------------演示結(jié)束-------------

system(“pause”);}

五．實(shí)驗(yàn)結(jié)果與體會

我的體會：

第五篇：操作系統(tǒng)存儲管理實(shí)驗(yàn)介紹

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)五 存儲管理

一、實(shí)驗(yàn)?zāi)康?、加深對操作系統(tǒng)存儲管理的理解、能過模似頁面調(diào)試算法，加深理解操作系統(tǒng)對內(nèi)存的高度管理

二、總的設(shè)計(jì)思想、環(huán)境語言、工具等總的設(shè)計(jì)思想：

1、編寫函數(shù)計(jì)算并輸出下述各種算法的命中率

① OPT頁面置換算法

OPT所選擇被淘汰的頁面是已調(diào)入內(nèi)存，且在以后永不使用的，或是在最長時間內(nèi)不再被訪問的頁面。因此如何找出這樣的頁面是該算法的關(guān)鍵?？蔀槊總€頁面設(shè)置一個步長變量，其初值為一足夠大的數(shù)，對于不在內(nèi)存的頁面，將其值重置為零，對于位于內(nèi)存的頁面，其值重置為當(dāng)前訪問頁面與之后首次出現(xiàn)該頁面時兩者之間的距離，因此該值越大表示該頁是在最長時間內(nèi)不再被訪問的頁面，可以選擇其作為換出頁面。② FIFO頁面置換算法

FIFO總是選擇最先進(jìn)入內(nèi)存的頁面予以淘汰，因此可設(shè)置一個先進(jìn)先出的忙頁幀隊(duì)列，新調(diào)入內(nèi)存的頁面掛在該隊(duì)列的尾部，而當(dāng)無空閑頁幀時，可從該隊(duì)列首部取下一個頁幀作為空閑頁幀，進(jìn)而調(diào)入所需頁面。③ LRU頁面置換算法

LRU是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的，它利用“最近的過去”作為“最近的將來”的近似，選擇最近最久未使用的頁面予以淘汰。該算法主要借助于頁面結(jié)構(gòu)中的訪問時間time來實(shí)現(xiàn)，time記錄了一個頁面上次的訪問時間，因此，當(dāng)須淘汰一個頁面時，選擇處于內(nèi)存的頁面中其time值最小的頁面，即最近最久未使用的頁面予以淘汰。

④ LFU頁面置換算法

LFU要求為每個頁面配置一個計(jì)數(shù)器（即頁面結(jié)構(gòu)中的counter），一旦某頁被訪問，則將其計(jì)數(shù)器的值加1，在需要選擇一頁置換時，則將選擇其計(jì)數(shù)器值最小的頁面，即內(nèi)存中訪問次數(shù)最少的頁面進(jìn)行淘汰。⑤ NUR頁面置換算法

NUR要求為每個頁面設(shè)置一位訪問位（該訪問位仍可使用頁面結(jié)構(gòu)中的counter表示），當(dāng)某頁被訪問時，其訪問位counter置為1。需要進(jìn)行頁面置換時，置換算法從替換指針開始（初始時指向第一個頁面）順序檢查處于內(nèi)存中的各個頁面，如果其訪問位為0，就選擇該頁換出，否則替換指針下移繼續(xù)向下查找。如果內(nèi)存中的所有頁面掃描完畢未找到訪問位為0的頁面，則將替換指針重新指向第一個頁面，同時將內(nèi)

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

存中所有頁面的訪問位置0，當(dāng)開始下一輪掃描時，便一定能找到counter為0的頁面。

2、在主函數(shù)中生成要求的指令序列，并將其轉(zhuǎn)換成頁地址流；在不同的內(nèi)存容量下調(diào)用上述函數(shù)使其計(jì)算并輸出相應(yīng)的命中率。

環(huán)境語言：Linux下的GNU 編譯環(huán)境

三、數(shù)據(jù)結(jié)構(gòu)與模塊說明

程序中用到的數(shù)據(jù)結(jié)構(gòu)、類型定義及主要的函數(shù)原型如下：

1、數(shù)據(jù)結(jié)構(gòu)

（1）頁面結(jié)構(gòu) typedef struct{ int pn, pfn, counter, time;} pl_type;pl_type pl[total_vp];其中pn為頁面號（頁號），pfn為頁幀號（物理塊號），counter為一個周期內(nèi)訪問該頁面的次數(shù)，time為訪問時間；pl[total_vp]為頁面結(jié)構(gòu)數(shù)組，由于共有320條指令，每頁可裝入10條指令，因此虛頁長total_vp的值為32。

（2）頁幀控制結(jié)構(gòu) struct pfc_struct{ int pn, pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;其中pfc[total_vp]定義用戶進(jìn)程的頁幀控制結(jié)構(gòu)數(shù)組，在該實(shí)驗(yàn)中，用戶內(nèi)存工作區(qū)是動態(tài)變化的，最多可達(dá)到用戶進(jìn)程的虛頁數(shù)目，即32個物理塊。

*freepf_head為空閑頁幀頭的指針 *busypf_head為忙頁幀頭的指針 *busypf_tail忙頁幀尾的指針

2、變量定義

(1)int a[total_instruction]: 指令流數(shù)組(2)int diseffect: 頁面失效次數(shù)

(3)int page[total_instruction]: 每條指令所屬頁面號

(4)int offset[total_instruction]: 每頁裝入10條指令后取模運(yùn)算得出的頁內(nèi)偏移地址(5)int total_pf: 用戶進(jìn)程的內(nèi)存頁幀數(shù)

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

3、主要函數(shù)

(1)void initialize(int): 初始化函數(shù)

該函數(shù)主要對頁面結(jié)構(gòu)數(shù)組pl和頁幀結(jié)構(gòu)數(shù)組pfc進(jìn)行初始化，如置頁面結(jié)構(gòu)中的頁面號pn，初始化頁幀號pfn為空，訪問次數(shù)counter為0，訪問時間time為-1；同樣對頁幀數(shù)組進(jìn)行初始化，形成一個空閑頁幀隊(duì)列。

(2)void OPT(int): 計(jì)算使用最佳頁面算法時的命中率

(3)void FIFO(int): 計(jì)算使用先進(jìn)先出頁面置換算法時的命中率(4)void LRU(int): 計(jì)算使用最近最久未使用頁面置換算法時的命中率(5)void LFU(int): 計(jì)算使用最少使用置換算法時的命中率(6)void NUR(int): 計(jì)算使用最近未使用置換算法時的命中率

四、主要算法的設(shè)計(jì)與實(shí)現(xiàn)

void FIFO(int total_pf)/*先進(jìn)先出頁面置換算法*/ { int i,j;pfc_type *p;initialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;i

if(pl[page[i]].pfn==INVALID)/*頁面失效*/ { diseffect=diseffect+1;

if(freepf_head==NULL)/*無空閑頁幀*/ {

} p=freepf_head->next;//有空閑頁幀 freepf_head->next=NULL;freepf_head->pn=page[i];/* 將所需頁面調(diào)入空閑頁幀 */ pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NULL)/* 若忙頁幀隊(duì)列為空，則將其頭尾指針都指向剛調(diào)入頁p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID;//將忙頁幀隊(duì)首頁面作為換出頁面 freepf_head=busypf_head;freepf_head->next=NULL;busypf_head=p;//忙頁幀頭指針后移

面所在的頁幀 */

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

busypf_head=busypf_tail=freepf_head;else{ //否則，將剛調(diào)入頁面所在的頁幀掛在忙頁幀隊(duì)列尾部

} freepf_head=p;//空閑頁幀頭指針后移 busypf_tail->next=freepf_head;busypf_tail=freepf_head;} } printf(“FIFO:%6.4f ”,1-(float)diseffect/320);} void LRU(int total_pf)/*最近最久未使用頁面置換算法*/ { int i,j;int min,minj,present_time;initialize(total_pf);present_time=0;for(i=0;i

if(pl[page[i]].pfn==INVALID)/*頁面失效*/ {

diseffect++;if(freepf_head==NULL)/*無空閑頁幀*/ { min=32767;for(j=0;j

} freepf_head=&pfc[pl[minj].pfn];//騰出一個單元 pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=NULL;if(min>pl[j].time && pl[j].pfn!=INVALID){

}

min=pl[j].time;minj=j;面*/

} pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效 pl[page[i]].time=present_time;//修改頁面的訪問時間

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

} freepf_head=freepf_head->next;//減少一個free 頁面

else pl[page[i]].time=present_time;//命中則修改該單元的訪問時間

present_time++;} printf(“LRU:%6.4f ”,1-(float)diseffect/320);} void NUR(int total_pf)/* 最近未使用頁面置換算法 */ { int i,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0;for(i=0;i

if(pl[page[i]].pfn==INVALID)/*頁面失效*/ { diseffect++;if(freepf_head==NULL)/*無空閑頁幀*/ {

cont_flag=TRUE;old_dp=dp;while(cont_flag){

if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)

cont_flag=FALSE;//找到位于內(nèi)存且未被訪問的頁面

else {

dp++;

if(dp==total_vp)dp=0;//將替換指針重新指向第一個頁面 if(dp==old_dp)

{/* 若內(nèi)存中所有頁面掃描完畢未找到訪問位為0的頁面，將內(nèi)存中所有頁面的訪問位置0 */

} freepf_head=&pfc[pl[dp].pfn];//騰出一個單元

}

}

for(j=0;j

pl[j].counter=0;

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

} pl[dp].pfn=INVALID;freepf_head->next=NULL;

} pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效 freepf_head=freepf_head->next;//減少一個free 頁面

else pl[page[i]].counter=1;//命中則將訪問位置1

if(i%clear_period==0)//清零周期到，將所有訪問位清零

{

for(j=0;j

} } } void OPT(int total_pf)/* 最佳頁面置換算法 */ { int i,j,max,maxpage,d,dist[total_vp];initialize(total_pf);for(i=0;i

for(j=0;j

} d=1;/* 對于位于內(nèi)存且在當(dāng)前訪問頁面之后將再次被訪問的頁面，dist重置為當(dāng)前頁 面與之后首次出現(xiàn)該頁面時兩者之間的距離 */ for(j=i+1;j

dist[j]=32767;printf(“NUR:%6.4f ”,1-(float)diseffect/320);

else //不在內(nèi)存的頁面該變量則置為0

dist[j]=0;

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

}

} if(pl[page[j]].pfn!=INVALID && dist[page[j]]==32767)

dist[page[j]]=d;

d++;max=-1;//查找dist變量值最大的頁面作為換出頁面 for(j=0;j

} freepf_head=&pfc[pl[maxpage].pfn];//騰出一個單元 freepf_head->next=NULL;pl[maxpage].pfn=INVALID;if(max

}

max=dist[j];maxpage=j;

} } pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效 freepf_head=freepf_head->next;//減少一個free 頁面

printf(“OPT:%6.4f ”,1-(float)diseffect/320);} void LFU(int total_pf)/* 最少使用頁面置換算法 */ { int i,j,min,minpage;initialize(total_pf);for(i=0;i

min=32767;for(j=0;j

if(min>pl[j].counter&&pl[j].pfn!=INVALID){

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

}

}

}

min=pl[j].counter;minpage=j;pl[j].counter=0;

freepf_head=&pfc[pl[minpage].pfn];//騰出一個單元 pl[minpage].pfn=INVALID;freepf_head->next=NULL;

pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效 pl[page[i]].counter++;//增加頁面訪問次數(shù) freepf_head=freepf_head->next;//減少一個free 頁面

} else pl[page[i]].counter++;//命中增加頁面訪問次數(shù)

}

printf(“LFU:%6.4f ”,1-(float)diseffect/320);}

五、運(yùn)行結(jié)果

本實(shí)驗(yàn)的運(yùn)行結(jié)果如下圖所示（以O(shè)PT、FIFO、LRU為例）：

從上述結(jié)果可知，隨著內(nèi)存頁面數(shù)的增加，三種算法的訪問命中率逐漸增大。在內(nèi)存頁面數(shù)為4~25個頁面之間時，三種算法的命中率大致在56%至88%之間變化，但是，OPT算法和其他兩種算法之間的差別一般在6~12個百分點(diǎn)左右。在內(nèi)存頁面為25~32個頁面時，由于用戶進(jìn)程的所有指令基本上都已裝入內(nèi)存，從而命中率增加較大，各種算法之間的差別不大。

河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

比較上述三種算法，OPT算法的命中率最高，LRU算法和FIFO算法的命中率則較為接近。

六、總結(jié)

經(jīng)過測試結(jié)果完全正常。經(jīng)過編寫和學(xué)習(xí)讓我對操作系統(tǒng)方面的知識更深一步的得到了理解和鞏固。讓我在今后的學(xué)習(xí)中可以更好的去理解和體會。