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

实验报告学院（系）名称：计算机与通信工程学院姓名 刘俊杰学号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#include#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-sizesize)p0=p0-next;if(p0-sizea-size)p0-size=p0-size-a-size;a-address=p0-address;p0-address=p0-address+a-size;elseprintf(无法分配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-sizesize)p0=p0-next; if(p0-sizea-size) p1=p0; p0=p0-next;else printf(无法分配!n);while(p0!=NULL)if(p0-sizep1-size)p0=p0-next;else if(p0-sizesize)&(p0-sizea-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-sizesize)p0=p0-next;if(p0-sizea-size) p1=p0; p0=p0-next;elseprintf(无法分配!n);while(p0!=NULL) if(p0-sizesize)p0=p0-next;else if(p0-sizep1-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;elsep3-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-addressaddress)&(p1-next!=NULL)p2=p1;p1=p1-next;if(m-addressaddress)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; elsehead=p3;p3-next=p1;elsep3-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;elsep2-next=p1;elseif(p3-address-p2-address)=(p2-size)p2-size=p2-size+p3-size;elsep3-next=p1;p2-next=p3;elsep3-size=m-size;p3-address=m-address;if(p3-address-p1-address)=(p1-size)p1-size=p1-size+p3-size; elsep1-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);elsewhile(m1!=NULL)printf(空闲单元地址为%d,其大小为%dn,m1-address,m1-size);m1=m1-next;if(n1=NULL)printf(已分配表为空!n);elsewhile(n1!=NULL)printf(已分配单元地址为%d,其大小为%d,其名称为%dn,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()