2022年操作系统磁盘管理 .pdf

1 1.需求分析（1）设计内容和要求（包括原始数据、技术参数、条件、设计要求等）设计内容：1）采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收；2）采用空白块成组链接结构实现磁盘空间的分配和回收；3）采用位示图结构实现磁盘空间的分配和回收。基本要求：1）具有创建文件、空间分配、删除文件、释放空间等基本功能；2）把文件目录、磁盘空间管理的数据结构变化情况显示出来。（2）需求分析内容1）空白文件目录是管理磁盘空间的一种方法,该方法将文件存储设备上的每个连续空闲区看作一个空白文件，系统为所有空白文件单独建立一个目录,每个空白文件在这个目录中占一个表目.表目的内容至少包括第一个空白块的地址(物理块号),空白块的数目。2）位示图是另一种常用的管理磁盘空间的方法,该方法通过建立一张位示图来表示为l 时表示该块已分配,当某位为 0 时表示该块空闲。3）位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配。有的系统把“0”作为盘块已分配的标记，把“1”作为空闲标志(它们的本质上是相同的，都是用一位的两种状态标志空闲和已分配两种情况)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。1.1 小组分工温庭栋任务为：采用空白文件目录结构管理磁盘空间；魏子育任务为：采用空白块成组链接结构实现磁盘空间的分配和回收；卫虹任务为：采用位示图结构实现磁盘空间的分配和回收；2.总体设计（1）磁盘存储空间管理是文件系统的重要内容采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收空白文件目录法进行空间分配时，需要建立相关的数据结构，记录目前空白区域和已使用区域，假设开始时全部区域空闲。当有文件需要存储时，先检查空白文件目录，找到适合区域立即分配，并修改空名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 24 页 -2 白文件目录表和已使用区域分配表。为此需建立两张表格，分别记录相关数据。插入文件程序流图如图 2-1；小于等于大于图 2-1开始插入文件系统filemenu，filename 为文件名，size为文件大小Tag=0 freeblocki.size=applyarea 文件大于空白块，分配失败修改空闲目录的首位号和空闲块号添加文件确定文件首尾号，占有块数删除空闲块结束名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 24 页 -3 删除文件流程图如图 2-2 图 2-2（2）采用空白块成组链接结构实现磁盘空间的分配和回收对于要求将磁盘存储空间的空闲块成组链接，我们可以设计几个相应的一维数组，分别表示磁盘的各个磁盘，数组中的元素表示每个磁盘的分块，分配时，通过查空闲表MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况 MA复制到归还块中，然后在MA这重新登记一个新组。1）假定磁盘存储空间已被划分成长度为n 的等长块，共有M块可供使用。UNIX系统采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块（NM）分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第一组的开始输入文件名存在该文件不存在该文件删除该文件，调整空白块的大小，首位号结束名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 24 页 -4 块数和块号登记在专用块中，登记的格式如下：表 2-3 0空闲块数k1空闲块号12空闲块号2MMMMK空闲块号kMMMM当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。2)开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。用二维数组A：array 0,M-1 of array 0,n-1 来模拟管理磁盘空间，用 Ai表示第 I 块，第 0 块 A0 作为专用块。3)成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即 MA=A0。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再为申请者分配。4)归还一块时给出归还的块号，若当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况 MA复制到归还块中，然后在MA重新登记一个新组。(3)采用位示图结构实现磁盘空间的分配和回收磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 24 页 -5 算法流程图如下：分配流程图如下图2-4：图 2-4 开始输入文件名称，所占物理块64-busyneednum 文件大于空白块，分配失败分配成功结束名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 24 页 -6(2)释放流程图如图：2-4 图 2-4 开始输入文件名存在该文件不存在该文件删除该文件，调整空白块的大小，首位号结束名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 24 页 -7 3.详细设计1.采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收文件存储空间管理是文件系统的重要内容。常用的管理思想有空白文件目录法、空白块链法和位示图法。本实验采用前两种方法进行空间分配。空白文件目录法进行空间分配时，需要建立相关的数据结构，记录目前空白区域和已使用区域，假设开始时全部区域空闲。当有文件需要存储时，先检查空白文件目录，找到适合区域立即分配，并修改空白文件目录表和已使用区域分配表。为此需建立两张表格，分别记录相关数据。表 3-1；空白文件目录表（初始）表 3-2；空白文件目录（中间）核心代码int alloc(int applyarea)/为文件分配存储块的函数，磁盘空间的分配 int i,tag=0,j=0,flag=1;for(i=0;i applyarea&flag=1 序号首空白块号空白块个数物理块号标志0 8 5 8,9,10,11,12 未分配1 15 4 15,16,17,18 未分配2 20 7 20,21,22,23,24,25,26,27 未分配3 30 8 30,31,32,33,34,35,36,37,38 未分配4 60 13 60,61,62,63,64,65,66,6,68,69,70,71,72,73 未分配文件名首空白块号空白快个数物理块号备注名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 24 页 -8&freeblocki.namewtd=NULL)freeblocki.startaddress=freeblocki.startaddress+applyarea;freeblocki.size=freeblocki.size-applyarea;tag=1;/*有满足条件的空闲区时，tag 置 1*/flag=0;freeblocki.namewtd=fname;printf($%c/n,freeblocki.name);return freeblocki.startaddress-applyarea;else if(freeblocki.state=1&freeblocki.size=applyarea&flag=1&freeblocki.namewtd=NULL)freeblocki.startaddress=freeblocki.startaddress+applyarea;freeblocki.size=freeblocki.size-applyarea;freeblocki.state=0;flag=0;tag=1;/*有满足条件的空闲区时，tag 置 1*freeblocki.namewtd=fname if(tag=0)return-1;void setfree()/实现磁盘空间的回收 int i,j,k;char s;printf(输入要删除的文件名:/n);getchar();scanf(%c,&s);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 24 页 -9 for(j=0;j100;j+)if(FMenuj.Fname=s)break;for(i=0;iN;i+)for(k=0;k100;k+)printf($%c%d/n,freeblocki.name,i);if(freeblocki.namek=s)freeblocki.state=1;freeblocki.startaddress=freeblocki.startaddress-(int)ceil(FMenuj.size*1.0/100);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;iN;i+)printf(|%3d.%3d.%3d.%3d.|,i,freeblocki.startaddress,freeblocki.size,freeblocki.state);printf(n);printf(名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 24 页 -10|.|);printf(n);图 3-3；初始化格式图 3-4；分配磁盘图 3-5；回收磁盘2.采用空白块成组链接结构实现磁盘空间的分配和回收；名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 24 页 -11(1)假定磁盘存储空间已被划分成长度为n 的等长块，共有M块可供使用。UNIX 系统中采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块（NM）分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第一组的块数和块号登记在专用块中，登记的格式如下：表 3-6；空闲块0 空闲块数k 1 空闲块号1 2 空闲块号2 K 空闲块号k 当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。（2）现模拟 UNIX系统的空闲块成组链接，假定共有8 块可供使用，每3 块为一组，则空闲块成组链接的初始状态为：表 3-7；初始化空闲快名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 24 页 -12 开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。用二维数组A：array 0,M-1 of array 0,n-1 来模拟管理磁盘空间，用 Ai表示第 I 块，第 0 块 A0 作为专用块。(3)成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即MA:=A0。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再者分配。(4)归还一块时给出归还的块号，且当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况 MA复制到归还块中，然后在MA重新登记一个新组。(5)设计分配和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一次分配或归还后能显示或打印各空闲块组的情况（各组的空闲块数和块号）。本实验省去了块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。(6)运行你所设计的程序，假定空闲块链接的初始状态如提示（2），现先分配4 块，再依次归还第2 块和第 6 块。把执行后分配到的块号依次显示或打印出来，且显示或打印空闲块组的情况。在上次执行的基础上继续分配3 块，然后归还第1 块，再申请5 块，显示或打印依次分配到的块号及空闲块组情况。核心代码名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 24 页 -13 IntA94=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 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,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;j0)名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 24 页 -14 printf(%d ,Atempj);mark+No=Atempj;else i=MA0;if(i=1)printf(n所有的快都已被分配！);else printf(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;j1)/*若该组不止一个空闲块*/i=MA0;s=MAi;MA0-;printf(n被分配的块号:n%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()/*回收空闲块*/int i,j,temp;printf(n请输入你想回收的块号:n);名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 24 页 -16 scanf(%d,&j);getchar();/*得到待回收的空闲块号*/for(temp=1;temp=No;temp+)if(marktemp=j)break;if(tempNo+1)/*若该空闲块已在，退出*/printf(n该块还未被分配!);return;if(MA03)/*当前组不满3块*/i=MA0;MAi+1=j;MA0+;else /*已有 3 块*/for(i=0;i=3;i+)Aji=MAi;MA0=1;MA1=j;display();/*显示*/名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 24 页 -17 图 3-8：初始化视图图 3-9：分配块名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 24 页 -18 位数4 图 3-11：分配块图 3-12：回收块3.采用位示图结构实现磁盘空间的分配和回收（1）为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。（2）申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共8 个柱面，每个柱面有两个磁道，每个磁道分成4 个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号磁道号=名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 24 页 -19 物理记录号=位数 mod4（3）归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。按照（2）中假设的盘组，归还块在位示图中的位置计算如下：字节号=柱面号位数=磁道号4+物理记录号（4）设计申请一块磁盘空间和归还一块磁盘空间的程序。要求能显示或打印程序运行前运行后的位示图；分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。源代码void showbitmap(void)/showbitmap函数，功能打印位示图信息 printf(当前系统磁盘位示图（0 表示块可用）：n);/用来和位示图bitmap 相与得到某位的状态 printf(第一磁道第二磁道 n);printf(0扇区 1扇区 2扇区 3扇区 0 扇区 1扇区 2扇区 3扇区);for(int i=0;ibitmapi);printf(n);system(pause);void diskallocate(void)/diskallocate函数，分配物理块给 /由用户输入需要的物理块数：名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 24 页 -20 int neednum;int i;int busy=0;char filestor32;/用户名 printf(输入需要分配的块数:n);scanf(%d,&neednum);printf(输入文件名:n);scanf(%s,filestor);for(i=0;ibitmapi;if(64-busyneednum)printf(没有足够的空闲磁盘，分配失败！);else printf(开始分配.n);for(i=0;ibitmapi)/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;名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 24 页 -21 printf(分配成功！n);showbitmap();system(pause);void diskreturn(void)/回收物理块 char filereturn32;int i;printf(输入要回收的文件名);scanf(%s,filereturn);for(i=0;ifilenamei)printf(此文件没有被分配空间);break;else bitinfo-bitmapi=0;showbitmap();system(pause);名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 24 页 -22 图 3-13：初始化图 3-14：位示图名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 24 页 -23 图 3-15：物理块分配图 3-16：物理块回收名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 24 页 -24 4.心得体会（1）采用空白文件目录结构管理磁盘空间实现磁盘空间的分配和回收通过采用空白文件目录结构管理磁盘空间实现磁盘的分配和回收，采用C语言进行编译，对 C语言有了更新和更深的认识，并且此次试验是在Linux 系统下调试，起初也是错误百出，总是运行不了，后来经过查阅资料，问题得以解决，自己的能力也得到了提升。本次实训我了解了 Linux 的简单操作，更加明白做程序得慢慢来，实训过程中得多与同学进行交流，不断修复完善。（2）采用空白块成组链接结构实现磁盘空间的分配和回收通过这次实验，对于 Linux 的系统有了简单的熟悉，然后，了解了磁盘存储空间的管理，对自己负责的空白块成组链接结构实现磁盘空间的分配和回收的整个过程有了了解。在实验过程中，遇到的主要问题就是Windows和 Linux 的编码方式不同，以及库函数也不同。总体来说，第一次使用Linux 有惊奇，也有收获，学习和了解空白块成组链接结构，也是收获颇丰。（3）采用位示图结构实现磁盘空间的分配和回收通过本次对磁盘空间管理算法的实验，我掌握了通过位示图对磁盘空间进行管理的算法，本次实验我调用了3 个函数，分别是分配输出位示图函数，分配函数，回收函数，然后再运用一个主函数对几个函数进行调用。通过实验，实现了在Linux 环境下的编译，有了更加大的挑战，对我而言更是一种很有利的提升，丰富了自己的课外知识，开阔了自己的事野，对磁盘空间管理算法有了更深刻的认识。名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 24 页 -