暨南大学本科实验报告专用纸
课程名称 《操作系统原理实验》 成绩评定 实验项目名称 进程控制 指导教师 戴红 实验项目编号 0806002904 实验项目类型 综合型实验地点 学生姓名 岑江斌 学号 2008051584 学院 电气信息学院 系 计算机科学系 专业 软件工程
实验时间 年 月 日 下午 温度 ℃ 湿度
一， 实验目的。
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态扮区存储管理方式及其实现过程的理解。
二， 实验内容。
1分别实现首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中，空闲分区通过空闲区链进行管理；进行内存分配时，系统优先使用空闲区低端的空间。
2、假设初试状态下，可用的内存空间为640KB，并有下列的请求序列： 作业1申请 130KB
作业2申请 60KB
作业3申请 100KB
作业2释放 60KB
作业4申请 200KB
作业3释放 100KB
作业1释放 130KB
作业5申请 140KB
作业6申请 60KB
作业7申请 50KB
作业6释放 60KB
3、每次分配和回收后显示空闲内存分区链情况。
三， 实验源代码。
最佳适应算法：
#include"stdio.h"
#include"stdlib.h"
int i=1;//id
typedef struct mem
{
int start;
int end;
struct mem *next;
}mem;
typedef struct work
{
int id;
int size;//memsize
int start;
struct work *next;
}work;
work* initwork(int size)
{
work *head=(work *)malloc(sizeof(head));
head->id=i;
head->start=1;
head->size=size;
head->next=NULL;
return head;
}
work* insertwork(work *head,int start,int size)
{
i++;
work *pi,*pb;//pi is the insert one ##pb is the point pi=(work*)malloc(sizeof(work));
pi->id=i;
pi->start=start;
pi->size=size;
pi->next=NULL;
if(head==NULL){head=pi;head->next=NULL;}
pb=head;
while(pb->next!=NULL){pb=pb->next;}
pb->next=pi;
return head;
}
mem *initmem(int size)
{
mem *head=(mem*)malloc(sizeof(mem));
head->start=1;
head->end=640;
head->next=NULL;
return head;
}
mem *insertmem(mem *head,int start,int size)
{
mem *pi,*pb,*pf;
int pbsize;
pb=head;
pbsize=pb->end-pb->start+1;
pi=(mem*)malloc(sizeof(mem));
pi->start=start;
pi->end=size+start-1;
if(pb==NULL){head=pi;pi->next=NULL;}
else
{
while(pi->start>pb->start&&pb->next!=NULL){pf=pb;pb=pb->next;}
if(pi->startstart)
{
if(pb==head)
{
head=pi;//头节点
pi->next=pb;
}
else
{
pf->next=pi;//其他位置
pi->next=pb;
}
}
else
{
pb->next=pi;
pi->next=NULL;//在表末插入
}
}
//合并相邻的内存
pf=pb=head;
while(pb->next!=NULL)
{
if(pf->end+2>pb->start)
{
pf->end=pb->end;
pf->next=pb->next;
}
pf=pb;
pb=pb->next;
}
return head;
}
int getstart(work*head,int size)
{
work *pb;
pb=head;
while(pb!=NULL)
{
if(pb->size==size)
{
return pb->start;
}
pb=pb->next;
}
return 0;
}
int alloc(mem *head,int size)
{
mem *pb;
pb=head;
int a;
while(pb!=NULL)
{
if(sizeend-pb->start+1))
{
a=pb->start;
pb->start=pb->start+size;
return a;
}
pb=pb->next;
}
return 0;
}
work*free1(work *head,int size)
{
work *pb,*pf;
while(head==NULL){printf("no this nod");goto end;}
pb=head;
while(pb->size!=size&&pb->next!=NULL)
{
pf=pb;
pb=pb->next;
}
if(pb->size==size)
{
if(pb==head)head=pb->next;
else pf->next=pb->next;
}
end:
return head;
}
void printw(work *head)
{
work *pb;
pb=head;
while(pb!=NULL)
{
printf("id start size---->\n");
printf("%d%7d%8d\n",pb->id,pb->start,pb->size);
pb=pb->next;
}
}
void printm(mem *head)
{
mem *pb;
pb=head;
while(pb!=NULL)
{
printf("start end---->\n");
printf("%d%9d\n",pb->start,pb->end);
pb=pb->next;
}
}
void main()
{
int wrec;//接收返回的地址
int mrec;
mem *mhead;
mhead=initmem(640);
work *whead;
//1
whead=initwork(130);
wrec=alloc(mhead,130);
//2
wrec=alloc(mhead,60);
whead=insertwork(whead,wrec,60);
//3
wrec=alloc(mhead,100);
whead=insertwork(whead,wrec,100);
//4
mrec=getstart(whead,60);
whead=free1(whead,60);
mhead=insertmem(mhead,mrec,60);
//5
wrec=alloc(mhead,200);
whead=insertwork(whead,wrec,200);
//6
mrec=getstart(whead,100);
whead=free1(whead,100);
mhead=insertmem(mhead,mrec,100);
//7
mrec=getstart(whead,130);
whead=free1(whead,130);
mhead=insertmem(mhead,mrec,130);
//8
wrec=alloc(mhead,140);
whead=insertwork(whead,wrec,140);
//9
wrec=alloc(mhead,60);
whead=insertwork(whead,wrec,60);
//10
wrec=alloc(mhead,50);
whead=insertwork(whead,wrec,50);
//11
mrec=getstart(whead,60);
whead=free1(whead,60);
mhead=insertmem(mhead,mrec,60);
printf("作业的链表\n");
printw(whead);
printf("========================\n");
printf("空闲分区链表\n");
printm(mhead);
}
首次适应算法：
#include "stdio.h"
struct allocquery /* 定义请求序列结构体*/
{
int num;
int state; /* a表示申请，f表示释放 */
int length;
};
struct allocquery allocq[11];
struct freequery /* 定义内存分配队列 */
{
int flag; /* IDNo. 0表示空闲，其他数值表示相应作业 */ int firstadd; /* 起始地址 */
int length; /* 占有长度 */
};
struct freequery freeq[11];
/* 首次适应算法函数*/
void first_alg(struct allocquery allocqnow,int *ptotal,struct freequery *pfreeq);
main()
{
int i,j;
FILE *fp;
char *fname="c:\\a.txt";
int Freetotal=1;
fp=fopen(fname,"w+");
allocq[0].num=1; allocq[0].state='a'; allocq[0].length=130; allocq[1].num=2; allocq[1].state='a'; allocq[1].length=60; allocq[2].num=3; allocq[2].state='a'; allocq[2].length=100; allocq[3].num=2; allocq[3].state='f'; allocq[3].length=60; allocq[4].num=4; allocq[4].state='a'; allocq[4].length=200; allocq[5].num=3; allocq[5].state='f'; allocq[5].length=100;
allocq[6].num=1; allocq[6].state='f'; allocq[6].length=130; allocq[7].num=5; allocq[7].state='a'; allocq[7].length=140; allocq[8].num=6; allocq[8].state='a'; allocq[8].length=60; allocq[9].num=7; allocq[9].state='a'; allocq[9].length=50; allocq[10].num=6; allocq[10].state='f'; allocq[10].length=60;
freeq[0].flag=0; freeq[0].firstadd=0; freeq[0].length=640;
for(i=0;i
{
first_alg(allocq[i],&Freetotal,freeq);
fprintf(fp,"\nTotal free blocks:%d ",Freetotal) ;
fprintf(fp,"\nIDNo. address length");
for(j=0;freeq[j].length!=0;j++)
fprintf(fp,"\n%5d%10d%10d",freeq[j].flag,freeq[j].firstadd,freeq[j].length);
}
}
void first_alg(struct allocquery allocqnow,int *ptotal,struct freequery *pfreeq)
{
int i,j,num;
int temp_num,temp_add,temp_length;
struct freequery temp_f1,temp_f2;
if (allocqnow.state=='a') /* 表示申请空间 */
{
for (i=0;i
{
if((pfreeq[i].flag==0)&(pfreeq[i].length>allocqnow.length)) {
temp_num=pfreeq[i].flag;
temp_add=pfreeq[i].firstadd+allocqnow.length;
temp_length=pfreeq[i].length-allocqnow.length;
pfreeq[i].flag=allocqnow.num;
pfreeq[i].length=allocqnow.length;
if (pfreeq[i+1].length==0)
{
pfreeq[i+1].flag=temp_num;
pfreeq[i+1].firstadd=temp_add;
pfreeq[i+1].length=temp_length;
}
else
if (pfreeq[i+1].firstadd!=temp_add)
{
temp_f1.flag=temp_num; temp_f1.firstadd=temp_add;
temp_f1.length=temp_length;
temp_f2=pfreeq[i+1];
for (j=i+1;pfreeq[j].length!=0;j++)
{
pfreeq[j]=temp_f1;
temp_f1=temp_f2;
temp_f2=pfreeq[j+1];
}
pfreeq[j]=temp_f1;
}
break;
}
}
}
else /* 释放空间*/
{
for (i=0;i
{
if (pfreeq[i].flag==allocqnow.num)
{
if ((pfreeq[i-1].flag==0)&(pfreeq[i+1].flag==0)&(i>0)) {
pfreeq[i-1].length=pfreeq[i-1].length+allocqnow.length+pfreeq[i+1].length;
for (j=i;pfreeq[j].length!=0;j++)
{
pfreeq[j].flag=pfreeq[j+2].flag;
pfreeq[j].firstadd=pfreeq[j].firstadd;
pfreeq[j].length=pfreeq[j].length;
}
}
else if ((pfreeq[i-1].flag==0)&(i>0))
{
pfreeq[i-1].length=pfreeq[i-1].length+allocqnow.length; for (j=i;pfreeq[j].length!=0;j++)
{
pfreeq[j].flag=pfreeq[j+1].flag;
pfreeq[j].firstadd=pfreeq[j+1].firstadd;
pfreeq[j].length=pfreeq[j+1].length;
}
}
else if (pfreeq[i+1].flag==0)
{
pfreeq[i].flag=0;
pfreeq[i].length=allocqnow.length+pfreeq[i+1].length; for (j=i+1;pfreeq[j].length!=0;j++)
{
pfreeq[j].flag=pfreeq[j+1].flag;
pfreeq[j].firstadd=pfreeq[j+1].firstadd;
pfreeq[j].length=pfreeq[j+1].length;
}
}
else
{
pfreeq[i].flag=0;
}
}
}
}
num=0; /* 统计空闲块*/
for (i=0;pfreeq[i].length!=0;i++)
if (pfreeq[i].flag==0) num++;
*ptotal=num;
}
四， 实验结果。
五、实验心得
通过这次实验，取用首次适应算法和最佳适应算法了解了动态分区分配方式中使用的数据结构和分配算法，以及了解了动态分区存储管理方式。
暨南大学本科实验报告专用纸
课程名称 《操作系统原理实验》 成绩评定 实验项目名称 进程控制 指导教师 戴红 实验项目编号 0806002904 实验项目类型 综合型实验地点 学生姓名 岑江斌 学号 2008051584 学院 电气信息学院 系 计算机科学系 专业 软件工程
实验时间 年 月 日 下午 温度 ℃ 湿度
一， 实验目的。
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态扮区存储管理方式及其实现过程的理解。
二， 实验内容。
1分别实现首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中，空闲分区通过空闲区链进行管理；进行内存分配时，系统优先使用空闲区低端的空间。
2、假设初试状态下，可用的内存空间为640KB，并有下列的请求序列： 作业1申请 130KB
作业2申请 60KB
作业3申请 100KB
作业2释放 60KB
作业4申请 200KB
作业3释放 100KB
作业1释放 130KB
作业5申请 140KB
作业6申请 60KB
作业7申请 50KB
作业6释放 60KB
3、每次分配和回收后显示空闲内存分区链情况。
三， 实验源代码。
最佳适应算法：
#include"stdio.h"
#include"stdlib.h"
int i=1;//id
typedef struct mem
{
int start;
int end;
struct mem *next;
}mem;
typedef struct work
{
int id;
int size;//memsize
int start;
struct work *next;
}work;
work* initwork(int size)
{
work *head=(work *)malloc(sizeof(head));
head->id=i;
head->start=1;
head->size=size;
head->next=NULL;
return head;
}
work* insertwork(work *head,int start,int size)
{
i++;
work *pi,*pb;//pi is the insert one ##pb is the point pi=(work*)malloc(sizeof(work));
pi->id=i;
pi->start=start;
pi->size=size;
pi->next=NULL;
if(head==NULL){head=pi;head->next=NULL;}
pb=head;
while(pb->next!=NULL){pb=pb->next;}
pb->next=pi;
return head;
}
mem *initmem(int size)
{
mem *head=(mem*)malloc(sizeof(mem));
head->start=1;
head->end=640;
head->next=NULL;
return head;
}
mem *insertmem(mem *head,int start,int size)
{
mem *pi,*pb,*pf;
int pbsize;
pb=head;
pbsize=pb->end-pb->start+1;
pi=(mem*)malloc(sizeof(mem));
pi->start=start;
pi->end=size+start-1;
if(pb==NULL){head=pi;pi->next=NULL;}
else
{
while(pi->start>pb->start&&pb->next!=NULL){pf=pb;pb=pb->next;}
if(pi->startstart)
{
if(pb==head)
{
head=pi;//头节点
pi->next=pb;
}
else
{
pf->next=pi;//其他位置
pi->next=pb;
}
}
else
{
pb->next=pi;
pi->next=NULL;//在表末插入
}
}
//合并相邻的内存
pf=pb=head;
while(pb->next!=NULL)
{
if(pf->end+2>pb->start)
{
pf->end=pb->end;
pf->next=pb->next;
}
pf=pb;
pb=pb->next;
}
return head;
}
int getstart(work*head,int size)
{
work *pb;
pb=head;
while(pb!=NULL)
{
if(pb->size==size)
{
return pb->start;
}
pb=pb->next;
}
return 0;
}
int alloc(mem *head,int size)
{
mem *pb;
pb=head;
int a;
while(pb!=NULL)
{
if(sizeend-pb->start+1))
{
a=pb->start;
pb->start=pb->start+size;
return a;
}
pb=pb->next;
}
return 0;
}
work*free1(work *head,int size)
{
work *pb,*pf;
while(head==NULL){printf("no this nod");goto end;}
pb=head;
while(pb->size!=size&&pb->next!=NULL)
{
pf=pb;
pb=pb->next;
}
if(pb->size==size)
{
if(pb==head)head=pb->next;
else pf->next=pb->next;
}
end:
return head;
}
void printw(work *head)
{
work *pb;
pb=head;
while(pb!=NULL)
{
printf("id start size---->\n");
printf("%d%7d%8d\n",pb->id,pb->start,pb->size);
pb=pb->next;
}
}
void printm(mem *head)
{
mem *pb;
pb=head;
while(pb!=NULL)
{
printf("start end---->\n");
printf("%d%9d\n",pb->start,pb->end);
pb=pb->next;
}
}
void main()
{
int wrec;//接收返回的地址
int mrec;
mem *mhead;
mhead=initmem(640);
work *whead;
//1
whead=initwork(130);
wrec=alloc(mhead,130);
//2
wrec=alloc(mhead,60);
whead=insertwork(whead,wrec,60);
//3
wrec=alloc(mhead,100);
whead=insertwork(whead,wrec,100);
//4
mrec=getstart(whead,60);
whead=free1(whead,60);
mhead=insertmem(mhead,mrec,60);
//5
wrec=alloc(mhead,200);
whead=insertwork(whead,wrec,200);
//6
mrec=getstart(whead,100);
whead=free1(whead,100);
mhead=insertmem(mhead,mrec,100);
//7
mrec=getstart(whead,130);
whead=free1(whead,130);
mhead=insertmem(mhead,mrec,130);
//8
wrec=alloc(mhead,140);
whead=insertwork(whead,wrec,140);
//9
wrec=alloc(mhead,60);
whead=insertwork(whead,wrec,60);
//10
wrec=alloc(mhead,50);
whead=insertwork(whead,wrec,50);
//11
mrec=getstart(whead,60);
whead=free1(whead,60);
mhead=insertmem(mhead,mrec,60);
printf("作业的链表\n");
printw(whead);
printf("========================\n");
printf("空闲分区链表\n");
printm(mhead);
}
首次适应算法：
#include "stdio.h"
struct allocquery /* 定义请求序列结构体*/
{
int num;
int state; /* a表示申请，f表示释放 */
int length;
};
struct allocquery allocq[11];
struct freequery /* 定义内存分配队列 */
{
int flag; /* IDNo. 0表示空闲，其他数值表示相应作业 */ int firstadd; /* 起始地址 */
int length; /* 占有长度 */
};
struct freequery freeq[11];
/* 首次适应算法函数*/
void first_alg(struct allocquery allocqnow,int *ptotal,struct freequery *pfreeq);
main()
{
int i,j;
FILE *fp;
char *fname="c:\\a.txt";
int Freetotal=1;
fp=fopen(fname,"w+");
allocq[0].num=1; allocq[0].state='a'; allocq[0].length=130; allocq[1].num=2; allocq[1].state='a'; allocq[1].length=60; allocq[2].num=3; allocq[2].state='a'; allocq[2].length=100; allocq[3].num=2; allocq[3].state='f'; allocq[3].length=60; allocq[4].num=4; allocq[4].state='a'; allocq[4].length=200; allocq[5].num=3; allocq[5].state='f'; allocq[5].length=100;
allocq[6].num=1; allocq[6].state='f'; allocq[6].length=130; allocq[7].num=5; allocq[7].state='a'; allocq[7].length=140; allocq[8].num=6; allocq[8].state='a'; allocq[8].length=60; allocq[9].num=7; allocq[9].state='a'; allocq[9].length=50; allocq[10].num=6; allocq[10].state='f'; allocq[10].length=60;
freeq[0].flag=0; freeq[0].firstadd=0; freeq[0].length=640;
for(i=0;i
{
first_alg(allocq[i],&Freetotal,freeq);
fprintf(fp,"\nTotal free blocks:%d ",Freetotal) ;
fprintf(fp,"\nIDNo. address length");
for(j=0;freeq[j].length!=0;j++)
fprintf(fp,"\n%5d%10d%10d",freeq[j].flag,freeq[j].firstadd,freeq[j].length);
}
}
void first_alg(struct allocquery allocqnow,int *ptotal,struct freequery *pfreeq)
{
int i,j,num;
int temp_num,temp_add,temp_length;
struct freequery temp_f1,temp_f2;
if (allocqnow.state=='a') /* 表示申请空间 */
{
for (i=0;i
{
if((pfreeq[i].flag==0)&(pfreeq[i].length>allocqnow.length)) {
temp_num=pfreeq[i].flag;
temp_add=pfreeq[i].firstadd+allocqnow.length;
temp_length=pfreeq[i].length-allocqnow.length;
pfreeq[i].flag=allocqnow.num;
pfreeq[i].length=allocqnow.length;
if (pfreeq[i+1].length==0)
{
pfreeq[i+1].flag=temp_num;
pfreeq[i+1].firstadd=temp_add;
pfreeq[i+1].length=temp_length;
}
else
if (pfreeq[i+1].firstadd!=temp_add)
{
temp_f1.flag=temp_num; temp_f1.firstadd=temp_add;
temp_f1.length=temp_length;
temp_f2=pfreeq[i+1];
for (j=i+1;pfreeq[j].length!=0;j++)
{
pfreeq[j]=temp_f1;
temp_f1=temp_f2;
temp_f2=pfreeq[j+1];
}
pfreeq[j]=temp_f1;
}
break;
}
}
}
else /* 释放空间*/
{
for (i=0;i
{
if (pfreeq[i].flag==allocqnow.num)
{
if ((pfreeq[i-1].flag==0)&(pfreeq[i+1].flag==0)&(i>0)) {
pfreeq[i-1].length=pfreeq[i-1].length+allocqnow.length+pfreeq[i+1].length;
for (j=i;pfreeq[j].length!=0;j++)
{
pfreeq[j].flag=pfreeq[j+2].flag;
pfreeq[j].firstadd=pfreeq[j].firstadd;
pfreeq[j].length=pfreeq[j].length;
}
}
else if ((pfreeq[i-1].flag==0)&(i>0))
{
pfreeq[i-1].length=pfreeq[i-1].length+allocqnow.length; for (j=i;pfreeq[j].length!=0;j++)
{
pfreeq[j].flag=pfreeq[j+1].flag;
pfreeq[j].firstadd=pfreeq[j+1].firstadd;
pfreeq[j].length=pfreeq[j+1].length;
}
}
else if (pfreeq[i+1].flag==0)
{
pfreeq[i].flag=0;
pfreeq[i].length=allocqnow.length+pfreeq[i+1].length; for (j=i+1;pfreeq[j].length!=0;j++)
{
pfreeq[j].flag=pfreeq[j+1].flag;
pfreeq[j].firstadd=pfreeq[j+1].firstadd;
pfreeq[j].length=pfreeq[j+1].length;
}
}
else
{
pfreeq[i].flag=0;
}
}
}
}
num=0; /* 统计空闲块*/
for (i=0;pfreeq[i].length!=0;i++)
if (pfreeq[i].flag==0) num++;
*ptotal=num;
}
四， 实验结果。
五、实验心得
通过这次实验，取用首次适应算法和最佳适应算法了解了动态分区分配方式中使用的数据结构和分配算法，以及了解了动态分区存储管理方式。