实践教学
*******************
兰州理工大学
计算机和通信学院
2012年秋季学期 操作系统原理课程设计
题 目： 磁盘空间管理模拟实验 专业班级： 计算机科学和技术4班 姓 名： 张 建 新 学 号： 1 0 2 4 0 4 2 5 指导教师： 王 燕
成 绩： ____________________
目 录
摘要 ........................................................................................................... 2 正文 ........................................................................................................... 3
一、问题描述 ............................................................................................................... 3 二、设计目的 ............................................................................................................... 3 三、设计要求 ............................................................................................................... 4 四、详细设计 ............................................................................................................... 4
五、结果分
析...................................................................................................................8
设计总结 .................................................................................................. 9 参考文献 ................................................................................................ 10 致 谢 ..................................................................................................... 11 附录：部分源代码 .............................................................................. 10
摘 要
要把文件信息存放在存储介质上，必须先找出存储介质上可供使用的空闲块。存储介质上某个文件不再需要时，又要收回它所占的存储空间作为空闲块。用户作业在执行期间经常要求建立一个新文件或撤消一个不再需要的文件，因此，文件系统必须要为它们分配存储空间或收回它所占的存储空间。如何实现存储空间的分配和收回，取决于对空闲块的管理方法，主要有两种对磁盘存储空间的分配和收回的方法：位示图法（用一张位示图（简称位图）来指示磁盘存储空间的使用情况），空闲块链接法（在UNIX操作系统中，把磁盘存储空间的空闲块成组链接）。
关键词：磁盘的分配和回收管理；位示图；成组链接。
正 文
一． 问题描述
位示图法：一个简单的管理方法是用一张位示图（简称位图）来指示磁盘存储空间的使用情况。一个盘组的分块确定后，根据分配的总块数决定位图由多少个字组成,建筑位图中的每一位和盘组分块1-1对应,“1”状态表示相应块已占用，“0”状态表示该块空闲。
成组链接法：首先定义磁盘分配数组并初始化，9个一维数组分别表示9个空闲块，程序运行时，先将专用块A〔0〕复制到内存中，然后进行功能选择，分配时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。 回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。显示分组情况。系统初始化时先将专用块内容读入 内存 ，当有申请空闲块要求时，就直接在内存专用块中找到哪些块是空闲的，每分配一块后把空闲块数减 1。但要把一组中第一块分配出去之前，可以先把登记在该块中的下一组的块号保存在专用块中(此时 ，原专用块中的信息巳经无用了 ，因它指示的一组空闲块都已分配掉)。当中文组空闲块分配完后,则将下一组内容读入内存专用块中，以便继续分配时查找。
二. 设计目的
通过该题目的设计过程，掌握磁盘存储管理的原理、软件开发方法并提高解决实际问题的能力。学习使用位示图管理磁盘空间的分配和回收，了解程序运行前和回收磁盘的物理地址过程。学会用模拟UNIX系统的成组链接法实现磁盘空间的管理。了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。希望通过本次设计过程可以提高自己的分析问题的能力和实际动手的能力，将学到的知识用于实践中。
三．设计要求
(1) 位示图法
位示图是一张可以反映磁盘空间是否被占有的模拟图，用一个二维数组表示磁盘的空间，数组内每一个元素表示磁盘内相应的分块，数组元素为“1”表示该块已被占，“0”表示该块为空。数组元素位置和磁盘分块一一对应，即可描述出磁盘空间的利用情况。 (2) 成组链接法
对于要求将磁盘存储空间的空闲块成组链接，我们可以设计几个相应的一维数组，分别表示磁盘的各个磁盘，数组中的元素表示每个磁盘的分块，分配时，通过查空闲表MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。 回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。
四． 详细设计
1. 界面设计
下图（1）为用位示图法分配一个磁盘空间后的状态图：
图（1） 位示图法分配操作运行结果
下图（2）为用位示图法回收一个已分配的磁盘空间后的状态图：
图（2）位示图法回收操作运行结果
下图（3）为用成组链接法模拟磁盘空间利用情况图：
图(3)成组链接法 2. 算法设计 成组链接法：
（1）int MA[4]; /*空闲块数组*/
(2)intA[9][4]={{3,1,2,3},{3,4,5,6},{0,0,0,0},{0,0,0,0},{3,0,7,8}, {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}}; /*磁盘空间*/
（3）int mark[9]; /*存放已分配的块*/ int No=0; /*已分配的块数*/
（4）void display( )： 显示分组情况 （5）void assign( )： 分配空闲块 （6）void callback( )：回收空闲块 （7）void menu( )： 功能选择函数 位示图法：
（1）#include unsigned int size[5]={1,1,1,1,1} ;/*保存位示图*/ （2）void out() /*输出位示图函数*/ （3）void callback()/*回收函数*/ （4）void assign() /*分配函数*/ （5）void menu( )：功能选择函数 五． 结果分析 用位示图表示的磁盘空间可以很形象的反映出磁盘中空间的利用情况，不 足之处在于每次分配和回收只可以对单一的分块进行操作，不能同时进行几个块的分配和回收，要进行多个块的分配时，只能单独分配，且块之间没有相互链接，对于大的空间分配只能在连续空间进行。 用成组链接法模拟的磁盘空间能够解决用位示图中存在的问题，它可以通过链表的形式存取信息，对于较大的空间分配，若一个磁盘空间不够，通过指针找到下一个空闲的分区，但操作过程比较复杂，没有位示图方便，简捷。 设计总结 经过本次课程设计，完成题目“磁盘空间管理模拟实验”， 熟悉了UNIX/LINUX的常用基本命令，理解并掌握了UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。 做课程设计是为了对平时学习的理论知识和实际操作相结合，在理论和实践上进一步巩固已学基本理论及使用知识并加以综合提高，学会将知识使用于实际的方法，提高分析和解决问题的能力。在做课程设计的过程中，深深感觉到自身所学知识的有限。有些题目书本上没有提及，所以就没有去研究过，做的时候突然间觉得自己真的有点无知，虽然现在去看依然可以解决问题，但还是浪费了许多，这一点是必须在以后的学习中加以改进的地方，同时也要督促自己在学习的过程中不断的完善自我。在设计过程中的思考和讨论，对现有知识能够运用计算机来解决现实生活中的实际问题确立了信心，对模块化程序设计思想有了比较清晰的印象，为今后的程序设计奠定了一定的心理和技术上的准备。 这次课程设计加强了我对计算机操作系统的认识，对我个人而言是对所学课程内容掌握情况的一次自我验证。通过课程设计提高了我对所学知识的综合使用能力，全面检查并掌握所学的内容，培养独立思考，在分析问题、解决问题的过程 中，更是获得一种成功的喜悦。 参考文献 1. 汤子瀛，哲凤屏.《计算机操作系统》.西安电子科技大学学出版社. 2. 王清，李光明.《计算机操作系统》.冶金工业出版社. 3.孙钟秀等. 操作系统教程. 高等教育出版社 4.曾明. Linux操作系统使用教程. 陕西科学技术出版社. 5. 张丽芬，刘利雄.《操作系统实验教程》. 清华大学出版社. 6. 孟静， 操作系统教程－－原理和实例分析. 高等教育出版社 7. 周长林，计算机操作系统教程. 高等教育出版社 8. 张尧学，计算机操作系统教程，清华大学出版社 9. 任满杰，操作系统原理实用教程，电子工业出版社 致 谢 这次课程设计，我通过自己的实际分析及亲自动手调试程序，最终完成了作用，收获颇丰。 首先有了这次实践的机会，给了自己一个舞台，同时也是对自身的检验。还有多亏了老师们从理论到上机亲自指导的辛苦教授，给予了我们最大帮助和全面指导，在这里，尤其感谢我的指导老师王燕老师，您不辞辛苦，在给很多学生指导的情况下还不厌其烦的给我耐心指导，另外，要感谢我的《操作系统》的代课老师刘嘉老师孜孜不倦的教导，在这里，我衷心向您致谢！最后还要感谢热心的同学们，在我陷入误区的时候，是他们热心的帮助使我摆脱困境。 最后衷心感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利。 附录： 1.成组链接法 #include int MA[4]; /*空闲块数组*/ int A[9][4]={{3,1,2,3},{3,4,5,6},{0,0,0,0},{0,0,0,0},{3,0,7,8},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}}; /*磁盘空间*/ int mark[9]; /*存放已分配的块*/ int No=0; /*已分配的块数*/ void display1() { int i,j,temp,count; No=0; if(MA[1]!=0) { i=MA[0]; printf(\"\\ngroup1:\"); for(j=1;j<=i;j++) { printf(\"%d \ mark[++No]=MA[j]; } temp=MA[1]; count=2; while(A[temp][1]!=0) { printf(\"\\ngroup%d:\ i=A[temp][0]; for(j=1;j<=i;j++) { printf(\"%d \ mark[++No]=A[temp][j]; } count++; temp=A[temp][1]; } printf(\"\\ngroup%d:\ i=A[temp][0]; for(j=2;j<=i+1;j++) if(A[temp][j]>0) { printf(\"%d \ mark[++No]=A[temp][j]; } } else { i=MA[0]; if(i==1) printf(\"\\nThe blocks are all assigned\"); else { printf(\"\\ngroup1:\"); for(j=2;j<=i;j++) { printf(\"%d \ mark[++No]=MA[j]; } } } } void display() /*显示分组情况*/ { int i,j; if(MA[0]!=0) display1(); else { i=MA[1]; for(j=0;j<=3;j++) MA[j]=A[i][j]; display1(); } } void assign() /*分配空闲块*/ { int s,i; if(MA[0]>1) /*若该组不止一个空闲块*/ { i=MA[0]; s=MA[i]; MA[0]--; printf(\"\\nnumber of the block:%d\ } else if(MA[0]==1) /*只剩一个空闲块*/ { if(MA[1]!=0) /*还有其它空闲块组*/ { s=MA[1]; for(i=0;i<=3;i++) A[0][i]=A[s][i]; MA[0]--; printf(\"\\nnumber of the block:%d\ } else /*没有其它空闲块组*/ { printf(\"\\nThere isn't any space\"); return; } } else /*当前组已分配完*/ { for(i=0;i<=3;i++) MA[i]=A[0][i]; assign(); } display(); /*显示分组情况*/ } void callback() /*回收空闲块*/ { int i,j,temp; printf(\"\\ninput the No. of the block you want to callback:\"); scanf(\"%d\ getchar(); /*得到待回收的空闲块号*/ for(temp=1;temp<=No;temp++) { if(mark[temp]==j) break; } if(temp else /*已有3块*/ { for(i=0;i<=3;i++) A[j][i]=MA[i]; MA[0]=1; MA[1]=j; } display(); /*显示*/ } void menu() /*功能选择函数*/ { int choice; char judge; printf(\"\\ninput your choice:(1--assign,2--callback):\"); scanf(\"%d\ getchar(); if(choice==1) assign(); else if(choice==2) callback(); else printf(\"\\ninvalid command!\"); printf(\"\\ncontinue or not?(y--Yes,n--Not):\"); scanf(\"%c\ getchar(); if(judge=='y') menu(); else { printf(\"\\nNow the graph is:\"); display(); printf(\"\\npress any key to quit\"); } } main() { int i; for(i=0;i<=3;i++) MA[i]=A[0][i]; display(); menu(); } 2.位示图法 #include unsigned int size[5]={1,1,1,1,1} ;/*保存位示图*/ void out()/*输出位示图函数*/ { unsigned int i,j,m; for(j=0;j<5;j++)/*循环输出size的各个数的各个二进制位*/ {m=size[j]; for(i=0;i<16;i++)/**/ {printf(\"%d \ m=m/2; if(i==7) printf(\"\\n\"); } printf(\"\\n\"); } } void callback()/*回收函数*/ { unsigned int i,j,k,s=1,q,m,sq,zhm,cid; printf(\"确定要回收块的柱面号、磁道号、扇区号:\\n\"); printf(\"请输入柱面号：\"); scanf(\"%d\ printf(\"\\n请输入磁道号：\"); scanf(\"%d\ printf(\"\\n请输入扇区号：\"); scanf(\"%d\ if(zhm%2==0)/*计算对应的位示图位置*/ { i=zhm/2; j=cid*4+sq+1; } else { i=(zhm-1)/2; j=cid*4+sq+9; } q=size[i]; m=j-1; while(m) {q=q/2; m--;} if(q%2==1)/*判断该块是否被分配*/ {if(j==1)size[i]-=1;/*将位示图对应为置零*/ else {for(m=1;m printf(\"该块以被分配!\"); } void assign()/*分配函数*/ { unsigned int n=0,i,s=1,j,k,q,m,sq,zhm,cid; for(i=0 ,k=0;i<5;i++) { q=size[i] ; j=0; while(1) /*查找位示图的第一个为零的位，将其分配，该位置一*/ { j++ ; if((q%2)==0) { if(j==1) size[i]+=1; else {for(m=1;m if(k==1) /*将找到的位示图位转换成物理地址*/ { if((j-1)/8==1) {zhm=2*i+1; cid=(j-9)/4; sq=(j-9)%4;} else {zhm=2*i; cid=(j-1)/4; sq=(j-1)%4; } n=1; break;/*退出for循环*/ } } if(n==0) printf(\"没有空间可分配!\\n\"); else {printf(\"分配成功!\\n\");/*输出物理地址*/ printf(\"柱面号为: %d\\n\ printf(\"磁道号为: %d\\n\ printf(\"扇区号为: %d\\n\ } printf(\"分配后的位示图为:\\n\"); out(); } void menu() /*功能选择函数*/ { int choice; char judge; printf(\"\\n请选择操作:(1--分配,2--回收):\"); scanf(\"%d\ getchar(); if(choice==1) assign(); else if(choice==2) callback(); else printf(\"\\n没有此项!\"); printf(\"\\n继续还是退出?(y--继续,n--退出):\"); scanf(\"%c\ getchar(); if(judge=='y') menu(); else { printf(\"\\n现在的位示图:\\n\"); out(); printf(\"\\n按任意键退出！\\n\"); getchar(); } } main() { out(); menu(); } 因篇幅问题不能全部显示，请点此查看更多更全内容