第一篇：實驗三 存儲器的分配與回收算法實現(二維數組)

實驗三 存儲器的分配與回收算法

◆實驗名稱：存儲器的分配與回收算法實驗 ◆儀器、設備：計算機

◆參考資料：操作系統實驗指導書 ◆實驗目的：

設計一個存儲器的分配與回收算法管理方案，并編寫模擬程序實現。◆實驗內容：

1.模擬操作系統的主存分配，運用可變分區的存儲管理算法設計主存分配和回收程序，并不實際啟動裝入作業。

2.采用最先適應法、最佳適應法、最壞適應法分配主存空間。

3.當一個新作業要求裝入主存時，必須查空閑區表，從中找出一個足夠大的空閑區。若找到的空閑區大于作業需要量，這是應把它分成二部分，一部分為占用區，加一部分又成為一個空閑區。

4.當一個作業撤離時，歸還的區域如果與其他空閑區相鄰，則應合并成一個較大的空閑區，登在空閑區表中。

5.運行所設計的程序，輸出有關數據結構表項的變化和內存的當前狀態。◆實驗要求：

1． 詳細描述實驗設計思想、程序結構及各模塊設計思路； 2． 詳細描述程序所用數據結構及算法； 3． 明確給出測試用例和實驗結果；

4． 為增加程序可讀性，在程序中進行適當注釋說明；

5． 認真進行實驗總結，包括：設計中遇到的問題、解決方法與收獲等； 6． 實驗報告撰寫要求結構清晰、描述準確邏輯性強；

實驗過程中，同學之間可以進行討論互相提高，但絕對禁止抄襲。◆實驗過程記錄（源程序、測試用例、測試結果及心得體會等

實驗代碼如下：

#include

int work[10][2];

//作業名字 大小

int idle[10][2];

//空閑區大小 地址

int free[10][3];

//已分配區域的名字 地址 大小

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++){ //初始化數組

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(){ //求空閑單元數

for(int i=0;i <9;i++)

if(idle[i][1]!=0)

num++;}

void jishu1(){ //求作業數

for(int i=0;i <9;i++)

if(work[i][1]!=0)

b++;

}

void zuixian(){ //最先適應法

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(){ //最佳適應法

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(){ //最壞適應法

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){ //回收進程函數

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 <<“要回收的作業不存在！” <

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<<“該進程已被成功回收！”<

} }

void fp(){

int tag=0;//判斷空閑區與請求區大小

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 <<“作業過大沒有足夠存儲空間！” <

void print(){

num=0;

b=1;

jishu();

jishu1();

cout <<“已分配表為:” <

for(int i=0;i <=b;i++)

if(free[i][2]!=0)

cout <<“作業名:” <

cout <

cout <<“空閑區表為:” <

for(int j=0;j

if(idle[j][1]!=0)

cout <<“起始地址:” <

cout <

void main(){ //主函數運行上面定義的函數

init();

int n;

cout <<“1.分配空間；2.回收空間；” <

cin>>ch1;

cout <

cout <<“1.最先適應法；2.最佳適應法；3.最壞適應法；” <

cin>>ch2;

cout <

cout <<“請輸入要分配內存的作業名及占用內存大小:”;

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 <<“輸入要回收的作業名：” <

cin>>n;

huishou(n);

} 實驗截圖：

成功回收時：

回收失敗時：

實驗體會：

本次實驗的難度較大，尤其是回收進程，主要編寫幾個算法和回收程序，最佳，最優，最壞算法和回收算法，我用的是數組，有工作數組，空閑數組，已分配數組。最后再編寫算法，但是回收算法現在還是有些不清晰，需要進一步研究！

第二篇：操作系統實驗四主存空間的分配與回收首次適應算法和循環首次適應算法

實驗報告

【實驗名稱】

首次適應算法和循環首次適應算法

【實驗目的】

理解在連續分區動態的存儲管理方式下，如何實現主存空間的分配與回收。

【實驗原理】

首次適應（first

fit，FF）算法

FF算法要求空閑分區鏈以地址遞增的次序鏈接。在分配內存時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閑分區即可。然后再按照作業的大小，從該分區中劃出一塊內存空間，分配給請求者，余下的空閑分區仍留在空閑鏈中。若從鏈首直至鏈尾都不能找到一個能滿足要求的分區，則表明系統中已經沒有足夠大的內存分配給該進程，內存分配失敗，返回。

循環首次適應（next

fit，NF）算法

為避免低址部分留下許多很小的空閑分區，以及減少查找可用空閑分區的開銷，循環首次適應算法在為進程分配內存空間時，不再是每次都從鏈首開始查找，而是從上次找到的空閑分區的下一個空閑分區開始查找，直至找到一個能滿足要求的空閑分區，從中劃出一塊玉請求大小相等的內存空間分配給作業。

【實驗內容】

實現主存空間的分配與回收：

1.采用可變式分區管理，使用首次適應算法實現主存空間的分配與回收；

2.采用可變式分區管理，使用循環首次適應算法實現主存空間的分配與回收。

數據結構和符號說明：

typedef

struct

PCB//進程控制塊

{

char

ProgressName[10];

//進程名稱

int

Startaddress;

//進程開始地址

int

ProgressSize;

//進程大小

int

ProgressState

=

0;

//進程狀態

};

typedef

struct

FREE

//空閑區結構體

{

int

Free_num;

//空閑區名稱

int

Startaddress;

//空閑區開始地址

int

Endaddress;

//空閑區結束地址

int

Free_Space;

//空閑區大小

};

算法流程圖：

首次適應算法

循環首次適應算法

程序代碼及截圖：

#include

#include

#include

#include

#define

N

1024

typedef

struct

PCB//進程控制塊

{

char

ProgressName[10];

//進程名稱

int

Startaddress;

//進程開始地址

int

ProgressSize;

//進程大小

int

ProgressState

=

0;

//進程狀態

};

typedef

struct

FREE

//空閑區結構體

{

int

Free_num;

//空閑區名稱

int

Startaddress;

//空閑區開始地址

int

Endaddress;

//空閑區結束地址

int

Free_Space;

//空閑區大小

};

int

count

=

0;

//當前內存中進程個數

bool

ROM[N];//設置內存塊

int

p

=

0;//循環首次使用需要標記當前的空閑區塊

FREE

FREE[100];//設置空閑區數組為100個

int

FREE_counter

=

0;//空閑區的個數

PCB

num[20];

//作業隊列

void

init()//初始化操作

{

for(int

i=0;

i

i++)

ROM[i]

=

0;

}

void

showProgress(PCB

&a)

{

printf(“----------------------------------------------------------------------＼n“);

printf(“進程名＼t＼t開始地址＼t＼t大小＼t＼t結束地址＼n“);//輸出內存信息

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()//打印空閑區的情況

{

printf(“----------------------------------------------------------------------＼n“);

printf(“

空閑區名＼t|

開始地址＼t|

大小

＼t|

結束地址＼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()

//尋找空閑區

{

int

i,j,p;

//計數值

FREE_counter

=

0;//預設空閑區數為0

for(i

=

0;

i

N;

i++)

if(ROM[i]

==

0)

{

p

=

i;

for(j

=

i;

j

N;

j++)

{

if(ROM[j]==0)//未找到空閑區，則將j賦值給i后繼續循環

{

i

=

j;

continue;

}

if(ROM[j]==1)//找到空閑區

{

FREE_counter++;//空閑區個數+1；

FREE[FREE_counter].Free_num

=

FREE_counter;//設置空閑區編號

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)//對最后一個內存進行特殊操作

{

FREE_counter++;

FREE[

FREE_counter].Free_num

=

FREE_counter;//對空閑區進行處理

FREE[

FREE_counter].Startaddress

=

p;

FREE[

FREE_counter].Endaddress

=j-1;

FREE[

FREE_counter].Free_Space

=

j-p;

}

}

}

void

First_Fit(PCB

&a)//首次適應算法

{

int

i,j,k;

for(i=0;

i

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)

{

a.Startaddress

=

i;//設置作業的開始地址

a.ProgressState

=

1;//標記作業在內存中

for(k=i;

k

k++)

ROM[k]=1;

printf(“進程%s插入成功，進程%s的初始地址為%d,結束地址為%d＼n“,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);

return;

}

}

if(i==N)//未查詢到合適的區域

printf(“插入失敗，無可用空間！＼n“);

}

void

Next_Fit(PCB

&a)//循環首次適應算法來實現作業調度

{

int

i,j,k;

for(i=p;

i

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)//找到合適的空閑區

{

a.Startaddress=i;

a.ProgressState=1;

for(k=i;

k

k++)

ROM[k]=1;

printf(“插入成功，進程%s的初始地址為%d,結束地址為%d＼n“,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);

p=i+a.ProgressSize;

return;

}

}

}

for(i=0;

i

i++)//當未找到時，從第一個空閑區開始查詢，結束條件為小于所標記的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)//成功找到結束，并標記當前P為現在的作業的尾部

{

a.Startaddress=i;

a.ProgressState=1;

for(k=i;

kk++)

ROM[k]=1;

printf(“插入成功，進程%s的初始地址為%d＼n“,a.ProgressName,a.Startaddress);

p=i+a.ProgressSize;

break;

}

}

if(i==p)//查詢兩部分都未找到合適的區域，輸出插入失敗語句

printf(“插入失敗，無可用空間＼n“);

}

void

Delete(PCB

&a)//刪除作業，修改內存信息和初始化該作業信息

{

int

i;

for(i=a.Startaddress;

i

i++)

ROM[i]=0;

a.ProgressState=0;//狀態標記為未使用

printf(“進程%s刪除成功＼n“,a.ProgressName);

}

int

main()

{

int

choose1,choose;

char

ProgressName[10];

PCB

a;

init();

printf(“＼t主存空間的分配與回收＼n“);

printf(“---------------------------------------＼n“);

printf(“＼t1、首次適應算法＼n“);

printf(“＼t2、循環首次適應算法＼n“);

printf(“---------------------------------------＼n“);

printf(“請選擇分配算法：“);

scanf(“%d“,&choose1);

system(“cls“);

while(1)

{

w:system(“cls“);

printf(“當前分配算法：“);

if(choose1

==

1)

printf(“首次適應算法＼n“);

else

printf(“循環首次適應算法＼n“);

printf(“---------------------------------------＼n“);

printf(“＼t1、插入進程＼n“);

printf(“＼t2、刪除進程＼n“);

printf(“＼t3、顯示進程的信息＼n“);

printf(“＼t4、顯示空閑區＼n“);

printf(“---------------------------------------＼n“);

printf(“請輸入：“);

scanf(“%d“,&choose);

system(“cls“);

switch(choose)

{

case

1:

printf(“請輸入進程名:“);

scanf(“%s“,&a.ProgressName);

printf(“請輸入進程的大小：“);

scanf(“%d“,&a.ProgressSize);

for(int

i

=

0;

i

count;

i++)

if(strcmp(num[i].ProgressName,a.ProgressName)==0)

{

printf(“已存在同名進程，無法插入。＼n“);

system(“pause“);

goto

w;

}

if(choose1==1)//首次適應算法

First_Fit(a);

else

Next_Fit(a);//循環首次適應算法

num[count++]=a;

break;

case

2:

if(count

==

0)

{

printf(“當前沒有進程在內存中，無法刪除！＼n“);

system(“pause“);

goto

w;

}

printf(“輸入刪除的進程名字：“);

scanf(“%s“,&ProgressName);

for(int

i=0;

i

i++)

if(!strcmp(num[i].ProgressName,ProgressName))

Delete(num[i]);

else

printf(“沒有找到對應進程，請重新輸入。＼n“);

break;

case

3:

showProgress(a);

break;

case

4:

find_FREE();

showFree();

break;

default:

printf(“＼n無效的輸入。＼n“);

}

system(“pause“);

}

return

0;

}

主界面：

首次適應算法，初始空閑區：

插入進程：

插入3個進程：

空閑區信息：

刪除進程2：

刪除后空閑區狀況：

再插入一個進程，可以看到其其初始地址為100：

循環首次適應算法,插入3個進程

刪除進程2后：

再插入進程A，發現其從上次找到的空閑分區的下一個空閑分區開始查找，其初始地址為750而不是200：