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

1、实验二、 可变分区存储管理一、 实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给

2、该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、 实验主要仪器设备和材料 实验环境 硬件环境：IBM-PC或兼容机 软件环境：VC+ 6.0 四、 实验原理及设计分析 某系统采用可变分区存储管理

3、，在系统运行当然开始，假设初始状态下，可用的内存空间为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内存。作

4、业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。 2 空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。 设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配

5、时，系统优先使用空闲低端的空间。 设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。 2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。 3、主存空间分配 （1）首次适应算法 在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个

6、能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。 （2）最佳适应算法 在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中 4、主存空间回收 当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况： （

7、1） 释放区下邻空闲区（低地址邻接） （2） 释放区上邻空闲区（高地址邻接） （3） 释放区上下都与空闲区邻接 （4） 释放区上下邻都与空闲区不邻接 五、测试及实现效果 1、首次适应算法 分配内存 分配结果 回收内存2、最佳适应算法 分配内存查看内存释放内存六、附录（实验代码）#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream.h>#include <windows.h>#define Free 0 /空闲状态#define Bus

8、y 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错 #define Status int;int n=0; /判断是否要开创空间表long MAX_length;/最大内存空间typedef struct FreeArea/定义一个空闲区说明表结构int number; /分区号long size; /分区大小long address; /分区地址int state; /状态ElemType;/ 线性表的双向链表存储结构 typedef struct DuLNode ElemType data; struct DuLNode *prior; /前趋指针st

9、ruct DuLNode *next; /后继指针DuLNode,*DuLinkList;DuLinkList first; /头结点DuLinkList last; /尾结点Status allocation(int);/内存分配Status free(int); /内存回收Status FirstFit(int,int);/首次适应算法Status BestFit(int,int); /最佳适应算法void show();/查看分配Status InitList();/开创空间表Status InitList()/开创带头结点的内存空间链表first=(DuLinkList)malloc(

10、sizeof(DuLNode);last=(DuLinkList)malloc(sizeof(DuLNode);first->prior=NULL;first->next=last;last->prior=first;last->next=NULL;last->data.address=0;last->data.size=MAX_length;last->data.number=0;last->data.state=Free;return OK;/ 分 配 主 存 Status allocation(int ch)int number,reque

11、st;printf("请输入作业(分区号):"); scanf("%d",&number);printf("请输入需要分配的主存大小(单位:KB)："); scanf("%d",&request);if(request<0 |request=0) printf("分配大小不合适，请重试!n"); return ERROR;if(ch=2) /选择最佳适应算法 if(BestFit(number,request)=OK) printf("分配成功!n");

12、 else printf("内存不足，分配失败!"); return OK;else /默认首次适应算法 if(FirstFit(number,request)=OK) printf("分配成功!n"); else printf("内存不足，分配失败!"); return OK;/ 首次适应算法Status FirstFit(int number,int request)/传入作业名及申请量DuLinkList DLL=(DuLinkList)malloc(sizeof(DuLNode); /为申请作业开辟新空间且初始化DLL->

13、;data.number=number; DLL->data.size=request;DLL->data.state=Busy;DuLNode *p=first->next;while(p) if(p->data.state=Free && p->data.size=request)/有大小恰好合适的空闲块 p->data.state=Busy;p->data.number=number;return OK; break;if(p->data.state=Free && p->data.size>re

14、quest)/有空闲块能满足需求且有剩余"DLL->prior=p->prior;DLL->next=p; DLL->data.address=p->data.address;p->prior->next=DLL; p->prior=DLL;p->data.address=DLL->data.address+DLL->data.size; p->data.size-=request; return OK;break;p=p->next;return ERROR;/ 最佳适应算法 Status BestFit

15、(int number,int request)int ch; /记录最小剩余空间DuLinkList DLL=(DuLinkList)malloc(sizeof(DuLNode); DLL->data.number=number; DLL->data.size=request;DLL->data.state=Busy;DuLNode *p=first->next;DuLNode *q=NULL; /记录最佳插入位置while(p) /初始化最小空间和最佳位置if(p->data.state=Free &&(p->data.size>r

16、equest | p->data.size=request) ) q=p;ch=p->data.size-request; break;p=p->next;while(p) if(p->data.state=Free && p->data.size=request)/空闲块大小恰好合适p->data.number=number;p->data.state=Busy;return OK; break;if(p->data.state=Free && p->data.size>request)/空闲块大于分

17、配需求if(p->data.size-request<ch)/剩余空间比初值还小 ch=p->data.size-request;/更新剩余最小值 q=p;/更新最佳位置指向 p=p->next;if(q=NULL) return ERROR;/没有找到空闲块else/找到了最佳位置并实现分配 DLL->prior=q->prior; DLL->next=q; DLL->data.address=q->data.address; q->prior->next=DLL; q->prior=DLL; q->data.ad

18、dress+=request; q->data.size=ch; return OK;/ 释放内存 Status free(int number)DuLNode *p=first;while(p) if(p->data.number=number)p->data.state=Free;p->data.number=Free;if(p->prior->data.state=Free)/与前面的空闲块相连p->prior->data.size+=p->data.size;p->prior->next=p->next;p->

19、;next->prior=p->prior; if(p->next->data.state=Free)/与后面的空闲块相连p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next; break; p=p->next;return OK;/ 显示内存存分配情况 void show()printf("* 内 存 分 配 情 况 *n");DuLNode *p=first->next;while

20、(p) printf("分 区 号："); if(p->data.number=Free) printf("Freen"); else printf("%dn",p->data.number); printf("起始地址：%ldn",p->data.address); printf("分区大小：%ldKBn",p->data.size); printf("状 态："); if(p->data.state=Free) printf("空

21、闲n"); else printf("已分配!n"); printf("-n"); p=p->next;/ 主 函 数void main()/system("color 1D");printf("n");printf("- 动态内存分配管理 -n");printf("n");int ch,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