操作系统-可变分区存储管理

实验二、可变分区存储管理实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。实验主要仪器设备和材料实验环境硬件环境：IBM-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，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。2空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。3、主存空间分配（1）首次适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。（2）最佳适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中4、主存空间回收当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：（1）释放区下邻空闲区（低地址邻接）（2）释放区上邻空闲区（高地址邻接）（3）释放区上下都与空闲区邻接（4）释放区上下邻都与空闲区不邻接五、测试及实现效果1、首次适应算法分配内存分配结果回收内存2、最佳适应算法分配内存查看内存释放内存六、附录（实验代码）#include<>#include<>#include<>#include<>#include<>#defineFree0//空闲状态#defineBusy1//已用状态#defineOK1//完成#defineERROR0//出错#defineStatusint;intn=0;//判断是否要开创空间表longMAX_length;//最大内存空间typedefstructFreeArea//定义一个空闲区说明表结构{ intnumber;//分区号 longsize;//分区大小 longaddress;//分区地址 intstate;//状态}ElemType;//线性表的双向链表存储结构typedefstructDuLNode{ ElemTypedata; structDuLNode*prior;//前趋指针 structDuLNode*next;//后继指针}DuLNode,*DuLinkList;DuLinkListfirst;//头结点DuLinkListlast;//尾结点Statusallocation(int);//内存分配Statusfree(int);//内存回收StatusFirstFit(int,int);//首次适应算法StatusBestFit(int,int);//最佳适应算法voidshow();//查看分配StatusInitList();//开创空间表StatusInitList()//开创带头结点的内存空间链表{ first=(DuLinkList)malloc(sizeof(DuLNode)); last=(DuLinkList)malloc(sizeof(DuLNode)); first->prior=NULL; first->next=last; last->prior=first; last->next=NULL; last->=0; last->=MAX_length; last->=0; last->=Free; returnOK;}//分配主存Statusallocation(intch){ intnumber,request; printf("请输入作业(分区号):"); scanf("%d",&number); printf("请输入需要分配的主存大小(单位:KB)："); scanf("%d",&request); if(request<0||request==0) { printf("分配大小不合适，请重试!\n"); returnERROR; } if(ch==2)//选择最佳适应算法 { if(BestFit(number,request)==OK)printf("分配成功!\n"); elseprintf("内存不足，分配失败!"); returnOK; } else//默认首次适应算法 { if(FirstFit(number,request)==OK)printf("分配成功!\n"); elseprintf("内存不足，分配失败!"); returnOK; }}//首次适应算法StatusFirstFit(intnumber,intrequest)//传入作业名及申请量{ DuLinkListDLL=(DuLinkList)malloc(sizeof(DuLNode));//为申请作业开辟新空间且初始化 DLL->=number; DLL->=request; DLL->=Busy; DuLNode*p=first->next; while(p) { if(p->==Free&&p->==request)//有大小恰好合适的空闲块 { p->=Busy; p->=number; returnOK; break; } if(p->==Free&&p->>request)//有空闲块能满足需求且有剩余" { DLL->prior=p->prior; DLL->next=p; DLL->=p->; p->prior->next=DLL; p->prior=DLL; p->=DLL->data.address+DLL->; p->-=request; returnOK; break; } p=p->next; } returnERROR;}//最佳适应算法StatusBestFit(intnumber,intrequest){ intch;//记录最小剩余空间 DuLinkListDLL=(DuLinkList)malloc(sizeof(DuLNode)); DLL->=number; DLL->=request; DLL->=Busy; DuLNode*p=first->next; DuLNode*q=NULL;//记录最佳插入位置 while(p)//初始化最小空间和最佳位置 { if(p->==Free&&(p->>request||p->==request)) { q=p; ch=p->-request; break; } p=p->next; } while(p) { if(p->==Free&&p->==request)//空闲块大小恰好合适 { p->=number; p->=Busy; returnOK; break; } if(p->==Free&&p->>request)//空闲块大于分配需求 { if(p->-request<ch)//剩余空间比初值还小 { ch=p->-request;//更新剩余最小值 q=p;//更新最佳位置指向 } } p=p->next; } if(q==NULL)returnERROR;//没有找到空闲块 else {//找到了最佳位置并实现分配 DLL->prior=q->prior; DLL->next=q; DLL->=q->;q->prior->next=DLL;q->prior=DLL;q->+=request;q->=ch;returnOK; }}//释放内存Statusfree(intnumber){ DuLNode*p=first; while(p) { if(p->==number) { p->=Free; p->=Free; if(p->prior->==Free)//与前面的空闲块相连 { p->prior->+=p->; p->prior->next=p->next; p->next->prior=p->prior; } if(p->next->==Free)//与后面的空闲块相连 { p->+=p->next->; p->next->next->prior=p; p->next=p->next->next; } break; } p=p->next; } returnOK;}//显示内存存分配情况voidshow(){ printf("********内存分配情况********\n"); DuLNode*p=first->next; while(p) { printf("分区号："); if(p->==Free)printf("Free\n");elseprintf("%d\n",p->);printf("起始地址：%ld\n",p->);printf("分区大小：%ldKB\n",p->);printf("状态：");if(p->==Free)printf("空闲\n");elseprintf("已分配!\n");printf("---------------------------------------\n");p=p->next; }}//主函数voidmain(){ //system("color1D"); printf("\n"); printf("-----------动态内存分配管理-----------\n"); printf("\n"); intch,d=0;//算法选择标记 printf("--1.首次适应算法--\n"); printf("--2.最佳适应算法--\n"); printf("--0.退出--\n"); printf("\n"); printf("-----------------------------------------------------------\n"); printf("请选择分配算法：");scanf("%d",&ch); printf("\n"); printf("请输入内存空间的大小(单位:KB)："); scanf("%ld",&MAX_length); printf("\n"); if(ch==0||ch==1||ch==2)d++; while(d==0) { printf("数字不正确，请选择0--2之间的数字\n"); scanf("%d",&ch); if(ch==0||ch==1||ch==2)d++; } if(ch==0)exit(0); if(n==0)InitList();//开创空间表 intselection;//操作选择标记 while(1) { printf("-----------