OS实验指导三——存储器管理.doc

OS实验指导三 操作系统实验指导三 实验项目（三）基本存储器管理实验实验类型设计实验学时4一、实验目的理解分区式存储管理的基本原理，熟悉分区分配和回收算法。即理解在不同的存储管理方式下，如何实现主存空间的分配与回收；并掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、设备与环境 1. 硬件设备：PC机一台2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如VC VC+Java 等编程语言环境。三、实验原理实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。A、主存空间分配 （1）首次适应算法算法要求空闲分区表以地址递增的次序排列。在分配内存时，从表首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。若从头到尾不存在满足要求的分区，则分配失败。（2）最佳适应算法所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。（3）最坏适应算法最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 B、主存空间回收当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：a) 释放区下邻空闲区（低地址邻接）b) 释放区上邻空闲区（高地址邻接）c) 释放区上下都与空闲区邻接d) 释放区上下邻都与空闲区不邻接四、实验要求1. 模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。2. 采用首次适应法、最佳适应法、最坏适应法分配主存空间。3. 当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4. 当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5. 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。五、实验设计参考1.算法流图l main函数的流程图初始化first和end整理分区序号显示空闲分区链选择算法aa=1，首次适应算法a=2，最佳适应算法a=3，最坏适应算法选择操作ii=1，分配空间函数ai=0，退出程序i=2，回收空间函数结束l 分配空间的流程图分配空间函数a=1a=2a=3输入申请内存大小按顺序找空闲块初始化q，使它指向空闲块中长度小的一块输入申请内存大小初始化q，使它指向空闲块中长度大的一块p-data.length=requestp的状态为已分配剩下p-data.length-=request输入申请内存大小YYNN返回到整理分区序号p-data.lengthrequest分配不成功l 回收空间的流程图p的状态改为空闲回收p，p的前一个为firstp的后一个是endp的后一个状态空与后面空闲块相连将p 的状态改为空闲将p 的状态改为空闲回收空间函数p的后一个是endYNYNYNp的前一个状态空p的前一个状态空p的后一个状态空p的后一个状态空p的后一个状态空p的后一个状态空YYYNNN与前面空闲块相连p的状态改为空闲与前面空闲块相连与后面空闲块相连YN返回到整理分区序号2. 相关数据结构及关键函数说明 使用了struct free_table数据结构用来说明分区。包含：分区序号（num）、起始地址（address）、分区长度（length）和分区状态（state）。 使用了线性表的双向链表存储结构（struct Node），里面包含前驱指针（prior）和后继指针（next）。一开始定义一条（含有first和end）的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分配和回收。 在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）。其中： sort（）函数用来整理分区序号。如在删序号3时，它与前面序号2相连在一起了，然后序号2中的长度若满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了； allocation（）用来分配空间。也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）； recovery（）用来回收内存。包含四种情况的处理，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接。3.源码参考： #include#include#define OK 1 /完成#define ERROR 0 /出错typedef int Status;typedef struct free_table/定义一个空闲区说明表结构 int num; /分区序号 long address; /起始地址 long 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)malloc(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-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) printf(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) /有大小恰好合适的空闲块 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-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-data.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.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 Worst_fit(int request) int ch; /记录最大剩余空间 Node *p=first-next; 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-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-data.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(请输入申请分配的主存大小(单位: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-data.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) 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-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(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(*n); printf(tt用以下三种方法实现主存空间的分配n); printf(t(1)首次适应算法t(2)最佳适应算法t(3)最差适应算法n);printf(*n); printf(n); printf(请输入所使用的内存分配算法:); scanf(%d,&a); while(a3) printf(输入错误，请重新输入所使用的内存分配算法:n); scanf(%d,&a); switch(a) case 1:printf(nt*使用首次适应算法：*n);break; case 2:print