实验三、存储管理
一、实验目的：
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。
在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验理解在分页式存储管理中怎样实现虚拟存储器。
在本实验中，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
二、实验题目：
设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。
对分区的管理法可以是下面三种算法之一： （任选一种算法实现）
首次适应算法
循环首次适应算法
最佳适应算法
三．实验源程序文件名:cunchuguanli.c
执行文件名:cunchuguanli.exe
四、实验分析：
1)本实验采用可变分区管理，使用首次适应算法实现主存的分配和回收
1、可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。
为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表
空闲区说明表格式如下：
其中，起址——指出一个空闲区的主存起始地址，长度指出空闲区的大小。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。
2、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区，留在空闲区表中。为了尽量减少由于分割造成的空闲区，尽可能分配低地址部分的空闲区，而尽量保存高地址部分有较大的 连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序从低到高登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”项留在表格的后部。
3、采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
4、当一个作业执行完成撤离时，作业所占的分区应该归还给系统，归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在上述中列举的 情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。
2)流程图：
<1> 主存回收算法
,2>首次适应分配模拟算法
3)源程序:
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
#define getjcb(type) (type*)malloc(sizeof(type))
#define getsub(type) (type*)malloc(sizeof(type))
int num,num2; //要调度的作业数和要回收的区域数
int m=0; //已分配作业数
int flag; //分配成功标志
int isup,isdown; //回收区域存在上邻和下邻的标志
int is=0;
struct jcb{
char name[10];
char state;
int ntime; //所需时间
int size; //所需空间大小
int addr; //所分配分区的首地址
struct jcb *link;
} *ready =NULL, *p,*q,*as=NULL;//作业队列ready,已分配作业队列as
typedef struct jcb JCB;
struct subarea{ //分区块
char name[10];
int addr; //分区首地址
int size; //分区大小
char state;
struct subarea *link;
} *sub=NULL,*r,*s,*cur; //空闲分区队列sub,当前分区指针cur
typedef struct subarea SUB;
void sort() /* 建立对作业按到达时间进行排列的函数,直接插在队列之尾*/
{
JCB *first;
if(ready==NULL) ready=p;
else{
first=ready;
while(first->link!=NULL)
first=first->link;
first->link=p;
p->link=NULL;
}
}
void sort3() /*建立对已分配作业队列的排列函数,直接插在队列之尾*/
{
JCB *fir;
if(as==NULL) as=q;
else{
fir=as;
while(fir->link!=NULL)
fir=fir->link;
fir->link=q;
q->link=NULL;
}
m++;
}
void input() /* 建立作业控制块函数*/
{
int i;
printf("\n请输入要调度的总作业数:");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n作业号No.%d:\n",i);
p=getjcb(JCB);
printf("\n输入作业名:");
scanf("%s",&p->name);
printf("\n输入作业的大小:");
scanf("%d",&p->size);
printf("\n输入作业所需运行时间:");
scanf("%d",&p->ntime);
p->state='w';
p->link=NULL;
sort(); /* 调用sort函数*/
}
printf("\n 按任一键继续......\n");
getch();
}
void input2() /*建立要回收区域的函数*/
{
JCB *k;
int has;
q=getjcb(JCB);
printf("\n输入区域名(作业名):");
scanf("%s",&q->name);
p=as;
while(p!=NULL)
{if(strcmp(p->name,q->name)==0) /*在已分配作业队列中寻找*/
{
q->addr=p->addr;
q->size=p->size;
has=1; /*输入作业名存在标志位*/
if(p==as) as=p->link; /*在已分配作业队列中删除该作业*/
else
{k=as;
while(k->link!=p) k=k->link;
k->link=k->link->link; /*删除*/
}
printf("输出该作业首地址:%d\n",q->addr);
printf("输出该作业大小:%d\n\n",q->size);
q->link=NULL;
break;
}
else
{p=p->link; has=0;} /*输入作业名不存在标志*/
}
if(has==0)
{printf("\n输入作业名错误!请重新输入!\n");
input2();
}
}
void print()
{printf("\n\n\n\n");
printf("\t\t**************************************\n");
printf("\t\t\t三.存储管理实验演示\n");
printf("\t\t**************************************\n\n\n");
printf("\t\t\t\t蓝小花\n");
printf("\t\t\t\t计算机学院\n");
printf("\t\t\t\t软件4班\n");
printf("\t\t\t\t3204007102\n");
printf("\t\t\t\t20##年12月\n");
printf("\n\n\n");
printf("\t\t\t按任意键进入演示");
getch();
system("cls");
}
void init_sub() /*初始化空闲分区表*/
{
r=getsub(SUB);
strcpy(r->name,"0"); r->addr=5; r->size=10; r->state='F';
sub=r;
s=getsub(SUB);
strcpy(s->name,"1"); s->addr=20; s->size=120; s->state='F';
sub->link=s;r=s;
s=getsub(SUB);
strcpy(s->name,"2"); s->addr=160; s->size=40; s->state='F';
r->link=s;r=s;
s=getsub(SUB);
strcpy(s->name,"3"); s->addr=220; s->size=10; s->state='F';
r->link=s;r=s;
s=getsub(SUB);
strcpy(s->name,"4"); s->addr=250; s->size=20; s->state='F';
r->link=s;r=s;
s=getsub(SUB);
strcpy(s->name,"5"); s->addr=300; s->size=80; s->state='F';
r->link=s;
}
//--------------------------------------------------------------------------
void disp() /*空闲分区表的显示函数*/
{
printf("\n\n");
printf("\t\t 分区 首地址 长度 状态 \n");
r=sub;
while(r!=NULL)
{
printf("\t\t %s\t\t%d\t\t%d\t\t%c\n",r->name,r->addr,r->size,r->state);
r=r->link;
}
printf("\n");
}
void disp2() /*显示已分配内存的作业表函数*/
{
printf("\n\n");
printf("\t\t 作业名 首地址 长度 状态 \n");
p=as;
while(p!=NULL)
{
printf("\t\t %s\t\t%d\t\t%d\t\t%c\n",p->name,p->addr,p->size,p->state);
p=p->link;
}
printf("\n\n");
}
void assign2(JCB *pr) /*首次适应作业分区*/
{
SUB *k;
r=sub; /*从空闲表头开始寻找*/
while(r!=NULL)
{
if(((r->size)>(pr->size))&&(r->state=='n')) /*有空闲分区大于作业大小的情况*/
{
pr->addr=r->addr;
r->size-=pr->size;
r->addr+=pr->size;
flag=1; /*分配成功标志位置1*/
q=pr;
q->state='r';
sort3(); /*插入已分配作业队列*/
printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);
break;
}
else if(((r->size)==(pr->size))&&(r->state=='n')) /*有空闲分区等于作业大小的情况*/
{
pr->addr=r->addr;
flag=1; /*分配成功标志位置1*/
q=pr;
sort3(); /*插入已分配作业队列*/
s=sub; /*空闲分区已完成分配,应删除*/
while(s->link!=r) s=s->link;
s->link=s->link->link; /*删除空闲分区*/
printf("作业%s的分区为[%s],首地址为%d.\n",p->name,r->name,pr->addr);
break;
}
else
{r=r->link; flag=0;}
}
if(flag==0) /*作业过大的情况*/
{
printf("作业%s长度过大，内存不足，分区分配出错!\n",p->name);
is=1;
}
}
void reclaim2(JCB *pr) /*首次适应与循环首次适应区域回收*/
{
SUB *k;
r=sub;
while(r!=NULL)
{
if(r->addr==((pr->addr)+(pr->size))) /*回收区域有下邻*/
{
pr->size+=r->size;
s=sub;
isdown=1; /*下邻标志位置1*/
while(s!=NULL)
{
if(((s->addr)+(s->size))==(pr->addr)) /*有下邻又有上邻*/
{
s->size+=pr->size;
k=sub;
while(k->link!=r) k=k->link;
k->link=k->link->link;
isup=1; /*上邻标志位置1*/
break;
}
else
{s=s->link; isup=0;} /*上邻标志位置0*/
}
if(isup==0) /*有下邻无上邻*/
{
r->addr=pr->addr;
r->size=pr->size;
}
break;
}
else
{r=r->link; isdown=0;} /*下邻标志位置0*/
}
if(isdown==0) /*区域无下邻*/
{
s=sub;
while(s!=NULL)
{
if(((s->addr)+(s->size))==(pr->addr)) /*无下邻但有上邻*/
{
s->size+=pr->size;
isup=1; /*上邻标志位置1*/
break;
}
else
{ s=s->link; isup=0;} /*上邻标志位置0*/
}
if(isup==0) /*无下邻且无上邻*/
{
k=getsub(SUB); /*重新生成一个新的分区结点*/
strcpy(k->name,pr->name);
k->addr=pr->addr;
k->size=pr->size;
k->state='n';
r=sub;
while(r!=NULL)
{
if((r->addr)>(k->addr)) /*按分区首地址排列,回收区域插在合适的位置*/
{
if(r==sub) /*第一个空闲分区首址大于回收区域的情况*/
{ k->link=r; sub->link=k; }
else
{
s=sub;
while(s->link!=r) s=s->link;
k->link=r;
s->link=k;
}
break;
}
else r=r->link;
}
if(r==NULL) /*所有空闲分区的首址都大于回收区域首址的情况*/
{
s=sub;
while(s->link!=NULL) s=s->link;
s->link=k;
k->link=NULL;
}
}
}
printf("\n区域%s己回收.",pr->name);
}
menu()
{
printf("\n\n\n\t\t**************************************\n");
printf("\t\t\t存储管理实验演示\n");
printf("\t\t**************************************\n\n\n");
printf("\t\t\t 1. 显示空闲分区 \n");
printf("\t\t\t 2. 分配和回收作业 \n");
printf("\t\t\t 0. 退出 \n");
printf("\t\t\t请选择你要的操作:");
switch(getchar())
{
case '1':
system("cls");
disp();
getch();
system("cls");
menu();
break;
case '2':
system("cls");
printf("\n首次适应算法");
input();
printf("\n");
while(num!=0)
{
p=ready;
ready=p->link;
p->link=NULL;
assign2(p);
num--;
}
printf("\n显示回收后的空闲分区表和已分配作业表...");
getch();
printf("\n\t\t 完成分配后的空闲分区表 \n");
disp();
printf("\n\t\t 已分配作业表 \n");
disp2();
if(is==0)
printf("\n 全部作业已经被分配内存.");
else printf("\n 作业没有全部被分配内存.\n");
printf("\n\n按任意键进行区域回收.");
printf("\n");
while(as!=NULL)
{getch();
input2();
printf("按任意键继续...");
getch();
printf("\n");
reclaim2(q);
printf("\n显示回收后的空闲分区表和已分配作业表...");
getch();
printf("\n\t\t 回收后的空闲分区表 \n");
disp();
printf("\n\t\t 已分配作业表 \n");
disp2();
printf("\n继续回收...(Enter)");
}
printf("\n所有已分配作业已完成!");
printf("\nPress any key to return...");
getch();
system("cls");
menu();
break;
case '0':
system("cls");
break;
default:
system("cls");
menu();
}
}
void main() /*主函数*/
{
init_sub();
print();
menu();
}
4)调试结果:
1> 进入界面,显示操作:
2> 选择操作1,显示目前的空闲分区:
3>返回界面,选择操作2,输入如下信息:
4>显示分配作业后的空闲区表和作业链表:
5>作业继续运行,完后回收作业,如下:
6>此时,作业已经全部回收,空闲区表内容跟初始空闲区表内容一样.
五.心得体会
这个实验完成的很不容易.