操作系统磁盘管理

1、 1.需求分析（1）设计内容和要求（包括原始数据、技术参数、条件、设计要求等）设计内容：1）采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收；2）采用空白块成组链接结构实现磁盘空间的分配和回收；3）采用位示图结构实现磁盘空间的分配和回收。基本要求：1）具有创建文件、空间分配、删除文件、释放空间等基本功能；2）把文件目录、磁盘空间管理的数据结构变化情况显示出来。（2）需求分析内容1）空白文件目录是管理磁盘空间的一种方法,该方法将文件存储设备上的每个连续空闲区看作一个空白文件，系统为所有空白文件单独建立一个目录,每个空白文件在这个目录中占一个表目.表目的内容至少包括第一个空白块

2、的地址(物理块号),空白块的数目。 2）位示图是另一种常用的管理磁盘空间的方法,该方法通过建立一张位示图来表示为l时表示该块已分配,当某位为0时表示该块空闲。 3）位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配。有的系统把“0”作为盘块已分配的标记，把“1”作为空闲标志(它们的本质上是相同的，都是用一位的两种状态标志空闲和已分配两种情况)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。1.1小组分工温庭栋任务为：采用空白文件目录结构管理磁盘空间；魏子育任务为：采用空白块成组链

3、接结构实现磁盘空间的分配和回收；卫虹任务为：采用位示图结构实现磁盘空间的分配和回收；2.总体设计（1）磁盘存储空间管理是文件系统的重要内容采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收空白文件目录法进行空间分配时，需要建立相关的数据结构，记录目前空白区域和已使用区域，假设开始时全部区域空闲。当有文件需要存储时，先检查空白文件目录，找到适合区域立即分配，并修改空白文件目录表和已使用区域分配表。为此需建立两张表格，分别记录相关数据。插入文件程序流图 如图2-1；开始插入文件系统filemenu，filename为文件名，size为文件大小Tag=0freeblocki.size >

4、;= applyarea文件大于空白块，分配失败 小于 等于 大于 删除空闲块修改空闲目录的首位号和空闲块号 添加文件确定文件首尾号，占有块数结束 图2-1 删除文件流程图 如图2-2开始输入文件名不存在该文件存在该文件 删除该文件，调整空白块的大小，首位号 结束 图2-2（2）采用空白块成组链接结构实现磁盘空间的分配和回收对于要求将磁盘存储空间的空闲块成组链接，我们可以设计几个相应的一维数组，分别表示磁盘的各个磁盘，数组中的元素表示每个磁盘的分块，分配时，通过查空闲表MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请

5、者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。 回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。1） 假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。UNIX系统采用空闲块成组链接的方法 来管理磁盘存储空间，将磁盘中的每N个空闲块（N<M）分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第一组的块数和块号登记

6、在专用块中，登记的格式如下： 表2-30空闲块数k1空闲块号12空闲块号2MMMMK空闲块号kMMMM当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。2)开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。用二维数组A：array 0M-1 of array 0n-1来模拟管理磁盘空间，用Ai表示第I块，第0块A0作为专用块。3) 成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即MA =A0。申请一块磁盘空间时，查MA，从中找出空闲块号

7、，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再为申请者分配。4) 归还一块时给出归还的块号，若当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在MA重新登记一个新组。(3)采用位示图结构实现磁盘空间的分配和回收磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来

8、指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。算法流程图如下：分配流程图如下图2-4：开始输入文件名称，所占物理块文件大于空白块，分配失败64-busy<neednum分配成功结束 图2-4(2)释放流程图如图：2-4开始输入文件名不存在该文件存在该文件 删除该文件，调整空白块的大小，首位号 结束 图2-43.详细设计1.采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收文件存储空间管理是文件系统的重要内容。常用的管理思想有空白文件目录法、空白块链法和位示图法。本实验采用前两种方法进行空间分配。空白文件目录法进行空间分

9、配时，需要建立相关的数据结构，记录目前空白区域和已使用区域，假设开始时全部区域空闲。当有文件需要存储时，先检查空白文件目录，找到适合区域立即分配，并修改空白文件目录表和已使用区域分配表。为此需建立两张表格，分别记录相关数据。表3-1；空白文件目录表（初始）序号首空白块号空白块个数物理块号标志0858,9,10,11,12未分配115415,16,17,18未分配220720,21,22,23,24,25,26,27未分配330830,31,32,33,34,35,36,37,38未分配4601360,61,62,63,64,65,66,6,68,69,70,71,72,73未分配表3-2；空白

10、文件目录（中间）文件名首空白块号空白快个数物理块号备注核心代码int alloc(int applyarea)/为文件分配存储块的函数，磁盘空间的分配 int i,tag=0,j=0,flag=1; for( i=0 ; i< N ; i+ ) if(freeblocki.state=1 && freeblocki.size > applyarea && flag=1 && wtd=NULL) freeblocki.startaddress = freeblocki.startaddress + appl

11、yarea; freeblocki.size=freeblocki.size-applyarea; tag=1;/*有满足条件的空闲区时，tag置1*/ flag=0; wtd=fname; printf("$ %c/n",); return freeblocki.startaddress-applyarea; else if(freeblocki.state=1 && freeblocki.size=applyarea && flag=1 && freeblocki

12、.namewtd=NULL) freeblocki.startaddress = freeblocki.startaddress + applyarea; freeblocki.size=freeblocki.size-applyarea; freeblocki.state=0; flag=0; tag=1;/*有满足条件的空闲区时，tag置1* wtd=fname if(tag=0) return -1;void setfree()/实现磁盘空间的回收 int i,j,k; char s; printf("输入要删除的文件名: /n"); g

13、etchar(); scanf("%c",&s); for(j=0;j<100 ;j+) if(FMenuj.Fname=s) break; for(i=0;i<N;i+) for(k=0;k<100;k+) printf("$ %c %d/n",,i); if(k=s) freeblocki.state=1; freeblocki.startaddress=freeblocki.startaddress - (int)ceil(FMenuj.size*1.0/100)

14、 ; freeblocki.size=freeblocki.size + (int)ceil(FMenuj.size*1.0/100) ; void print()/打印输出表 int i; printf("n");printf(" |序号.第一个空白块.连续空闲块个数.状态.|"); printf("n"); printf(" |.|"); printf("n"); for(i=0;i<N;i+) printf(" |%3d.%3d.%3d.%3d.|", i,fre

15、eblocki.startaddress,freeblocki.size,freeblocki.state); printf("n"); printf(" |.|"); printf("n"); 图3-3；初始化格式图3-4；分配磁盘图3-5；回收磁盘2.采用空白块成组链接结构实现磁盘空间的分配和回收；(1) 假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。UNIX系统中采用空闲块成组链接的方法 来管理磁盘存储空间，将磁盘中的每N个空闲块（N<M）分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块

16、数和块号，第一组的块数和块号登记在专用块中，登记的格式如下：  表3-6；空闲块0空闲块数k1空闲块号12空闲块号2MMMMK空闲块号k 当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。（2）现模拟UNIX系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲块成组链接的初始状态为：表3-7；初始化空闲快开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。用二维数组A：array 0M-1 of array 0n-1来模拟管理磁盘空间，用Ai表示第I块，第0块A0作为专用块。(3) 成组链接的分组情况记录在磁盘物理块

17、中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即MA: =A0。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再者分配。(4) 归还一块时给出归还的块号，且当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在MA重新登记一个新组。(5) 设计分配

18、和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一次分 配或归还后能显示或打印各空闲块组的情况（各组的空闲块数和块号）。本实验省去了块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。(6) 运行你所设计的程序，假定空闲块链接的初始状态如提示（2），现先分配4块，再依次归还第2块和第6块。把执行后分配到的块号依次显示或打印出来，且显示或打印空闲块组的情况。在上次执行的基础上继续分配3块，然后归还第1块，再申请5块，显示或打印依次分配到的块号及空闲块组情况。核心代码IntA94=3,1,2,3,3,4,5,6,0,0,0,0,0,0,0,0,3,0,7,

19、8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; /*磁盘空间*/int mark9; /*存放已分配的块*/int No=0; /*已分配的块数*/void display1()/打印显示结构 int i,j,temp,count; No=0; if(MA1!=0) i=MA0; printf("n组1:t"); for(j=1;j<=i;j+) printf("%d ",MAj); mark+No=MAj; temp=MA1; count=2; while(Atemp1!=0) printf("n组%d:t&quo

20、t;,count); i=Atemp0; for(j=1;j<=i;j+) printf("%d ",Atempj); mark+No=Atempj; count+; temp=Atemp1; printf("n组%d:t",count); i=Atemp0; for(j=2;j<=i+1;j+) if(Atempj>0) printf("%d ",Atempj); mark+No=Atempj; else i=MA0; if(i=1) printf("n所有的快都已被分配！"); else pr

21、intf("n组1:"); for(j=2;j<=i;j+) printf("%d ",MAj); mark+No=MAj; void display() /*显示分组情况*/ int i,j; if(MA0!=0) display1(); else i=MA1; for(j=0;j<=3;j+) MAj=Aij; display1(); void assign() /*分配空闲块*/ int s,i; if(MA0>1) /*若该组不止一个空闲块*/ i=MA0; s=MAi; MA0-; printf("n被分配的块号:n

22、%dn",s); else if(MA0=1) /*只剩一个空闲块*/ if(MA1!=0) /*还有其它空闲块组*/ s=MA1; for(i=0;i<=3;i+) A0i=Asi; MA0-; printf("n被分配的块号:n%dn",s); else /*没有其它空闲块组*/ printf("n没有空闲空间！"); return; else /*当前组已分配完*/ for(i=0;i<=3;i+) MAi=A0i; assign(); display(); /*显示分组情况*/ void callback() /*回收空闲块

23、*/ int i,j,temp; printf("n请输入你想回收的块号:n"); scanf("%d",&j); getchar(); /*得到待回收的空闲块号*/ for(temp=1;temp<=No;temp+) if(marktemp=j) break; if(temp<No+1) /*若该空闲块已在，退出*/ printf("n该块还未被分配!"); return; if(MA0<3) /*当前组不满3块*/ i=MA0; MAi+1=j; MA0+; else /*已有3块*/ for(i=0;

24、i<=3;i+) Aji=MAi; MA0=1; MA1=j; display(); /*显示*/ 图3-8：初始化视图图3-9：分配块图3-11：分配块图3-12：回收块3.采用位示图结构实现磁盘空间的分配和回收（1）为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文 件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。（2）申请一

25、块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共8个柱面，每个柱面有两个磁道，每个磁道分成4个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号位数4磁道号= 物理记录号= 位数mod4（3）归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。按照（2）中假设的盘组，归还块在位示图中的位置计算如下：字节号=柱面号位数=磁道号´4+物理记录号（4）设计申请一块磁盘空间和归还一块磁盘空

26、间的程序。要求能显示或打印程序运行前运行后的位示图；分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。源代码void showbitmap(void) /showbitmap函数，功能打印位示图信息 printf("当前系统磁盘位示图（0表示块可用）：n"); /用来和位示图bitmap相与得到某位的状态 printf(" 第一磁道 第二磁道n"); printf(" 0扇区 1扇区 2扇区 3扇区 0扇区 1扇区 2扇区 3扇区") ; for( int i = 0 ;i<

27、;COUNT;i+) if( 0=i%8) printf("n"); printf("%d柱面",(i+1)/8); printf(" %dt",bitinfo->bitmapi); printf("n"); system("pause");void diskallocate(void) /diskallocate函数，分配物理块给 /由用户输入需要的物理块数： int neednum; int i ; int busy = 0; char filestor32; /用户名 printf(

28、"输入需要分配的块数:n"); scanf("%d",&neednum); printf("输入文件名:n"); scanf("%s",filestor); for( i=0;i<COUNT;i+) /统计已占用的物理块 busy =busy + bitinfo->bitmapi; if( 64-busy<neednum ) printf("没有足够的空闲磁盘，分配失败！"); else printf("开始分配.n"); for(i=0 ; i<COUNT; i+) if( 0=bitinfo->bitmapi) / printf("分配块物理地址为:第%d个柱面，t第%d个磁道,t第%d个扇区n",i/8+1,i%8/4,(i%8)%4); bitinfo->bitmapi = 1; strcpy(bitinfo->filenamei , filestor); neednum-; if( 0=neednum) break; printf("分配成功！n"); showbitmap(); system("pause&q