第一篇：計算機操作系統動態分區存儲管理方式下的內存空間的分配與回收實驗報告

計算機操作系統

實驗報告

實驗二

實驗題目：存儲器管理

系別：計算機科學與技術系

班級：

姓名：

學號：2

一、實驗目的

深入理解動態分區存儲管理方式下的內存空間的分配與回收。

二、實驗內容

編寫程序完成動態分區存儲管理方式下的內存分配和回收的實現。具體內容包括：

確定用來管理內存當前使用情況的數據結構； 采用首次適應算法完成內存空間的分配； 分情況對作業進行回收；

編寫主函數對所做工作進行測試。

三、實驗原理

分配：動態分區存儲管理方式把內存除OS占用區域外的空間看作一個大的空閑區。當作業要求裝入內存時，根據作業需要內存空間的大小查詢內存中各個空閑區，當從內存中找到一個大于或等于該作業大小的內存空閑區時，選擇其中一個空閑區，按作業要求劃出一個分區裝入該作業。

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

四、實驗方法

實現動態分區的分配與回收，主要考慮三個問題：

第一、設計記錄內存使用情況的數據表格，用來記錄空閑區和作業占用的區域(利用結構體類型數組來保存數據)；

第二、在設計的數據表格基礎上設計內存分配算法（采用首次適應算法找合適的分區（對空閑分區表進行排序），分配時要考慮碎片問題）；

第三、在設計的數據表格基礎上設計內存回收算法（分四種情況進行回收（上鄰、下鄰、上下鄰和無相鄰分區）。

五、實驗步驟

第一，設計記錄內存使用情況的數據表格 ? 已分配分區表：起始地址、長度、標志（0表示“空表項”，1表示“已分配”）? 空閑分區表：

起始地址、長度、標志（0表示“空表項”，1表示“未分配”）

struct used_table { float address;

//已分分區起始地址

float length;

//已分分區長度，單位為字節

int flag;

//已分配表區登記欄標志，用0表示空欄目，char zuoyename;};

//已分配區表

Struct free_table[ { float address;

//空閑分區起始地址

float length;

//空閑分區長度，單位為字節

int flag;

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

第二，在設計的表格上進行內存分配

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

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

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

操作：空閑區的長度=空閑區的長度+作業的大小

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

操作： 空閑區的始址=回收作業的始址

空閑區的長度=空閑區的長度+作業的長度

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

操作：空閑區的始址=上鄰的始址

空閑區的長度=上鄰的長度+作業的長度+下鄰的長度

刪除下鄰

4、無上下鄰：

操作：找flag=0的行

空閑區的始址=回收作業的始址

空閑區的長度=作業的長度

六、實驗代碼

# include # include #define M 10 //允許的空閑區表長最大為m #define N 10 //允許的最大作業數量為n #define MIN 1 //碎片的最大值

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

float length;//已分分區長度

int flag;//已分配表區登記欄標志，用0表示空欄目

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

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

}free_table[M];//空閑分區表

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

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

free_table[0].length=SLENGTH;//空閑分區表的長度 free_table[0].flag=1;//標志位置1表示未分配

for(i=1;i

free_table[i].length=0;

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

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

used_table[i].length=0;

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

<<“1-分配主存”<

<<“2-回收主存”<

<<“3-顯示主存”<

<<“0-退出”<

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

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

return;

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

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

cin>>zyn>>zyl;

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

break;

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

cout<<“n請輸入要回收分區的作業名：”;

cin>>zyn;

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

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

<<“ 起始地址 分區長度 標志”<

for(i=0;i

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

cin.get();

cout<<“n輸出已分配區表：”<

<<“ 起始地址 分區長度 標志”<

for(i=0;i

cout<

<

break;}

default:{

cout<<“n沒有該選項！”<

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){ //未找到可用空閑區，返回

cout<<“無可用空閑區！”<

return;} /*找到可用空閑區，開始分配：若空閑區大小與作業要求分配的空間差小于MIN,則將找到的空閑區全部分配給該作業；若空閑區大小與要求分配的空間的差大于minisize,則從空閑區劃出一部分分配給作業。*/ 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;} /*修改已分配區表*/ i=0;while(used_table[i].flag!=0&&i

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

S=used_table[s].address;//取作業zyn在內存中的首地址

L=used_table[s].length;//取作業zyn所分配到的內存的長度

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

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

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

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

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

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

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

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

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

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;}}

七、實驗結果

1、總的存儲空間

2、分配空間

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

（2）有上鄰

（3）有下鄰

（4）無上下鄰，回收7

八、實驗總結

1、通過實驗學會了理解動態分區存儲管理方式下的內存空間的分配與回收

2、學會了回收的四種方式

3、實驗過程中遇到了問題，學會了與同學探討解決

第二篇：操作系統實驗報告-可變分區存儲管理方式的內存分配回收

實驗三 可變分區存儲管理方式的內存分配回收

一．實驗目的

（1）深入了解可變分區存儲管理方式的內存分配回收的實現。

二．實驗內容

編寫程序完成可變分區存儲管理方式的內存分配回收，要求有內存空間分配表，并采用最優適應算法完成內存的分配與回收。

三．實驗原理

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

四．實驗部分源程序

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

int start,end;// 起始，結束

int length;// 長度大小

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

SP p=Head->next;

cout<<“n 空閑區說明表 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;// 指導書上的作業分配

Head->next=p;// 與頭結點連接

p->next=q;

q->next=NULL;

DispSpace();}

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

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

{//當兩者長度相等

q=p->next;

p->next=q->next;

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

DispSpace();return;

}

}

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

DispSpace();return;}

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

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)){ // 上鄰區

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->start=sta;

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

return;

}

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

p->end=en;

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

return;

}

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

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<<“現在分配大小為 6K 的作業 4 申請裝入主存: ”;

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

//--------指導書測試數據演示----------

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

CallBack(10,4);

DispSpace();

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

CallBack(26,6);

DispSpace();

//---------------演示結束-------------

system(“pause”);}

五．實驗結果與體會

我的體會：

第三篇：操作系統課程設計_動態分區分配存儲管理

操作系統課程設計

設計題目 動態分區分配存儲管理

學生姓名學

號 專業班級 指導教師

呂 霆

20102675 計算機10-01班

第一章

課程設計概述

1.1 設計任務: 動態分區分配存儲管理

1.2 設計要求

建立描述內存分配狀況的數據結構； ?建立描述進程的數據結構； ?使用兩種方式產生進程：（a）自動產生，（b）手工輸入； ? 在屏幕上顯示內存的分配狀況、每個進程的執行情況； ? 建立分區的分配與回收算法，支持緊湊算法； ? 時間的流逝可用下面幾種方法模擬：（a）按鍵盤，每按一次可認為過一個時間單位；(b)響應WM_TIMER；

? 將一批進程的執行情況存入磁盤文件，以后可以讀出并重放；

? 支持算法：首次適應算法、循環首次適應算法、最佳適應算法：最壞適應算法。

1.3 設計目的

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

2.1動態分區分配算法原理

首次適應算法

* 算法概述：分配內存時，從鏈首開始順序查找，找到滿足的空閑分區則劃出空間分配，余下的空閑空間仍保留在空閑鏈表中

* 實現方法：分配時從數組第一個元素開始比較，若符合條件則將該元素減去對應作業的值

循環首次適應算法

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

* 實現方法：在首次適應算法的基礎上增加一個值用于記錄找到的空閑分區的位置

最佳適應算法

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

分配給作業

* 實現方法：我們決定每次分配先把空閑分區按從小到大的順序排列，然后將第一個匹配分區分配給作業

最壞適應算法

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

* 實現方法：算法與最佳適應算法幾乎相同，僅在排序時把空閑分區表按從大到小的順序排列，所以未作詳細注釋

回收分區

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

通過移動內存中的作業的位置,以把原來多個分散的小分區拼接成一個大分區的方法.第三章 開發環境

此程序是本人利用c++語言在vs2012的開發環境中實現的第四章 程序實現--數據結構

#include #include #include using namespace std;ofstream stream;//輸出流對象 int ary1[20][4];//內存分配狀態 int ary2[20][3];//空閑分區狀態 int ary3[10];//進程分配狀態

int recycle;//需要回收的盤塊序號 int id1;//算法選擇號 int m;//內存區數 int n;//空閑區數 int q;//進程數

int r=0;//循環首次適應算法：對應的這次查找到的空閑分區序號 //打印輸出函數 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<<“-------------內存分配狀態-------------”<

} cout <

} cout <

}

//作業信息的自動產生 void create_pro(){

}

//作業的手動生成 void create_zuoye(){ int j;int choice2;int id3=rand()%10;m=id3;//內存區數量 cout<<“產生”<

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

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

}

//內存信息的自動產生 void create_apply(){

int k=0;//空閑區數量 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<<“輸入想創建的作業請求大小”<

} cout<<“你創建了”<>j;ary3[i]=j;

}

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

}

//首次適應算法 void first_fit()int k,x,y,o=0;int a=0;cout<<“輸入想創建的內存分區塊數 : ”;cin>>k;

cout<<“輸入”<

} cout<<“輸入內存塊的分配狀態”<

} 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;//狀態 n++;ary1[i][0]=i;//序號 cin>>x;ary1[i][1]=x;//大小 } n=k;//空閑塊數量

{

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])//進程占用空間小于等于其中一個空閑區的大小 {

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//否則的話，空閑鏈對應的地方盤塊大小小了進程占用的大小，并且內存分配從對應的 {

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];那一項開始增加一項

} 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

//首次循環適應算法 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//對應的空閑塊大小大于進程需要大小 { //-----改變內存分配情況-----r=(r+1)%n;//改變第k塊的內容 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;//從k+1之后所有向后移一格 m++;//內存塊數增加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];//---改變內存分配---k=ary2[j][0];//得到對應空閑塊對應內存塊的序號 k--;ary1[k][3]=2;//把對應內存塊標志位上改成已分配 //------------------//--改變空閑塊表：把從這塊空閑塊以下的所有空閑塊向上移一格--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<<“[”<

}

}

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

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

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

}

{ 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塊內容：對應的數組是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];

}

//最壞適應算法 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++;} {

//把對應的內存分配進行更改 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;//用來存放進行比較時的中間結果 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 {

//把對應的內存分配進行更改 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

}

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

（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{//剩下比較復雜的四種情況

if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]==2))//回收區上鄰接著空閑盤塊，下連接著{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-1][3]=0;k=0;for(j=0;j

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

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

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))//回收區上下連接的都是空閑盤塊 { cout<<”回收區上下連接的都是空閑盤塊“<

} 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))//回收區下鄰接著空閑盤塊，上鄰接著{ cout<<”回收區下鄰接著空閑盤塊，上鄰接著已分配盤塊“<

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

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))//空閑區上下鄰接的都是已分配盤塊 {

} 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<<”回收區上下連接的都是空閑盤塊“<

} 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;//記錄空閑盤塊數量 int sum_avl=0;//總共空閑區大小 int num_apl=0;//統計總共空閑區有多大 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;//包括最后一個空閑區 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“<

}

//主函數入口

void main(){

if(choice1==1){

}

num=rand()&10;q=num;int id3=2+rand()%8;m=id3;//內存區數量 create_apply();create_pro();int i;int j;int num;int choice1;//操作選擇標記 int choice2;int flag=1;//標記是否再執行 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首次適應算法-----2循環首次適應算法-----3最佳適應算法 **“<>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<<”*******************生成內存狀態******************“<>recycle;if((recycle>m)||(recycle<1)){

} cout<<”錯誤:內存中不存在此塊！“<

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

}

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

第四篇：可變分區存儲管理方式的內存分配和回收

#include//定義輸入/輸出函數

#include//數據流輸入/輸出

#include//字符串處理

#include//參數化輸入/輸出

const int MJ=10;//假定系統允許的最大作業數量為10

typedef struct node{

int address;

int length;

char tag[10];

}job;

job frees[MJ];

int free_quantity;

job occupys[MJ];

int occupy_quantity;

int read()

{

FILE *fp;

char fn[10];

cout<<“請輸入初始空閑表文件名:”;

cin>>fn;

if((fp=fopen(fn,“r”))==NULL){ 其意義是在當前目錄下打開文件file a，只允許進行“讀”操作，并使fp指向該文件

cout<<“錯誤,文件打不開,請檢查文件名”<

}

else{

while(!feof(fp)){

fscanf(fp,“%d,%d”,&frees[free_quantity].address,&frees[free_quantity].length);free_quantity++;fscanf(文件指針，格式字符串，輸入表列)；

}

return 1;

}

return 0;

}

void sort()

{

int i,j,p;

for(i=0;i

p=i;

for(j=i+1;j

if(frees[j].address

p=j;

}

}

if(p!=i){

frees[free_quantity]=frees[i];

frees[i]=frees[p];

frees[p]=frees[free_quantity];

}

}

}

void view()

{

int i;

cout<

cout<<“輸出空閑區表：n起始地址 分區長度狀態n”<

for(i=0;i

cout.setf(2);

cout.width(12);

cout<

cout.width(10);

cout<

cout.width(8);

cout<

}

cout<

cout<<“輸出已分分區表：n起始地址 分區長度 占用作業名n”<

for(i=0;i

cout.setf(2);

cout.width(12);

cout<

cout.width(10);

cout<

cout.width(8);

cout<

}

}

void ear()

{

char job_name[10];

int job_length;

int i,j,flag,t;

cout<<“請輸入分配內存的作業名和空間大小:”;

cin>>job_name;

cin>>job_length;

flag=0;

for(i=0;i

if(frees[i].length>=job_length){

flag=1;

}

}

if(flag==0){//未找到空閑區，返回

cout<

}

else{

t=0;

i=0;

while(t==0){

if(frees[i].length>=job_length){//找到可用空閑區，開始分配

t=1;

}

i++;

}

i--;

occupys[occupy_quantity].address=frees[i].address;//修改已分配區表

strcpy(occupys[occupy_quantity].tag,job_name);

occupys[occupy_quantity].length=job_length;

occupy_quantity++;

if(frees[i].length>job_length){

frees[i].address+=job_length;

frees[i].length-=job_length;

}

else{

for(j=i;j

frees[j]=frees[j+1];

}

free_quantity--;

cout<<“內存空間成功:)”<

}

}

}

void reclaim()//回收作業所占的內存空間

{

char job_name[20];

int i,j,flag,p=0;

int address;

int length;//尋找已分分區表中對應的登記項

cout<<“輸入要回收分區的作業名:”;

cin>>job_name;

flag=-1;

for(i=0;i

if(!strcmp(occupys[i].tag,job_name)){

flag=i;

address=occupys[i].address;

length=occupys[i].length;

}

}

if(flag==-1){ //在已分分區表中找不到作業

cout<<“沒有這個作業名”<

}

else{//修改空閑區表，加入空閑表

for(i=0;i

if((frees[i].address+frees[i].length)==address){

if(((i+1)

for(j=i+1;j

frees[j]=frees[j+1];

}

free_quantity--;

p=1;

}

else{

frees[i].length+=length;

p=1;

}

}

if(frees[i].address==(address+length)){

frees[i].address=address;

frees[i].length+=length;

p=1;

}

}

if(p==0){

frees[free_quantity].address=address;

frees[free_quantity].length=length;

free_quantity++;

}//刪除分配表中的該作業

for(i=flag;i

occupys[i]=occupys[i+1];

}

occupy_quantity--;

}

}

void main()

{

int flag=0;

int t=1;

int chioce=0;

int i;

for(i=0;i

frees[i].address=-1;//空閑區表初始化

frees[i].length=0;

strcpy(frees[i].tag,“free”);

occupys[i].address=-1;//已分分區表初始化

occupys[i].length=0;

strcpy(occupys[i].tag,“");

}

free_quantity=0;

occupy_quantity=0;

flag=read();

while(flag==1){

sort();

cout<<”選擇功能項:（0-退出，1-分配內存，2-回收內存，3-顯示內存）n“<

cin>>chioce;

switch(chioce){

case 0:

flag=0;

break;

case 1:

ear();

break;

case 2:

reclaim();

break;

case 3:

view();

break;

default:

cout<<”沒有該選項n"<

}

}

}

第五篇：可變分區存儲管理方式的內存分配和回收實驗報告

一．實驗目的

通過編寫和調試存儲管理的模擬程序以加深對存儲管理方案的理解，熟悉可變分區存儲管理的內存分配和回收。二．實驗內容

1．確定內存空間分配表；

2．采用最優適應算法完成內存空間的分配和回收； 3．編寫主函數對所做工作進行測試。

三．實驗背景材料

實現可變分區的分配和回收，主要考慮的問題有三個：第一，設計記錄內存使用情況的數據表格，用來記錄空閑區和作業占用的區域；第二，在設計的數據表格基礎上設計內存分配算法；第三，在設計的數據表格基礎上設計內存回收算法。

首先，考慮第一個問題，設計記錄內存使用情況的數據表格，用來記錄空間區和作業占用的區域。

由于可變分區的大小是由作業需求量決定的，故分區的長度是預先不固定的，且分區的個數也隨內存分配和回收變動。總之，所有分區情況隨時可能發生變化，數據表格的設計必須和這個特點相適應。由于分區長度不同，因此設計的表格應該包括分區在內存中的起始地址和長度。由于分配時空閑區有時會變成兩個分區：空閑區和已分分區，回收內存分區時，可能會合并空閑分區，這樣如果整個內存采用一張表格記錄己分分區和空閑區，就會使表格操作繁瑣。分配內存時查找空閑區進行分配，然后填寫己分配區表，主要操作在空閑區；某個作業執行完后，將該分區變成空閑區，并將其與相鄰的空閑區合并，主要操作也在空閑區。由此可見，內存的分配和回收主要是對空閑區的操作。這樣為了便于對內存空間的分配和回收，就建立兩張分區表記錄內存使用情況，一張表格記錄作業占用分區的“己分分區表”；一張是記錄空閑區的“空閑區表”。這兩張表的實現方法一般有兩種：一種是鏈表形式，一種是順序表形式。在實驗中，采用順序表形式，用數組模擬。由于順序表的長度必須提前固定，所以無論是“已分分區表”還是“空閑區表”都必須事先確定長度。它們的長度必須是系統可能的最大項數。

“已分分區表”的結構定義

#define n 10 //假定系統允許的最大作業數量為n struct { float address;//已分分區起始地址

float length;//已分分區長度、單位為字節 int flag;//已分分區表登記欄標志，“0”表示空欄目，實驗中只支持一個字符的作業名

}used_table[n];//已分分區表

“空閑區表”的結構定義

#define m 10 //假定系統允許的空閑區最大為m struct { float address;//空閑區起始地址

float length;//空閑區長度、單位為字節

int flag;//空閑區表登記欄標志，“0”表示空欄目，“1”表示未分配 }used_table[n];//空閑區表

第二，在設計的數據表格基礎上設計內存分配。

裝入一個作業時，從空閑區表中查找滿足作業長度的未分配區，如大于作業，空閑區劃

第1頁 分成兩個分區，一個給作業，一個成為小空閑分區。

實驗中內存分配的算法采用“最優適應”算法，即選擇一個能滿足要求的最小空閑分區。第三，在設計的數據表格基礎上設計內存回收問題。內存回收時若相鄰有空閑分區則合并空閑區，修改空閑區表。

四、參考程序

#define n 10 //假定系統允許的最大作業數量為n #define m 10 //假定系統允許的空閑區最大為m #define minisize 100 struct { float address;//已分分區起始地址

float length;//已分分區長度、單位為字節

int flag;//已分分區表登記欄標志，“0”表示空欄目，實驗中只支持一個字符的作業名

}used_table[n];//已分分區表 struct { float address;//空閑區起始地址

float length;//空閑區長度、單位為字節 int flag;//空閑區表登記欄標志，“0”表示空欄目，“1”表示未分配 }used_table[n];//空閑區表

allocate(J,xk)//采用最優分配算法分配xk大小的空間 char J;float xk;{int i,k;float ad;k=-1;for(i=0;i=xk&&free_table[i].flag==1)if(k==-1||free_table[i].length

//找到可用空閑區，開始分配；若空閑區大小與要求分配的空間差小于minisize大小，則空閑區全部分配；

//若空閑區大小與要求分配的空間差大于minisize大小，則從空閑區劃分一部分分配

if(free_table[k].length-xk<=minisize){free_table[k].flag=0;ad=free_table[k].address;

第2頁 xk=free_table[k].length;} else {free_table[k].length=free_table[k].length-xk;ad=free_table[k].address+free_table[k].length;} //修改已分配區表

i=0;while(used_table[i].flag!=0&&i=n)//無表目填寫已分分區 {printf(“無表目填寫以分分區，錯誤n”);if(free_table[k].flag==0)//前面找到的是整個空閑區 free_table[k].flag=1;else //前面找到的是某個空閑區的一部分 free_table[k].length=free_table[k].length+xk;return;} else //修改已分配區表 {used_table[i].address=ad;used_table[i].length=xk;used_table[i].flag=J;} return;}//內存分配函數結束

reclaim(J)//回收作業名為J的作業所占的內存空間 char J: {int i,k,j,s,t;float S,L;//尋找已分分區表中對應的登記項 S=0;while((used_table[S].flag!=J||used_table[S].flag==0)&&S=n)//在已分分區表中找不到名字為J的作業 {printf(“找不到該作業n”);return;} //修改已分分區表

used_table[S].flag=0;//取得歸還分區的起始地址S和長度L S=used_table[S].address;L=used_table[S].length;j=-1;k=-1;i=0;

第3頁 //尋找回收分區的上下鄰空閑區，上鄰表目K，下鄰表目J while(i

{free_table[k].length=free_table[j].length+free_table[k].length+L;free_table[j].flag+0;} else //上鄰空閑區，下鄰非空閑區，與上鄰合并 free_table[k].length=free_table[k].length+L;else if(j!=-1)//上鄰非空閑區，下鄰空閑區，與下鄰合并 {free_table[j].address=S;free_table[j].length=free_table[j].length+L;} else { //上下鄰均為非空閑區，回收區域直接填入 t=0;//在空閑區表中尋找空欄目 while(free_table[t].flag==1&&t=m)//空閑區表滿,回收空間失敗,將已分配分區表復原

{printf(“內存空閑表沒有空間，回收空間失敗n”);used_table[S].flag=J;return;} free_table[t].address=s;free_table[t].length=l;free_table[t].flag=1;} return(true);} //內存回收函數結束

main(){ int i,a;float xk;char J;//空閑區表初始化

free_table[0].address=10240;

第4頁 free_table[0].length=102400;free_table[0].flag=1;for(i=1;i

case 1;//a=1 分配內存空間

printf(“輸入作業名J和作業所需長度XK：”);scanf(“%c%c%f”,&j,&xk);allocate(j,xk);//分配內存空間 break;case 2;//a=2 回收內存空間 printf(“輸入要回放分區的作業名”);scanf(“%c%c”,&j);reclaim(j);//回收內存空間 break;case 3;//a=3顯示內存情況，輸出空閑區表和已分分區表 printf(“輸出空閑區表：n起始地址 分區長度 標志n”);for(i=0;i

第5頁