操作系统动动态分配管理系统.doc

操作系统动动态分配管理系统

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

个人收集整理 勿做商业用途
淮北师范大学

《操作系统设计实验报告》

题目-—动态分区分配管理系统

班级：09非师
设计者：曹严严
指导老师：周影
时间： 2012/03/14—-—2012/03/15

目录

1程序设计的内容和相关的要求-—-——--—-—--——-—--—--——--—----———-—

2程序总的功能说明———--—-—--—————-----—-—-—----—--———-——-—————-—

3程序的模块的说明—---—-———-————-—--———--—————--——-—--———————--—

4程序设计的流程图—-—-—-—---——-—-——-—-------——-----——----—————--

5程序的操作说明及运行结果—----————---—-—-—————--—---—————-—--—

6源程序的清单-———-----—————--—————--———-----——--————-—------——-

7心得体会-----——----—--—----—--—---—-—---——------—-———-——————-—

1程序设计的内容和相关的要求
课程设计的目的：操作系统课程设计是计算机学院重要的教学环节,它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。
l 进一步巩固和复习操作系统的基础知识。
l 培养学生结构化程序、模块化程序设计的方法和能力。
l 提高学生调试程序的技巧和软件设计的能力。
l 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。

实现的任务：编写一个动态分区分配程序.

设计内容:
用高级语言编写和调试一个动态分区内存分配程序,演示实现下列两种动态分区分配算法

1.首次适应算法
2。循环首次适应算法
设计要求：
1。内存中有0-100M的空间为用户程序空间，最开始用户空间是空闲的；
2.作业数量、作业大小、进入内存空间、运行时间需要通过界面进行输入;
3.可读取样例数据（要求存放在外部文件夹中）进行作业数量、作业大小、进图内存时间、运行时间的初始化；
4.根据作业进图内存的时间，采用简单的先进先出原则进行从外村到内存的调度,作业具有等待（从外存进入内存执行）、装入（在内存可执行)、结束（运行结束，退出内存)三种状态.(为了简化，不考虑cpu的调度与切换，运行时间为作业在内存中驻留的时间）；
5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作,所有过程均有动态图形变化的显示;
6.采用可视化界面,可随时暂停显示当前内存分配和使用情况图。

2程序总的功能说明：
本程序可以从界面直接输入作业并进行动态的内存分配,也可以自动地生成作业文件并自行调度进行内存分配，每次分配可以选择两种算法（首次适应算法和循环首次算法）中的一种，每次作业结束后可以进入操作主界面进行再次作业的操作。
3程序各模块的功能说明：
（1） 界面显示函数：
showInterface（PL p,Job job)；显示操作界面
showJob(Job job）；显示作业链表；
showPartitiion(PL pl)显示分区链表
（2） 执行练习的功能函数:
copyJob(Job p）；作业链表复制函数函数
InitpartitionList(PL &p）；链表初始化分区函数函数
CreateJoblist(Job &job,int count）;创建作业链表函数
InsertNode(Job p，Job ＆job）；按时间顺序创建链表函数
InitpartitionList(PL &p）；初始化分区链表函数
（3）文件函数
openFile(）；打开文件函数
ReadFile()；读取文件函数
RandomParameter(）；随即参数读入文件函数
main()///主函数
4程序设计的流程图 :
总体设计流程图:
动态分区分配界面
作业生成
退出操作
界面输入
自动生成文件
生成方式
1
2
3
分配
方式
首次适应
循环首次适应应
1
2
3
作为一个整体

首次适应算法：开始
接受作业
作业n--
执行
·
进入
内存回收
释放空间
结束
Intime==time

Waitingjobstate
（0或1）

空闲分区状态
（0或1）

n=0

作业等待序列
Y
N
Y
N
Y
0
0
1
0

回收函数:
回收函数
回收区在空闲分区前
不连接回收
连接回收
回收区在空闲分区间
回收区在空闲分区后

5程序操作说明书及结果
在vc++6.0环境中运行本程序,先进行编译，然后再进行链接，在进行执行将会出现显示界面。按照显示界面上显示的提示进行操作，就可以实现相应的功能：
1。运行进入操作主界面：

6源程序清单
＃include<time.h>
#include <conio。h>
＃include〈stdio.h>
#include〈stdlib.h〉
#include 〈windows.h>
＃define MemorySize 100//为空闲分区分配的最大空间（按题目要求）
int workload；//输入作业的数量；
typedef struct jobList
｛
int id; // 作业的name
int size； // 作业大小（需要的存储空间大小)
int intime； //进入时间
int runtime； //运行时间
int state； //作业的状态(0表示等待，1表示执行，2表示结束并释放）
struct jobList *next; // 作业链表指针
｝ ＊Job；
typedef struct partitionList
｛
int id;
int startAddress; //分区起始地址
int size； //分区大小
int state； //分区的状态
struct partitionList *prior；
struct partitionList *next； // 分区链表指针
｝*PL；

FILE *fp;
/＊***＊＊＊＊＊＊*＊＊＊＊＊*＊＊*＊**＊打开文件*＊＊****＊**＊*＊***＊＊＊＊＊＊＊****/
void openFile（）
{
if(（fp=（fopen（”D:\\作业文件.txt”,”w”)））==NULL)
{
printf（”无法打开文件!\n”)；
exit(0）；
｝
}
/**＊＊＊＊＊***＊*＊***＊＊*＊**＊*读取文件＊＊＊*****＊******＊*＊＊＊＊*＊＊**＊＊/

void ReadFile()
{
if（(fp=(fopen("D:\\作业文件。txt"，”r")））==NULL)
{
printf（”无法打开文件!\n”);
exit（0）；
｝
｝
/*＊*****＊****将随机产生进程的参数写入文件**＊**＊＊＊＊**＊*＊＊＊****/
void RandomParameter（）
{
openFile（);

for（int i=0;i〈workload；i++）
｛
fprintf（fp,"％d %d ％d %d %d\n"，i+1,rand（）％80，rand(）％20,rand(）％10+1,0);
}
fclose（fp)；

｝

/***＊**＊*＊＊＊＊***＊＊＊＊*＊＊显示分区函数**＊＊*＊***＊＊*＊**＊*＊**＊＊/

void showPartitiion(PL pl)
{
printf（”\t**＊**＊＊＊＊*****＊*****＊＊＊**＊*＊＊＊******＊＊*\n”）；
printf(”\t＊ StartAddr\tid\tsize state ＊\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”);
｝

/**＊*＊*＊＊**＊＊＊**＊＊*按进入时间顺序创建一个作业链表**＊*＊*＊*＊*＊*＊＊*＊*＊**＊/

void InsertNode（Job p,Job &job） //将创建的新结点插入到链表中
{

Job q1,q2;
q1=job;
q2=job-〉next;
int i=0;
if(！q2)
{
p-〉next=q2；
q1-〉next=p;
｝
while(q2！=NULL＆＆q2—〉intime〈p->intime）
{
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;
}

｝

Job CreateJoblist(Job ＆job,int count）//创建作业链表
{

job=（Job）malloc(sizeof(jobList)）;
if（!job）
exit（0);
job->next=NULL;
Job p；
printf("id\tsize\tintime\truntime\n”)；
for(int i=0；i〈count;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）；
｝
return job；

｝
/*＊**＊＊***＊＊**＊**＊＊从外部文件读入数据并进行作业初始化*＊**＊*＊＊＊＊＊**＊*＊＊/
Job ReadInitJob（Job &job)
｛
ReadFile();
job=(Job）malloc（sizeof(jobList))；
if（!job）
exit（0）；
job-〉next=NULL；
Job p；

for(int i=0；i〈workload;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)；
｝
return job；
}
/**＊＊*＊＊*******＊***＊**初始化分区链表＊*＊****＊＊**＊**＊*＊＊＊＊＊*＊/

PL InitpartitionList(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;
return p；

｝

/＊**＊＊＊***＊*＊＊将一个作业链表复制到另一个链表＊*＊＊*＊**＊＊**＊＊＊/

Job copyJob(Job p）
｛
Job q,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;
｝

return L;
｝

/＊＊＊*＊*******＊将一个分区链表复制到另一个链表＊*＊＊＊＊***＊*＊***/

PL copypartition(PL p）
｛

PL q，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;
}

return L；
｝

/**＊＊**＊＊***＊＊**＊*＊＊**作业链表*＊*******＊＊***＊＊＊＊＊＊*/
void showJob(Job job）
{
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"）；
｝

/**＊＊*＊＊＊＊＊＊＊＊*＊*＊**＊＊＊*回收内存******＊＊***＊＊＊*＊***＊＊＊＊**/

void Recover（PL pl3，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；
｝

}
else if(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；

｝

｝
else if(！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;
｝
}
else if（！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;
}

}

else if（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；

｝

}

/＊＊*＊*＊**＊******＊＊*＊*＊*首次适应算法***＊**＊＊＊＊＊＊＊*＊*＊**＊＊＊/

void CycleFirstFit(PL pl，Job job)
{

int t=0；
int n=workload;
while(t+1&&n）
{
PL pl1=pl,pl2;
printf（"时钟:%d\n”,t);
Job job1=job；
job1=job1—〉next;
Job j1=job;
j1=j1—>next;
Job j2=job;
j2=j2—〉next;
Job j3=job;
j3=j3-〉next;
PL pl3=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—>size<job1-〉size||pl1—>state==1）) pl1=pl1—>next；
if（pl1)
{
pl2=(PL)malloc(sizeof(partitionList)）;
pl2-〉startAddress=pl1-〉startAddress+job1—>size;
pl2—〉state=0;
pl2-〉id=0;
pl2->size=pl1—〉size-job1—>size;
if(pl2-〉size>5）
｛
pl1—〉size=job1—〉size;
pl1—>state=1；
pl1—〉id=job1-〉id;
if（pl1—〉next）
pl1—〉next->prior=pl2；
pl2—>next=pl1-〉next;
pl2->prior=pl1；
pl1-〉next=pl2；
pl1=pl；
}
else
{
pl1—〉state=1;
pl1—>id=job1-〉id;

｝
showJob（job)；
showPartitiion（pl);
｝
else
｛
printf（”内存不足,将作业:％d置于等待状态！等待内存释放在进行分配!\n”，job1->id）；
Job j=job1;
while(j）
｛
j->intime+=1;
j—〉state=0;
j=j—〉next;
｝
Job jj=job;
jj=jj->next;
while(jj）
{
if(jj—〉state==2)
｛
while（pl3)
{
if（pl3—>id=jj—〉id)
pl3-〉state=0;
pl3=pl3->next;
}
｝
jj=jj—〉next;
}
pl3=pl；
Recover（pl3，pl)；
｝
}
job1=job1-〉next;
｝
t=t+1；
Sleep（500);
｝
PL p=pl；
while（p)
{
p-〉state=0;
p=p->next;
}
showJob(job)；
showPartitiion（pl);
printf(”所有进程分配完毕！\n"）；
｝
/＊*******＊＊＊***＊＊＊＊*＊＊＊循环首次算法＊*＊*＊**＊****＊*＊*＊**＊*＊/
void FirstFit(PL pl，Job job）
{

int t=0；
int n=workload；
while（t+1&&n)
｛
PL pl1=pl，pl2;
printf("时钟：％d\n"，t）；
Job job1=job;
job1=job1->next；
Job j1=job；
j1=j1—〉next;
Job j2=job;
j2=j2—>next；
Job j3=job;
j3=j3—〉next;
PL pl3=pl;
while(j2）
｛
if(j2—>intime+j2—>runtime==t）
{

printf("作业id:%d运行结束,释放内存!\n”,j2—〉id);
n=n-1；
j2—>state=2；
pl3=pl；
while(pl3）
｛
if(pl3—>id==j2-〉id）
pl3—>state=0;
pl3=pl3->next；
}
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->size<job1-〉size|｜pl1-〉state==1）） pl1=pl1—>next；
if(pl1)
｛
pl2=(PL）malloc(sizeof(partitionList）)；
pl2—〉startAddress=pl1—>startAddress+job1-〉size；
pl2—〉state=0；
pl2—>id=0；
pl2—>size=pl1-〉size—job1->size;
if（pl2—>size>=5) //碎片最大值设为 5
{
pl1—>size=job1-〉size；
pl1-〉state=1;
pl1-〉id=job1—>id;
if(pl1—>next）
pl1—>next—〉prior=pl2；
pl2->next=pl1—>next；
pl2->prior=pl1；
pl1->next=pl2;
pl1=pl；
｝
else
｛
pl1—〉state=1；
pl1->id=job1->id；

｝
showJob(job)；
showPartitiion（pl）;
｝
else
{
printf（"内存不足，将作业：%d置于等待状态!等待内存释放在进行分配!\n”,job1—>id);
Job j=job1;
while（j）
{
j—〉intime+=1;
j—>state=0；
j=j—〉next;
}
pl3=pl;
Recover（pl3，pl)；
｝
}
job1=job1-〉next;
｝
t=t+1;

Sleep（500）；
｝
PL p=pl；
while（p）
{
p—>state=0;
p=p—>next；
}
showJob（job);
showPartitiion(pl)；
printf（”所有进程分配完毕！\n”）;
}

/*＊＊*＊*＊*＊＊＊*＊**＊＊*******界面显示**＊＊＊*＊**＊*＊***＊＊*＊*＊＊＊**/
void showInterface(PL p，Job job）
{
int a，con=0;
Job j1,j2；
while(1）{
printf("\t1。首次适应\n\n");
printf（”\t2。循环首次适应\n\n”）；
printf("\t3.退出\n请选择：\n”）；
if(con==0｜｜con==1）scanf（”％d",&a)；
switch（a）
{

case 1: InitpartitionList(p）;j1=copyJob(job）;
FirstFit（p，j1);
break；
case 2: InitpartitionList（p)；j2=copyJob（job）；
CycleFirstFit( p，j2)；
break;
case 3:exit（0）;break；
}
printf（"重新选用算法（输入1),退出本次作业操作（输入3)\n”）；
scanf("%d",&con);
if（con==1）