数学计算机科学学院实验报告
专业名称 软件开发已应用
实 验 室 学苑楼2#202
实验课程 计算机操作系统
实验名称 动态分区存储管理
姓 名 ____ 杨剑_______
学 号 ___0915266______
同组人员 _____ 无________
实验日期 ____2011/5/23___
一、【实验目的】：
1、熟悉主存分配与回收
2、理解在不同的存储管理方式，如何实现主存空间的分配与回收
3、掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方
式及其实现过程。
二、【实验内容和要求】：
主存的分配和回收的实现是与住存储器的管理方式有关的。所谓分配，就是解决多进程如何共享主存空间的问题。所谓回收，就是当进程运行完时将进程所占的主存空间归还给系统。
实验要求使用可变分区存储管理方式，分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法、三种算法来实现主存的分配与回收。
同时要求设计一个实用友好的可视化用户界面，并显示分配与回收过程。
三、【实验原理】
实验中为有效地对内存进行管理，实验中应设计一些数据结构，能有效地进行分配和回收，具体分析如下：
1、 设计一个空闲分区表，空闲分区表通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲分区低端的空间。
2、 设计一个内存分区表，可用链表管理，用以表示当前以内存使用情况。
3、 设计一个进程申请队列以及进程完成后的释放顺序，实现主存的分配和回收。
4、 要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。
四、【实验环境】（使用的软件）
Microsoft Visual C++ 6.0
五、【实验设计分析】：
内存分配：
①动态输入构造空闲区表，并显打印示构造好的空闲分区表。
②键盘接收内存申请。
③根据申请，实施内存分配，并返回分配所得内存首址。
④分配完后，调整空闲分区表（即扣除分配部分），并显示调整后的空闲分区表。
⑤若分配失败，返回分配失败信息。
内存回收：
①显示当前的空闲分区表和内存分区表。
②从键盘接收回收分区的首址与大小，按内存回收的四种情况进行内存回收。
③显示回收后已调整好的的空闲分区表
六、【实验过程和步骤】：
● 数据结构设计
① 空闲分区表的设计，该空闲分区表记录内存中未使用的各个分区，记录内容有未使用分区的大小、首地址，用链表就行管理；相关代码如下：
Typedef struct free
{
Int size; //分区大小
Int address;//首地址
free *next;
}；
②内存分区表设计，用以表示当前内存的使用情况，记录内容已使用分区的大小、首地址，用链表进行管理，相关数据结构如下：
Typedef struct map
{
Int size; //分区大小
Int address;//首地址
map *next;
}；
③进程申请队列的设计，用作进程到达的缓冲队列，记录各进程的相关信息，如进程的所需内存的大小、进程名，相关数据结构如下：
Typedef struct pro
{
Int size; //分区大小
sring name;
pro *next;
};
● 内存分配
当有进程进行内存申请时，我们利用首次适应算法从空闲分区链表、找出一块做够大的空间进行分配并对空闲分区和内存分区的相关结点进行处理，若未找到则返回错误信息，相关示意图如下：
● 内存回收
内存的回收存在以下几种情况：
①上邻空闲区：合并两分区，删除正回收的节点，改变上邻分区大小为两分区之和
②下邻空闲区：合并两分区，删除下邻分区节点，改变正回收节点大小为两分区之和，改变正回收节点的首址。
③上、下邻空闲区：合并三分区，删除下邻分区和正在回收节点，改变上分区节点大小为三分区之和，改变上分区收节点的首址
④不邻接，则建立一新表项。
相关的示意图如下：
① ② ③
l 相关代码
1．采用最优分配算法分配作业空间，主要代码如下：
void allocate(char J,float xk)//采用最优分配算法分配xk大小的空间
{
int i,k,l;
float ad;
k=-1;
for(i=0;i<m;i++) //寻找空间大于xk的最小空闲区登记项k
if(free_table[i].length>=xk && free_table[i].flag==1)
if(k==-1 || free_table[i].length<free_table[k].length)
k=i;
if(k==-1) //未找到可用空闲区,返回
{
AfxMessageBox(“有效空间不足！”);
return;
}
//找到可用空闲区,开始分配:若空闲区大小与要求分配的空间差小于minisize大小,则空闲区全部分配;若空闲区大小与要求分配的空间差大于minisize大小,则从空闲区划出一部分分配
if(free_table[k].length-xk<=minisize)
{
free_table[k].flag=0;
ad=free_table[k].address;
xk=free_table[k].length;
}
else
{
free_table[k].length=free_table[k].length-xk;
ad=free_table[k].address+free_table[k].length;
}
//修改已分配区表
l=0;
for(i=0;i<n;i++)
{
while(used_table[i].flag=='0'&&i<n) //寻找空表目
{
if(i>=n) //无表目填写已分分区
{
AfxMessageBox("无表目填写已分分区错误!");//修正空闲区表
if(free_table[k].flag==0) //前面找到的是整个空闲区
free_table[k].flag=1;
else //前面找到的是某个空闲区的一部分
{
free_table[k].length=free_table[k].length+xk;
return;
}
}
else //修改已分配区表
{
used_table[i].address=ad;
used_table[i].length=xk;
used_table[i].flag=J;
}
l=1;
}
if(l==1) break;
}
return;
}//主存分配函数结束
3． 作业的回收
bool reclaim(char J)//回收作业名为J的作业所占主存空间
{
int i,k,j, s,t;
float S,L;
//寻找已分配区表中对应登记项
s=0;
while((used_table[s].flag!=J || used_table[s].flag=='0')&&s<=n)
{
if(s>=n) //在已分配区表中找不到名字为J的作业
{
AfxMessageBox("找不到该作业");
return (false);
}
s++;
}
//修改已分配区表
if(used_table[s].flag==J)
{ used_table[s].flag='0';
//取得归还分区的起始地址S和长度L
S=used_table[s].address;
L=used_table[s].length;
j=-1;k=-1;i=0;
//寻找回收分区的上下邻空闲区,上邻表目k,下邻表目J
while(i<m&&(j==-1||k==-1))
{
if(free_table[i].flag==1)
{ if(free_table[i].address+free_table[i].length==S)k=i;//找 到上邻
if(free_table[i].address==S+L)
j=i; //找到下邻
}
i++;
}
if(k!=-1)
if(j!=-1) //上邻空闲区,下邻空闲区,三项合并
{ free_table[k].length=free_table[j].length+free_table[k].length+L; free_table[j].flag=0;
}
else //上邻空闲区,下邻非空闲区,与上邻合并
free_table[k].length=free_table[k].length+L;
else
if(j!=-1) //上邻非空闲区,下邻为空闲区,与下邻合并
{ free_table[j].address=S;
free_table[j].length=free_table[j].length+L;
}
else //上下邻均为非空闲区,回收区域直接填入
{ //在空闲区表中寻找空栏目
t=0;
while(free_table[t].flag==1 && t<=m)
{
if(t>=m) //空闲区表满,回收空间失败,将已分配区表复原
{
AfxMessageBox("主存空闲表没有空间,回收空间失!");
used_table[s].flag=J;
return (false);
}
t++;
}
free_table[t].address=S;
free_table[t].length=L;
free_table[t].flag=1;
}
}
return(true);
}//主存归还函数结束
● 程序流程图
七、【测试数据和实验结果分析】：
假设初始状态下，可用的内存空间为400KB，并有下列的请求序列：
（1）进程1申请130KB （2）进程2申请60KB
（3）进程3申请100KB （4）进程2释放60KB
（5）进程4申请200KB （6）进程3释放100KB
（7）进程1释放130KB （8）进程5申请140KB
（9）进程6申请60KB （10）进程7申请50KB
（11）进程6释放60KB
● 实验结果分析：
由测试数据知，首先进程1、2、3到达缓冲队列依次申请各自所需内存，对应着上图1，之后进程3、1依次释放，对应图2，从实验结果看，实验结果的正确性得到验证。
八、【实验心得】：
本实验极大的帮助我们理解了动态分区作业存储管理的实现过程。在对作业采用最优适应算法的同时，还外加代码弥补了最优适应算法会产生极小的零碎空闲区的弊端。在作业存储时，当前作业的起始地址=原空闲区起始地址+原空闲区偏移地址-当前作业的偏移地址；由此可知当前作业在空闲区内是从空闲区的高地址开始分配。在对作业回收时，作业临区的回收采用if、else语句及其嵌套语句，清楚合理的实现了4中情况下的作业回收。
第二篇：动态分区存储管理实例
动态分区存储管理实例
⒈ 实验内容
主存储器空间分配实验。
⒉ 实验目的
通过首次适应算法、最佳适应算法和最坏适应算法实现主存空间的分配，可以使读者可好地理解存储分配算法。
⒊ 实验题目
编写一段程序来模拟可变分区管理方法。要求能通过文件形式定义空闲区表；能随意输入作业及需要分配的空间；能分别使用首次适应算法、最佳适应算法和最坏适应算法对输入的作业进行空间分配；能显示系统空闲表和已分配空间表。
⒋ 实验提示
⑴可变分区方式是按作业需要的主存空间大小来分区。当装入一个作业时，首先要查看是否有足够的空闲空间来分配，若有则按指定的分配方式进行分配；否则作业不能装入。随着作业的装入和撤离主存空间被分为若干个大大小小的不连续的区间，为了表明各区间的状态可以用一个内存分区表如表7-13所示来表示。
表7-13 内存分区表
这样我们可以定义一个如下的结构表示内存分区信息。
typedef struct node
{
int start; //起始地址
int length; //长度
char tag[20]; //标志
}job;
⑵可变分区的三种算法就是为作业分配主存空间的方法。
● 首次适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入第一个满足条件的空间中去。
● 最佳适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最小的一个空间中去。
● 最坏适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最大的一个空间中去。
从三种算法的说明可以看出，分配空间的过程主要可以分两步：
● 查询所有满足作业需求的空间块。
● 按照指定的算法将作业装入空间块中。
⑶在操作的最初主存空间实际就是一个大的空闲区，不涉及到如何分配的问题。为直接模拟运行一段时间后主存中出现了多个空闲块的状态，题目要求从一个文件读入空闲区表。在这里我们可以设计一个空闲区表文件的结构为如表7-14所示：
表7-14 空闲区表
这样也可以方便地将空闲表一次读入程序中，而不必再一个个的输入。
⑷主要变量及函数说明如表7-15所示
表7-15 变量与函数说明表
⑸mem.txt文件内容如下：
20 32
52 8
60 120
180 331
⒌ 实例代码
//动态分区算法memory.c
//运行环境Redhad9.0 gcc 4.0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXJOB 200 //定义存储数据最大值
typedef struct node //内存块结构
{
int start;
int length;
char tag[20];
}job;
job frees[MAXJOB]; //定义空闲区表
int free_quantity; //空闲区块数
job occupys[MAXJOB]; //定义已分配区表
int occupy_quantity; //已分配区块数
//初始化函数
void initial()
{
int i;
for(i=0;i<MAXJOB;i++){
frees[i].start=-1;
frees[i].length=0;
strcpy(frees[i].tag,"free"); //定义所有块为空闲块
occupys[i].start=-1;
occupys[i].length=0;
strcpy(occupys[i].tag,""); //已分配块为0
}
free_quantity=0;
occupy_quantity=0;
}
//读数据函数，从文件中读入空闲表的设置
int readData()
{
FILE *fp;
char fname[20];
printf("请输入初始空闲表文件名:"); //输入空闲表文件的文件名
scanf("%s",&fname);
if((fp=fopen(fname,"r"))==NULL){
printf("错误,文件打不开,请检查文件名\n");
}
else{
while(!feof(fp)){ //打开文件读入空闲表信息
fscanf(fp,"%d %d",&frees[free_quantity].start,&frees[free_quantity].length);
free_quantity++;
}
return 1;
}
return 0;
}
//排序空闲表
void sort()
{
int i,j,p;
for(i=0;i<free_quantity-1;i++){
p=i;
for(j=i+1;j<free_quantity;j++){
if(frees[j].start<frees[p].start){
p=j;
}
}
if(p!=i){
frees[free_quantity]=frees[i];
frees[i]=frees[p];
frees[p]=frees[free_quantity];
}
}
}
//显示函数
void view()
{
int i;
printf("\n---------------------------\n");
printf("当前空闲表:\n"); //显示空闲表
printf("起始地址\t长度\t状态\n");
for(i=0;i<free_quantity;i++){
printf("%8d\t%4d\t%s\n",frees[i].start,frees[i].length,frees[i].tag);
}
printf("\n----------------------------\n");
printf("当前已分配表:\n");
printf("起始地址\t长度\t占用作业名\n");
for(i=0;i<occupy_quantity;i++){ //显示已分配表
printf("%8d\t%4d\t%s\n",occupys[i].start,occupys[i].length,occupys[i].tag);
}
getchar();
}
//最先适应分配算法
void earliest()
{
char job_name[10];
int job_length;
int i,j,flag,t;
printf("请输入新申请内存空间的作业名:");
scanf("%s",&job_name);
printf("请输入新申请内存空间的大小:");
scanf("%d",&job_length);
flag=0;
for(i=0;i<free_quantity;i++){ //顺序查找满足条件的空间
if(frees[i].length>=job_length){
flag=1;
}
}
if(flag==0){ //没找到满足的空间
printf("\n当前没有能满足你申请长度的空闲内存,请稍候再试\n");
}
else{ //找到了满足的空间
t=0;
i=0;
while(t==0){
if(frees[i].length>=job_length){
t=1;
}
i++;
}
i--;
occupys[occupy_quantity].start=frees[i].start; //分配满足条件的空间
strcpy(occupys[occupy_quantity].tag,job_name);
occupys[occupy_quantity].length=job_length;
occupy_quantity++;
if(frees[i].length>job_length){
frees[i].start+=job_length;
frees[i].length-=job_length;
}
else{
for(j=i;j<free_quantity-1;j++){
frees[j]=frees[j+1];
}
free_quantity--;
printf("内存空间成功!\n");
}
}
}
//最优适应分配算法
void excellent()
{
char job_name[20];
int job_length;
int i,j,flag,t;
printf("请输入新申请内存空间的作业名:");
scanf("%s",&job_name);
printf("请输入新申请内存空间的大小:");
scanf("%d",&job_length);
flag=0;
for(i=0;i<free_quantity;i++){
if(frees[i].length>=job_length){
flag=1;
}
}
if(flag==0){
printf("\n当前没有能满足你申请长度的空闲内存,请稍候再试\n");
}
else{
t=0;
i=0;
while(t==0){
if(frees[i].length>=job_length){
t=1;
}
i++;
}
i--;
for(j=0;j<free_quantity;j++){ //找到满足条件的最小空闲空间
if((frees[j].length>=job_length)&&(frees[j].length<frees[i].length)){
i=j;
}
}
occupys[occupy_quantity].start=frees[i].start; //分配空闲空间
strcpy(occupys[occupy_quantity].tag,job_name);
occupys[occupy_quantity].length=job_length;
occupy_quantity++;
if(frees[i].length>job_length){
frees[i].start+=job_length;
frees[i].length-=job_length;
}
else{
for(j=i;j<free_quantity-1;j++){
frees[j]=frees[j+1];
}
free_quantity--;
printf("内存空间成功!\n");
}
}
}
//最坏适应算法
void worst()
{
char job_name[20];
int job_length;
int i,j,flag,t;
printf("请输入新申请内存空间的作业名:");
scanf("%s",&job_name);
printf("请输入新申请内存空间的大小:");
scanf("%d",&job_length);
flag=0;
for(i=0;i<free_quantity;i++){
if(frees[i].length>=job_length){
flag=1;
}
}
if(flag==0){
printf("\n当前没有能满足你申请长度的空闲内存,请稍候再试\n");
}
else{
t=0;
i=0;
while(t==0){
if(frees[i].length>=job_length){
t=1;
}
i++;
}
i--;
for(j=0;j<free_quantity;j++){ //找到满足条件的最大空闲空间
if((frees[j].length>=job_length)&&(frees[j].length>frees[i].length)){
i=j;
}
}
occupys[occupy_quantity].start=frees[i].start; //分配空闲空间
strcpy(occupys[occupy_quantity].tag,job_name);
occupys[occupy_quantity].length=job_length;
occupy_quantity++;
if(frees[i].length>job_length){
frees[i].start+=job_length;
frees[i].length-=job_length;
}
else{
for(j=i;j<free_quantity-1;j++){
frees[j]=frees[j+1];
}
free_quantity--;
printf("内存空间成功!\n");
}
}
}
//主函数
int main()
{
int flag=0;
int t=1;
int chioce=0;
initial(); //初始化
flag=readData(); //读空闲表文件
while(flag==1){
sort(); //排序
//显示菜单
printf("\n=====================================\n");
printf("动态分区算法");
printf("\n=====================================\n");
printf("1.显示空闲表和分配表\n2.最先适应法 \n3.最优适应法 \n4.最坏适应法 \n0.退出\n=============");
printf("请选择:");
scanf("%d",&chioce); //输入选择的菜单项
switch(chioce){
case 1: //显示空闲表和分配表
view();
break;
case 2: //调用最先适应法
earliest();
break;
case 3: //最优适应法
excellent();
break;
case 4: //最坏适应法
worst();
break;
case 0: //退出
flag=0;
break;
default:
printf("\n选择错误!\n");
}
}
}
运行结果：
[root@redlinux ys]# gcc memory.c –o memory.o
[root@redlinux ys]#./memory.o
请输入初始空闲表文件名:mem.txt↙
=====================================
动态分区算法
=====================================
1.显示空闲表和分配表
2.最先适应法
3.最优适应法
4.最坏适应法
0.退出
=============请选择:1↙
---------------------------
当前空闲表:
起始地址 长度 状态
20 32 free
52 8 free
60 120 free
180 331 free
----------------------------
当前已分配表:
起始地址 长度 占用作业名
选择2后，情况如下：(由于篇幅有限，简化了运行过程)
=============请选择:2↙
请输入新申请内存空间的作业名:a↙
请输入新申请内存空间的大小:32↙
内存空间成功!
=============请选择:2↙
请输入新申请内存空间的作业名:b↙
请输入新申请内存空间的大小:24↙
---------------------------
当前空闲表:
起始地址 长度 状态
52 8 free
84 96 free
180 331 free
----------------------------
当前已分配表:
起始地址 长度 占用作业名
20 32 a
60 24 b