实验二：存储器的分配与回收算法实现.doc

实验二：存储器的分配与回收算法实现

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

2

个人收集整理 勿做商业用途
实验报告
学院（系）名称：计算机与通信工程学院
姓名
刘俊杰
学号
20115542
专业
信息与计算科学
班级
2011级1班
实验项目
实验二：存储器的分配与回收算法实现
课程名称
操作系统
课程代码
0668036
实验时间
2013—11-27 3-4节
2013-11—29 7-8节
2013-12-4 3-4节
2013-12-6 7—8节
实验地点
主校区7—215
批改意见
成绩

教师签字:

实验内容：
1． 本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业.
2． 采用最先适应法、最佳适应法、最坏适应法分配主存空间。
3． 当一个新作业要求装入主存时,必须查空闲区表,从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。
4． 当一个作业撤离时，归还的区域如果与其他空闲区相邻,则应合并成一个较大的空闲区，登在空闲区表中。
5． 设计的模拟系统中，进程数不小于5，进程调度方式可以采用实验一中的任何一种。
6． 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。
实验要求：
1． 详细描述实验设计思想、程序结构及各模块设计思路;
2． 详细描述程序所用数据结构及算法；
3． 明确给出测试用例和实验结果；
4． 为增加程序可读性，在程序中进行适当注释说明；
5． 认真进行实验总结，包括:设计中遇到的问题、解决方法与收获等;
6． 实验报告撰写要求结构清晰、描述准确逻辑性强；
7． 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
代码实现：
＃include〈stdio.h>
＃include〈malloc.h>
＃define NULL 0
#define LEN1 sizeof(struct job）//作业大小
#define LEN2 sizeof(struct idle）//空闲区单元大小
#define LEN3 sizeof（struct allocate）//已分配区单元大小
int SPACE=100；//定义内存空间大小
int ORIGI=1；//定义内存起始地址
struct job//定义作业
｛
int name；
int size;
int address；
};
struct idle//定义空闲区
{
int size；
int address；
struct idle ＊next；
｝;
struct allocate//定义已分配区
｛
int name;
int size；
int address；
struct allocate ＊next；
｝;
struct idle *creatidle（void）//建立空闲表
｛
struct idle *head；
struct idle *p1;
p1=（struct idle＊)malloc（LEN2)；
p1-〉size=SPACE；
p1—>address=ORIGI；
p1-〉next=NULL;
head=p1;
return(head);
}
struct allocate ＊creatallocate(void）//建立已分配表
｛
struct allocate *head；
head=NULL；
return(head)；
｝
struct job ＊creatjob(void)//建立作业
{
struct job *p；
p=（struct job*)malloc(LEN1）；
printf（”请输入要运行的作业的名称与大小：\n”）;
scanf（”%d%d”，&p—〉name，&p—>size);
return(p）；
｝
struct idle *init1（struct idle *head,struct job ＊p)//首次适应算法分配内存
｛
struct idle *p0,＊p1;
struct job ＊a;
a=p;
p0=head;
p1=p0；
while（p0->next！=NULL＆＆p0->size<a-〉size)
｛
p0=p0->next；
｝
if（p0—〉size>a->size)
{
p0—〉size=p0—>size—a—>size；
a—>address=p0->address;
p0—>address=p0—>address+a-〉size；
}
else
｛
printf(”无法分配\n”);
}
return(head);
｝
struct idle ＊init2(struct idle ＊head，struct job *p）//最优
{
struct idle ＊p0，*p1;
struct job ＊a；
a=p；
p0=head;
if（p0==NULL）
{
printf(”无法进行分配！\n");
}
while(p0—>next！=NULL&&p0-〉size<a—〉size）
{
p0=p0—>next;
｝
if（p0-〉size>a-〉size)
{
p1=p0;
p0=p0—>next；
}
else
｛
printf（"无法分配!\n”）；
}
while(p0！=NULL)
｛
if（p0-〉size〉p1->size）
｛
p0=p0->next；
}
else if((p0—〉size〈p1—〉size)&＆(p0->size〉a-〉size)）
{
p1=p0；
p0=p0—〉next；
}
｝
p1—>size=(p1—〉size）-（a-〉size）；
a—〉address=p1-〉address;
p1-〉address=（p1—〉address）+（a—〉size)；
return(head)；
}
struct idle *init3(struct idle *head,struct job *p)//最差
｛
struct idle ＊p0，*p1;
struct job *a；
a=p；
p0=head;
if(p0==NULL）
｛
printf（”无法进行分配！");
｝
while(p0-〉next！=NULL&＆p0—〉size<a—>size）
{
p0=p0-〉next;
｝
if(p0—>size〉a->size）
{
p1=p0；
p0=p0->next；
}
else
{
printf("无法分配！\n”）；
}

while（p0!=NULL）
{
if（p0-〉size<p1—〉size）
{
p0=p0—>next；
}
else if(p0-〉size〉p1->size）
{
p1=p0;
p0=p0—>next;
}
}
p1->size=(p1->size)-（a—〉size)；
a->address=p1-〉address;
p1—>address=(p1—〉address)+（a->size）;
return（head)；
}
struct allocate ＊reallocate（struct allocate *head，struct job *p）//重置已分配表
｛
struct allocate *p0,＊p1,＊p2；//*p3，＊p4;
struct job *a;
//struct idle ＊b；
a=p；
p0=(struct allocate*)malloc（LEN3);
p1=(struct allocate*)malloc(LEN3);
if(head==NULL)
｛
p0->name=a—>name；
p0->size=a—〉size；
p0-〉address=ORIGI；
p0—>next=NULL；
head=p0；
}
Else
{
p1->name=a->name;
p1-〉size=a->size;
p1->address=a—>address；
p2=head;
while（p2—>next！=NULL)
{
p2=p2-〉next;
} p2—〉next=p1;
p1-〉next=NULL；
｝
return（head);
｝
struct allocate ＊del（struct allocate ＊head，struct job *p）//删除指定的作业
{
struct job ＊p1；
struct allocate ＊p2,*p3；
p2=head;
p1=p；
while（（p1—〉name!=p2—>name)＆＆(p2—>next!=NULL)）
｛
p3=p2;
p2=p2->next;
｝
if(p1—>name==p2—〉name)
{
if（p2==head)
head=p2—〉next;
else
p3—〉next=p2—>next;
}
return（head）；
}
struct job *delejob（struct allocate ＊head）
{
struct job *p1;
struct allocate *p2;
int num;
p1=(struct job*）malloc(LEN1);
printf（"请输入要删除的作业的名称\n”）;
scanf(”%d"，＆num)；
p2=head；
while（(num!=p2->name）＆＆(p2—>next！=NULL)）
{
p2=p2—>next;
｝
if(num==p2—〉name)
｛
p1—〉name=p2—〉name；
p1->size=p2-〉size；
p1-〉address=p2—〉address；
}
return（p1）;
｝
struct idle *unite（struct job ＊p，struct idle *head)//合并相邻内存空间
{
struct idle *p1,＊p2,*p3;
struct job *m；
m=p;
p1=head;
p3=（struct idle＊)malloc（LEN2）;
while（(p1—>address〈m-〉address)&&(p1—>next！=NULL))
｛
p2=p1;
p1=p1->next；
｝
if（m—〉address〈p1—〉address）
{
if(head==p1)
｛
p3->size=m->size;
p3—〉address=m—>address；
if（（p1—〉address—p3->address）==(p3-〉size）)
{
p1-〉address=p3-〉address;
p1->size=p3—〉size+p1-〉size;
｝
else
{
head=p3;
p3—〉next=p1；
｝
}
else
{
p3—>size=m—>size；
p3—>address=m—〉address;
if（(p1-〉address—p3—>address）==(p3-〉size））
{
p1-〉address=p3->address；
p1—>size=p3—>size+p1—>size;
if（（p3—〉address—p2-〉address)==(p2->size））
{
p2-〉size=p1—〉size+p2—〉size;
p2—>next=p1-〉next;
｝
else
｛
p2—〉next=p1;
｝
｝
else
{
if（(p3->address—p2—>address）==(p2—>size))
｛
p2->size=p2—>size+p3-〉size；
}
else
{
p3—〉next=p1;
p2—〉next=p3;
｝
｝
}
}
else
｛
p3-〉size=m—>size；
p3—〉address=m—>address；
if((p3->address-p1—>address)==（p1—〉size))
｛
p1-〉size=p1->size+p3->size;
}
else
｛
p1-〉next=p3；
p3->next=NULL;
｝
｝
return（head）；
｝
void print(struct idle ＊h1,struct allocate *h2）
{
struct idle *m1;
struct allocate *n1；
m1=h1;
n1=h2；
if(m1==NULL）
｛
printf（"空闲表为空！\n”);
｝
else
{
while（m1!=NULL)
{
printf（”空闲单元地址为％d,其大小为％d\n",m1—〉address，m1—>size）；
m1=m1—>next;
}
｝
if(n1==NULL）
{
printf（"已分配表为空！\n");
｝
else
{
while(n1!=NULL)
｛
printf（"已分配单元地址为%d,其大小为％d,其名称为％d\n”,n1-〉address，n1—>size，n1-〉name）;
n1=n1—>next;
}
}
｝
void FF(void）
｛
struct idle ＊p1；
struct allocate *p2；
struct job *p,*q；
int y=1；
int n=0；
int a=1；
int c；
p1=creatidle（）；
p2=creatallocate()；
printf(”初始情况为：\n")；
print（p1,p2）;
while（a==y)
｛
printf（"请输入要进行的操作:1.建立作业 2。删除作业 3.结束操作\n");
scanf("％d”,&c）；
switch(c）
｛
case 1：
p=creatjob(）；
p1=init1(p1,p）；
p2=reallocate（p2,p)；
print（p1,p2）；break；
case 2：
q=delejob(p2);
p2=del(p2,q）;
//p2=reallocate(p2，q)；
p1=unite(q，p1）;
print(p1，p2);break;
case 3：
y=0；break；

}
}
｝
void BF(void)
｛
struct idle *p1；
struct allocate *p2;
struct job ＊p,*q；
int y=1;
int n=0;
int a=1;
int c；
p1=creatidle（）；
p2=creatallocate（）；
printf(”初始情况为:\n")；
print(p1，p2）；
while(a==y）
{
printf(”请输入要进行的操作：1。建立作业 2.删除作业 3。结束操作\n"）；
scanf（”%d",&c)；
switch(c)
｛
case 1:
p=creatjob(）；
p1=init2(p1，p);
p2=reallocate（p2,p)；
print（p1，p2);break；
case 2：
q=delejob（p2);
p2=del(p2，q）;
//p2=reallocate(p2，q）；
p1=unite（q,p1)；
print(p1，p2）;break;
case 3:
y=0；break；

｝
}
}
void WF(void)
｛

struct idle *p1;
struct allocate ＊p2；
struct job *p,＊q;
int y=1；
int n=0;
int a=1;
int c;
p1=creatidle（）；
p2=creatallocate（）;
printf（"初始情况为：\n”）;
print(p1,p2);
while(a==y)
{
printf("请输入要进行的操作：1。建立作业 2.删除作业 3.结束操作\n"）;
scanf("%d"，＆c）；
switch（c)
｛
case 1:
p=creatjob（);
p1=init3(p1,p)；
p2=reallocate(p2,p)；
print(p1，p2）;break；
case 2:
q=delejob(p2)；
p2=del(p2，q）；
//p2=reallocate(p2，q）；
p1=unite(q，p1)；
print(p1，p2）;break；
case 3:
y=0;break;

}
}
}

第14页 共14页