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

实验二：存储器的分配与回收算法实现 作者： 日期：2 个人收集整理 勿做商业用途实验报告学院（系）名称：计算机与通信工程学院姓名 刘俊杰学号20115542专业信息与计算科学班级2011级1班实验项目实验二：存储器的分配与回收算法实现课程名称操作系统课程代码0668036实验时间201311-27 3-4节2013-1129 7-8节2013-12-4 3-4节 2013-12-6 78节实验地点主校区7215批改意见成绩教师签字: 实验内容：1 本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业.2 采用最先适应法、最佳适应法、最坏适应法分配主存空间。3 当一个新作业要求装入主存时,必须查空闲区表,从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4 当一个作业撤离时，归还的区域如果与其他空闲区相邻,则应合并成一个较大的空闲区，登在空闲区表中。5 设计的模拟系统中，进程数不小于5，进程调度方式可以采用实验一中的任何一种。6 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。实验要求：1 详细描述实验设计思想、程序结构及各模块设计思路;2 详细描述程序所用数据结构及算法；3 明确给出测试用例和实验结果；4 为增加程序可读性，在程序中进行适当注释说明；5 认真进行实验总结，包括:设计中遇到的问题、解决方法与收获等;6 实验报告撰写要求结构清晰、描述准确逻辑性强；7 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。代码实现：includestdio.hincludemalloc.hdefine 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；p1address=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”，&pname，&psize);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！=NULLp0-sizenext；if（p0sizea-size)p0size=p0sizeasize；aaddress=p0-address;p0address=p0address+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(p0next！=NULL&p0-sizenext; if（p0-sizea-size) p1=p0; p0=p0next；else printf（无法分配!n”）；while(p0！=NULL)if（p0-sizep1-size）p0=p0-next；else if(p0sizep1size)&(p0-sizea-size)）p1=p0；p0=p0next；p1size=(p1size）-（a-size）；aaddress=p1-address;p1-address=（p1address）+（asize)；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&p0sizesize）p0=p0-next;if(p0sizea-size） p1=p0； p0=p0-next；elseprintf(无法分配！n”）；while（p0!=NULL） if（p0-sizenext；else if(p0-sizep1-size）p1=p0;p0=p0next;p1-size=(p1-size)-（asize)；a-address=p1-address;p1address=(p1address)+（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=aname；p0-size=asize；p0-address=ORIGI；p0next=NULL；head=p0；Else p1-name=a-name;p1-size=a-size;p1-address=aaddress；p2=head;while（p2next！=NULL) p2=p2-next; p2next=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（p1name!=p2name)(p2next!=NULL)）p3=p2;p2=p2-next;if(p1name=p2name)if（p2=head)head=p2next;elsep3next=p2next;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）(p2next！=NULL)）p2=p2next; if(num=p2name)p1name=p2name；p1-size=p2-size；p1-address=p2address；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（(p1addressm-address)&(p1next！=NULL)p2=p1;p1=p1-next；if（maddressp1address）if(head=p1)p3-size=m-size;p3address=maddress；if（p1addressp3-address）=(p3-size）)p1-address=p3-address;p1-size=p3size+p1-size; elsehead=p3;p3next=p1；elsep3size=msize；p3address=maddress;if（(p1-addressp3address）=(p3-size）p1-address=p3-address；p1size=p3size+p1size;if（p3addressp2-address)=(p2-size）p2-size=p1size+p2size;p2next=p1-next;elsep2next=p1;elseif（(p3-addressp2address）=(p2size)p2-size=p2size+p3-size；elsep3next=p1;p2next=p3;elsep3-size=msize；p3address=maddress；if(p3-address-p1address)=（p1size)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,m1address，m1size）；m1=m1next;if(n1=NULL）printf（已分配表为空！n);elsewhile(n1!=NULL)printf（已分配单元地址为%d,其大小为d,其名称为dn”,n1-address，n1size，n1-name）;n1=n1next; 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页