1、操作系统实验四报告主存空间分配和回收含源码分析 计算机 学院 计算机科学与技术 专业 班学号 姓名 教师评定_ 实验题目 主存空间的分配和回收 一、实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以
2、调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。三、实验主要仪器设备和材料实验环境硬件环境：I
3、BM-PC或兼容机软件环境：VC+ 6.0四、实验原理及设计分析某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、 作业2 申请60KB、 作业3 申请100KB 、 作业2 释放 60KB 、 作业4 申请 200KB、 作业3释放100KB、 作业1 释放130KB 、 作业5申请140KB 、 作业6申请60KB 、作业7申请50KB） 当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时
4、间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为
5、“1”。设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。3、主存空间分配 （1）首次适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配
6、存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。（2）最佳适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中（3）最坏适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开
7、始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。4、主存空间回收 当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：（1）释放区下邻空闲区（低地址邻接）（2）释放区上邻空闲区（高地址邻接）（3）释放区上下都与空闲区邻接（4）释放区上下邻都与空闲区不邻接五、程序流程图main函数里的流程图分配空间里的流程图回收空间里的流程图p的状态改为空闲回收p，p的前一个
8、为firstp的后一个是endp的后一个状态空与后面空闲块相连将p 的状态改为空闲将p 的状态改为空闲回收空间函数p的后一个是endYNYNYNp的前一个状态空p的前一个状态空p的后一个状态空p的后一个状态空p的后一个状态空p的后一个状态空YYYNNN与前面空闲块相连p的状态改为空闲与前面空闲块相连与后面空闲块相连YN返回到整理分区序号六、相关数据结构及关键函数说明本程序采用了一个struct free_table数据结构，里面包含分区序号（num）、起始地址（address）、分区长度（length）和分区状态（state）。还用了线性表的双性链表存储结构（struct Node），里面包含
9、前区指针（prior）和后继指针（next）。一开始定义一条（含有first和end）的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分配和回收。在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函数是用来整理分区序号的，如在删序号3时，她与前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了；allocation（）是
10、分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）；recovery（）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。七、源代码#include#include#define OK 1 /完成#define ERROR 0 /出错typedef int Status;typedef struct free_table/定义一个空闲区说明表结构 int num; /分区序号 long address; /起始地址 long
11、 length; /分区大小 int state; /分区状态ElemType;typedef struct Node/ 线性表的双向链表存储结构 ElemType data; struct Node *prior; /前趋指针 struct Node *next; /后继指针Node,*LinkList; LinkList first; /头结点LinkList end; /尾结点int flag;/记录要删除的分区序号Status Initblock()/开创带头结点的内存空间链表 first=(LinkList)malloc(sizeof(Node); end=(LinkList)mal
12、loc(sizeof(Node); first-prior=NULL; first-next=end; end-prior=first; end-next=NULL; end-data.num=1; end-data.address=40; end-data.length=600; end-data.state=0; return OK;void sort()/分区序号重新排序 Node *p=first-next,*q; q=p-next; for(;p!=NULL;p=p-next) for(q=p-next;q;q=q-next) if(p-data.num=q-data.num) q-
13、data.num+=1; /显示主存分配情况void show() int flag=0;/用来记录分区序号 Node *p=first; p-data.num=0; p-data.address=0; p-data.length=40; p-data.state=1; sort(); printf(ntt主存空间分配情况n); printf(*nn); printf(分区序号t起始地址t分区大小t分区状态nn); while(p) printf(%dtt%dtt%d,p-data.num,p-data.address,p-data.length); if(p-data.state=0) pr
14、intf(tt空闲nn); else printf(tt已分配nn); p=p-next; printf(*nn);/首次适应算法Status First_fit(int request) /为申请作业开辟新空间且初始化 Node *p=first-next; LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; p-data.num=1; while(p) if(p-data.state=0)&(p-data.length=request) /有大小恰好合适的空闲块
15、p-data.state=1; return OK; break; else if(p-data.state=0) & (p-data.lengthrequest) /有空闲块能满足需求且有剩余 temp-prior=p-prior; temp-next=p; temp-data.address=p-data.address; temp-data.num=p-data.num; p-prior-next=temp; p-prior=temp; p-data.address=temp-data.address+temp-data.length; p-data.length-=request; p
16、-data.num+=1; return OK; break; p=p-next; return ERROR;/最佳适应算法Status Best_fit(int request) int ch; /记录最小剩余空间 Node *p=first; Node *q=NULL; /记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; p-data.num=1; while(p) /初始化最小空间和最佳位置 if(p-data.state=0) & (p-d
17、ata.length=request) ) if(q=NULL) q=p; ch=p-data.length-request; else if(q-data.length p-data.length) q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/没有找到空闲块 else if(q-data.length=request) q-data.state=1; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.addr
18、ess; temp-data.num=q-data.num; q-prior-next=temp; q-prior=temp; q-data.address+=request; q-data.length=ch; q-data.num+=1; return OK; return OK;/最差适应算法Status Worst_fit(int request) int ch; /记录最大剩余空间 Node *p=first-next; Node *q=NULL; /记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.len
19、gth=request; temp-data.state=1; p-data.num=1; while(p) /初始化最大空间和最佳位置 if(p-data.state=0 & (p-data.length=request) ) if(q=NULL) q=p; ch=p-data.length-request; else if(q-data.length data.length) q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/没有找到空闲块 else if(q-data.length=request) q-d
20、ata.length=1; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; temp-data.num=q-data.num; q-prior-next=temp; q-prior=temp; q-data.address+=request; q-data.length=ch; q-data.num+=1; return OK; return OK;/分配主存Status allocation(int a) int request;/申请内存大小 printf(请输入申请分配的
21、主存大小(单位:KB):); scanf(%d,&request); if(requestnext) if(q=p) if(q-prior-data.state=0&q-next-data.state!=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=q-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-data.state=0) q-data.length+=q-next-da
22、ta.length; q-next=q-next-next; q-next-next-prior=q; q-data.state=0; q-data.num=flag; if(q-prior-data.state=0&q-next-data.state=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=q-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-data.state!=0
23、) q-data.state=0; return OK;Status deal2(Node *p)/处理回收空间 Node *q=first; for(;q!=NULL;q=q-next) if(q=p) if(q-prior-data.state=0&q-next-data.state!=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=p-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q
24、-next-data.state=0) q-data.state=0; if(q-prior-data.state=0&q-next-data.state=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=q-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-data.state!=0) q-data.state=0; return OK;/主存回收Status recovery(
25、int flag) Node *p=first; for(;p!=NULL;p=p-next) if(p-data.num=flag) if(p-prior=first) if(p-next!=end)/当前P指向的下一个不是最后一个时 if(p-next-data.state=0) /与后面的空闲块相连 p-data.length+=p-next-data.length; p-next-next-prior=p; p-next=p-next-next; p-data.state=0; p-data.num=flag; else p-data.state=0; if(p-next=end)/当前P指向的下一个是最后一个时 p-data.state=0; /结束if(p-prior=block_first)的情况 else if(p-prior!=first) if(p-next!=end) deal1(p); else deal2(p); /结束if(p-prior!=block_first)的情况 /结束if(p-data.num=flag)的情况 printf(t*回收成功*); return OK; /主函数void main() int i; /操作选择标记 int a;/算法选择标记 printf(*
