齐齐哈尔大学
操作系统课程综合实践
题目：存储管理
---
动态分区
分配算法的模拟
班级：计本
062
姓名：wolfboy
学号：1111111111
指导教师：TEACHER
2008 年 12 月
班级 姓名 指导教师
题目：存储管理---动态分区分配算法的模拟
评分标准
评分标准 分数权重
评分的依据
得分
A C
选题
10
选题符合大纲要求，
题目较新颖，工作量
大
选题基本符合大纲要
求，工作量适中
工作态度
10
态度端正，能主动认
真完成各个环节的工
作，不迟到早退，出
勤好。
能够完成各环节基本
工作，出勤较好。
存储结构、
算法描述
20
能 正 确 选 择 存 储 结
构，定义准确，算法
流程图或类 C 语言描
述的算法准确无误
能 正 确 选 择 存 储 结
构，算法流程图或类
C 语言描述的算法基
本准确
独立解决问
题的能力
10
具有独立分析、解决
问题能力，有一定的
创造性，能够独立完
成软件的设计与调试
工 作 ， 程 序 结 构 清
晰，逻辑严谨，功能
完善。
有一定的分析、解决
问题能力。能够在老
师指导下完成软件的
设计与调试工作，程
序功能较完善。
答辨问题回
答
20
能准确回答老师提出
的问题
能基本准确回答老师
提出的问题
程序运行情
况
10
程序运行正确、界面
清晰，测试数据设计
合理。
程序运行正确、界面
较清晰，能给出合适
的测试数据。
综合实践报
告
20
格 式 规 范 ， 层 次 清
晰，设计思想明确，
解决问题方法合理，
体会深刻。
格式较规范，设计思
想基本明确，解决问
题方法较合理。
总分
指导教师（签字）：
1
存储管理
---动态分区分配算法的模拟
摘要:分区分配算法就是系统在寻找空闲的分区分配给某一用户作业,具体可采用首次适应
算法,循环首次适应算法和最佳适应算法。下面将针对每个算法的数据结构及算法实现进行
分析，在分析算法前，先对此次课题进行了分析，再对一些基础相关知识进行了整理。
关键字:分区分配算法；首次适应；循环首次适应；最佳适应
概 述
动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现
可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区
的分配和回收操作这样三个问题。
1、设计目的及开发环境
(1)设计目的
分区管理是满足多道程序运行的最简单的存储管理方式，为了实现对内存
空间的有效管理，需要采取一些方法和策略，用以实现对内存空间的分配或回
收。
(2)开发环境
操作系统：windows xp
开发环境：Dev-C++ 5
2 数据结构设计
(1) 空闲区说明表结构：把空闲区定义为结构体变量，包括空闲区始址，空
闲区大小和空闲区状态，用 0 表示空表目，1 为可用空闲块。
struct freearea
{
int startaddress;/*空闲区始址*/
int size;/*空闲区大小*/
int state;/*空闲区状态:0 为空表目，1 为可用空闲块*/
}freeblock[N]={{20,20,1},{80,50,1},{150,30,1},{300,30,0},{600,10,1}};
2
(2) 为作业分配主存空间的函数 alloc()，三个算法分别对应三个分配主存空间
的算法。applyarea 为作业申请量，tag 为检查是否有满足作业需要的空闲区
的标志。
首次适应算法:
检查空闲区说明表是否有满足作业要求的空闲区时,如果大于作业要求,则分配给
作业,修改地址和空闲区大小,并将 tag 置“1”,表示有满足作业要求的空闲区,返
回为作业分配主存的地址.程序如下所示：
if(freeblock[i].state==1&&freeblock[i].size>applyarea)
{
freeblock[i].startaddress=freeblock[i].startaddress+applyare
a;
freeblock[i].size=freeblock[i].size-applyarea;
tag=1;
return freeblock[i].startaddress-applyarea;
}
如果空闲区等于作业要求，则分配给作业,修改地址和空闲区大小,并将 tag 置
“1”,表示有满足作业要求的空闲区,返回为作业分配主存的地址.
if(freeblock[i].state==1&&freeblock[i].size==applyarea)
{
freeblock[i].state=0;
tag=1;
return freeblock[i].startaddress;
}
如果没有满足条件的空闲区，分配不成功，返回-1
if(tag==0)return -1;
循环首次适应算法的 alloc()函数与首次适应算法的 alloc()函数区别在于从哪
里开始找是否有满足作业要求的空闲区，它是从上次找到的空闲区的下一个空
闲分区开始找，只需要改变 for 循环的条件即可。
for(i=s;i<N;i++)
最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。检查
空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，
小于。若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否
有“大于”的情况：
if(freeblock[i].state==1&&freeblock[i].size==applyarea)
{
3
freeblock[i].state=0;
tag=1;
return freeblock[i].startaddress;
}
检查“大于”的情况：先把所有大于所要求的空闲区放入数组,
for(i=0;i<N;i++)
{
if(freeblock[i].state==1&&freeblock[i].size>applyarea)a[j++]=i;
}
再从数组中挑出最小的那个：
如果数组中的元素大于一个，则需要一个个比较过去，然后取出最小的那个分
配给作业：
if(j>1)
{
h=a[0];
min=freeblock[h];
for(k=1;k<j;k++)
{
h=a[k];
if(freeblock[h].size<min.size)
{
mid.size=freeblock[h].size;
mid.state=freeblock[h].state;
mid.startaddress=freeblock[h].startaddress;
freeblock[h].size=min.size;
freeblock[h].state=min.state;
freeblock[h].startaddress=min.startaddress;
min.size=mid.size;
min.state=mid.state;
min.startaddress=mid.startaddress;
}
}
min.startaddress=min.startaddress+applyarea;
min.size=min.size-applyarea;
tag=1;
return min.startaddress-applyarea;
4
评论6