2023年计算机操作系统内存分配实验报告

一、实验目的

熟悉主存的分派与回收。理解在不同的存储管理方式下，如何实现主存空间的分派与回

收。掌握动态分区分派方式中的数据结构和分派算法及动态分区存储管理方式及其实现过

程。

二、实验内容和规定

主存的分派和回收的实现是与主存储器的管理方式有关的。所谓分派,就是解决多道作

业或多进程如何共享主存空间的问题。所谓回收，就是当作业运营完毕时将作业或进程所占

的主存空间归还给系统。

可变分区管理是指在解决作业过程中建立分区，使分区大小正好适合作业的需求，并且

分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空

闲空间,若有,则按需要量分割一个分区分派给该作业；若无,则作业不能装入，作业等待。

随着作业的装入、完毕，主存空间被提成许多大大小小的分区，有的分区被作业占用，而有的

分区是空闲的。

实验规定使用可变分区存储管理方式，分区分派中所用的数据结构采用空闲分区表和空

闲分区链来进行，分区分派中所用的算法采用初次适应算法、最佳适应算法、最差适应算法

三种算法来实现主存的分派与回收。同时、规定设计一个实用和谐的用户界面，并显示分派

与回收的过程。同时规定设计一个实用和谐的用户界面,并显示分派与回收的过程。

三、实验重要仪器设备和材料

实验环境

硬件环境：PC或兼容机

软件环境:VC++6.0

四、实验原理及设计分析

某系统采用可变分区存储管理,在系统运营当然开始，假设初始状态下，可用的内存空间

为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。

(作业1申请130KB、作业2申请60KB、作业3申请100KB、作业2释放

60KB、

作业4申请200KB、作业3释放100KB、作业1释放130KB、作业5申请1

40KB、

作业6申请60KB、作业7申请50KB)

当作业1进入内存后，分给作业1(130KB),随着作业1、2、3的进入，分别分派60K

B、100KB,通过一段时间的运营后，作业2运营完毕，释放所占内存。此时，作业4进入

系统，规定分派200KB内存。作业3、1运营完毕，释放所占内存。此时又有作业5申请

140KB,作业6申请60KB,作业7申请50KB。为它们进行主存分派和回收。

1、采用可变分区存储管理，使用空闲分区链实现主存分派和回收。

空闲分区链:使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分派和链接,

在每个分区的起始部分设立状态位、分区的大小和链接各个分区的前向指针，由状态位指示

该分区是否分派出去了；同时,在分区尾部还设立有一后向指针，用来链接后面的分区；分区

中间部分是用来存放作业的空闲内存空间，当该分区分派出去后，状态位就由“0”置为“1”。

设立一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分派时.，

系统优先使用空闲低端的空间。

设计一个空闲分区说明链,设计一个某时刻主存空间占用情况表，作为主存当前使用基

础。初始化空间区和已分派区说明链的值，设计作业申请队列以及作业完毕后释放顺序，实

现主存的分派和回收。规定每次分派和回收后显示出空闲内存分区链的情况。把空闲区说明

徒的变化情况以及各作业的申请、释放情况显示打印出来。

2.采用可变分区存储管理,分别采用初次适应算法、最佳适应算法和最坏适应算法实现

主存分派和回收。

3、主存空间分派

(1)初次适应算法

在该算法中，把主存中所有空闲区按其起始地址递增的顺序排列。在为作业分派存

储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满

足规定的空闲区，从中划出与请求的大小相等的存储空间分派给作业，余下的空闲区仍

留在空闲区链中。

(2)最佳适应算法

在该算法中，把主存中所有空闲区按其起始地址递增的顺序排列。在为作业分派存

储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足规

定的空闲区且该空闲区的大小比其他满足规定的空闲区都小，从中划出与请求的大小

相等的存储空间分派给作业，余下的空闲区仍留在空闲区链中

(3)最坏适应算法

在该算法中，把主存中所有空闲区按其起始地址递增的顺序排列。在为作业分派存

储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足

规定的空闲区且该空闲区的大小比其他满足规定的空闲区都大，从中划出与请求的大

小相等的存储空间分派给作业,余下的空闲区仍留在空闲区链中。

4、主存空间回收

当一个作业执行完毕撤离时，作业所占的分区应当归还给系统。归还的分区假如与其

它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的

合并问题，规定考虑四种情况：

(1)释放区下邻空闲区(低地址邻接)

(2)释放区上邻空闲区(高地址邻接)

(3)释放区上下都与空闲区邻接

(4)释放区上下邻都与空闲区不邻接

五、程序流程图

main函数里的流程图

二生封骨"、汪C

分派空间里的流程图

回收空间里的流程图

向的空间雨粕

六、相关数据结构及关键函数说明

本程序采用了一个structfree_table数据结构，里面包含分区序号（num）、起始地

址（address）、分区长度（length）和分区状态（state）。还用了线性表的双性链表存储结

构(structNode)理面包含前区指针(prior)和后继指针(next)。一开始定义一条(具有

first和end)的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分派和回

收。

在该程序中关键函数有,sort()、al1ocation(),recovery()、和First_fit()、Be

st_fit()、Worst_fit();其中sort()函数是用来整理分区序号的，如在删序号3时，她与

前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分

派，然后序号在2的基础上加1,一直加，加到与原本序号3的下一个序号也就是4相等，这时

sort()就开始有明显的工作了;al1ocation()是分派空间的，也是过渡到三个算法

中的，当三个算法中满足或者不满足分派请求，都会又返回值给allocation();recovery()

是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与

空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。

七、源代码

#inc1ude<stdio.h>

#include<stdlib.h>

#defineOK1〃完毕

#defineERROR0〃犯错

typedefintStatus；

typedefstructfree_table//定义一个空闲区说明表结构

(

intnum;//分区序号

longaddress;//起始地址

1ong1ength;〃分区大小

intstate;〃分区状态

}E1emType;

typedefstruetNode//线性表的双向链表存储结构

E1emTypedata;

structNode*prior;//前趋指针

structNode*next;〃后继指针

}Node,*LinkList;

LinkListfirst;//头结点

LinkListend;〃尾结点

intflag，记录要删除的分区序号

StatusInitb1ock()〃开创带头结点的内存空间链表

(

first=(LinkList)malloc(sizeof(Node));

end=(LinkList)malloc(sizeof(Node));

first->prior=NULL;

first->next=end;

end->prior=first;

end->next=NULL;

end->data.num=1;

end—>data.address=40;

end->data.length=600;

end—>data.state=0;

returnOK;

voidsort()//分区序号重新排序

Node*p=first->next,*q；

q=p->next;

for(;p!=NULL；p=p->next)

(

°for(q=p->next;q；q=q->next)

°(

®if(p->data.num>=q->data.num)

(

q->data.num+=1?

)

}0

}

}

//显示主存分派情况

voidshow()

(intflag=0；//用来记录分区序号

Node*p=first;

p->data.num=O;

p->data.address=0;

p—>data.1ength=40;

p->data.state=l；

sort();

printf(H\n\t\t》主存空间分派情况(\n)；

***************************************************

*******E\nn)•

printf（"分区序号\t起始地址\t分区大小\t分区状态\n\n"）;

while(p)

printf("％d\t\t%d\t\t%d",p->data.nurn,p->data.address,p->data.leng

th);

if(p->data.state==O)printf("\t\t空闲\n\n");

eIseprintf("\t\t己分派\n\n");

p=p->next;

printf(”***********头****************************************

******\n\nn)；

//初次适应算法

StatusFirst_fit(intrequest)

//为申请作业开辟新空间且初始化

Node*p=first->next;

LinkLis11emp=(LinkList)malloc(sizeof(Node));

temp->data.length=request；

temp->data.state=1；

p->data.num=l；

while(p)

if((p—>data.state==0)&&(p->data.length==request))

{//有大小恰好合适的空闲块

p->data.state=l;

returnOK;

break；

)

elseif((p->data.state==0)&&(p->data.length>request))

{//有空闲块能满足需求且有剩余

temp->prior=p->prior;

temp->next=p;

temp->data.address=p->data.address；

temp->data.num=p->data.num;

p—>prior->next=temp;

p->prior=temp;

p—>data.address=temp->data.address+temp—>data.length;

p->data.length-=request;

p->data.num+=1;

returnOK;

break;

)

p=p—>next;

)

returnERROR;

)

〃最佳适应算法

StatusBest_fit(intrequest)

intch;〃记录最小剩余空间

Node*p=first;

Node*q=NULL;//记录最佳插入位置

LinkLis11emp=(LinkList)malloc(sizeof(Node));

temp—>data.length=request;

temp->data.state=l；

®p->data.num=1;

while(p)//初始化最小空间和最佳位置

(

if((p->data.state==0)&&(p->data.length>=request))

(

if(q二二NULL)

(

q=P;

ch=p->data.length-request;

}

elseif(q->data.length>p—>data.1ength)

{

q=p;

ch=p->data.length-request;

)

)

p=p->next;

)

if(q==NULL)returnERROR;〃没有找到空闲块

elseif(q—>data.length二二request)

。q->data.state=l;

returnOK;

)

eIse

(

temp->prior=q->prior;

temp->next=q;

temp->data.address=q->data.address;

temp->data.num=q->data.num;

q—>prior—>next=temp;

q->prior=temp;

q->data.address+=request;

q->data.length=ch;

q->data.num+=l；

returnOK；

)

returnOK;

)

//最差适应算法

StatusWorst_fit(intrequest)

(

intch;//记录最大剩余空间

Node*p=first->next；

Node*q=NULL；//记录最佳插入位置

LinkListtemp=(LinkList)ma1loc(sizeof(Node));

temp—>data.length=request;

temp—>data.state=1;

p>data.num=l;

whi1e(p)〃初始化最大空间和最佳位置

(

if(p->data.state==0&&(p->data.length>=request))

|

if(q==NULL)

(

q=p;

ch=p->data.1ength-request；

)

e1seif(q—>data.1ength<p->data.length)

(

q二p；

ch=p->data.1ength-request；

)

)

p=p—>next;

)

if(q==NULL)returnERROR；//没有找到空闲块

elseif(q->data.1ength==request)

q->data.length=1;

returnOK;

)

e1se

(

temp->prior=q->prior;

temp->next=q;

temp->data,address=q—>data.address；

ternp—>data.num=q->data.num;

q->prior->next=temp;

q->prior=temp;

q->data.address+=request;

q->data.length=ch；

q->data.num+=l；

returnOK;

}

returnOK;

)

〃分派主存

Statusallocation(inta)

(

intrequest；//申请内存大小

printf(H请输入申请分派的主存大小(单位:KB):")；

scanf("％d"，&request)；

if(request<0||request==0)

Printf("分派大小不合适，请重试！”)；

returnERROR;

)

switch(a)

(

easel：〃默认初次适应算法

if(First_fit(request)==OK)printf(n\t****分派成功！*****);

e1seprintf("\t****内存局限性，分派失败！****”)；

returnOK;

break；

case2：//选择最佳适应算法

if(Best_fit(request)==OK)printf("\t****分派成功！***

*”)；

else内存局限性,分派失败!****”)；

returnOK；

break;

case3:〃选择最差适应算法

if(Worst_fit(request)==OK)printf("\t****分派成功！****")；

elseprintfC'\t****内存局限性，分派失败！****”)；

returnOK;

。fibreak;

)

)

Statusdeal1(Node*p)//解决回收空间

Node*q=first;

for(;q!=NULL；q=q->next)

(

if(q==p)

(

if(q->prior->data.state==0&&q->next->data.state!=0)

(

q->prior->data.1ength+=q->data.1ength;

q->prior—>next=q—>next;

q->next—>prior=q->prior;

q=q->prior;

q->data.state=O；

q->data,num=flag-1；。

)

if(q—>prior—>data.state!=0&&q->next->data.state==0)

(

q->data.1ength+=q->next->dala.length;

q->next=q->next->next;

q->next->next->prior=q;

q->data.state=0;

q->data.num=f1ag；

)

if(q->prior->data.state==0&&q->next->data.state==0)

q->prior->data.1ength+=q->data.length;

q->prior->next=q->next;

q->next->prior=q->prior；

q=q->prior;

q->data.state=0；

q->data.num=flag—1；。

)

if(q->prior->data.state!=0&&q->next->data.state!=0)

0{

oq->data.state=0;

。}

)

)

returnOK;

)

Statusdeal2(Node*p)〃解决回收空间

(

Node*q=first;

for(;q!=NULL;q=q->next)

(

6if(q==p)

(

if(q->prior->data.state==0&&q->next->data.state!=0)

°{

q->prior—>data.length+=q->data.length;

q->prior->next=q—>next；

q->next—>prior=q—>prior;

q=p->prior;

q->data.state=0;

q->data.num=flag-1;

。)

if(q->prior->data.state!=0&&q->next—>data.state==0)

(

q->data.state=0;«>

0}

if(q->pnor->data.state==O&&q->next—>data.state==0)

(

oq->prior->data.length+=q->dala.1ength;

q->prior—>next=q->next;

q->next->prior=q—>prior;

q=q->prior;

q—>data,state=0;

q->data.num=flag-1;

)

if(q->prior->data.state!=0&&q->next->data.state!=0)

0{

。oq-Adata.state=0;

°}

)

)

returnOK;

//主存回收

Statusrecovery(intflag)

(

Node*p=first;

for(;p!=NULL;p=p—>next)

(

匕if(p->data.num==f1ag)

{

。if(p->prior==first)

。(

。if(p->next!=end)〃当前P指向的下一个不是最后一个时

。(

oif(p—>next->data.state==0)〃与后面的空闲块相连

6(

p—>data.length+=p->next->data.1ength;

p->next->next->prior=p；

p->next=p->next—>next;

p->data.state=O;

p->data.num=flag;

00}

。elsep->data.state=0;

6)

。。if(p->next=二end)〃当前P指向的下一个是最后一个时

p—>data.state=O；

)〃结束if(p->Prior==block_first)的情况

eIseif(p—>prior!=first)

。{

if(p->next!=end)

{

deal1(p);

6}

。else

{

3deal2(p);

)

。}〃结束if(p->prior!=block_first)的情况

}〃结束if(p—>data.num==flag)的情况

prinlf(”\t****回收成功****0);

returnOK;

〃主函数

voidmain()

inti;//操作选择标记

inta;//算法选择标记

”********************************火********************

*****\n");

Printf("\t't用以下三种方法实现主存空间的分派\n");

printf("\t(1)初次适应算法\t⑵最佳适应算法\t(3)最差适应算法\n")；

printf("**********************************************

************\n")・

printf("\n")；

printf(”请输入所使用的内存分派算法:“)；

seanf(”％dn,&a);

whi1e(a<1||a>3)

(

printf("输入错误，请重新输入所使用的内存分派算法:\n")；

scanf(u%du,&a);

)

switch(a)

ocase1：printf(H\n\t****使用初次适应算法:****\n");break;

case2:printf("\n\t****使用最佳适应算法:****\n");break;

case3：printf(”\n\t****使用最坏适应算法:****\n0);break;

}

Initblock();〃开创空间表

while(l)

(

show();

printf(M\tl:分派内存\t2:回收内存\t0:退出\n")；

printf("请输入您的操作：”)；

seanf("％d”,&i);

if(i==l)

allocation(a);//分派内存

eIseif(i==2)//内存回收

(

printf("请输入您要释放的分区号

scanf("%d",&flag);

recovery(flag)；

)

elseif(i==0)

0{

sprintf("\n退出程序\n")；

break;//退出

0}

else//输入操作有误

(

printf("输入有误，请重试！")；

continue；

八、执行结果和结果分析

XXXXXXXXXXXXXXXXXXXXXXXXX*XXXXXXX射XXXXXXX丈XMXXXXXMXXXXXXM

⑴首次^■史鬻矗应算法

XMXiOCMXXXMXXIOOOOOOOCMXMXXXXXMXMXXMXXMXX

初始化初次适应算法:

请输入所使用的内存分配算法：i

****使用首次适应算法：****

》主存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140600空闲

XXXXXXX-XMXKXXMMXXMXXXXXM~XXX*MXX*X*X*>e*)(*XXX**・

当作业1、2、3顺利分派内存空间后:

小痣!己内存2:回收内存0:退出

料鬻入甯曲舞酉曲拿强大小（单位:KB>n00

****^酉己成功!****

———今再悔笑照^圾”售-

分区序号起始地址分区大小分区状态

0040已分酉己

140130已分酉己

217060已分酉己

3230100已分酉己

4330310空闲

回收序号2里面的内存:

1：分配内存2：回收内存0：退出

圜1本您的建隹山2

请输入遂要释放的卷筌号：2

****回收成功****

之三道主回色酉己慢匹f

分区序号起始地址分区大小分区状态

日040已分配

140130已分配

217060空闲

3230100已分配

4330310空闲

XXXMX.XXXXXMXXX.X.X.XXX.*X.XXXXXMXM-XMXMX.XMXMX.—XXXXMXM-XMX|

分派作业4:

2：回收内存。：退出

蹴盛穿I王至大小（单位:KB〉：200

成功I

》王存空间分配情况《

分区序号起始地址分区大小分区状态

040已分配

140130已分配

217060空闲

3230100已分配

4330200已分配

5530110空闲

XM*X*XMXX*XX-XX*XMXX*XX*XX>fXX*M*XX-XX*XX-X*XXNXM*X*XMXX>fW

回收序号3里面的内存（与上邻序号2相连了）

翻濯”醍,窕己施内存号:23：回收内存0：退出

****回收成功****

》王存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140130已分配

2170160空闲

4330200已分配

5530110空闲

回收序号1里的内存（与下邻序号2相连了）

1：窕己内存2：回收内存0：退出

造鼠灌的凛底2

请输入忽要释放的卷耳号：1

****回收成功****

》王存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140290空闲

4330200已分配

5530110空闲

XXXXXXXXX关射X*XXXXXMXXXXXXXXXWXXXMXXXXXMXXXXXXXX

继续分派（会发现总是按顺序查找满足规定的第一个空闲块,一旦发现就会分派）：

人1：分配内存2：回收内存0：退出

请输入您的弹隹：1

请辎入南请芬里的急大小（单位:KB〉：140

****^配成功！****

话庶:需鬻

分区序号起始地址分区大小分区状态

0040已分配

140140已分配

2180150空闲

4330200已分配

5530110空闲

舞己内存2:回收内存0:退出

请顿入您的操相：1

请输入串请芬酉《的生登大小〈单位：KB>:60

****^酉己成功!****

》主存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140140已分配

218060已分配

324090空闲

4330200已分配

5530110空闲

、一、拂己内存2：回收内存0：退出

料翦入A畲L请，原酉曲会大小（单位;KB＞二50

****^酉己，成功!****

之生至军回色更慢迈s

分区序号起始地址分区大小分区状态

0040已分配

L40140已分配

218060已分配

324050已分配

429040空闲

5330200已分配

6530110空闲

XXXXXXXXXXXXXXXXXX)(X)(XXX*X■♦XXXXXXXXXXXXXXMXXXXX】KXXXXXXXXXX

初始化最佳适应算法:

请输入所使用的内存分配算法：2

****使用最佳适应算法：****

》主存空间分配情况《

XXXXXMXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXZ*XXXMXXXXXXXXXXXX

分区序号起始地址分区大小分区状态

0040已分配

140600空闲

XXXXXMXXXXXXXXXXMXXXXXXXXXXXXXMXXXXXXXXXXXXXXXXXXXXXXXXXXX

、,已内存2：回收内存0：退出

翻入甯请黎配福兴大小（单位:KB）：100

****^配成功！****

》王存空间分配情况《

分区序号起始地址分区大小分区状态

040已分配

140130已分配

217060已分配

3230100已分配

4330310空闲

配内存2：回收内存0：退出

埴鼠谟的辑信/

请输入愚要释成的卷1号：2

****回收成功****

》王存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140130已分配

217060空闲

3230100已分配

4330310空闲

11

幅、1喉：分配内铲存21:回收内存0：退出

****回收成功****

》圭存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140290空闲

4330200已分配

5530110空闲

XXXMXX—XMXXXWX，XMXXXX**X**XX~M・XMXXX”MMX*“*XXXXMXXX，X*X

继续分派（会发现总是查找满足规定的空闲块且其比其他空闲块长度小，一旦发现就会分

派）：

退

存

内

U/0出

富

主

入你

Q的1

E刀

小

舌大

号

主

入芾

的

配

R请

己

吩

~！

E王f

间

分

情

存

况

酉

k己<

工

分区序号起始地址分区大小分区状态

0040已分配

140140已分配

2180150空闲

4330200已分配

5530110空闲

j：施内存2：回收内存0?1

请输人门的榛伯1

请输入国请芬配的主查大小（单位:KB）：60

****^?配成功！****

》王存空间分配情况《

分区序号起始地址分区大小分区状态

0040已分配

140140已分配

2180150空闲

-1330200已分配

1.53060已分配

659050空闲

1：分配内存2：回“呐仔0：4妣

请输入逑僧瓣：1

请输入再请二少配的丰督大小（单位:

KB＞：50

**分配成功！****

》王存空间分配道迟8mmmmmu

*XXXXX'XMMXXXXMMMXMMX

分区序号起始地址分区大小分区状态

0040已分配

140140已分配

2180150空闲

4330200已分配

553060已分配

659050已分配

初始化最坏适应算法:

请输入所使用的内存分配算法：3

*****使用取坏适应舁法：

》王存空间分配情况《

分区序号起始地址分区大小分区状态

40已分配

■1M600空闲

己内存2：回收内存0：退出

:主

小〈单位：KB〉：100

****4r0£