操作系统磁盘管理.docx
《操作系统磁盘管理.docx》由会员分享，可在线阅读，更多相关《操作系统磁盘管理.docx（27页珍藏版）》请在冰点文库上搜索。
操作系统磁盘管理
1.需求分析
（1）设计内容和要求（包括原始数据、技术参数、条件、设计要求等）
设计内容：
1）采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收；
2）采用空白块成组链接结构实现磁盘空间的分配和回收；
3）采用位示图结构实现磁盘空间的分配和回收。
基本要求：
1）具有创建文件、空间分配、删除文件、释放空间等基本功能；
2）把文件目录、磁盘空间管理的数据结构变化情况显示出来。
（2）需求分析内容
1）空白文件目录是管理磁盘空间的一种方法,该方法将文件存储设备上的每个连续空闲区看作一个空白文件，系统为所有空白文件单独建立一个目录,每个空白文件在这个目录中占一个表目.表目的内容至少包括第一个空白块的地址（物理块号）,空白块的数目。
2）位示图是另一种常用的管理磁盘空间的方法,该方法通过建立一张位示图来表示为l时表示该块已分配,当某位为0时表示该块空闲。
3）位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。
当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配。
有的系统把“0”作为盘块已分配的标记，把“1”作为空闲标志（它们的本质上是相同的，都是用一位的两种状态标志空闲和已分配两种情况）磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。
1.1小组分工
温庭栋任务为：
采用空白文件目录结构管理磁盘空间；
魏子育任务为：
采用空白块成组链接结构实现磁盘空间的分配和回收；
卫虹任务为：
采用位示图结构实现磁盘空间的分配和回收；
2.总体设计
（1）磁盘存储空间管理是文件系统的重要内容
采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收空白文件目录法进行空间分配时，需要建立相关的数据结构，记录目前空白区域和已使用区域，假设开始时全部区域空闲。
当有文件需要存储时，先检查空白文件目录，找到适合区域立即分配，并修改空白文件目录表和已使用区域分配表。
为此需建立两张表格，分别记录相关数据。
插入文件程序流图如图2-1；
小于
等于
大于
图2-1
删除文件流程图如图2-2
图2-2
（2）采用空白块成组链接结构实现磁盘空间的分配和回收
对于要求将磁盘存储空间的空闲块成组链接，我们可以设计几个相应的一维数组，分别表示磁盘的各个磁盘，数组中的元素表示每个磁盘的分块，分配时，通过查空闲表MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。
回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。
1）假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。
UNIX系统
采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块（N表2-3
0
空闲块数k
1
空闲块号1
2
空闲块号2
M
M
M
M
K
空闲块号k
M
M
M
M
当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。
2）
开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。
用二维数组A：
array[0…M-1]ofarray[0…n-1]来模拟管理磁盘空间，用A[i]表示第I块，第0块A[0]作为专用块。
3）成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。
定义一个数组MA存放专用块内容，即MA=A[0]。
申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。
当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再为申请者分配。
4）归还一块时给出归还的块号，若当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在MA重新登记一个新组。
（3）采用位示图结构实现磁盘空间的分配和回收
磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。
为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。
位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。
算法流程图如下：
分配流程图如下图2-4：
图2-4
（2）释放流程图如图：
2-4
图2-4
3.详细设计
1.采用空白文件目录结构管理磁盘空间，实现磁盘空间的分配和回收
文件存储空间管理是文件系统的重要内容。
常用的管理思想有空白文件目录法、空白块链法和位示图法。
本实验采用前两种方法进行空间分配。
空白文件目录法进行空间分配时，需要建立相关的数据结构，记录目前空白区域和已使用区域，假设开始时全部区域空闲。
当有文件需要存储时，先检查空白文件目录，找到适合区域立即分配，并修改空白文件目录表和已使用区域分配表。
为此需建立两张表格，分别记录相关数据。
表3-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
未分配
表3-2；空白文件目录（中间）
文件名
首空白块号
空白快个数
物理块号
备注
核心代码
intalloc（intapplyarea）///为文件分配存储块的函数，磁盘空间的分配
{
inti,tag=0,j=0,flag=1;
for（i=0;iif（freeblock[i].state==1&&freeblock[i].size>applyarea&&flag==1&&freeblock[i].name[wtd]==NULL）
{
freeblock[i].startaddress=freeblock[i].startaddress+applyarea;
freeblock[i].size=freeblock[i].size-applyarea;
tag=1;/*有满足条件的空闲区时，tag置1*/
flag=0;
freeblock[i].name[wtd]=fname;
printf（"$%c/n",freeblock[i].name）;
returnfreeblock[i].startaddress-applyarea;
}
else
if（freeblock[i].state==1&&freeblock[i].size==applyarea&&flag==1&&freeblock[i].name[wtd]==NULL）
{freeblock[i].startaddress=freeblock[i].startaddress+applyarea;
freeblock[i].size=freeblock[i].size-applyarea;
freeblock[i].state=0;
flag=0;
tag=1;/*有满足条件的空闲区时，tag置1*
freeblock[i].name[wtd]=fname
}
if（tag==0）
return-1;
}
voidsetfree（）///实现磁盘空间的回收
{
inti,j,k;
chars;
printf（"输入要删除的文件名:
/n"）;
getchar（）;
scanf（"%c",&s）;
for（j=0;j<100;j++）
if（FMenu[j].Fname==s）
{break;}
for（i=0;i{
for（k=0;k<100;k++）
printf（"$%c%d/n",freeblock[i].name,i）;
if（freeblock[i].name[k]==s）
{freeblock[i].state=1;
freeblock[i].startaddress=freeblock[i].startaddress-（（int）ceil（FMenu[j].size*1.0/100））;
freeblock[i].size=freeblock[i].size+（（int）ceil（FMenu[j].size*1.0/100））;
}
}
}
voidprint（）//打印输出表
{
inti;
printf（"\n"）;
printf（"|序号.......第一个空白块......连续空闲块个数......状态.....|"）;printf（"\n"）;
printf（"|..........................................................|"）;printf（"\n"）;
for（i=0;i{
printf（"|%3d...........%3d....................%3d.......%3d........|",
i,freeblock[i].startaddress,freeblock[i].size,freeblock[i].state）;printf（"\n"）;
printf（"|..........................................................|"）;printf（"\n"）;
}
}
图3-3；初始化格式
图3-4；分配磁盘
图3-5；回收磁盘
2.采用空白块成组链接结构实现磁盘空间的分配和回收；
（1）假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。
UNIX系统中采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块（N 表3-6；空闲块
0
空闲块数k
1
空闲块号1
2
空闲块号2
K
空闲块号k
当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。
（2）现模拟UNIX系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲块成组链接的初始状态为：
表3-7；初始化空闲快
开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。
用二维数组A：
array[0…M-1]ofarray[0…n-1]来模拟管理磁盘空间，用A[i]表示第I块，第0块A[0]作为专用块。
（3）成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。
定义一个数组MA存放专用块内容，即MA:
=A[0]。
申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。
当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再者分配。
（4）归还一块时给出归还的块号，且当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在MA重新登记一个新组。
（5）设计分配和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一次分配或归还后能显示或打印各空闲块组的情况（各组的空闲块数和块号）。
本实验省去了块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。
（6）运行你所设计的程序，假定空闲块链接的初始状态如提示
（2），现先分配4块，再依次归还第2块和第6块。
把执行后分配到的块号依次显示或打印出来，且显示或打印空闲块组的情况。
在上次执行的基础上继续分配3块，然后归还第1块，再申请5块，显示或打印依次分配到的块号及空闲块组情况。
核心代码
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}};/*磁盘空间*/
intmark[9];/*存放已分配的块*/
intNo=0;/*已分配的块数*/
voiddisplay1（）//打印显示结构
{inti,j,temp,count;
No=0;
if（MA[1]!
=0）
{i=MA[0];
printf（"\n组1:
\t"）;
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（"\n组%d:
\t",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（"\n组%d:
\t",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（"\n所有的快都已被分配！
"）;
else
{printf（"\n组1:
"）;
for（j=2;j<=i;j++）
{printf（"%d",MA[j]）;
mark[++No]=MA[j];
}
}
}
}
voiddisplay（）/*显示分组情况*/
{inti,j;
if（MA[0]!
=0）
display1（）;
else
{i=MA[1];
for（j=0;j<=3;j++）
MA[j]=A[i][j];
display1（）;
}
}
voidassign（）/*分配空闲块*/
{ints,i;
if（MA[0]>1）/*若该组不止一个空闲块*/
{i=MA[0];
s=MA[i];
MA[0]--;
printf（"\n被分配的块号:
\n%d\n",s）;
}
elseif（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（"\n被分配的块号:
\n%d\n",s）;
}
else/*没有其它空闲块组*/
{printf（"\n没有空闲空间！
"）;
return;
}
}
else/*当前组已分配完*/
{for（i=0;i<=3;i++）
MA[i]=A[0][i];
assign（）;
}
display（）;/*显示分组情况*/
}
voidcallback（）/*回收空闲块*/
{inti,j,temp;
printf（"\n请输入你想回收的块号:
\n"）;
scanf（"%d",&j）;
getchar（）;/*得到待回收的空闲块号*/
for（temp=1;temp<=No;temp++）
{if（mark[temp]==j）
break;
}
if（temp{printf（"\n该块还未被分配!
"）;
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（）;/*显示*/
}
图3-8：
初始化视图
图3-9：
分配块
图3-11：
分配块
图3-12：
回收块
3.采用位示图结构实现磁盘空间的分配和回收
（1）为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。
为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。
位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。
但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。
（2）申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。
假设现在有一个盘组共8个柱面，每个柱面有两个磁道，每个磁道分成4个物理记录。
那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：
柱面号=字节号
磁道号=[]
物理记录号= 位数mod4
（3）归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。
按照
（2）中假设的盘组，归还块在位示图中的位置计算如下：
字节号=柱面号
位数=磁道号4+物理记录号
（4）设计申请一块磁盘空间和归还一块磁盘空间的程序。
要求能显示或打印程序运行前运行后的位示图；分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。
源代码
voidshowbitmap（void）//showbitmap函数，功能打印位示图信息
{
printf（"当前系统磁盘位示图（0表示块可用）：
\n"）;//用来和位示图bitmap相与得到某位的状态
printf（"第一磁道第二磁道\n"）;
printf（"0扇区1扇区2扇区3扇区0扇区1扇区2扇区3扇区"）;
for（inti=0;i{
if（0==i%8）
{
printf（"\n"）;
printf（"%d柱面",（i+1）/8）;
}
printf（"%d\t",bitinfo->bitmap[i]）;
}
printf（"\n"）;
system（"pause"）;
}
voiddiskallocate（void）//diskallocate函数，分配物理块给
{
//由用户输入需要的物理块数：
intneednum;
inti;
intbusy=0;
charfilestor[32];//用户名
printf（"输入需要分配的块数:
\n"）;
scanf（"%d",&neednum）;
printf（"输入文件名:
\n"）;
scanf（"%s",filestor）;
for（i=0;i{
busy=busy+bitinfo->bitmap[i];
}
if（64-busy{
printf（"没有足够的空闲磁盘，分配失败！
"）;
}
else
{
printf（"开始分配...\n"）;
for（i=0;i{
if（0==bitinfo->bitmap[i]）
{
//printf（"分配块物理地址为:
第%d个柱面，\t第%d个磁道,\t第%d个扇区\n",i/8+1,i%8/4,（i%8）%4）;
bitinfo->bitmap[i]=1;
strcpy（bitinfo->filename[i],filestor）;
neednum--;
}
if（0==neednum）
{
break;
}
}
printf（"分配成功！
\n"）;
}
showbitmap（）;
system（"pause"）;
}
voiddiskreturn（void）//回收物理块
{
charfilereturn[32];
inti;
printf（"输入要回收的文件名"）;
scanf（"%s",filereturn）;
for（i=0;i{
if（0!
=strcmp（filereturn,bitinfo->filename[i]））
{
printf（"此文件没有被分配空间"）;
break;
}
else
{
bitinfo->bitmap[i]=0;
}
}
showbitmap（）;
system（"pause"）;
}
图3-13：
初始化
图3-14：
位示图
图3-15：
物理块分配
图3-16：
物理块回收
4.心得体会
（1）采用空白文件目录结构管理磁盘空间实现磁盘空间的分配和回收
通过采用空白文件目录结构管理磁盘空间实现磁盘的分配和回收，采用C语言进行编译，对C语言有了更新和更深的认识，并且此次试验是在Linux系统下调试，起初也是错误百出，总是运行不了，后来经过查阅资料，问题得以解
升级会员 