信息技术学院《嵌入式操作系统》课程综合设计报告书姓名：班级：学号：题目：磁盘存储空间的分配与回收时间： 2013年月日指导教师：摘要要把文件信息存放在存储介质上，必须先找出存储介质上可供使用的空闲块。
存储介质上某个文件不再需要时，又要收回它所占的存储空间作为空闲块。
用户作业在执行期间经常要求建立一个新文件或撤消一个不再需要的文件，因此，文件系统必须要为它们分配存储空间或收回它所占的存储空间。
如何实现存储空间的分配和收回，取决于对空闲块的管理方法，主要有两种对磁盘存储空间的分配和收回的方法：位示图法（用一张位示图（简称位图）来指示磁盘存储空间的使用情况），成组链接法（在LINIX操作系统中，把磁盘存储空间的空闲块成组链接）。
关键字：磁盘分配、磁盘回收、位示图、成组链接目录一、任务要求------------------------------------------------------------------------------------------------ 4二、设计目的------------------------------------------------------ 4三、设计方案------------------------------------------------------ 43.1 位示图法---------------------------------------------------- 53.2 成组连接法-------------------------------------------------- 53.3 主要模块 --------------------------------------------------------------------------------------------- 6四、程序流程图---------------------------------------------------- 7五、结果与调试---------------------------------------------------- 75.1程序执行结果------------------------------------------------- 75.2程序调试 ---------------------------------------------------------------------------------------------- 8六、总结---------------------------------------------------------- 8七、参考文献------------------------------------------------------ 9八、附录---------------------------------------------------------- 98.1 位示图法---------------------------------------------------- 98.2成组连接法-------------------------------------------------- 14一、任务要求通过磁盘存储空间的分配与回收，掌握磁盘存储管理的原理、软件开发方法并提高解决实际问题的能力。
学习使用位示图管理磁盘空间的分配与回收，了解程序运行前和回收磁盘的物理地址过程。
学会用模拟LINIX系统的成组链接法实现磁盘空间的管理。
希望通过本次设计过程可以提高自己的分析问题的能力和实际动手的能力，将学到的知识用于实践中。
二、设计目的磁盘格式化时,系统把磁盘存储空间分成许多磁道。
每个磁道又分成若干个扇区(又叫做块)。
这些空间就是用来存放用户文件的。
当用户的文件不再需要时,就应该删除。
把一个文件存放到磁盘上时,可以组织成连续文件,链接文件,索引文件等。
因此,磁盘空间的分配方法也有两种,一种是连续空间的分配；一种是不连续空间的分配(又叫动态分配)。
如何充分有效的利用磁盘空间,是应解决的重要课题之一。
通过本次设计,使学生对磁盘空间的分配与回收有一个较深入的理解。
三、设计方案要在磁盘上建立顺序文件时，必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。
可假定磁盘初始化时，已把磁盘存储空间划分成若干等长的块（扇区），按柱面号和盘面号的顺序给每一块确定一个编号。
随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有的区存放着文件，而有的区是空闲的。
当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时，则该文件占用的区应成为空闲区。
3.1 位示图法一个简单的管理方法是用一张位示图（简称位图）来指示磁盘存储空间的使用情况。
一个盘组的分块确定后，根据分配的总块数决定位图由多少个字组成，位图中的每一位与盘组分块一一对应。
位示图是一张可以反映磁盘空间是否被占有的模拟图，用一个二维数组表示磁盘的空间，数组内每一个元素表示磁盘内相应的分块，数组元素为“1”表示该块已被占，“0”表示该块为空。
数组元素位置与磁盘分块一一对应，即可描述出磁盘空间的利用情况。
3.2 成组链接法首先定义磁盘分配数组并初始化，9个一维数组分别表示9个空闲块，程序运行时，先将专用块A〔0〕复制到内存中，然后进行功能选择，分配时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。
回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。
显示分组情况。
系统初始化时先将专用块内容读入内存，当有申请空闲块要求时，就直接在内存专用块中找到哪些块是空闲的，每分配一块后把空闲块数减1。
但要把一组中第一块分配出去之前，可以先把登记在该块中的下一组的块号保存在专用块中(此时，原专用块中的信息巳经无用了，因它指示的一组空闲块都已分配掉)。
当中文组空闲块分配完后,则将下一组内容读入内存专用块中，以便继续分配时查找。
3.3 主要模块int main() /*主函数*/void out() /*输出函数*/void callback() /*回收函数*/void menu() /*功能选择函数*/void display() /*显示分组情况函数*/void assign() /*分配空闲块函数*/四、程序流程图是 否五、结果与调试5.1 程序执行结果位示图法开始申请磁盘块查看位示图找位号等是否找 到？返回，磁盘已满,本次无法分配由字位号计算相对块号和柱面号,磁道号,物理记录号,并输出这些相应参数置位示图相应位为1返回成组链接法5.2 程序调试用位示图表示的磁盘空间可以很形象的反映出磁盘中空间的利用情况，不足之处在于每次分配与回收只可以对单一的分块进行操作，不能同时进行几个块的分配与回收，要进行多个块的分配时，只能单独分配，且块之间没有相互链接，对于大的空间分配只能在连续空间进行。
用成组链接法模拟的磁盘空间能够解决用位示图中存在的问题，它可以通过链表的形式存取信息，对于较大的空间分配，若一个磁盘空间不够，通过指针找到下一个空闲的分区，但操作过程比较复杂，没有位示图方便、简捷。
六、总结通过本次课程设计，我对Linux操作系统有了更进一步的理解，特别是在磁盘的分配和回收这块。
在做课程设计的过程中，深深感觉到自身所学知识的有限。
有些题目书本上没有提及，所以就没有去研究过，做的时候突然间觉得自己真的有点无知，虽然现在去看依然可以解决问题，但还是浪费了许多，这一点是必须在以后的学习中加以改进的地方，同时也要督促自己在学习的过程中不断的完善自我。
在设计过程中的思考和讨论，对现有知识能够运用计算机来解决现实生活中的实际问题确立了信心，对模块化程序设计思想有了比较清晰的印象，为今后的程序设计奠定了一定的心理和技术上的准备。
这次课程设计加强了我对LINUX系统的认识，对我个人而言是对所学课程内容掌握情况的一次自我验证。
通过课程设计提高了我对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考，在分析问题、解决问题的过程中，更是获得一种成功的喜悦。
七、参考文献[1]《嵌入式Linux实时操作系统及应用编程》北京：清华大学出版社，2011.5[2]《C++面向对象程序设计》2006[3]《Visual C++ 应用程序》人民教育出版社[4]贾宗璞,许合利<<C语言程序设计>>江苏：中国矿业大学出版社，2007.6[5]谭浩强<<C程序设计（第二版）>>北京：清华大学出版社，2001.1八、附录8.1 位示图法：#include<stdio.h>unsigned int size[5]={1,1,1,1,1};void out(){ unsigned int i,j,m;for(j=0;j<5;j++){m=size[j];for(i=0;i<16;i++) /**/{printf("%d ",m%2);m=m/2;if(i==7)printf("\n");}printf("\n");}}void callback(){ unsigned int i,j,s=1,q,m,sq,zhm,cid;printf("确定要回收块的柱面号、磁道号、扇区号:\n");printf("请输入柱面号：");scanf("%d",&zhm);printf("\n请输入磁道号：");scanf("%d",&cid);printf("\n请输入扇区号：");scanf("%d",&sq);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<j;m++)s*=2 ;size[i]-=s;}printf("回收成功!");printf("回收后的位示图为:\n");out();}elseprintf("该块以被分配!");}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<j;m++)s*=2 ;size[i]+=s;}k=1;break ;}q=q/2;}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",zhm);printf("磁道号为: %d\n",cid);printf("扇区号为: %d\n",sq);}printf("分配后的位示图为:\n");out();}void menu(){ int choice;char judge;printf("\n请选择操作:(1--分配,2--回收):");scanf("%d",&choice);getchar();if(choice==1)assign();else if(choice==2)callback();elseprintf("\n没有此项!");printf("\n继续还是退出?(y--继续,n--退出):");scanf("%c",&judge);getchar();if(judge=='y')menu();else{ printf("\n现在的位示图:\n");out();printf("\n按任意键退出！\n");getchar();}}main(){printf("\t\t————欢迎进入磁盘空间管理模拟实验————\n");printf( " \n");printf("★★★★10级计算机科学与技术0914100516 孙俏★★★★\n");printf("﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌\n");out();menu();}8.2 成组链接法#include<stdio.h>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 ",MA[j]);mark[++No]=MA[j];}temp=MA[1];count=2;while(A[temp][1]!=0){ printf("\ngroup%d:",count);i=A[temp][0];for(j=1;j<=i;j++){printf("%d ",A[temp][j]);mark[++No]=A[temp][j];}count++;temp=A[temp][1];}printf("\ngroup%d:",count);i=A[temp][0];for(j=2;j<=i+1;j++)if(A[temp][j]>0){printf("%d ",A[temp][j]);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 ",MA[j]);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",s);}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",s);}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",&j);getchar();for(temp=1;temp<=No;temp++){ if(mark[temp]==j)break;}if(temp<No+1){ printf("\nThe block is in the disk");return;}if(MA[0]<3){ i=MA[0];MA[i+1]=j;MA[0]++;}else{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("\n做出选择:(1--分配,2--回收):");scanf("%d",&choice);getchar();if(choice==1)assign();else if(choice==2)callback();elseprintf("\n错误请求!");printf("\ncontinue or not (y--Yes,n--Not):");scanf("%c",&judge);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();}。