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

计算机科学与技术学院
《操作系统》综合试验报告
（2016/2017学年第一学期）
学生姓名:
学生专业：网络工程
学生班级：网络班
学生学号： 2
指导教师：
2016年　12　月　12　日
计算机科学与技术学院
综合试验任务书
课程设计名称
《操作系统》课程设计
课程设计题目
模拟实现用位示图法管理文件存储空间的分配与回收
学生姓名

专业班级
网
学号
2
综合试验任务内容
［问题描述]
设计实现一个综合的应用程序。内容如下:
（1）首先对位示图算法原理进行深刻的理解和掌握；
（2)程序首先要给出位示图初态。分配时,参数为文件名及需要分配的块
数.回收时,参数为文件名.
（3）回答信息：分配时，能够分配时，给出文件名和分配的具体块号。
否则，给出无法分配的信息。显示位示图.
（4)回收时:给出回收的具体块号。显示位示图.
[基本要求］
（1）理解文件存储空间的分配与回收的基本概念，掌握产生文件存储空间的分配与回收的几种方法，体会位示图算法是管理文件存储空间的分配与回收的一种行之有效的方法。
（2)通过编写程序实现位示图算法，进一步理解位示图算法的原理和执行过程，掌握位示图算法的描述和应用，进一步熟练掌握文件存储空间的分配与回收的方法。
［测试要求］
对每一个模块的功能进行黑盒测试,保证各个模块功能的正确性。
指导教师：
时 间: 年 月 5 日

目录
第一章 功能需求描述1
1。1功能列表与说明1
1。2 操作界面1
1.3 界面操作1
第二章 系统设计描述2
2。1 任务分解说明2
2。2主要数据结构设计说明2
2。3主要函数接口说明2
第三章算法设计描述5
3。1主要函数和函数的流程图5
3.1.1。 盘块的分配算法流程图5
3。2。2。盘块的回收算法流程图6
第四章 开发过程描述7
4。1 程序源码7
4.2 程序中遇到的错误及错误原因7
4.3测试程序功能所用的数据和测试方法7
第五章 设计心得体会8
附录1 程序源代码9
第一章 功能需求描述
1.1功能列表与说明
功能名称
功能描述
分配文件
文件分配
回收文件
回收文件
退出
退出程序
1.2 操作界面
文件的存取和回收
1。分配文件
2。回收文件
3.退出
请输入选项:
1.3 界面操作
如图可以很清楚的看到可以输入1 2 3 三个数分别对应分配文件、回收文件、退出三种操作。
第二章 系统设计描述
2。1 任务分解说明
1。 位示图法系统初始化。
2 .位示图法分配与回收算法。
2.2主要数据结构设计说明
1。空闲区结构体定义
typedefstruct node{
intstart_location; //空闲区对象变量的开始位置
intfree_number; //空闲区块数目
struct node*next; //指向下一个空闲区的指针
｝free_link；
2. 申请空间作业结构体定义
typedefstruct link｛
char office［20]； //作业名
intbegin_location； //作业申请空间后的开始位置
intoffice_number; //作业申请空间区的数目
struct link ＊next； //指向下一个申请空闲区的作业指针
｝office;
3。 相关位示图操作的结构体定义
typedefstruct {
free_link ＊p； //空间区链表指针
office ＊q； //作业链表指针
}work;
2.3主要函数接口说明
1.显示菜单函数
void menu（）｛｝
2. 置空位示图进行初始化
voidzero_wst(）{
inti;
for(i=0；i〈256;i++)
WST[i］=0；
｝
3。 位示图输出显示将初始化或者申请或者回收后的位示图进行显示
voidprint_wst（int WST[256])｛}
4. 已经申请空间的作业相关情况输出显示包括:作业名、申请空间的开始位置和截至位置
voidprint_office（work *w){}
5。 位示图操作的初始化包括：空闲区链表的初始化、作业链表的初始化
work *start（）{｝
6. 申请空间操作
work *request（work ＊w，int WST[256］）｛}
7。 回收空间操作
work *delect(work *w，int WET［］){}
8。 主函数
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;
}
｝
｝
第三章算法设计描述
3。1主要函数和函数的流程图
3.1.1。 盘块的分配算法流程图
Request()分配

输入文件名,和块数.

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

否

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

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

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

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

返回

图3—1 盘块的分配
3.2。2.盘块的回收算法流程图
Delect()回收

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

能否找到对应文件

要回收的单元前为空
是

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

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

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

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

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

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

返回

图3—2 盘块的回收算法流程图
第四章 开发过程描述
4。1 程序源码
由于源码较长，单独附加在后面，见附录1—程序源码
4。2 程序中遇到的错误及错误原因
编程中几乎没有遇到什么大的问题，只有一些语法中的小错误，编译器就解决完毕。
4.3测试程序功能所用的数据和测试方法
此次测试使用黑盒测试方法，目的是测试功能是否跟预期一样
测试用例
预期输出
实际输出
输入1选择分配功能
输出请输入文件名和块数
输出请输入文件名和块数
输入文件名和块数
显示已有文件名：块数
显示已有文件名:块数
输入2选择回收
输出请输入文件名
输出请输入文件名
第五章 设计心得体会
1。准备越充分，实验越顺利。古人云,磨刀不误砍柴工。前期的知识储备、文献储备、材料准备、方法准备可以避免手忙脚乱,充分的预实验使你充满信心。一步一个脚印,就不必“从头再来”.最不能容忍的是在开始的几步偷懒，造成后面总有一些无法排除的障碍.
2。交流是最好的老师做实验遇到困难是家常便饭。你的第一反应是什么?反复尝试？放弃?看书？这些做法都有道理，但首先应该想到的是交流.对有身份的人，私下的请教体现你对他的尊重;对同年资的人，公开的讨论可以使大家畅所欲言，而且出言谨慎.千万不能闭门造车。一个实验折腾半年，后来别人告诉你那是死路，岂不冤大头？
3。一半时间做实验,一半时间看文献。
千万不能把时间全部消耗在实验台上。看文献、看书、看别人的操作、听别人的经验、研究别人的思路，边做边思考。要学会比较，不要盲从.否则，会被一些小小的问题困扰许久.
附录1 程序源代码
＃include”stdio.h”
#include"malloc。h”
＃include”windows。h"
#include”string。h"
///#include"iostream。h”
#include 〈iostream〉
using namespace std；
int WST［256］；
/＊＊*＊＊*＊＊＊＊＊＊＊**＊*＊＊*＊＊＊＊**＊＊＊＊＊*＊***＊
空闲区结构体定义
start_location 空闲区对象变量的开始位置
free_number 空闲区块数目
next 指向下一个空闲区的指针
＊＊*＊*＊＊＊＊＊＊＊＊＊*＊＊＊＊＊＊＊*＊*＊*＊*＊＊＊**＊＊＊＊/
typedefstruct node{
intstart_location;
intfree_number;
struct node＊next;
}free_link；
/＊＊*＊*＊＊＊*＊*＊*＊＊＊＊＊***＊＊＊＊＊*＊＊＊*＊＊＊＊**
申请空间作业结构体定义
office［] 作业名
begin_location 作业申请空间后的开始位置
office_number 作业申请空间区的数目
next 指向下一个申请空闲区的作业指针
＊＊＊*＊*＊*＊**＊＊＊*＊*＊＊＊＊*＊*＊＊*＊**＊*＊**＊＊*/
typedefstruct link｛
char office[20］；
intbegin_location；
intoffice_number;
struct link *next；
｝office；
/*＊＊＊*＊＊*＊＊＊＊**＊＊＊＊**＊*＊＊＊＊＊＊*＊＊＊＊*＊＊*＊
相关位示图操作的结构体定义
p 空间区链表指针
q 作业链表指针
＊＊＊＊*＊＊＊**＊＊＊＊*＊＊**＊*****＊＊＊*＊*＊＊**＊**＊/
typedefstruct ｛
free_link *p;
office *q;
｝work；
/＊＊***＊*＊*＊＊＊＊＊**＊＊＊*＊＊＊＊＊＊＊＊＊＊＊＊***＊＊＊＊
程序菜单
*＊**＊＊＊＊＊＊*＊**＊＊*＊＊＊＊**＊*＊**＊*＊*＊＊*＊＊＊**/
void menu（)｛
printf(” 文件的存取和回收\n")；
printf（" 1——分配文件\n”）;
printf（” 2—-回收文件\n”）；
printf（” 3——退出\n\t”）;
printf(” 请输入选项： ”)；
}
/*＊**＊*＊＊＊＊＊****＊＊*＊＊**＊＊*＊*＊＊＊**＊＊*＊＊＊*
置空位示图进行初始化
＊*＊＊**＊**＊***＊＊＊*＊**＊＊＊＊*＊*＊＊＊＊＊＊＊＊＊＊＊＊＊/
voidzero_wst(）{
inti；
for(i=0;i<256；i++）
WST[i］=0;
}
/*＊＊＊**＊*＊*＊＊＊＊*＊＊*＊*＊＊**＊＊*＊＊*＊＊＊＊＊＊＊＊＊＊
位示图输出显示将初始化或者申请或者回收后的位示图进行显示
*＊**＊＊＊＊＊＊＊＊*＊＊*****＊***＊*＊＊＊＊＊＊＊＊＊＊＊＊*＊＊/
voidprint_wst（int WST［256］)｛
inti，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")；
｝
/＊＊＊＊*＊＊＊*＊**＊＊＊＊＊**＊＊*＊＊＊*＊＊*＊*＊＊*＊＊＊*
已经申请空间的作业相关情况输出显示
包括：作业名申请空间的开始位置和截至位置
＊＊*＊＊＊＊****＊＊＊＊＊＊＊＊＊*＊＊＊**＊***＊*＊**＊＊*＊/
voidprint_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］){
inti,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］；
inti;
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;
｝
｝
｝
计算机科学与技术学院
课程设计成绩评审表
课程设计名称
《软件分析与建模》课程设计
课程设计题目

学生姓名

专业班级

同组人

学号

指导教师

设计成绩

评价内容
签 字：
时 间： 年 月 日

17