目录摘要 (2)前言 (3)正文 (4)1. 实验目的 (4)2. 设计思想 (4)3. 实验结构图 (5)4. 各模块的伪码算法 (5)5. 测试分析 (10)6. 测试结果 (11)7. 源程序 (14)总结 (24)参考文献 (25)致谢 (26)摘要要把文件信息存放在存储介质上，必须先找出存储介质上可供使用的空闲块。

存储介质上某个文件不再需要时，又要收回它所占的存储空间作为空闲块。

用户作业在执行期间经常要求建立一个新文件或撤消一个不再需要的文件，因此，文件系统必须要为它们分配存储空间或收回它所占的存储空间。

如何实现存储空间的分配和收回，取决于对空闲块的管理方法，主要有两种对磁盘存储空间的分配和收回的方法：位示图法（用一张位示图（简称位图）来指示磁盘存储空间的使用情况），空闲块链接法（在UNIX操作系统中，把磁盘存储空间的空闲块成组链接）。

关键词：磁盘的分配和回收管理；位示图；成组链接。

前言通过该题目的设计过程，掌握磁盘存储管理的原理、软件开发方法并提高解决实际问题的能力。

学习使用位示图管理磁盘空间的分配与回收，了解程序运行前和回收磁盘的物理地址过程。

学会用模拟UNIX系统的成组链接法实现磁盘空间的管理。

了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。

希望通过本次设计过程可以提高自己的分析问题的能力和实际动手的能力，将学到的知识用于实践中。

正文1. 实验目的磁盘格式化时,系统把磁盘存储空间分成许多磁道。

每个磁道又分成若干个扇区(又叫做块)。

这些空间就是用来存放用户文件的。

当用户的文件不再需要时,就应该删除。

把一个文件存放到磁盘上时,可以组织成连续文件,链接文件,索引文件等。

因此,磁盘空间的分配方法也有两种,一种是连续空间的分配;一种是不连续空间的分配(又叫动态分配)。

如何充分有效的利用磁盘空间,是操作系统应解决的重要课题之一。

通过本实验,使学生对磁盘空间的分配与回收有一个较深入的理解。

2. 设计思想位示图法：一个简单的管理方法是用一张位示图（简称位图）来指示磁盘存储空间的使用情况。

一个盘组的分块确定后，根据分配的总块数决定位图由多少个字组成,位图中的每一位与盘组分块一一对应。

位示图是一张可以反映磁盘空间是否被占有的模拟图，用一个二维数组表示磁盘的空间，数组内每一个元素表示磁盘内相应的分块，数组元素为“1”表示该块已被占，“0”表示该块为空。

数组元素位置与磁盘分块一一对应，即可描述出磁盘空间的利用情况。

成组链接法：首先定义磁盘分配数组并初始化，9个一维数组分别表示9个空闲块，程序运行时，先将专用块A〔0〕复制到内存中，然后进行功能选择，分配时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。

回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。

显示分组情况。

系统初始化时先将专用块内容读入内存，当有申请空闲块要求时，就直接在内存专用块中找到哪些块是空闲的，每分配一块后把空闲块数减1。

但要把一组中第一块分配出去之前，可以先把登记在该块中的下一组的块号保存在专用块中(此时，原专用块中的信息巳经无用了，因它指示的一组空闲块都已分配掉)。

当中文组空闲块分配完后,则将下一组内容读入内存专用块中，以便继续分配时查找。

3. 实验结构图4. 各模块的伪码算法1)对位示图法申请磁盘块查看位示图找位号等是否找到是：由字位号计算相对块号和柱面号,磁道号,物理记录号,并输出这些相应参数否：返回，磁盘已满,本次无法分配置位示图相应位为1 返回定义分配函数：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 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("该块以被分配!");}2)对成组链接法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) /*当前组不满3块*/{ i=MA[0];MA[i+1]=j;MA[0]++;}else /*已有3块*/{for(i=0;i<=3;i++)A[j][i]=MA[i];MA[0]=1;MA[1]=j;}display(); /*显示*/}5. 测试分析用位示图表示的磁盘空间可以很形象的反映出磁盘中空间的利用情况，不足之处在于每次分配与回收只可以对单一的分块进行操作，不能同时进行几个块的分配与回收，要进行多个块的分配时，只能单独分配，且块之间没有相互链接，对于大的空间分配只能在连续空间进行。

用成组链接法模拟的磁盘空间能够解决用位示图中存在的问题，它可以通过链表的形式存取信息，对于较大的空间分配，若一个磁盘空间不够，通过指针找到下一个空闲的分区，但操作过程比较复杂，没有位示图方便，简捷。

6. 测试结果1)位示图法✧编译及连接时界面：✧刚运行时界面：✧分配空间时界面：✧回收空间时界面：2)成组链接法分配空间时界面：回收空间时界面：7. 源程序位示图法：#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++)/*循环输出size的各个数的各个二进制位*/{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("★★★★08级计算机一08240128 李彦博★★★★\n");printf("﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌\n");out();menu();}成组链接法：#include<stdio.h>int MA[4]; /*空闲块数组*/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}}; /*磁盘空间*/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) /*当前组不满3块*/{ i=MA[0];MA[i+1]=j;MA[0]++;}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("\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();}总结经过本次课程设计，完成题目“磁盘空间管理模拟实验”，熟悉了UNIX/LINUX 的常用基本命令，理解并掌握了UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。