动态分区分配管理系统.docx
《动态分区分配管理系统.docx》由会员分享，可在线阅读，更多相关《动态分区分配管理系统.docx（35页珍藏版）》请在冰点文库上搜索。
动态分区分配管理系统
动态分区分配管理系统
学院
专业
学号
学生姓名
指导教师姓名
2014年3月14日
目录
1程序设计的内容和相关的要求---------------------------------2
2程序总的功能说明--------------------------------------------3
3程序的模块的说明--------------------------------------------4
4程序设计的流程图--------------------------------------------5
5程序的操作说明及运行结果-----------------------------------7
6源程序-------------------------------------------------------11
7心得体会----------------------------------------------------27
1程序设计的内容和相关的要求：
课程设计的目的：
操作系统课程设计是计算机学院重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。
●进一步巩固和复习操作系统的基础知识。
●培养学生结构化程序、模块化程序设计的方法和能力。
●提高学生调试程序的技巧和软件设计的能力。
●提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。
实现的任务：
编写一个动态分区分配程序。
设计内容：
用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法
1.首次适应算法
2.循环首次适应算法
设计要求：
1.内存中有0-100M的空间为用户程序空间，最开始用户空间是空闲的；
2.作业数量、作业大小、进入内存空间、运行时间需要通过界面进行输入；
3.可读取样例数据（要求存放在外部文件夹中）进行作业数量、作业大小、进图内存时间、运行时间的初始化；
4.根据作业进图内存的时间，采用简单的先进先出原则进行从外村到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。
（为了简化，不考虑cpu的调度与切换，运行时间为作业在内存中驻留的时间）；
5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作，所有过程均有动态图形变化的显示；
6.采用可视化界面，可随时暂停显示当前内存分配和使用情况图。
2程序总的功能说明：
本程序可以从界面直接输入作业并进行动态的内存分配，也可以自动地生成作业文件并自行调度进行内存分配，每次分配可以选择两种算法（首次适应算法和循环首次算法）中的一种，每次作业结束后可以进入操作主界面进行再次作业的操作。
首次适应算法（First-fit）：
当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。
只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。
循环首次首次适应算法（Next-first）：
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划一块与要求大小相等的内存空间分配给作业。
内存回收：
将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。
并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。
3程各模块的功能说明：
（1）界面显示函数：
showInterface（PLp,Jobjob）；显示操作界面
showJob（Jobjob）；显示作业链表；
showPartitiion（PLpl）显示分区链表
（2）执行练习的功能函数：
copyJob（Jobp）；作业链表复制函数函数
InitpartitionList（PL&p）；链表初始化分区函数函数
CreateJoblist（Job&job,intcount）；创建作业链表函数
InsertNode（Jobp,Job&job）；按时间顺序创建链表函数
InitpartitionList（PL&p）；初始化分区链表函数
（3）文件函数
openFile（）；打开文件函数
ReadFile（）；读取文件函数
RandomParameter（）；随即参数读入文件函数
main（）///主函数
4程序设计的流程图：
总体设计流程图：
首次适应算法：
回收函数：
五程序操作说明书及结果：
在vc++6.0环境中运行本程序，先进行编译，然后再进行链接，在进行执行将会出现显示界面。
按照显示界面上显示的提示进行操作，就可以实现相应的功能：
六源程序：
#include
#include
#include
#include
#include
#defineMemorySize100//为空闲分区分配的最大空间（按题目要求）
intworkload;//输入作业的数量；
typedefstructjobList
{
intid;//作业的name
intsize;//作业大小（需要的存储空间大小）
intintime;//进入时间
intruntime;//运行时间
intstate;//作业的状态（0表示等待，1表示执行，2表示结束并释放）
structjobList*next;//作业链表指针
}*Job;
typedefstructpartitionList
{
intid;
intstartAddress;//分区起始地址
intsize;//分区大小
intstate;//分区的状态
structpartitionList*prior;
structpartitionList*next;//分区链表指针
}*PL;
FILE*fp;
/************************打开文件***************************/
voidopenFile（）
{
if（（fp=（fopen（"D:
\\作业文件.txt","w"）））==NULL）
{
printf（"无法打开文件!
\n"）;
exit（0）;
}
}
/************************读取文件****************************/
voidReadFile（）
{
if（（fp=（fopen（"D:
\\作业文件.txt","r"）））==NULL）
{
printf（"无法打开文件!
\n"）;
exit（0）;
}
}
/************将随机产生进程的参数写入文件********************/
voidRandomParameter（）
{
openFile（）;
for（inti=0;i{
fprintf（fp,"%d%d%d%d%d\n",i+1,rand（）%80,rand（）%20,rand（）%10+1,0）;
}
fclose（fp）;
}
/**********************显示分区函数**********************/
voidshowPartitiion（PLpl）
{
printf（"\t***************************************\n"）;
printf（"\t*StartAddr\tid\tsizestate*\n"）;
printf（"\t***************************************\n"）;
while（pl）
{
printf（"\t*%d\t\t%d\t%d\t%d*",pl->startAddress,pl->id,pl->size,pl->state）;
printf（"\n"）;
pl=pl->next;
}
printf（"\t***************************************\n"）;
Sleep（1000）;
if（kbhit（）==1）system（“pause”）;
}
/******************按进入时间顺序创建一个作业链表*********************/
voidInsertNode（Jobp,Job&job）//将创建的新结点插入到链表中
{
Jobq1,q2;
q1=job;
q2=job->next;
inti=0;
if（!
q2）
{
p->next=q2;
q1->next=p;
}
while（q2!
=NULL&&q2->intimeintime）
{
q1=q2;
q2=q2->next;
i=1;
}
if（!
q2&&i==1）
{
p->next=q2;
q1->next=p;
}
if（q2!
=NULL&&p->intime<=q2->intime）
{
p->next=q2;
q1->next=p;
}
}
JobCreateJoblist（Job&job,intcount）//创建作业链表
{
job=（Job）malloc（sizeof（jobList））;
if（!
job）
exit（0）;
job->next=NULL;
Jobp;
printf（"id\tsize\tintime\truntime\n"）;
for（inti=0;i{
p=（Job）malloc（sizeof（jobList））;
if（!
p）
exit（0）;
scanf（"%d\t%d\t%d\t%d",&p->id,&p->size,&p->intime,&p->runtime）;
p->state=0;
if（p->size>100）
{printf（"作业过大不能为之分配内存，请重新输入的作业：
\n"）;
scanf（"%d\t%d\t%d\t%d",&p->id,&p->size,&p->intime,&p->runtime）;
p->state=0;
InsertNode（p,job）;
}
else
InsertNode（p,job）;
}
returnjob;
}
/******************从外部文件读入数据并进行作业初始化*****************/
JobReadInitJob（Job&job）
{
ReadFile（）;
job=（Job）malloc（sizeof（jobList））;
if（!
job）
exit（0）;
job->next=NULL;
Jobp;
for（inti=0;i{
p=（Job）malloc（sizeof（jobList））;
if（!
p）exit（0）;
fscanf（fp,"%d%d%d%d%d",&p->id,&p->size,&p->intime,&p->runtime,&p->state）;
InsertNode（p,job）;
}
returnjob;
}
/*********************初始化分区链表***********************/
PLInitpartitionList（PL&p）
{
p=（PL）malloc（sizeof（partitionList））;
if（!
p）
exit（0）;
p->size=MemorySize;
printf（"输入分区首地址:
"）;
scanf（"%d",&p->startAddress）;
p->state=0;
p->id=0;
p->next=NULL;
p->prior=NULL;
returnp;
}
/*************将一个作业链表复制到另一个链表***************/
JobcopyJob（Jobp）
{
Jobq,L,s=p,r;
L=（Job）malloc（sizeof（jobList））;
L->next=NULL;
r=L;
s=s->next;
while（s）
{
q=（Job）malloc（sizeof（jobList））;
q->id=s->id;
q->state=0;
q->intime=s->intime;
q->runtime=s->runtime;
q->size=s->size;
r->next=q;
q->next=NULL;
r=q;
s=s->next;
}
returnL;
}
/*************将一个分区链表复制到另一个链表***************/
PLcopypartition（PLp）
{
PLq,L,s=p,r;
L=（PL）malloc（sizeof（partitionList））;
L->next=NULL;
r=L;
s=s->next;
while（s）
{
q=（PL）malloc（sizeof（partitionList））;
q->size=s->size;
q->startAddress=s->startAddress;
q->state=s->state;
r->next=q;
q->next=NULL;
r=q;
s=s->next;
}
returnL;
}
/*********************作业链表*********************/
voidshowJob（Jobjob）
{
job=job->next;
printf（"\n将作业按进入时间排序表示:
\n"）;
printf（"\t******************************************\n"）;
printf（"\t*id\tsize\tintime\truntime\tstate*\n"）;
printf（"\t******************************************\n"）;
while（job）
{
printf（"\t*%d\t%d\t%d\t%d\t%d*",job->id,job->size,job->intime,job->runtime,job->state）;
printf（"\n"）;
job=job->next;
}
printf（"\t******************************************\n"）;
printf（"\n"）;
}
/***********************回收内存*************************/
voidRecover（PLpl3,PL&pl）
{
while（pl3）
{
if（pl3->state==0）
{
if（pl3->next&&pl3->prior&&pl3->prior->state==0&&pl3->next->state==1）
{
pl3->size+=pl3->prior->size;
pl3->startAddress=pl3->prior->startAddress;
pl3->state=0;
pl3->id=0;
if（pl3->prior->prior）
{
pl3->prior->prior->next=pl3;
pl3->prior=pl3->prior->prior;
}
else
{
pl3->prior=pl3->prior->prior;
pl=pl3;
pl3=pl;
}
}
elseif（pl3->prior&&pl3->next&&pl3->next->state==0&&pl3->prior->state==1）
{
pl3->size+=pl3->next->size;
pl3->state=0;
pl3->id=0;
if（pl3->next->next）
{
pl3->next->next->prior=pl3;
pl3->next=pl3->next->next;
}
else
{
pl3->next=pl3->next->next;
}
}
elseif（!
pl3->prior）
{
if（pl3->next->state==0）
{
pl3->size+=pl3->next->size;
pl3->state=0;
pl3->id=0;
if（pl3->next->next）
pl3->next->next->prior=pl3;
pl3->next=pl3->next->next;
}
else
{
pl3->state=0;
}
}
elseif（!
pl3->next）
{
if（pl3->prior->state==0）
{
pl3->size+=pl3->prior->size;
pl3->state=0;
pl3->id=0;
pl3->startAddress=pl->startAddress;
if（pl3->prior->prior）
{
pl3->prior->prior->next=pl3;
pl3->prior=pl3->prior->prior;
}
else
{pl3->prior=NULL;
pl=pl3;
pl3=pl;
}
}
else
{
pl3->state=0;
}
}
elseif（pl3->next&&pl3->prior&&pl3->next->state==0&&pl3->prior->state==0）
{
pl3->size=pl3->size+pl3->next->size+pl3->prior->size;
pl3->state=0;
pl3->id=0;
pl3->startAddress=pl3->prior->startAddress;
if（pl3->next->next）
pl3->next->next->prior=pl3;
if（pl3->prior->prior）
{
pl3->prior->prior->next=pl3;
pl3->next=pl3->next->next;
pl3->prior=pl3->prior->prior;
}
else
{
pl3->next=pl3->next->next;
pl3->prior=pl3->prior->prior;
pl=pl3;
pl3=pl;
}
}
}
pl3=pl3->next;
}
}
/**********************首次适应算法**********************/
voidCycleFirstFit（PLpl,Jobjob）
{
intt=0;
intn=workload;
while（t+1&&n）
{
PLpl1=pl,pl2;
printf（"时钟:
%d\n",t）;
Jobjob1=job;
job1=job1->next;
Jobj1=job;
j1=j1->next;
Jobj2=job;
j2=j2->next;
Jobj3=job;
j3=j3->next;
PLpl3=pl;
while（j2）
{
if（j2->intime+j2->runtime==t）
{
printf（"作业id:
%d运行结束,释放内存!
",j2->id）;
n=n-1;
j2->state=2;
showJob（job）;
showPartitiion（pl）;
}
j2=j2->next;
}
while（j1）
{
if（j1->intime==t）
{
printf（"作业id:
%d开始运行,对其分配!
",j1->id）;
j1->state=1;
}
j1=j1->next;
}
while（job1）
{
if（t==job1->intime）
{
while（pl1&&（pl1->sizesize||pl1->sta
升级会员 