操作系统实验可变分区内存分配首次适应算法模拟之令狐文艳创作.docx
《操作系统实验可变分区内存分配首次适应算法模拟之令狐文艳创作.docx》由会员分享，可在线阅读，更多相关《操作系统实验可变分区内存分配首次适应算法模拟之令狐文艳创作.docx（13页珍藏版）》请在冰点文库上搜索。
操作系统实验可变分区内存分配首次适应算法模拟之令狐文艳创作
题目可变分区内存分配首次适应算法模拟
令狐文艳
姓名：
学号：
专业：
学院：
指导教师：
林夕
二零一八年十一月
一、实验目的
主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
二、实验内容及原理
编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
可变分区方式是按作业需要的主存空间大小来分割分区的。
当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。
随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。
当进程运行完毕释放内存，系统根据回收区的首址，从空闲区链表中找到相应的插入点，此时可能出现以下4种情况之一：
1.回收区与插入点的前一个空闲分区F1相邻接，此时将两个分区合并
2.回收区与插入点的后一个空闲分区F2相邻接，此时将两个分区合并
3.回收区与插入点的前，后两个空闲分区相邻接，此时将三个分区合并
4.回收区既不与F1相邻接，又不与F2相邻接，此时应为回收区单独建立一个新表项
三、程序设计
1.算法流程
3.详细设计
（1）定义两个结构体
structkongxian//空闲分区
{
intstart;//起址
intend;//结束
intlength;//长度
}kongxian[N];
structzuoye//作业分区
{
intstart;//起址
intend;//结束
intlength;//长度
}zuoye[N];
（2）init（）//初始化函数kongxian结构体为010231024
print1（）//打印空闲分区
print2（）//打印作业分区
main（）中具体实现算法：
printf（"请输入作业的占用空间的长度"）;
scanf（"%d",&len）;
flag=0;
for（i=0;i{
if（kongxian[i].length>=len）//首次适应算法
{
flag=1;
break;
}
}
if（!
flag）
{
printf（"内存分配失败\n"）;
}
else
{
//将该作业加入作业区里
zuoye[n2].start=kongxian[i].start;
zuoye[n2].end=zuoye[n2].start+len;
zuoye[n2].length=len;
n2++;//作业数加1
if（kongxian[i].length==len）//该分区全部用于分配，删除该空闲分区
{
for（j=i;j{
kongxian[j].start=kongxian[j+1].start;
kongxian[j].end=kongxian[j+1].end;
kongxian[j].length=kongxian[j+1].length;
}
n1--;
}
else//该空闲分区部分用于分配，剩余的留在空闲分区中
{
kongxian[i].start+=len;
kongxian[i].length-=len;
}
}
（3）回收作业：
printf（"输入要回收的作业ID"）;
scanf（"%d",&id）;
front=middle=behind=0;
for（i=0;i{
if（kongxian[i].start>zuoye[id].end）
break;
if（kongxian[i].end==zuoye[id].start）//待回收的作业上面有空闲分区
{
front=1;
t1=i;
}
if（kongxian[i].start==zuoye[id].end）//待回收的作业下面有空闲分区
{
behind=1;
t2=i;
}
四、实验结果
五、实验小结
在设计的过程中，有很多问题不是很清楚，所以做起来就就很困难，刚开始的时候都有点无从下手的感觉。
很多时候在遇到问题时，基本知识都了解，但是就不知道怎么才能把它们都整合到一块，也就是说知识都是很零散的，没有一个完整的系统。
而且，又由于基础知识不牢固，使得我在这次的课程设计中感到更加力不从心。
在设计的过程中，每走一步就会发现，思路想出来很容易，但涉及到实现的时候，总是有点手无足措。
对于本次的课程设计，里面还有很多需要改进的地方。
一个程序的顺利出炉，少不了反复地调试和修改。
在调试的过程中，总是会发生很多错误，但在解决这些错误的时候，开始很模糊的概念就会变得越来越清晰。
其实很多错误都是很类似的，只要解决了一个，其余的就会迎刃而解了。
#include
#include
#include
#include
#defineN10000
intn1;//空闲分区的个数
intn2;//作业区的个数
structkongxian
{
intstart;//起址
intend;//结束
intlength;//长度
}kongxian[N];
structzuoye
{
intstart;//起址
intend;//结束
intlength;//长度
}zuoye[N];
intcmp1（constvoid*a,constvoid*b）
{
return（*（structkongxian*）a）.start-（*（structkongxian*）b）.start;
}
intcmp2（constvoid*a,constvoid*b）
{
return（*（structzuoye*）a）.start-（*（structzuoye*）b）.start;
}
voidinit（）
{
n1=1;//初始时只有一个空闲区
n2=0;//初始没有作业
kongxian[0].start=0;
kongxian[0].end=1023;
kongxian[0].length=1024;
}
voidprint1（）//打印空闲分区
{
inti;
for（i=0;iprintf（"空闲分区ID:
%d起止:
%d结束:
%d长度:
%d\n",i,kongxian[i].start,kongxian[i].end,kongxian[i].length）;
}
voidprint2（）//打印作业分区
{
inti;
for（i=0;iprintf（"作业分区ID：
%d起止:
%d结束:
%d长度:
%d\n",i,zuoye[i].start,zuoye[i].end,zuoye[i].length）;
}
intmain（）
{
inti,j,k,t,len,flag,id;
intfront,middle,behind;
intt1,t2;
init（）;
print1（）;
printf（"输入1装入新作业，输入0回收作业，输入-1结束\n"）;
while（scanf（"%d",&t）!
=EOF）
{
if（t==1）//装入新作业
{
printf（"请输入作业的占用空间的长度"）;
scanf（"%d",&len）;
flag=0;
for（i=0;i{
if（kongxian[i].length>=len）//首次适应算法
{
flag=1;
break;
}
}
if（!
flag）
{
printf（"内存分配失败\n"）;
}
else
{
//将该作业加入作业区里
zuoye[n2].start=kongxian[i].start;
zuoye[n2].end=zuoye[n2].start+len;
zuoye[n2].length=len;
n2++;//作业数加1
if（kongxian[i].length==len）//该分区全部用于分配，删除该空闲分区
{
for（j=i;j{
kongxian[j].start=kongxian[j+1].start;
kongxian[j].end=kongxian[j+1].end;
kongxian[j].length=kongxian[j+1].length;
}
n1--;
}
else//该空闲分区部分用于分配，剩余的留在空闲分区中
{
kongxian[i].start+=len;
kongxian[i].length-=len;
}
}
}
elseif（t==0）
{
printf（"输入要回收的作业ID"）;
scanf（"%d",&id）;
front=middle=behind=0;
for（i=0;i{
if（kongxian[i].start>zuoye[id].end）
break;
if（kongxian[i].end==zuoye[id].start）//待回收的作业上面有空闲分区
{
front=1;
t1=i;
}
if（kongxian[i].start==zuoye[id].end）//待回收的作业下面有空闲分区
{
behind=1;
t2=i;
}
}
if（!
front&&!
behind）//待回收的作业上下均没有空闲分区
{
kongxian[n1].start=zuoye[id].start;
kongxian[n1].end=zuoye[id].end;
kongxian[n1].length=zuoye[id].length;
n1++;//空闲分区增加一个
qsort（kongxian,n1,sizeof（structkongxian）,cmp1）;//插入空闲分区后排序
for（j=id;j{
zuoye[j].start=zuoye[j+1].start;
zuoye[j].end=zuoye[j+1].end;
zuoye[j].length=zuoye[j+1].length;
}
n2--;
}
if（front&&behind）//待回收的作业上下均有空闲分区
middle=1;
if（front&&!
middle）//合并待回收的作业和上面的空闲分区
{
kongxian[t1].end+=zuoye[id].length;
kongxian[t1].length+=zuoye[id].length;
for（j=id;j{
zuoye[j].start=zuoye[j+1].start;
zuoye[j].end=zuoye[j+1].end;
zuoye[j].length=zuoye[j+1].length;
}
n2--;
}
if（middle）//合并待回收的作业和上下的空闲分区
{
kongxian[t1].end=kongxian[t2].end;
kongxian[t1].length+=（zuoye[id].length+kongxian[t2].length）;
//删除空闲分区t2
for（j=t2;j{
kongxian[j].start=kongxian[j+1].start;
kongxian[j].end=kongxian[j+1].end;
kongxian[j].length=kongxian[j+1].length;
}
n1--;
for（j=id;j{
zuoye[j].start=zuoye[j+1].start;
zuoye[j].end=zuoye[j+1].end;
zuoye[j].length=zuoye[j+1].length;
}
n2--;
}
if（behind&&!
middle）//合并待回收的作业和下面的分区
{
kongxian[t2].start-=zuoye[id].length;
kongxian[t2].length+=zuoye[id].length;
for（j=id;j{
zuoye[j].start=zuoye[j+1].start;
zuoye[j].end=zuoye[j+1].end;
zuoye[j].length=zuoye[j+1].length;
}
n2--;
}
}
else
{
printf（"操作结束\n"）;
break;
}
print1（）;
print2（）;
}
return0;
}
升级会员 