模拟实现用位示图法管理文件存储空间的分配及回收.doc
-"操作系统"综合试验报告目录第一章功能需求描述21.1功能列表与说明21.2 操作界面21.3 界面操作2第二章系统设计描述22.1 任务分讲解明22.2主要数据构造设计说明22.3主要函数接口说明2第三章算法设计描述23.1主要函数和函数的流程图23.1.1.盘块的分配算法流程图23.2.2.盘块的回收算法流程图2第四章开发过程描述24.1 程序源码24.2 程序中遇到的错误及错误原因24.3测试程序功能所用的数据和测试法2第五章设计心得体会2附录1 程序源代码2. z.-第一章功能需求描述1.1功能列表与说明功能名称功能描述分配文件文件分配回收文件回收文件退出退出程序1.2 操作界面文件的存取和回收1.分配文件2.回收文件3.退出请输入选项:1.3 界面操作如图可以很清楚的看到可以输入1 2 3 三个数分别对应分配文件、回收文件、退出三种操作。第二章系统设计描述2.1 任务分讲解明1. 位示图法系统初始化。2 .位示图法分配与回收算法。2.2主要数据构造设计说明1.空闲区构造体定义typedef struct nodeint start_location; /空闲区对象变量的开场位置int free_number; /空闲区块数目struct node*ne*t; /指向下一个空闲区的指针free_link; 2. 申请空间作业构造体定义typedef struct linkchar office20;/作业名int begin_location;/作业申请空间后的开场位置int office_number;/作业申请空间区的数目struct link *ne*t;/指向下一个申请空闲区的作业指针office;3. 相关位示图操作的构造体定义typedef struct free_link *p;/空间区链表指针office *q;/作业链表指针work;2.3主要函数接口说明1.显示菜单函数 void menu() 2. 置空位示图进展初始化 void zero_wst() int i; for(i=0;i<256;i+) WSTi=0;3. 位示图输出显示将初始化或者申请或者回收后的位示图进展显示void print_wst(int WST256)4. 已经申请空间的作业相关情况输出显示包括:作业名、申请空间的开场位置和截至位置void print_office(work *w) 5. 位示图操作的初始化包括:空闲区链表的初始化、作业链表的初始化work *start() 6. 申请空间操作work *request(work *w,int WST256) 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:e*it(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 WST256;/*空闲区构造体定义start_location 空闲区对象变量的开场位置free_number 空闲区块数目ne*t 指向下一个空闲区的指针*/typedef struct nodeint start_location;int free_number;struct node*ne*t;free_link;/*申请空间作业构造体定义office 作业名begin_location 作业申请空间后的开场位置office_number 作业申请空间区的数目ne*t 指向下一个申请空闲区的作业指针*/typedef struct linkchar office20;int begin_location;int office_number;struct link *ne*t;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;i<256;i+)WSTi=0;/*位示图输出显示将初始化或者申请或者回收后的位示图进展显示*/void print_wst(int WST256)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",WSTi);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->ne*t;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->ne*t;/*位示图操作的初始化包括:空闲区链表的初始化作业链表的初始化*/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->ne*t=NULL;q=(office *)malloc(sizeof(office);q->ne*t=NULL;w->p=p;w->q=q;return w;/*申请空间操作*/work *request(work *w,int WST256)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->ne*t;printf("请输入文件名和块数:");s=(office*)malloc(sizeof(office);s->ne*t=NULL;while(t->ne*t!=NULL)t=t->ne*t;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->ne*t;if(flag=0)while(r!=NULL)if(r->free_number)>=(s->office_number)/用于查找空闲区中空闲块数是否大于欲分配的块数break;r=r->ne*t;if(r=NULL)printf("对不起,没有足够的空间分配失败!n");free(s);elset->ne*t=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);/新的空间区的起始地址-1for(i=m;i<=n;i+)/模拟分配WSTi=1;if(r->free_number=0)if(p=r)/p=r说明存中只有一个整块的空闲区free(r);p=NULL;elsee=p;while(e!=NULL)if(e->ne*t=r)break;e=e->ne*t;e->ne*t=r->ne*t;free(r);w->p=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->ne*t;if(s=NULL)printf("没有可以回收的文件!n");else printf("请输入文件名:");cin>>name;while(s!=NULL)if(strcmp(s->office,name)=0)break;s=s->ne*t;if(s=NULL)cout<<"对不起没有找到相关文件!n"elseif(WSTs->begin_location-1=0&&WSTs->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->ne*t;r->free_number=r->free_number+s->office_number;if(WSTs->begin_location-1=1&&WSTs->begin_location+s->office_number=0&&s->begin_location+s->office_number<256)|(s->begin_location=0&&WSTs->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->ne*t;r->start_location=r->start_location-s->office_number;r->free_number=r->free_number+s->office_number;if(WSTs->begin_location-1=0&&WSTs->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->ne*t;r->free_number=r->free_number+s->office_number+t->free_number;free(t);if(WSTs->begin_location-1=1&&WSTs->begin_location+s->office_number=1&&s->begin_location-1>=0&&s->begin_location+s->office_number<256)|(s->begin_location=0&&WSTs->begin_location+s->office_number=1&& s->begin_location+s->office_number<256)|(WSTs->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->ne*t=NULL;t->start_location=s->begin_location;t->free_number=s->office_number;if(r=NULL)p=t;if(r!=NULL&&r->ne*t=NULL)if(r->start_location<s->begin_location)r->ne*t=t;elset->ne*t=r;p=t;if(r!=NULL&&r->ne*t!=NULL)while(r!=NULL&&r->ne*t!=NULL)if(r->start_location<s->begin_location)&&(s->begin_location<r->ne*t->start_location)break;r=r->ne*t;t->ne*t=r->ne*t;r->ne*t=t;for(i=s->begin_location;i<(s->begin_location+s->office_number);i+)WSTi=0;while(e!=NULL)if(e->ne*t=s)break;e=e->ne*t;e->ne*t=s->ne*t;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:e*it(0);default:printf("输入错误,请重新输入!n");break;. z.