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

模拟实现用位示图法管理文件存储空间的分配与回收1模拟实现用位示图法管理文件存储空间的分配与回收1模拟实现用位示图法管理文件存储空间的分配与回收1xxx公司模拟实现用位示图法管理文件存储空间的分配与回收1文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度计算机科学与技术学院《操作系统》综合试验报告（2016/2017学年第一学期）学生姓名： 学生专业： 网络工程学生班级： 网络班学生学号： 2指导教师：2016年12月12日计算机科学与技术学院综合试验任务书课程设计名称《操作系统》课程设计课程设计题目模拟实现用位示图法管理文件存储空间的分配与回收学生姓名专业班级网学号2综合试验任务内容[问题描述]设计实现一个综合的应用程序。内容如下：（1）首先对位示图算法原理进行深刻的理解和掌握；（2）程序首先要给出位示图初态。分配时,参数为文件名及需要分配的块数。回收时，参数为文件名。（3)回答信息：分配时，能够分配时，给出文件名和分配的具体块号。否则,给出无法分配的信息。显示位示图。（4）回收时：给出回收的具体块号。显示位示图。[基本要求]（1）理解文件存储空间的分配与回收的基本概念，掌握产生文件存储空间的分配与回收的几种方法，体会位示图算法是管理文件存储空间的分配与回收的一种行之有效的方法。（2）通过编写程序实现位示图算法，进一步理解位示图算法的原理和执行过程，掌握位示图算法的描述和应用，进一步熟练掌握文件存储空间的分配与回收的方法。[测试要求]对每一个模块的功能进行黑盒测试，保证各个模块功能的正确性。指导教师：时间：年月5日目录TOC\o"1-3"\h\u第一章功能需求描述 1功能列表与说明 1操作界面 1界面操作 1第二章系统设计描述 2任务分解说明 2主要数据结构设计说明 2主要函数接口说明 2第三章算法设计描述 5主要函数和函数的流程图 5盘块的分配算法流程图 5盘块的回收算法流程图 6第四章开发过程描述 7程序源码 7程序中遇到的错误及错误原因 7测试程序功能所用的数据和测试方法 7第五章设计心得体会 8附录1程序源代码 9第一章功能需求描述功能列表与说明功能名称功能描述分配文件文件分配回收文件回收文件退出退出程序操作界面文件的存取和回收1.分配文件2.回收文件3.退出请输入选项：界面操作如图可以很清楚的看到可以输入123三个数分别对应分配文件、回收文件、退出三种操作。

第二章系统设计描述任务分解说明1.位示图法系统初始化。2.位示图法分配与回收算法。主要数据结构设计说明 1.空闲区结构体定义typedefstructnode{ intstart_location;申请空间作业结构体定义typedefstructlink{ charoffice[20]; 相关位示图操作的结构体定义 typedefstruct{ free_link*p; 示菜单函数 voidmenu(){}2.置空位示图进行初始化 voidzero_wst(){ inti; for(i=0;i<256;i++) WST[i]=0;}3.位示图输出显示将初始化或者申请或者回收后的位示图进行显示voidprint_wst(intWST[256]){}4.已经申请空间的作业相关情况输出显示包括:作业名、申请空间的开始位置和截至位置 voidprint_office(work*w){}5.位示图操作的初始化包括:空闲区链表的初始化、作业链表的初始化 work*start(){}6.申请空间操作 work*request(work*w,intWST[256]){}7.回收空间操作work*delect(work*w,intWET[]){}8.主函数voidmain(){ intflag; work*w; zero_wst(); w=start(); while(1){ system("cls"); print_wst(WST); print_office(w); menu(); cin>>flag; switch(flag){ case1:w=request(w,WST);break; case2:w=delect(w,WST);break; case3:exit(0); default:printf("输入错误,请重新输入!\n");break; } }}

第三章算法设计描述主要函数和函数的流程图盘块的分配算法流程图RRequest()分配输入文件名,输入文件名,和块数.strcmp(s->office,u->office)==0strcmp(s->office,u->office)==0该文件是否已存在否r->free_number>=s->office_number能否查找到一个足r->free_number>=s->office_number能否查找到一个足够的空闲区域否将该作业结点插入作业链表表尾,,将该作业结点插入作业链表表尾,,从该区域分配出对应大小空间,修改位示图当前空盘区块数是否分配完当前空盘区块数是否分配完否是释放该空闲区结点释放该空闲区结点,把修改work里面两个首地址返回返回图3-1盘块的分配盘块的回收算法流程图DelectDelect()回收输入要查找的文件名输入要查找的文件名,查找能否找到对应文件能否找到对应文件要回收的单元前为空是要回收的单元前为空是把该单元块数加入前一个空闲区结点否把该单元块数加入前一个空闲区结点要回收的单元后为空要回收的单元后为空是否把空闲区起始地址该为当前开始盘块空闲区盘块增加要回收的单元前后都空把空闲区起始地址该为当前开始盘块空闲区盘块增加要回收的单元前后都空结点空盘起始地址改为前一个,空闲区盘块增加结点空盘起始地址改为前一个,空闲区盘块增加要回收的单元自成空盘区结点否要回收的单元自成空盘区结点把该结点插入空闲区链表是把该结点插入空闲区链表修改位示图对应盘块的的内容修改位示图对应盘块的的内容,删除该文件结点.修改work里面两个首地址返回返回图3-2盘块的回收算法流程图第四章开发过程描述程序源码 由于源码较长，单独附加在后面，见附录1-程序源码程序中遇到的错误及错误原因 编程中几乎没有遇到什么大的问题，只有一些语法中的小错误，编译器就解决完毕。测试程序功能所用的数据和测试方法 此次测试使用黑盒测试方法，目的是测试功能是否跟预期一样测试用例预期输出实际输出输入1选择分配功能输出请输入文件名和块数输出请输入文件名和块数输入文件名和块数显示已有文件名：块数显示已有文件名：块数输入2选择回收输出请输入文件名输出请输入文件名

第五章设计心得体会1.准备越充分，实验越顺利。古人云，磨刀不误砍柴工。前期的知识储备、文献储备、材料准备、方法准备可以避免手忙脚乱，充分的预实验使你充满信心。一步一个脚印，就不必“从头再来”。最不能容忍的是在开始的几步偷懒，造成后面总有一些无法排除的障碍。2.交流是最好的老师做实验遇到困难是家常便饭。你的第一反应是什么反复尝试放弃看书这些做法都有道理，但首先应该想到的是交流。对有身份的人，私下的请教体现你对他的尊重；对同年资的人，公开的讨论可以使大家畅所欲言，而且出言谨慎。千万不能闭门造车。一个实验折腾半年，后来别人告诉你那是死路，岂不冤大头3.一半时间做实验，一半时间看文献。千万不能把时间全部消耗在实验台上。看文献、看书、看别人的操作、听别人的经验、研究别人的思路，边做边思考。要学会比较，不要盲从。否则，会被一些小小的问题困扰许久。附录1程序源代码#include""#include""#include""#include""///#include""#include<iostream>usingnamespacestd;intWST[256];/*************************************空闲区结构体定义start_location空闲区对象变量的开始位置free_number空闲区块数目next指向下一个空闲区的指针**************************************/typedefstructnode{ intstart_location; intfree_number; structnode*next; }free_link;/*************************************申请空间作业结构体定义office[]作业名begin_location作业申请空间后的开始位置office_number作业申请空间区的数目next指向下一个申请空闲区的作业指针**************************************/typedefstructlink{ charoffice[20]; intbegin_location; intoffice_number; structlink*next; }office;/**************************************相关位示图操作的结构体定义p空间区链表指针q作业链表指针***************************************/typedefstruct{ free_link*p; office*q;}work;/***************************************程序菜单****************************************/voidmenu(){ 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(intWST[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; returnw;}/**************************************申请空间操作***************************************/work*request(work*w,intWST[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; returnw;}/*********************************************回收空间操作**********************************************/work*delect(work*w,intWET[]){ charname[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->offic