可变分区存储管理

1、沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 操作系统 ）实验题目： 可变分区存储管理 班 级 计算机131 学 号 姓 名 杨光成 地 点 实训F608 指导教师 吕海华 王黎明 实 验 日 期 : 2015 年 5 月 19 日一、 实验题目主存储器空间分配实验。二、实验要求编写一段程序来模拟可变分区管理方法。要求能通过文件形式定义空闲区表；能随意输入作业及需要分配的空间；能分别使用首次适应算法、最佳适应算法和最坏适应算法对输入的作业进行空间分配；能显示系统空闲表和已分配空间表。三、实验目的通过首次适应算法、最佳适应算法和最坏适应算法实现主存空间的分配，可以使读者可好地理解存储

2、分配算法。四、实验原理分析可变分区方式是按作业需要的主存空间大小来分区。当装入一个作业时，首先要查看是否有足够的空闲空间来分配，若有则按指定的分配方式进行分配；否则作业不能装入。随着作业的装入和撤离主存空间被分为若干个大大小小的不连续的区间，为了表明各区间的状态可以用一个内存分区表如表1所示来表示。表1 内存分区表起始地址长度标志120k20k作业1200k50k空闲这样我们可以定义一个如下的结构表示内存分区信息。typedef struct nodeint start;/起始地址int length; /长度char tag20;/标志job;可变分区的三种算法就是为作业分配主存空间的方法。

3、 首次适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入第一个满足条件的空间中去。 最佳适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最小的一个空间中去。 最坏适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最大的一个空间中去。从三种算法的说明可以看出，分配空间的过程主要可以分两步： 查询所有满足作业需求的空间块。 按照指定的算法将作业装入空间块中。在操作的最初主存空间实际就是一个大的空闲区，不涉及到如何分配的问题。为直接模拟运行一段时间后主存中出现了多个空闲块的状态，题目要求从一个文件读入空闲区表。在这里我们可以设计一个空

4、闲区表文件的结构为如表2所示：表2 空闲区表起始地址长度200k50k这样也可以方便地将空闲表一次读入程序中，而不必再一个个的输入。主要变量及函数说明如表3所示。表3 变量与函数说明表typedef struct node内存块结构job frees空闲区表job occupys已分配区表free_quantity空闲区数量occupy_quantity已分配区数量void initial()初始化函数int readData()从文件读入空闲表函数void sort()排序空闲表void view()显示分区信息void earliest()最先适应分配算法void excellent()最

5、优适应分配算法void worst()最坏适应算法mem.txt空闲表文件5、 实验代码清单1、主函数（如图1）void main()int ch;/算法选择标记cout请输入所使用的内存分配算法：n;coutch;while(ch3)coutch;Initblock(); /开创空间表int choice; /操作选择标记while(1)show();cout请输入您的操作：;coutchoice;if(choice=1) alloc(ch); / 分配内存else if(choice=2) / 内存回收int flag;coutflag;free(flag);else if(choice=

6、0) break; /退出else /输入操作有误cout输入有误，请重试！endl;continue;图12、分配主存（如图2）Status alloc(int ch)int request = 0;coutrequest;if(request0 |request=0) cout分配大小不合适，请重试！endl;return ERROR;if(ch=2) /选择最佳适应算法if(Best_fit(request)=OK) cout分配成功！endl;else cout内存不足，分配失败！endl;return OK;if(ch=3) /选择最差适应算法if(Worst_fit(request

7、)=OK) cout分配成功！endl;else cout内存不足，分配失败！endl;return OK;else /默认首次适应算法if(First_fit(request)=OK) cout分配成功！endl;else cout内存不足，分配失败！data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/有大小恰好合适的空闲块p-data.state=Busy;return OK;break;if(p-data

8、.state=Free & p-data.sizerequest)/有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;图34、最佳适应（如图4和图5）Status Best_fit(int request)int ch;

9、 /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /记录最佳插入位置while(p) /初始化最小空间和最佳位置if(p-data.state=Free & (p-data.size=request) )if(q=NULL)q=p;ch=p-data.size-request;else if(q-data.size p-data.size)q=p

10、;ch=p-data.size-request;p=p-next;if(q=NULL) return ERROR;/没有找到空闲块else if(q-data.size=request)q-data.state=Busy;return OK;elsetemp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;return OK;图4图55、最差适应（如图6）Status

11、 Worst_fit(int request)int ch; /记录最大剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /记录最佳插入位置while(p) /初始化最大空间和最佳位置if(p-data.state=Free & (p-data.size=request) )if(q=NULL)q=p;ch=p-data.size-request;else

12、if(q-data.size data.size)q=p;ch=p-data.size-request;p=p-next;if(q=NULL) return ERROR;/没有找到空闲块else if(q-data.size=request)q-data.state=Busy;return OK;elsetemp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;ret

13、urn OK;图6图76、主存回收和显示主存分配情况（如图8）Status free(int flag)DuLNode *p=block_first;for(int i= 0; i next;elsereturn ERROR;p-data.state=Free;if(p-prior!=block_first & p-prior-data.state=Free)/与前面的空闲块相连p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;p=p-prior;if(p-next!=block_last & p-next-data.state=Free)/与后面的空闲块相连p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next; if(p-next=block_last & p-next-data.state=Free)/与最后的空闲块相连p-data.size+=p-next-data.size;p-next=NULL; return O