磁盘存储空间的分配和回收Word格式.docx
《磁盘存储空间的分配和回收Word格式.docx》由会员分享，可在线阅读，更多相关《磁盘存储空间的分配和回收Word格式.docx（24页珍藏版）》请在冰点文库上搜索。
该区的所有块，则相应登记栏中的状态修改成“空表目”。
删除一个文件时，从空闲区表中找一个状态为“空表目”的登记栏目，把归还的起始块号和块数填入对应的位置。
磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。
同学们
可参考实习四的第一题。
（3）当找到空闲块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三
个参数组成的物理地址：
柱面号、磁道号和物理记录号。
故必须把找到的空闲块号换算成磁
盘的物理地址。
为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。
现假定一个盘组共有200
个柱面，（编号0-199）每个柱面有20个磁道（编号0-19,同一柱面上的各磁道分布在各盘面上，故磁道号即盘面号。
），每个磁道被分成等长的6个物理记录（编号0-5,每个盘
面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号。
）。
那么，空闲块号与磁盘物理地址的对应关系如下：
m={空闲块号}
假设M=I-空闲块号—
则物理记录号=m—
磁道号={M}
20
柱面号=[M]
（4）删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑记录占磁盘上的一块，则可推算出归还后的起始空闲块号和块数，登记到空闲区表中。
换算关系如下:
起始空闲块号=（柱面号20+磁道号）6+物理记录号空闲块数=逻辑记录数
（5）请设计磁盘存储空间的分配和回收程序，要求把分配到的空闲块转换成磁盘物理地
址，把归还的磁盘空间转换成空闲块号。
假定空闲区表的初值如提示
（1）中指出，现有一文件要占用10块，运行你所设计的分配程序，显示或打印分配后的空闲区表以及分配到的磁盘空间的起始物理地址。
然后，有一
文件被删除，它占用的磁盘空间为：
1号柱面2号磁道，0号物理记录开始的4块，运行你所设计的回收程序，显示或打印回收后的空闲区表。
第二题：
用位示图管理磁盘存储空间
[提示]:
（1）为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文
件可以把逻辑记录存放在不连续的存储空间。
为了表示哪些磁盘空间已被占用，哪些磁盘空
间是空闲的，可用位示图来指出。
位示图由若干字节构成，每一位与磁盘上的一块对应，“1
状态表示相应块已占用，“0”状态表示该块为空闲。
位示图的形式与实习四中的位示图一
样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。
（2）申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一
位对应块的磁盘物理地址，且把该位置成占用状态“1”。
假设现在有一个盘组共80个柱面,每个柱面有两个磁道，每个磁道分成4个物理记录。
那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：
柱面号=字节号
磁道号=[位数]
物理记录号={位数}
（3）归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。
按照
（2）中假设的盘组，归还块在位示图中的位置计算如下：
字节号=柱面号
位数=磁道号4+物理记录号
（4）设计申请一块磁盘空间和归还一块磁盘空间的程序。
要求能显示或打印程序运行前
和运行后的位示图；
分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还
块对应于位示图的字节号和位数显示或打印出来。
（5）假定已有如表6-1的磁盘空间被占用了，现在要申请五块磁盘空间，运行分配程序，
按（4）中要求显示或打印运行的结果。
然后再归还如表6-2的空间，运行回收程序，按（4）
中的要求显示或打印运行结果。
表6-1
柱面号
磁道号
物理记录号
0「
表6-2
第三题：
模拟UNlX系统的空闲块成组链接法，实现磁盘存储空间的管理。
（1）假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。
UNlX系统
中采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块（N<
M）分
成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第
一组的块数和块号登记在专用块中，登记的格式如下：
当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。
（2）现模拟UNlX系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则
空闲块成组链接的初始状态为：
空闲块的链接就未
开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，
必按序排列了。
用二维数组A:
array[0∙∙∙M-1]Ofarray[0…n-1]来模拟管理磁盘空间，用A[i]表示第I
块，第O块A[0]作为专用块。
（3）成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。
定义一个数组MA存放专用
块内容，即MA:
=A[0]。
申请一块磁盘空间时，查MA,从中找出空闲块号，当一组的空闲
块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该
块分配给申请者。
当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，
再为申请者分配。
分配算法如图6-1。
图6-1采用成组链接的分配算法
（4）归还一块时给出归还的块号，叵当前组不满规定块数时，将归还块登记入该组；
若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接
情况MA复制到归还块中，然后在MA重新登记一个新组。
归还一块的算法如图6-2。
图6-2采用成组链接的回收算法
（5）设计分配和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一
次分配或归还后能显示或打印各空闲块组的情况（各组的空闲块数和块号）。
本实习省去了
块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。
（6）运行你所设计的程序，假定空闲块链接的初始状态如提示
（2）,现先分配4块,
再依次归还第2块和第6块。
把执行后分配到的块号依次显示或打印出来，且显示或打印空
闲块组的情况。
在上次执行的基础上继续分配3块，然后归还第1块，再申请5块，显示或打印依次分
配到的块号及空闲块组情况。
四、相关数据结构及说明
StrUCtfreeblock{
intFBbegin;
〃起始空闲块号
intnum;
//空闲块数
Charstate;
//状态
StrUCtfreeblock*next;
}
StrUCtfiletowrite{
Charname[10];
//文件名
intsize;
//文件大小
intaddr_cylinder;
//装入磁盘的首地址_柱面号intaddr_track;
//装入磁盘的首地址_磁道号intaddr_note;
//装入磁盘的首地址—物理记录号StrUCtfiletowrite*next;
六、源代码及注释
1、题一源代码：
#include<
stdlib.h>
stdio.h>
intgetmalloc（）//分配磁盘空间{
intflag=0;
structfreeblock*p=FBhead;
structfiletowrite*File;
File=（structfiletowrite*）malloc（sizeof（structfiletowrite））;
printf（"
输入要装入的文件名：
"
）;
scanf（"
%s"
File->
name）;
输入所需的磁盘空间大小：
%d"
&
File->
size）;
for（p=FBhead->
next;
p!
=NULL;
p=p->
next）if（（File->
size）<
=（p->
num））//分配空间
{
flag=1;
addr_cylinder=（（p->
FBbegin）/6）/20;
addr_track=（（p->
FBbegin）/6）%20;
addr_note=（p->
FBbegin）%6;
next=Filehead->
//加入文件链表
Filehead->
next=File;
if（（File->
（p->
num））//修改该快的起始地址和块数
p->
FBbegin=p->
FBbegin+File->
size;
num=p->
num-File->
elsep->
state='
U'
;
break;
if（flag==0）
抱歉!
目前没有足够的磁盘空间分配给该文件.\n"
else{
分配磁盘成功!
\n该文件的物理地址：
\n柱面号\t磁道号\t物理块号\n"
printf（"
%d\t%d\t%d\n"
addr_cylinder,File->
addr_track,File->
addr_note）;
}}intdeletelfree（）//回收磁盘空间{
charname[10];
intflag=0;
structfiletowrite*p;
输入要删除的文件名：
for（p=Filehead;
next!
next）
if（strcmp（p->
next->
name,name）==0）//找到该文件
intfunion=0,nunion=0;
intm=p->
addr_cylinder;
intn=p->
addr_track;
intk=p->
addr_note;
intaddr=（m*20+n）*6+k;
//起始空闲块号
inttail=p->
size+addr;
structfreeblock*pnode,*qnode,*tnode,*snode;
pnode=FBhead->
while（pnode!
=NULL）//先考虑和后面的部分或许有合并的情况
if（（pnode->
FBbegin）==tail）
pnode->
FBbegin=addr;
pnode->
num=pnode->
num+p->
nunion=1;
}pnode=pnode->
}qnode=FBhead->
while（qnode!
=NULL）//再考虑是否和前面的可以合并
{if（（qnode->
FBbegin+qnode->
num）==addr）
if（nunion==0）
qnode->
num=qnode->
funion=1;
else
{qnode->
num+pnode->
num;
tnode=FBhead;
while（tnode->
=pnode）tnode=tnode->
tnode->
next=pnode->
free（pnode）;
funion=1;
}
qnode=qnode->
if（funion==0&
&
nunion==0）//若没有和前面的或后面的进行合并，则新建一个表目
snode=（structfreeblock*）malloc（sizeof（structfreeblock））;
snode->
snode->
F'
if（FBhead->
next==NULL）
FBhead->
next=snode;
next=NULL;
{snode->
next=FBhead->
}}structfiletowrite*q;
q=p->
//除该文件p->
next=p->
free（q）;
break;
}}if（flag==0）printf（"
没有该文件!
\n"
文件删除成功!
intdispfree（）//显示磁盘空闲区表
inti=1;
\n磁盘空闲区表\n"
序号\t起始空闲块号\t空闲块个数\t状态\n"
if（（p->
state）=='
）
%d\t%d\t\t%d\t\t未分配\n"
i++,p->
FBbegin,p->
num）;
else
%d\t\t\t\t\t空表目\n"
i++）;
}}
intdispfile（）
structfiletowrite*p=Filehead;
输入要查看的文件名：
scanf（"
for（p=Filehead->
{if（strcmp（p->
name,name）==0）{printf（"
该文件的物理地址：
p->
addr_cylinder,p->
addr_track,p->
if（p==NULL）
intmain（）{
intn,i,A[MAX],B[MAX];
//A[MAX]表示起始空闲块号，B[MAX]表示空闲块个数
charch;
structfreeblock*pnew;
FBhead=（structfreeblock*）malloc（sizeof（structfreeblock））;
输入磁盘空闲区个数：
n）;
for（i=1;
i<
=n;
i++）{
pnew=（structfreeblock*）malloc（sizeof（structfreeblock））;
pnew->
next=pnew;
起始空闲块号：
FBbegin）;
空闲块个数：
pnew->
pnew=pnew->
}Filehead=（structfiletowrite*）malloc（sizeof（structfiletowrite））;
Filehead->
do{
system（"
cls"
\t\t\t5.退出\n"
请选择：
%c"
ch）;
switch（ch）{
case'
1'
:
getmalloc（）;
pause"
case'
2'
deletelfree（）;
3'
dispfree（）;
4'
dispfile（）;
5'
exit
（1）;
default:
输入错误!
请重新输入.\n"
}printf（"
getchar（）;
}while（ch!
=4）;
return0;
2、题二源代码：
#include<
#include<
process.h>
voidInitbitmap（intmap[8][8]）{intcylinder,track,sector;
charchoice='
Y'
初始化位视图...\n"
while（choice=='
y'
||choice=='
）{printf（"
柱面号:
"
cylinder）;
磁道号:
track）;
物理记录号:
sector）;
map[cylinder][4*track+sector]=1;
contiune?
getchar（）;
choice）;
}}voidallocate（intmap[8][8]）{inti,j;
intcylinder,track,sector;
for（i=0;
8;
i++）{for（j=0;
j<
j++）if（map[i][j]==0）
map[i][j]=1;
if（flag==1）break;
if（flag==1）
cylinder=i;
track=j/4;
sector=j%4;
分配到的柱面号、磁道号、物理记录数"
%d\t%d\t%d"
cylinder,track,sector）;
elseprintf（"
空间不足，分配失败!
}voidreclaim（intmap[8][8]）{intcylinder,track,sector;
if（map[cylinder][4*track+sector]==0）{
此块为未分配块！
回收出错！
}else{
map[cylinder][4*track+sector]=0;
回收块对应的字节号:
%4d\t位数:
%4d\n"
cylinder,4*track+sector）;
}}voidmain（）{
intbitmap[8][8];
inti,j;
intchoice;
or（i=0;
i++）for（j=0;
j++）
bitmap[i][j]=0;
Initbitmap（bitmap）;
while
（1）{
\n请输入选择:
1--分配，2---回收，3--显示位示图，0--退出\n"
switch（choice）{case1:
allocate（bitmap）;
case2:
reclaim（bitmap）;
case3:
for（i=0;
i++）{for（j=0;
j++）printf（"
%8d"
bitmap[i][j]）;
}break;
case0:
exit（0）;
default:
错误选择！
}}}
3、第三题源程序：
intMA[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}};
/*磁盘空间*/
intmark[9];
/*存放已分配的块*/
intNo=0;
/*已分配的块数*/
voiddisplay1（）
{inti,j,temp,count,No=0;
if（MA[1]!
=0）
{i
升级会员 