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

1、 计算机科学与技术学院操作系统综合试验报告 （2016/2017学年 第一学期）学生姓名：学生专业： 网络工程学生班级： 网络班学生学号：2指导教师： 2016年12月12日计算机科学与技术学院综合试验任务书课程设计名称操作系统课程设计课程设计题目模拟实现用位示图法管理文件存储空间的分配与回收学生姓名专业班级网学号2综合试验任务内容问题描述 设计实现一个综合的应用程序。内容如下： （1）首先对位示图算法原理进行深刻的理解和掌握； （2）程序首先要给出位示图初态。分配时,参数为文件名及需要分配的块 数。回收时，参数为文件名。 （3)回答信息：分配时，能够分配时，给出文件名和分配的具体块号。 否则

2、,给出无法分配的信息。显示位示图。 （4）回收时：给出回收的具体块号。显示位示图。 基本要求 （1）理解文件存储空间的分配与回收的基本概念，掌握产生文件存储空间的分配与回收的几种方法，体会位示图算法是管理文件存储空间的分配与回收的一种行之有效的方法。（2）通过编写程序实现位示图算法，进一步理解位示图算法的原理和执行过程，掌握位示图算法的描述和应用，进一步熟练掌握文件存储空间的分配与回收的方法。测试要求 对每一个模块的功能进行黑盒测试，保证各个模块功能的正确性。指导教师： 时 间： 年 月 5 日目录第一章 功能需求描述11.1功能列表与说明11.2 操作界面11.3 界面操作1第二章 系统设计

3、描述22.1 任务分解说明22.2主要数据结构设计说明22.3主要函数接口说明2第三章算法设计描述53.1主要函数和函数的流程图53.1.1. 盘块的分配算法流程图53.2.2.盘块的回收算法流程图6第四章 开发过程描述74.1 程序源码74.2 程序中遇到的错误及错误原因74.3测试程序功能所用的数据和测试方法7第五章 设计心得体会8附录1 程序源代码9第一章 功能需求描述1.1功能列表与说明功能名称功能描述分配文件文件分配回收文件回收文件退出退出程序1.2 操作界面文件的存取和回收1.分配文件2.回收文件3.退出请输入选项：1.3 界面操作如图可以很清楚的看到可以输入1 2 3 三个数分别

4、对应 分配文件、回收文件、退出三种操作。第二章 系统设计描述2.1 任务分解说明1. 位示图法系统初始化。2 .位示图法分配与回收算法。2.2主要数据结构设计说明1.空闲区结构体定义 typedef struct nodeint start_location; /空闲区对象变量的开始位置int free_number; /空闲区块数目struct node*next; /指向下一个空闲区的指针free_link; 2. 申请空间作业结构体定义typedef struct linkchar office20;/作业名int begin_location;/作业申请空间后的开始位置int offi

5、ce_number;/作业申请空间区的数目struct link *next;/指向下一个申请空闲区的作业指针office;3. 相关位示图操作的结构体定义typedef struct free_link *p;/空间区链表指针office *q;/作业链表指针work;2.3主要函数接口说明1.显示菜单函数 void menu() 2. 置空位示图进行初始化 void zero_wst() int i; for(i=0;iflag;switch(flag)case 1:w=request(w,WST);break;case 2:w=delect(w,WST);break;case 3:exi

6、t(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()回收输入要查找的文件

7、名,查找能否找到对应文件要回收的单元前为空是是把该单元块数加入前一个空闲区结点 否要回收的单元后为空是否把空闲区起始地址该为当前开始盘块空闲区盘块增加要回收的单元前后都空结点空盘起始地址改为前一个,空闲区盘块增加要回收的单元自成空盘区结点否把该结点插入空闲区链表是修改位示图对应盘块的的内容,删除该文件结点. 修改work里面两个首地址返回图3-2 盘块的回收算法流程图第四章 开发过程描述4.1 程序源码由于源码较长，单独附加在后面，见附录1-程序源码4.2 程序中遇到的错误及错误原因编程中几乎没有遇到什么大的问题，只有一些语法中的小错误，编译器就解决完毕。4.3测试程序功能所用的数据和测试方法

8、此次测试使用黑盒测试方法，目的是测试功能是否跟预期一样测试用例预期输出实际输出输入1选择分配功能输出请输入文件名和块数输出请输入文件名和块数输入文件名和块数显示已有文件名：块数显示已有文件名：块数输入2选择回收输出请输入文件名输出请输入文件名第五章 设计心得体会1.准备越充分，实验越顺利。古人云，磨刀不误砍柴工。前期的知识储备、文献储备、材料准备、方法准备可以避免手忙脚乱，充分的预实验使你充满信心。一步一个脚印，就不必“从头再来”。最不能容忍的是在开始的几步偷懒，造成后面总有一些无法排除的障碍。2.交流是最好的老师做实验遇到困难是家常便饭。你的第一反应是什么？反复尝试？放弃？看书？这些做法都有

9、道理，但首先应该想到的是交流。对有身份的人，私下的请教体现你对他的尊重；对同年资的人，公开的讨论可以使大家畅所欲言，而且出言谨慎。千万不能闭门造车。一个实验折腾半年，后来别人告诉你那是死路，岂不冤大头？3.一半时间做实验，一半时间看文献。千万不能把时间全部消耗在实验台上。看文献、看书、看别人的操作、听别人的经验、研究别人的思路，边做边思考。要学会比较，不要盲从。否则，会被一些小小的问题困扰许久。附录1 程序源代码#includestdio.h#includemalloc.h#includewindows.h#includestring.h/#includeiostream.h#include

10、using namespace std;int WST256;/*空闲区结构体定义start_location 空闲区对象变量的开始位置free_number 空闲区块数目next 指向下一个空闲区的指针*/typedef struct nodeint start_location;int free_number;struct node*next;free_link;/*申请空间作业结构体定义office 作业名begin_location 作业申请空间后的开始位置office_number 作业申请空间区的数目next 指向下一个申请空闲区的作业指针*/typedef struct link

11、char office20;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-退出nt);printf( 请输入选项: );/*置空位示图进行初始化*/void zero_wst()int i;for(i=0

12、;i256;i+)WSTi=0;/*位示图输出显示将初始化或者申请或者回收后的位示图进行显示*/void print_wst(int WST256)int i,j=0;printf(%3s,);for(i=0;i16;i+)printf(%3d,i);printf(n);printf(%3d,0);for(i=0;iq;q=q-next;if(q!=NULL)printf(已有文件:n);while(q!=NULL)printf(t%s:%d-%dn,q-office,q-begin_location,q-begin_location+q-office_number-1);q=q-next;/

13、*位示图操作的初始化包括:空闲区链表的初始化作业链表的初始化*/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

14、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(strcm

15、p(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);elset-next=s;m=r-start_location;/空闲区的起始地址s-begin_location=r-start_location;/作业从空闲区的起始

16、地址开始分配r-start_location=r-start_location+s-office_number;/改变空闲区空闲块数的起始地址r-free_number=r-free_number-s-office_number;/改变空间区块数的大小n=(r-start_location-1);/新的空间区的起始地址-1for(i=m;ifree_number=0)if(p=r)/p=r说明内存中只有一个整块的空闲区free(r);p=NULL;elsee=p;while(e!=NULL)if(e-next=r)break;e=e-next;e-next=r-next;free(r);w-p

17、=p;w-q=q;return w;/*回收空间操作*/work *delect(work *w,int WET)char name20;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(请输入文件名:);cinname;while(s!=NULL)if(strcmp(s-office,name)=0)break;s=s-next;if(s=NULL)coutbegin_location-1=0&WSTs-

18、begin_location+s-office_number=1&s-begin_location-1=0)|(WSTs-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(WSTs-begin_location-1=1&WSTs-begin

19、_location+s-office_number=0&s-begin_location+s-office_numberbegin_location=0&WSTs-begin_location+s-office_number=0&s-begin_location+s-office_numberbegin_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_nu

20、mber;if(WSTs-begin_location-1=0&WSTs-begin_location+s-office_number=0&s-begin_location-1=0&s-begin_location+s-office_numberbegin_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(WSTs-begin_location-1=1&WSTs-begin_locat

21、ion+s-office_number=1&s-begin_location-1=0&s-begin_location+s-office_numberbegin_location=0&WSTs-begin_location+s-office_number=1& s-begin_location+s-office_numberbegin_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!=N