操作系统实验四报告材料-主存空间分配和回收(含源码)

计算机 学院 计算机科学与技术 专业 班学号

姓名 教师评定_________________ 实验题目 主存空间的分配和回收

一、实验目的

熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。

二、实验内容和要求

主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。

可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。

实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。

三、实验主要仪器设备和材料

实验环境

硬件环境：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、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。

精彩文档

实用标准文案

空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。

设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。

设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。

2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。

3、主存空间分配 （1）首次适应算法

在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。 （2）最佳适应算法

在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中 （3）最坏适应算法

在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。 4、主存空间回收

当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：

（1） 释放区下邻空闲区（低地址邻接） （2） 释放区上邻空闲区（高地址邻接） （3） 释放区上下都与空闲区邻接 （4） 释放区上下邻都与空闲区不邻接 五、程序流程图 main函数里的流程图

精彩文档

实用标准文案

选择算法a a=1，首次适应算法 a=2，最佳适应算法 初始化first和end 整理分区序号 显示空闲分区链 a=3，最坏适应算法 选择操作i i=1，分配空间函数a i=0，退出程序 结束 i=2，回收空间函数

分配空间里的流程图

精彩文档

实用标准文案

分配空间函数 a=1 a=2 a=3 输入申请内存大小 初始化q，使它指向空闲块中长度小的一块 初始化q，使它指向空闲块中长度大的一块 按顺序找空闲块 输入申请内存大小 输入申请内存大小 p->data.length>request Y p的状态为已分配 Y N p->data.length=request 剩下 p->data.length-=request N 分配不成功 返回到整理分区序号

回收空间里的流程图

精彩文档

实用标准文案

回收空间函数 回收p，p的前一个为first N Y p的后一个是end Y N p的后一个状态空 Y p的后一个是end N 将p 的状态改为空闲 p的前一p的前一个状态空 Y 与后面空闲块相连 N 将p 的状态改为空闲 个状态空 Y N N Y p的后一个状态空 p的后一个状态空 p的后一个状态空 p的后一个状态空 Y 与前面空闲块相连 N p的状态改为空闲 p的状态改为空闲 与前面空闲块相连 与后面空闲块相连 返回到整理分区序号

六、相关数据结构及关键函数说明

本程序采用了一个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（）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。

七、源代码

#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(\"\\n\\》主存空间分配情况《\\n\");

printf(\"**********************************************************\\n\\n\"); printf(\"分区序号\起始地址\分区大小\分区状态\\n\\n\"); while(p) {

printf(\"%d\\%d\\%d\ if(p->data.state==0) printf(\"\\空闲\\n\\n\"); else printf(\"\\已分配\\n\\n\"); p=p->next; }

printf(\"**********************************************************\\n\\n\"); }

精彩文档

实用标准文案

//首次适应算法

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.length>request)) {//有空闲块能满足需求且有剩余 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 < 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.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\ if(request<0 ||request==0) {

printf(\"分配大小不合适，请重试！\"); return ERROR; }

switch(a) {

case 1: //默认首次适应算法

if(First_fit(request)==OK) printf(\"\****分配成功！****\"); else printf(\"\****内存不足，分配失败！****\"); return OK; break;

case 2: //选择最佳适应算法

if(Best_fit(request)==OK) printf(\"\****分配成功！****\"); else printf(\"\****内存不足，分配失败！****\"); return OK; break; case 3: //选择最差适应算法

if(Worst_fit(request)==OK) printf(\"\****分配成功！****\"); else printf(\"\****内存不足，分配失败！****\"); return OK; break; } }

Status deal1(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=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(\"\****回收成功****\"); return OK; }

//主函数 void main() {

int i; //操作选择标记 int a;//算法选择标记

printf(\"**********************************************************\\n\"); printf(\"\\用以下三种方法实现主存空间的分配\\n\");

printf(\"\(1)首次适应算法\(2)最佳适应算法\(3)最差适应算法\\n\"); printf(\"**********************************************************\\n\"); printf(\"\\n\");

printf(\"请输入所使用的内存分配算法:\"); scanf(\"%d\ while(a<1||a>3) {

printf(\"输入错误，请重新输入所使用的内存分配算法:\\n\"); scanf(\"%d\ }

精彩文档

实用标准文案

switch(a) { case 1:printf(\"\\n\****使用首次适应算法：****\\n\");break; case 2:printf(\"\\n\****使用最佳适应算法：****\\n\");break; case 3:printf(\"\\n\****使用最坏适应算法：****\\n\");break; }

Initblock(); //开创空间表 while(1) {

show();

printf(\"\1: 分配内存\2: 回收内存\0: 退出\\n\"); printf(\"请输入您的操作：\"); scanf(\"%d\ if(i==1)

allocation(a); // 分配内存 else if(i==2) // 内存回收 {

printf(\"请输入您要释放的分区号：\"); scanf(\"%d\ recovery(flag); }

else if(i==0) { printf(\"\\n退出程序\\n\"); break; //退出 }

else //输入操作有误 {

printf(\"输入有误，请重试！\"); continue; } } }

八、执行结果和结果分析

精彩文档

实用标准文案

初始化首次适应算法：

当作业1、2、3顺利分配内存空间后：

回收序号2里面的内存：

分配作业4：

精彩文档

实用标准文案

回收序号3里面的内存（与上邻序号2相连了）

精彩文档

实用标准文案

回收序号1里的内存（与下邻序号2相连了）

继续分配（会发现总是按顺序查找满足要求的第一个空闲块，一旦发现就会分配）：

精彩文档

实用标准文案

初始化最佳适应算法：

精彩文档

实用标准文案

精彩文档

实用标准文案

继续分配（会发现总是查找满足要求的空闲块且其比其他空闲块长度小，一旦发现就会分配）：

精彩文档

实用标准文案

精彩文档

实用标准文案

初始化最坏适应算法：

精彩文档

实用标准文案

继续分配（会发现总是查找满足要求的空闲块且其比其他空闲块长度小，一旦发现就会分配）：

精彩文档

实用标准文案

精彩文档

实用标准文案

九、所遇困难的解决以及心得体会

本实验我采取用一条链表同时表示空闲分区链和主存空间占用情况，因为主存总大小是固定的，把空闲分区链所表示的区域从总的内存里去除就是被占用的空间的大小，这个实验还是比较简单的，但在执行过程中还是遇到了很多问题，如在回收空间的函数中，因为要考虑到四种情况，我一开始的想法是这样的：让p指向链表开头，一直等找到p所指向的分区序号等于要删除的分区序号，然后开始执行，当p->prior不是链首first时要考虑p->next是不是链尾end，然后继续考虑p的前向指针和后向指针得状态是否为空闲；等考虑完p->prior不是链首了，就进行考虑p->prior是链首的问题，然后又进行了考虑p->next是不是链尾end，然后继续考虑p的前向指针和后向指针得状态是否为空闲；等考虑完了p->prior的问题又进行考虑p->next的问题，一直这样重复了，我都不知道，当时超烦的，后来静下心重新检查自己写得程序，才知道自己写得这个函数好凌乱。后来我直接把p->next=end的情况去掉了。才使得程序出现好转。当解决了回收问题，发现在回收后有有作业请求分配时，分配序号会出现这种情况，就是有分区序号相等的情况，如下图（a）；后来我采用了一个sort（）整理分区序号，一开始我把这个函数放到三个算法函数中，还是没有发生改变。然后我又继续检查程序，想到函数sort（）放到show（）函数中会怎样呢？没想到对了，真的能改变分区序号的值，如图（b）。其实sort（）就是实现图（c）里面的功能。当然还不止这两个问题的，不过在这过程序中，整理分区序号和回收内存是让我花的时间最多去解决的问题。总之这次收获还挺大的。

图（a）

精彩文档

实用标准文案

图（b）

图（c）

精彩文档