主存储器空间的分配和回收.doc

实验三 主存储器空间的分配和回收

【实习内容】

主存储器空间的分配和回收。

【实习目的】

一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。

【实习题目】

在可变分区管理方式下采用首次适应算法实现主存分配和实现主存回收。

0
5k
10k
14k
26k
32k
 128k
（1）可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：33
 操作系统

作业1

作业3

空闲区

作业2

空闲区

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

起 址
长 度
状 态
第一栏
14 K
12 K
未 分 配
第二栏
32 K
96 K
未 分 配

空 表 目

空 表 目

空 表 目

空 表 目

空 表 目

其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。
上述的这张说明表的登记情况是按提示

（1）中的例所装入的三个作业占用的主存区域后填写的。

(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。

为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

(3) 采用首次适应算法分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实习是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图4-1。

(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。

(5) 请按首次适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请为这些作业进行主存的分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

【实验流程图】

【源程序】

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int CANUSE = 1;
const int CANTUSE = 0;
//#define MSIZE 128;
const int MSIZE = 128;
//内存分区

struct MZone
{
//空闲区起始地址
int begin_addr;
//一个连续空闲区的长度
int length;
//状态
int state;
//内存中任务名
char task_name[32];
//指向下一个空闲分区
struct MZone *next;
};

//内存头指针
struct MZone *Mhead = NULL;

//showmemory函数，显示当前内存分配情况
void showmemory()
{
struct MZone *Mpoint = Mhead;
printf("内存的使用情况\n");
printf("beginaddr\tlength\tstate\ttask\n");

while( NULL!=Mpoint)
{
printf("%dk\t\t",Mpoint->begin_addr);
printf("%dk\t",Mpoint->length);
Mpoint->state?printf("CANUSE\t"):printf("CANTUSE\t");
printf("%s\n",Mpoint->task_name);
Mpoint = Mpoint->next;
}

system("pause");
}
//Minsert函数，功能插入任务到空闲分区
int Minsert(struct MZone* Mnew)
{
struct MZone *Zinsert = Mhead;

//flag用于指示是Zinsert到了NULL，既没有内存可以分配
int flag = 1;

while( Zinsert->length<Mnew->length || !Zinsert->state)
{
if( NULL!=Zinsert->next )
{
Zinsert = Zinsert->next;
}
else
{
Zinsert = Zinsert->next;
break;
}

}

if( NULL==Zinsert )
{
return 0;
}

if( MSIZE == Zinsert->begin_addr+Mnew->length )
{
Zinsert->state = CANTUSE;
strcpy(Zinsert->task_name , Mnew->task_name);
Zinsert->next = NULL;
return 1;
}
else
{
struct MZone *Ztail = (struct MZone *)malloc(sizeof(struct MZone));
Zinsert->state = CANTUSE;
strcpy(Zinsert->task_name , Mnew->task_name);
Zinsert->length = Mnew->length;
Zinsert->next = Ztail;

memset( Ztail, 0, sizeof(char)*32 );
Ztail->begin_addr = Zinsert->begin_addr + Mnew->length;
Ztail->state = CANUSE;
Ztail->length = MSIZE - Ztail->begin_addr;
Ztail->next = NULL;
return 1;

}
}

//memoallocate函数，用于分配内纯
void memoallocate(void)
{
struct MZone *Mnew = (struct MZone*)malloc(sizeof(struct MZone));
printf("输入要分配内存大小(kb):\n");
scanf("%d",&Mnew->length);
printf("输入任务名:\n");
scanf("%s",&Mnew->task_name);
Minsert(Mnew)?printf("分配内存成功\n"):printf("没有符合大小的空闲分区，内存分配失败。\n");
system("pause");
free(Mnew);

}

//Mreturn函数，功能回收内存
void Mreturn(char taskname[])
{

struct MZone *front = NULL;
struct MZone *position = Mhead;
struct MZone *tail = Mhead->next;

while( 0!=strcmp(position->task_name,taskname) )
{
front = position;
if( NULL!=position->next )
{
position = position->next;
}
else
{
position = NULL;
break;
}
tail = position->next;
}

if( NULL==position )
{
printf("内存中没有此任务！");
}
else
{
//不能用CANTUSE
if( NULL!=tail&&NULL!=front )
{

if( front->state&&tail->state )
{
front->length = front->length + position->length + tail->length;
front->next = tail->next;
free(position);
free(tail);
}
else if( front->state&&!tail->state )
{
front->length = front->length + position->length;
front->next = position->next;
free(position);
}

else if( !front->state&&tail->state )
{
position->length = position->length + tail->length;
memset( position->task_name, 0, sizeof(char)*32 );
position->next = tail->next;
position->state = CANUSE;
free(tail);
}
else if( !front->state&&!tail->state )
{
memset( position->task_name, 0, sizeof(char)*32 );
position->state = CANUSE;
}
}
else if( NULL!=tail&&NULL==front )
{
if( !tail->state )
{
memset( position->task_name, 0, sizeof(char)*32 );
position->state = CANUSE;
}
else
{
position->length = position->length + tail->length;
position->next = NULL;
free(tail);
}
}
else if( NULL==tail&&NULL!=front )
{
if(front->state)
{
front->length = front->length + position->length;
front->next = NULL;
free(position);
}
else
{
memset( position->task_name, 0, sizeof(char)*32 );
position->state = CANUSE;
}
}
else if( NULL==tail&&NULL==front )
{
memset( position->task_name, 0, sizeof(char)*32 );
position->state = CANUSE;
}
printf("内存回收成功！\n");
}
}

//memoreturn函数，用于回收内存
void memoreturn(void)
{
char tname[32];
printf("输入要收回的任务名\n");
scanf("%s",tname);
Mreturn(tname);
system("pause");
}

int main(void)
{
int func_ = 0;

//初始化Mhead
Mhead = (struct MZone*)malloc(sizeof(struct MZone));
Mhead->begin_addr = 0;
Mhead->length = MSIZE;
Mhead->state = CANUSE;
memset(Mhead->task_name, 0, sizeof(char)*32 );
Mhead->next = NULL;

while( 1 )

{
printf("******************首次适应算法实现主存分配和回收系统（内存MSIZE）***************");
printf("|1:查看内存分配情况\n");
printf("|2:申请分配内存\n");
printf("|3:申请回收内存\n");
printf("|4:退出程序\n");
printf("********************************************************************************");
scanf("%d",&func_);
switch( func_ )
{
case 1 :showmemory();break;
case 2 :memoallocate();break;
case 3 :memoreturn();break;
case 4 :return 1;
}
system("cls");
}

}

【输出】
空闲区说明表的初始状态：

作业4的申请量：

作业4分配后的空闲区说明表状态：

作业3和作业2的归还量以及回收作业3，作业2所占主存后的空闲区说明表：

14