陈蕾蕾文档格式.docx
《陈蕾蕾文档格式.docx》由会员分享,可在线阅读,更多相关《陈蕾蕾文档格式.docx(27页珍藏版)》请在冰点文库上搜索。
;
2)分区结构:
typedefstructDuLNode
intID;
//分区号
intstart;
//开始地址
intsize;
//大小
intstate;
//0=尚未使用1=使用2=释放
structDuLNode*prior;
//前驱指针
structDuLNode*next;
//后即指针
}DuLNode,*DuLinkList;
2、基本操作:
intFirstfit(int);
//首次适应算法
intNext_fit(int);
//循环首次适应算法
voidshowJob(int);
//显示作业表
voidshowPartiton(DuLinkList);
//显示分区表
DuLinkListInitpartitionList(DuLinkList&
p);
//初始化
voidhuishou(DuLinkListpl3,DuLinkList&
pl);
//回收函数
intPutin(int&
n);
//输入函数,输入作业相关信息
3、首次适应算法
空闲分区链以地址递增的次序链接,分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;
然后再按照作业的大小,从该分区中划出一块内存空间分配给请求者,取消的空闲分区仍留在空闲链中。
若从链首直至链尾都不能找到一个能满足要求的分区,则此次内存分配失败,返回。
4、循环首次适应算法
在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业。
三、主要功能模块流程图
主函数:
2
1
3
首次适应算法:
循环首次适应算法
四、系统测试
程序运行实例如下:
1、输入界面,按要求输入:
2、选择算法及分区首地址:
3、运行结束后显示,并继续选择:
4、退出:
五、结论
作业采用数组形式进行存储,起初想用数组模拟分区,但划分记录比较不易,时间空间复杂度较大,容易混乱,遂决定用链表形式模拟分区情况。
基本能运行符合要求,能模拟出动态分区过程及最终结果。
六、源程序及系统文件使用说明
#include<
stdio.h>
stdlib.h>
iostream.h>
windows.h>
#defineFree0
#defineUse1
#defineMAX_length100//最大内存空间为100MB
//--------------作业结构体数组----------------------------
typedefstructJOB
intnum;
intctime;
intrtime;
}Job;
//-------------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//---------------------------全局变量-------------------------------------------
intf;
Job*A;
//排序前
Job*a;
//排序后
Job*temp;
//-----------------------------功能函数-------------------------------------------
voiddelay()
for(intx=10000;
x>
0;
x--)
for(inty=1000;
y>
y--);
}
//--------------------------------------------------------------------------------
//------------------------初始化---------------------------------------------------
p)
p=(DuLinkList)malloc(sizeof(DuLNode));
//申请空间
if(!
exit(0);
p->
size=100;
//初始化大小
printf("
输入分区首地址:
"
);
scanf("
%d"
&
p->
start);
state=0;
//状态置空闲
ID=0;
next=NULL;
prior=NULL;
returnp;
//------------------------------------------------------------------------------
//-----------------------------输入函数---------------------------------------------
n)
inti;
Jobtemp;
请输入任务数目:
a=(Job*)malloc(n*sizeof(Job));
A=(Job*)malloc(n*sizeof(Job));
for(i=0;
i<
n;
i++)
{
printf("
\n"
信息输入:
\n\n"
作业号:
scanf("
a[i].num);
作业大小:
a[i].size);
作业进入时间:
a[i].ctime);
作业运行时间:
a[i].rtime);
a[i].state=0;
//默认状态为Free
A[i]=a[i];
}
for(intj=0;
j<
n;
j++)
for(i=j;
i++)
if(a[j].ctime>
a[i].ctime)
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}
//冒泡排序
freopen("
data.txt"
"
w"
stdout);
for(i=0;
i<
%d%d%d%d\n"
a[i].num,a[i].size,a[i].ctime,a[i].rtime);
fclose(stdout);
CON"
保存成功\n\n"
return1;
//----------------------------------------------------------------------------------------
//-----------------------------读文件-----------------------------------------------------
intorder(int&
Inputthenumberofthetask:
r"
stdin);
for(inti=0;
fclose(stdin);
//------------------------------------------------------------------------
//-------------------------显示分区-------------------------------
voidshowPartition(DuLinkListpl)
\n\t\t\t分区表\n"
\t---------------------------------------\n"
\t开始地址\t分区号\t大小状态\n"
while(pl)
\t%d\t\t%d\t%d\t"
pl->
start,pl->
ID,pl->
size);
if(pl->
state==0)
printf("
空闲\n"
state==1)
已分配\n"
pl=pl->
next;
//-------------------------------------------------------------------------
//---------------------------------回收函数---------------------------------
pl)
while(pl3)
if(pl3->
state==0)
{
if(pl3->
next&
&
pl3->
prior&
prior->
state==0&
next->
state==1)
{
pl3->
size+=pl3->
size;
pl3->
start=pl3->
start;
if(pl3->
prior)
{
next=pl3;
prior=pl3->
prior;
}
else
pl=pl3;
pl3=pl;
}
elseif(pl3->
next)
pl3->
prior=pl3;
next=pl3->
pl3->
elseif(!
start=pl->
{
}
else
{pl3->
pl=pl3;
pl3=pl;
size=pl3->
size+pl3->
pl3=pl3->
//--------------------------------------------------------------------------------------
//----------------------------------首次适应算法---------------------------------------
voidFirstfit(DuLinkListblock_first,intn)
intt=1;
intnum=n;
while(t&
num)
DuLinkListpl1=block_first,pl2,pl3=block_first;
时钟:
%d\n"
t);
DuLNode*p=block_first;
DuLNode*q=block_first;
for(intm=0;
m<
m++)
if(t==a[m].ctime+a[m].rtime)
num-=1;
a[m].state=2;
while(q)
if(q->
ID==a[m].num)
q->
state=Free;
q=q->
showJob(n);
showPartition(block_first);
for(m=0;
if(a[m].ctime==t)
{
a[m].state=1;
printf("
作业:
%d开始运行,对其分配!
a[m].num);
if(t==a[m].ctime)
while(pl1&
(pl1->
state==1||pl1->
size<
a[m].size))pl1=pl1->
if(pl1)
pl2=(DuLinkList)malloc(sizeof(DuLNode));
pl2->
start=pl1->
start+a[m].size;
size=pl1->
size-a[m].size;
if(pl2->
size>
5)
pl1->
size=a[m].size;
state=1;
ID=a[m].num;
if(pl1->
prior=pl2;
pl2->
next=pl1->
prior=pl1;
next=pl2;
pl1=block_first;
showJob(n);
showPartition(block_first);
cout<
<
内存不足,等待释放"
endl;
for(inti=m;
a[i].ctime+=1;
p=block_first;
huishou(p,block_first);
t+=1;
//---------------------------------------------------------------
//---------------------------显示作业----------------------------
voidshowJob(intn)
\n\t\t\t作业表:
\t--------------------------------------------------------------\n"
\t作业号\t大小\t进入时间\t运行时间\t状态\n"
for(intm=0;
\t%d\t%d\t%d\t%d\t"
a[m].num,a[m].size,a[m].ctime,a[m].rtime);
if(a[m].state==0)
等待\n"
if(a[m].state==1)
装入\n"
if(a[m]