模拟实现用位示图法管理文件存储空间的分配与回收.doc

(完整word版)模拟实现用位示图法管理文件存储空间的分配与回收

合肥学院
计算机科学与技术系

课程设计报告

20011～2012 学年第 1 学期

课程名称
操作系统原理
课程设计名称
模拟实现用位示图法管理文件存储空间的分配与回收
专 业 班 级

学生姓名

学 生 学 号

指 导 教 师

20011 年11 月

实验题目 模拟用位示图法管理文件存储空间的分配与回收
一、 实验目的：
1) 理解文件存储空间的分配与回收的基本概念，掌握产生文件存储空间的分配与回收的几种方法，体会位示图算法是管理文件存储空间的分配与回收的一种行之有效的方法。
2) 通过编写程序实现位示图算法，进一步理解位示图算法的原理和执行过程，掌握位示图算法的描述和应用，进一步熟练掌握文件存储空间的分配与回收的方法。
二、 实验内容:
（1）首先对位示图算法原理进行深刻的理解和掌握；
（2）程序首先要给出位示图初态。分配时,参数为文件名及需要分配的块数。回收时，参数为文件名。
（3)回答信息：分配时，能够分配时，给出文件名和分配的具体块号。否则,给出无法分配的信息。显示位示图。
（4）回收时：给出回收的具体块号。显示位示图。
三、 实验环境
Windows系统，在Ｃ＋＋的环境下来运行这儿程序
四、 实验主要步骤
1、初始化及使用数据结构
对数组WST[]元素初始化为0。定义以下3个链表并初始化。空闲区结构体定义free_link、申请空间作业结构体定义office、相关位示图操作的结构体定义work。
位示图算法是利用二进制的一位来表示磁盘中的一个盘块的使用情况。在外存上建立一张位示图（bitmap），记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。文件存储器上的物理块依次编号为：0、1、2、…。定义为一维数组WST[],操作起来更为方便。下表号与盘块号对应。在输出的时候控制输出为二维形式。

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
1
0
0
0
1
1
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
2
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
0
3

┇

15

位示图

2、申请空间算法
首先要输入文件名和大小，查找与已存在的文件是否重名。没有，则比较空闲区中空闲块数是否大于欲分配的块数。有的话分配。
分配的时候该作业要记录下自己所占盘块的其实盘号和所占用的盘快数。并修改对应盘块的位示图的值。
m=r->start_location;//空闲区的起始地址
s->begin_location=r->start_location;//作业从空闲区的起始地址开始分配
r->start_location=r->start_location+s->office_number;//改变空闲区空闲块数的起始地址
r->free_number=r->free_number-s->office_number;//改变空间区块数的大小
n=(r->start_location-1);//新的空间区的起始地址-1
for(i=m;i<=n;i++)//模拟分配
WST[i]=1;
3、回收空间算法
首先输入文件名，查找申请空间作业链表找到该作业。找到该作业时回收该盘块。回收时要判断盘块前后的是否为空。决定回收的盘块来加入哪个空闲区。
(1)if((WST[s->begin_location-1]==0&&WST[s->begin_location+s->office_number]==1&&s->begin_location-1>=0)||(WST[s->begin_location-1]==0&&s->begin_location+s->office_number==256&&s->begin_location-1>=0)){//前面为空盘块区，后面为已分配，并入前面
(2)if((WST[s->begin_location-1]==1&&WST[s->begin_location+s->office_number]==0&&s->begin_location+s->office_number<256)||(s->begin_location==0&&WST[s->begin_location+s->office_number]==0&&s->begin_location+s->office_number<256)){//后面为空盘,并入后面区域
(3)if(WST[s->begin_location-1]==0&&WST[s->begin_location+s->office_number]==0&&s->begin_location-1>=0&&s->begin_location+s->office_number<256){//前后都空,合为一个空盘区
(4)if((WST[s->begin_location-1]==1&&WST[s->begin_location+s->office_number]==1&&s->begin_location-1>=0&&s->begin_location+s->office_number<256)||(s->begin_location==0&&WST[s->begin_location+s->office_number]==1&&s->begin_location+s->office_number<256)||(WST[s->begin_location-1]==1&&s->begin_location+s->office_number==256&&s->begin_location-1>=0)||(s->begin_location==0&&s->begin_location+s->office_number==256)){//要回收的区域自成一个空盘结点
Request()分配

4.各算法流程图
盘块的分配：
输入文件名,和块数.

strcmp(s->office,u->office)==0该文件是否已存在

否

r->free_number>=s->office_number能否查找到一个足够的空闲区域
是

否

是
将该作业结点插入作业链表表尾,,从该区域分配出对应大小空间,修改位示图

当前空盘区块数是否分配完

否
是
释放该空闲区结点,把修改work里面两个首地址

返回

Delect()回收
盘块的回收：

输入要查找的文件名,查找

能否找到对应文件

要回收的单元前为空
是

是
把该单元块数加入前一个空闲区结点
否
要回收的单元后为空

是
否
把空闲区起始地址该为当前开始盘块空闲区盘块增加
要回收的单元前后都空

是
结点空盘起始地址改为前一个,空闲区盘块增加

要回收的单元自成空盘区结点
否

是
把该结点插入空闲区链表

修改位示图对应盘块的的内容,删除该文件结点. 修改work里面两个首地址

返回

五、记录实验结果并分析
1、在dos窗口界面下，我们看到的如下所示，这是程序初始化时出现的界面：
2现在我们对其进行操作：选择1—分配文件，出现如下界面：

我们不妨设文件名位“caozuoxitong”,并令块数为10，执行，得到如下的界面：

看到从第一行的第一列一直到第一行的第九列共10个盘块均已经被分配，并且令“0”该为“1”，表示盘块已分配。
盘块的分配已经完成，下面是盘块的回收：
选择2—回收文件，出现如下界面：

输入我们刚刚输入的文件名“caozuoxitong”，并回车，界面如下

我们看到从第一行的第一列一直到第一行的第九列已经全部变为“0”了，表示此时盘块已经回收。
按“3”退出。
对于程序中的其他的一些事项，比如盘块不够大；输入错误；找不到文件等情况，程序也给予相应的提示，用户在使用时，根据提示会很快改正相关的错误的。
六、实验总结及体会。
在做实验前，一定要将课本上的知识吃透，因为这是做实验的基础，否则，在老师讲解时就会听不懂,这将使你在做实验时的难度加大，浪费做实验的宝贵时间。如果你不清楚，在做实验时才去摸索，这将使你极大地浪费时间，使你事倍功半。做实验时，一定要亲力亲为,务必要将每个步骤，每个细节弄清楚,弄明白,实验后，还要复习，思考，这样，你的印象才深刻，记得才牢固，否则，过后不久你就会忘得一干二净，这还不如不做。做实验时，老师还会根据自己的亲身体会，将一些课本上没有的知识教给我们，拓宽我们的眼界，使我们认识到这门课程在生活中的应用是那么的广泛。
实验的过程全是我们学生自己动手来完成的，这样，我们就必须要弄懂实验的原理。在这里我深深体会到哲学上理论对实践的指导作用：弄懂实验原理，而且体会到了实验的操作能力是靠自己亲自动手，亲自开动脑筋，亲自去请教别人才能得到提高的。
我们做实验绝对不能人云亦云，要有自己的看法，这样我们就要有充分的准备，若是做了也不知道是个什么实验，那么做了也是白做。
七、源程序清单及注释。
#include"stdio.h"
#include"malloc.h"
#include"windows.h"
#include"string.h"
#include"iostream.h"
int WST[256];
/*************************************
空闲区结构体定义
start_location 空闲区对象变量的开始位置
free_number 空闲区块数目
next 指向下一个空闲区的指针
**************************************/

typedef struct node{
int start_location;
int free_number;
struct node*next;
}free_link;

/*************************************
申请空间作业结构体定义
office[] 作业名
begin_location 作业申请空间后的开始位置
office_number 作业申请空间区的数目
next 指向下一个申请空闲区的作业指针
**************************************/

typedef struct link{
char office[20];
int begin_location;
int office_number;
struct link *next;
}office;

/**************************************
相关位示图操作的结构体定义
p 空间区链表指针
q 作业链表指针
***************************************/

typedef struct {
free_link *p;
office *q;
}work;

/***************************************
程序菜单
****************************************/

void menu(){
printf(" 文件的存取和回收\n");
printf(" 1--分配文件\n");
printf(" 2--回收文件\n");
printf(" 3--退出\n\t");
printf(" 请输入选项: ");
}

/***************************************
置空位示图
进行初始化
****************************************/
void zero_wst(){
int i;
for(i=0;i<256;i++)
WST[i]=0;
}

/****************************************
位示图输出显示
将初始化或者申请或者回收后的位示图进行显示
*****************************************/
void print_wst(int WST[256]){
int i,j=0;
printf("%3s"," ");
for(i=0;i<16;i++)
printf("%3d",i);
printf("\n");
printf("%3d",0);
for(i=0;i<256;i++){
j++;
printf("%3d",WST[i]);
if(j%16==0&&i!=0&&j!=256){
printf("\n");
printf("%3d",j/16);
}
}
printf("\n");
}

/**************************************
已经申请空间的作业相关情况输出显示
包括:
作业名
申请空间的开始位置和截至位置
***************************************/

void print_office(work *w){
office *q;
q=w->q;
q=q->next;
if(q!=NULL){
printf("已有文件:\n");
while(q!=NULL){
printf("\t%s:%d-%d\n",q->office,q->begin_location,q->begin_location+q->office_number-1);
q=q->next;
}
}
}

/*************************************
位示图操作的初始化
包括:空闲区链表的初始化
作业链表的初始化
**************************************/
work *start(){
free_link *p;
office *q;
work *w;
w=(work *)malloc(sizeof(work));
p=(free_link*)malloc(sizeof(free_link));
p->start_location=0;
p->free_number=256;
p->next=NULL;
q=(office *)malloc(sizeof(office));
q->next=NULL;
w->p=p;
w->q=q;
return w;
}

/**************************************
申请空间操作
***************************************/

work *request(work *w,int WST[256]){
int i,m,n,flag=0;
free_link *p,*r,*e;//r->free_number 用于查找空闲区的块数
office *q,*s,*t,*u;//s 创建新节点,存储新建文件的信息,n用于查找是否有重复节点
p=w->p;
r=p;
q=w->q;
t=q;
u=q->next;
printf("请输入文件名和块数:");
s=(office*)malloc(sizeof(office));
s->next=NULL;
while(t->next!=NULL)
t=t->next;
scanf("%s%d",&(s->office),&(s->office_number));
while(u!=NULL){
if(strcmp(s->office,u->office)==0){
flag=1;
printf("对不起,该文件已存在!\n");
free(s);
break;
}
u=u->next;
}
if(flag==0){
while(r!=NULL){
if((r->free_number)>=(s->office_number))//用于查找空闲区中空闲块数是否大于欲分配的块数
break;
r=r->next;
}
if(r==NULL){
printf("对不起,没有足够的空间分配失败!\n");
free(s);
}
else{
t->next=s;
m=r->start_location;//空闲区的起始地址
s->begin_location=r->start_location;//作业从空闲区的起始地址开始分配
r->start_location=r->start_location+s->office_number;//改变空闲区空闲块数的起始地址
r->free_number=r->free_number-s->office_number;//改变空间区块数的大小
n=(r->start_location-1);//新的空间区的起始地址-1
for(i=m;i<=n;i++)//模拟分配
WST[i]=1;
if(r->free_number==0){
if(p==r){//p==r说明内存中只有一个整块的空闲区
free(r);
p=NULL;
}
else{
e=p;
while(e!=NULL){
if(e->next==r)
break;
e=e->next;
}
e->next=r->next;
free(r);
}
}
}
}
w->p=p;
w->q=q;
return w;
}

/*********************************************
回收空间操作
**********************************************/
work *delect(work *w,int WET[]){
char name[20];
int i;
free_link *p,*r,*t;
office *q,*s,*e;
p=w->p;
r=p;
t=p;
q=w->q;
s=q;
e=q;
s=s->next;
if(s==NULL){
printf("没有可以回收的文件!\n");
}
else {
printf("请输入文件名:");
cin>>name;
while(s!=NULL){
if(strcmp(s->office,name)==0)
break;
s=s->next;
}
if(s==NULL){
cout<<"对不起没有找到相关文件!\n";
}
else{
if((WST[s->begin_location-1]==0&&WST[s->begin_location+s->office_number]==1&&s->begin_location-1>=0)
||(WST[s->begin_location-1]==0&&s->begin_location+s->office_number==256&&s->begin_location-1>=0)){
while(r!=NULL){
if((r->start_location+r->free_number)==s->begin_location)
break;
r=r->next;
}
r->free_number=r->free_number+s->office_number;
}
if((WST[s->begin_location-1]==1&&WST[s->begin_location+s->office_number]==0&&
s->begin_location+s->office_number<256)||(s->begin_location==0&&
WST[s->begin_location+s->office_number]==0&&s->begin_location+s->office_number<256)){
while(r!=NULL){
if((s->begin_location+s->office_number)==r->start_location)
break;
r=r->next;
}
r->start_location=r->start_location-s->office_number;
r->free_number=r->free_number+s->office_number;
}
if(WST[s->begin_location-1]==0&&WST[s->begin_location+s->office_number]==0&&
s->begin_location-1>=0&&s->begin_location+s->office_number<256){
while(r!=NULL){
if((s->begin_location+s->office_number)==r->start_location){
t=r;
break;
}
r=r->next;
}
r->free_number=r->free_number+s->office_number+t->free_number;
free(t);
}

if((WST[s->begin_location-1]==1&&WST[s->begin_location+s->office_number]==1&&s->begin_location-1>=0
&&s->begin_location+s->office_number<256)
||(s->begin_location==0&&WST[s->begin_location+s->office_number]==1&&
s->begin_location+s->office_number<256)
||(WST[s->begin_location-1]==1&&s->begin_location+s->office_number==256&&s->begin_location-1>=0)
||(s->begin_location==0&&s->begin_location+s->office_number==256)){

t=(free_link*)malloc(sizeof(free_link));
t->next=NULL;
t->start_location=s->begin_location;
t->free_number=s->office_number;
if(r==NULL)
p=t;
if(r!=NULL&&r->next==NULL){
if(r->start_location<s->begin_location)
r->next=t;
else{
t->next=r;
p=t;
}
}
if(r!=NULL&&r->next!=NULL){
while(r!=NULL&&r->next!=NULL){
if((r->start_location<s->begin_location)&&(s->begin_location<r->next->start_location))
break;
r=r->next;
}
t->next=r->next;
r->next=t;
}
}
for(i=s->begin_location;i<(s->begin_location+s->office_number);i++)
WST[i]=0;
while(e!=NULL){
if(e->next==s)
break;
e=e->next;
}
e->next=s->next;
free(s);
}
}
w->p=p;
w->q=q;
return w;
}

/****************************************
主函数
****************************************/
void main(){
int flag;
work *w;
zero_wst();
w=start();
while(1){
system("cls");
print_wst(WST);
print_office(w);

menu();
cin>>flag;
switch(flag){
case 1:w=request(w,WST);break;
case 2:w=delect(w,WST);break;
case 3:exit(0);
default:printf("输入错误,请重新输入!\n");break;
}
}
}