主存储器空间的分配和回收
一、 实验题目：
（1） 在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收
（2） 在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收
二、 实验目的：
通过本实习帮助理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。
三、 实验原理：
第一题：在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收
(1) 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。
（3）采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。最先适应分配算法如图：
（4）当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示(1)中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图：
（5）请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来：
第二题：在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。
(1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。
(2) 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下图：
(3) 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。
按找到的计算出对应的块号，其计算
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
为：块号= j′8+I其中，j表示找到的是第n个字节，i表示对应的是第n位。根据分配给作业的块号，为作业建立一张页表，页表格式：
(4) 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：
字节号 j=[块号/8] （[ ]表示取整）
位数 i={块号/8} （{ }表示取余）
(5)设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行所设计的回收程序，收回作业归还的主存块。
要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。
四、 数据结构：
数组、链表
五、 程序代码：
第一题：
package 可变分区管理;
class Node1{//用Node来模拟内存的当前状态
int start;
int size;
boolean state;
int jobNo;
public Node1(){}
public Node1(int start,int size,boolean state,int jobNo){
this.start = start;
this.size = size;
this.state = state;
this.jobNo = jobNo;
}
public void print(){//打印Node类
if (this!=null)
System.out.println(" "+this.start+"\t"+this.size+"\t"+this.state+"\t"+this.jobNo);
}
}
//Link.java
class Link{ //用Link类来模拟连接各个内存，并添加作业
public void addJob(int size,int jobNo,Node1 a[]){
for(int i=0;i
#include
#include
#include
#include
#include
int bitmap[8][8]={ //初始化位图
{1,1,0,0,1,1,1,0},
{0,1,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}
};
int freecount=54; //初始时空闲页块数
typedef struct yebiao //页表结构体
{
int yehao; // 页号
int kuaihao; //块号
struct yebiao *next; //指向下一个页表项的指针
}YEBIAO;
typedef struct progress //进程结构体
{
char name[30]; //进程名
int size; //进程所需内存大小
struct progress *next; //指向下一个页表项的指针
struct yebiao *yb; //为其分配内存建立的页表首地址
}PROGRESS;
/*分配内存函数，为进程分配所需要的内存并建立页表*/
YEBIAO *allocation(int size)
{
YEBIAO *head;
YEBIAO *tem;
int n=0;
tem=(YEBIAO *)malloc(sizeof(YEBIAO));
head=tem;
for(int i=0;;i++) //遍历位图找到空闲的页块
{
if(bitmap[i/8][i%8]==1) continue; //如果页会已被占用直接查下一个页块
if(bitmap[i/8][i%8]==0)
{
bitmap[i/8][i%8]=1; //将空闲的位图
标识
采样口标识规范化 下载危险废物标识 下载医疗器械外包装标识图下载科目一标识图大全免费下载产品包装标识下载
置为一
tem->yehao=n; //建立一个页表项的页号
tem->kuaihao=i; //对应的块号
tem->next=NULL;
n++;
}
if(n==size) break; //如果已经分配了需要的页块直接退出查找
else
{
tem->next=(YEBIAO *)malloc(sizeof(YEBIAO));
tem=tem->next;
}
}
return head;
}
/*回收内存*/
void recovery(YEBIAO *a)
{
YEBIAO *b;
while(a->next!=NULL)
{
bitmap[a->kuaihao/8][a->kuaihao%8]=0; //将页块对应的标识位图对应标志置0
b=a->next; //指向下一个页表项
free(a); //释放页表项占用的空间
a=b;
}
bitmap[a->kuaihao/8][a->kuaihao%8]=0;
free(a);
}
void outputyebiao(YEBIAO *a) //输出页表的内容
{
cout<<"-------------------------"<yehao<kuaihao<next;
}while(a!=NULL); //遍历页表链表逐行输出页表项
cout<<"-------------------------"<next=NULL;
}
else //定位到链表的队尾将要插入的进程插入到队尾
{
tem=head;
while(tem->next!=NULL)
{
tem=tem->next;
}
tem->next=b;
}
return head;
}
PROGRESS *getprosess(PROGRESS *head) //输入进程为进程分配空间
{
PROGRESS *a;
char na[30];
int size;
cout<<"请输入进程名:";
cin>>na;
cout<<"请输入进程所占内存大小:";
cin>>size; //上面是输入进程的名称和所用内存空间大小
if(size>freecount) //如果进程
{
cout<<"进程所需内存的大小大于空闲的内存，无法添加进程。"<name,na);
a->size=size; //初始化进程的基本信息
freecount-=size; //将可用的页块数减去进程要用的页块数
a->yb=allocation(size); //为进程创建页表
cout<<"进程创建成功！"<next=NULL;
return insert(head,a); //将进程插入进程链表中
}
void outputprosess(PROGRESS *head) //输出进程信息
{
if(head==NULL) //判断进程队列是否为空
{
cout<<"当前没有进程!"<name<<" 进程所占内存的大小为:"<size<<"页"<yb);
head=head->next;
}while(head!=NULL);
}
PROGRESS * delecteprosess(PROGRESS *head) //删除进程
{
char na[30];
PROGRESS *a,*b;
cout<<"请输入要删除的进程名:"; //使用进程的名字来删除进程
cin>>na;
if(head==NULL) //如果进程为空，退出函数
{
cout<<"进程链表为空，没有进程可删除。"<name,na)==0) //如果找到要删除的进程
{
recovery(head->yb); //先删除进程的页表并释放所占的页
freecount+=head->size; //将可用的内存数加上进程所占的内孙
a=head->next;
free(head); //释放进程信息所占得内存空间
cout<<"进程"<next;
b=head;
while(a!=NULL) //遍历链表找到要删除的进程
{
if(strcmp(a->name,na)==0)
{
recovery(a->yb);
freecount+=a->size;
b->next=a->next;
free(a);
cout<<"进程"<next;
}
cout<<"您输入的进程名不对，删除进程失败。"<>n;
switch(n)
{
case 1: outputbit();outbiaoti();break;
case 2: system("cls");outputprosess(head);outbiaoti();break;
case 3: system("cls");head=getprosess(head); outbiaoti();break;
case 4: system("cls");head=delecteprosess(head); outbiaoti();break;
default: break;
}
}
}
六、 运行结果：
第一题：
第二题：
七、 实验心得：
这次的实验相对来说较难，之前对内存那块知识也不是很清楚，但通过实验，也参考了很多资料解释，但是还是对内存分配与回收有了更深入更清楚的了解，以后的程序编写不论是实验还是项目开发，无论大小，都应该把程序的整体框架构建好，提高重用性，再进行一步步实现。
浙公网安备 33021202002483