外存空闲空间管理模块的设计与实现C语言

计算机科学与应用系课程设计报告操作系统原理姓名学号指导教师专业日期成绩题目外存空闲空间管理模块的设计与实现指导教师评语目录1.题目描述......................................................................................................................................12.设计思想......................................................................................................................................13.功能..............................................................................................................................................14.数据结构和算法设计..................................................................................................................14.1数据结构.............................................................................................................................14.2算法设计.............................................................................................................................15.流程图..........................................................................................................................................25.1空闲表法流程图.................................................................................................................25.2位示图法流程图.................................................................................................................46.开发环境........................................................................................................................................67.结果分析........................................................................................................................................68.课程设计总结..............................................................................................................................10参考文献.........................................................................................................................................10附录：............................................................................................................................................1011.题目描述文件管理要解决的重要问题之一是如何为新创建的文件分配存储空间。其分配方法与内存的分配有诸多相似之处，即同样可采取连续分配方式或离散分配方式。前者具有较高的文件访问速度，但可能产生较多的外存零头；后者能有效地利用外存空间，但访问速度较慢。不论哪种分配方式，存储空间的基本分配单位都是磁盘块而非字节。为了实现存储空间的分配，系统首先必须能记住存储空间的使用情况。为此，系统应为分配存储空间而设置相应的数据结构；其次，系统应提供对存储空间进行分配和回收的手段。2.设计思想常用的文件存储空间的管理方法有：空闲表法、空闲链表法、位示图法、成组链接法。本次设计我用了空闲表法和位示图法来模拟实现外存空闲空间的管理。（1）空闲表法空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。（2）位示图法位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。磁盘上所有的盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，成为位示图。3.功能本设计是模拟实现外存空闲空间的管理，用户可以选择空闲表法或者位示图法来进行文件的分配与回收并查看各个文件的存储状态。4.数据结构和算法设计4.1数据结构（1）空闲表法数据结构分区表目结构定义structPartition。（2）位示图法数据结构空闲区结构体定义free_link、申请空间作业结构体定义office、相关位示图操作的结构体定义work。4.2算法设计（1）空闲表法算法设计空闲盘区的分配采用首次适应算法。在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者予以合并。（2）位示图法算法设计盘块分配时，顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位，转换成与之对应的盘块号，然后修改位示图。盘块回收时，将回收盘块的盘块号转换成位示2图的行号和列号，修改位示图。5.流程图5.1空闲表法流程图(1)盘块分配流程图，如图5-1所示。否否是是否是空闲分区大小是否大于文件大小空闲分区—文件大小=规定大小找完无法分配该空闲分区分给文件从该空间总划出申请空间修改分区说明表、空闲表返回查找空闲分区图5-1空闲表盘块分配流程图3(2)盘块回收流程图，如图5-2所示。否是否否是是5-2空闲表法盘块回收流程图回收的文件名字是否存在找到该文件存储盘块，标志位空表目后接空闲分区空闲？合并到后分区前空闲分区空闲？合并到前分区返回提示出错输入要查找的文件名,查找45.2位示图法流程图（1）盘块分配流程图，如图5-3所示。否是否是否是图5-3位示图法盘块分配流程图输入文件名和块数.strcmp(s-office,u-office)==0该文件是否已存在r-free_number=s-office_number能否查找到一个足够的空闲区域将该作业结点插入作业链表表尾，从该区域分配出对应大小空间,修改位示图当前空盘区块数是否分配完释放该空闲区结点,把修改work里面两个首地址返回Request()分配5（2）盘块回收流程图，如图5-4所示。是是否是否是否否图5-4位示图法盘块回收流程图要回收的单元自成空盘区结点Delect()回收输入要查找的文件名,查找能否找到对应文件要回收的单元前为空要回收的单元后为空要回收的单元前后都空把该结点插入空闲区链表修改位示图对应盘块的的内容,删除该文件结点.修改work里面两个首地址返回把空闲区起始地址改为当前开始盘块空闲区盘块增加结点空盘起始地址改为前一个,空闲区盘块增加把该单元块数加入前一个空闲区结点66.开发环境Windows系统，运行环境：VisualC++6.0。7.结果分析（1）运行首页面。（2）输入1，选择位示图法。（3）选择1，分配文件。（4）输入文件名1和块数11。7（5）选择1，继续分配文件，并输入文件名2和块数22。（6）输入1，继续分配文件，并输入文件名3和块数33。8（7）选择2，回收文件，并输入回收文件2。（8）返回首页面，选择2，用空闲表法。9（9）输入256。（10）输入1，选择分配，并且输入文件名1和大小11，查看分配状态。（11）输入1，继续分配，并且输入文件名2和大小22，查看分配状态。（12）输入2，选择回收，并且输入回收文件名2，查看分配状态。108.课程设计总结通过做这个实验，我明白了在做实验前，一定要将课本上的知识吃透，因为这是做实验的基础，否则，在老师讲解时就会听不懂，在编程序时就会思维混乱，摸不清头绪。做实验时，一定要亲力亲为，务必要将每个步骤，每个细节弄清楚，弄明白。实验后，还要复习，思考，这样印象才深刻，记得才牢固。实验的过程中我们必须要弄懂实验的原理。在这里我深深体会到哲学上理论对实践的指导作用：弄懂实验原理，而且体会到了实验的操作能力是靠自己亲自动手，亲自开动脑筋，亲自去请教别人才能得到提高的。在这里，感谢荆老师对我的指导和启迪，感谢同学们对我的帮助，这次实验虽然做的不算特别完美，不过我已经很努力了。这次实验对我对这部分知识的理解和编程能力有了很大的提高，以后我会更加努力的去做每一件事。参考文献【1】汤晓丹、梁红兵·计算机操作系统（第三版）西安：西安电子科技大学出版社，2007年：引用231页~233页。【2】揣锦华·C++程序设计语言（第一版）西安：西安电子科技大学出版社，2003年。【3】张坤、姜立秋·操作系统实验教程（第一版）北京：清华大学出版社，2008年。附录：#includestdio.h#includestdlib.h#includemalloc.h11#includewindows.h#includestring.h#includeiostream.hintMAX_SEGMENT=10;//最大碎片值structPartition//分区表目{intPar_Size;//分区大小intPar_No;//分区序号或者名字intAddr;//分区地址intIsUse;//分区使用情况,0表示空闲，1表示使用Partition*pri;//前向指针Partition*next;//后向指针};Partition*Int()//函数，返回Partition类型指针{//初始化空闲分区表Partition*list,*H,*H1;list=(structPartition*)malloc(sizeof(structPartition));list-next=NULL;H=list;if(!list){printf(\n错误,初始化分配失败！程序结束);exit(1);}H1=(structPartition*)malloc(sizeof(structPartition));printf(请预先输入分区总大小(以盘块为单位)：);scanf(%