磁盘存储空间的分配和回收.docx
《磁盘存储空间的分配和回收.docx》由会员分享，可在线阅读，更多相关《磁盘存储空间的分配和回收.docx（25页珍藏版）》请在冰点文库上搜索。
磁盘存储空间的分配和回收
实习六磁盘存储空间的分配与回收
1、实习内容
模拟磁盘空闲空间的表示方法,以及模拟实现磁盘空间的分配与回收。
2、实习目的
磁盘初始化时把磁盘存储空间分成许多块（扇区）,这些空间可以被多个用户共享。
用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去,这就涉及到磁盘存储空间的分配与回收。
一个文件存放到磁盘上,可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等,因此,磁盘存储空间的分配有两种方式,一种就是分配连续的存储空间,另一种就是可以分配不连续的存储空间。
怎样有效地管理磁盘存储空间就是操作系统应解决的一个重要问题,通过本实习使学生掌握磁盘存储空间的分配与回收算法。
3、实习题目
本实习模拟三种磁盘存储空间的管理方法。
第一题:
连续的磁盘存储空间的分配与回收。
[提示]:
（1）要在磁盘上建立顺序文件时,必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。
可假定磁盘初始化时,已把磁盘存储空间划分成若干等长的块（扇区）,按柱面号与盘面号的顺序给每一块确定一个编号。
随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块）,有的区存放着文件,而有的区就是空闲的。
当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录,当一个文件被删除时,则该文件占用的区应成为空闲区。
为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分,格式如下:
序号
起始空闲块号
空闲块个数
状态
1
5
6
未分配
2
14
3
未分配
3
21
30
未分配
4
空表目
（2）要建立文件时,先查找空闲区表,从状态为“未分配”的登记栏目中找出一个块数能满足要求的区,由起始空闲块号能依次推得可使用的其它块号。
若不需要占用该区的所有块时,则剩余的块仍应为未分配的空闲块,这时要修改起始空闲块号与空闲块数。
若占用了该区的所有块,则相应登记栏中的状态修改成“空表目”。
删除一个文件时,从空闲区表中找一个状态为“空表目”的登记栏目,把归还的起始块号与块数填入对应的位置。
磁盘存储空间的分配与回收算法类似于主存储器的可变分区方式的分配与回收。
同学们可参考实习四的第一题。
（3）当找到空闲块后,必须启动磁盘把信息存放到指定的块中,启动磁盘必须给出由三个参数组成的物理地址:
柱面号、磁道号与物理记录号。
故必须把找到的空闲块号换算成磁盘的物理地址。
为了减少移臂次数,磁盘上的信息按柱面上各磁道顺序存放。
现假定一个盘组共有200个柱面,（编号0-199）每个柱面有20个磁道（编号0-19,同一柱面上的各磁道分布在各盘面上,故磁道号即盘面号。
）,每个磁道被分成等长的6个物理记录（编号0-5,每个盘面被分成若干个扇区,故每个磁道上的物理记录号即为对应的扇区号。
）。
那么,空闲块号与磁盘物理地址的对应关系如下:
空闲块号
6
M
20
M
20
空闲块号
6
假设M=,m={}
则物理记录号=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
0
1
0
0
2
0
1
0
0
1
3
1
0
0
1
1
2
表6-2
柱面号
磁道号
物理记录号
0
0
2
0
1
0
1
0
1
第三题:
模拟UNIX系统的空闲块成组链接法,实现磁盘存储空间的管理。
[提示]:
（1）假定磁盘存储空间已被划分成长度为n的等长块,共有M块可供使用。
UNIX系统中采用空闲块成组链接的方法来管理磁盘存储空间,将磁盘中的每N个空闲块（N
0
空闲块数k
1
空闲块号1
2
空闲块号2
K
空闲块号k
当第一项内容为“0”时,则第二项起指出的空闲块就是最后一组。
（2）现模拟UNIX系统的空闲块成组链接,假定共有8块可供使用,每3块为一组,则空闲块成组链接的初始状态为:
开始时,空闲块号就是顺序排列的,但经若干次的分配与归还操作后,空闲块的链接就未必按序排列了。
用二维数组A:
array[0…M-1]ofarray[0…n-1]来模拟管理磁盘空间,用A[i]表示第I块,第0块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块,显示或打印依次分配到的块号及空闲块组情况。
4、相关数据结构及说明
structfreeblock{
intFBbegin;//起始空闲块号
intnum;//空闲块数
charstate;//状态
structfreeblock*next;}
struct {
char name[10];//文件名
int size;//文件大小
int addr_cylinder;//装入磁盘的首地址_柱面号
int addr_track;//装入磁盘的首地址_磁道号
int addr_note;//装入磁盘的首地址_物理记录号
struct *next; }
六、源代码及注释
1、题一源代码:
#include
#include
int getmalloc（）//分配磁盘空间 {
int flag=0;
struct freeblock *p=FBhead;
struct *File;
File=（struct *）malloc（sizeof（struct ））;
printf（"输入要装入的文件名:
"）;
scanf（"%s",File->name）;
printf（"输入所需的磁盘空间大小:
"）;
scanf（"%d",&File->size）;
for（p=FBhead->next;p!
=NULL;p=p->next）
if（（File->size）<=（p->num））//分配空间
{
flag=1;
File->addr_cylinder=（（p->FBbegin）/6）/20;
File->addr_track=（（p->FBbegin）/6）%20;
File->addr_note=（p->FBbegin）%6;
File->next=>next;//加入文件链表
>next=File;
if（（File->size）<（p->num））//修改该快的起始地址与块数
{
p->FBbegin=p->FBbegin+File->size;
p->num=p->num-File->size; }
else p->state='U';
break; }
if（flag==0）
printf（"抱歉!
目前没有足够的磁盘空间分配给该文件、\n"）;
else {
printf（"分配磁盘成功!
\n该文件的物理地址:
\n柱面号\t磁道号\t物理块号\n "）;
printf（" %d\t %d\t %d\n",File->addr_cylinder,File->addr_track,File->addr_note）; } }
int deletelfree（）//回收磁盘空间 {
char name[10]; int flag=0;
struct *p;
printf（"输入要删除的文件名:
"）;
scanf（"%s",&name）;
for（p=>next!
=NULL;p=p->next）
{
if（strcmp（p->next->name,name）==0）//找到该文件
{
flag=1;
int funion=0,nunion=0;
int m=p->next->addr_cylinder;
int n=p->next->addr_track;
int k=p->next->addr_note;
int addr=（m*20+n）*6+k;//起始空闲块号
int tail=p->next->size+addr;
struct freeblock *pnode,*qnode,*tnode,*snode;
pnode=FBhead->next;
while（pnode!
=NULL）//先考虑与后面的部分或许有合并的情况
{
if（（pnode->FBbegin）==tail）
{
pnode->FBbegin=addr;
pnode->num=pnode->num+p->next->size;
nunion=1;
break; }
pnode=pnode->next; }
qnode=FBhead->next;
while（qnode!
=NULL）//再考虑就是否与前面的可以合并
{
if（（qnode->FBbegin+qnode->num）==addr）
{
if（nunion==0）
{
qnode->num=qnode->num+p->next->size;
funion=1;
break; }
else
{
qnode->num=qnode->num+pnode->num; t
node=FBhead;
while（tnode->next!
=pnode）
tnode=tnode->next;
tnode->next=pnode->next;
free（pnode）;
funion=1;
break;
}
}
qnode=qnode->next; }
if（funion==0&&nunion==0）//若没有与前面的或后面的进行合并,则新建一个表目
{
snode=（struct freeblock *）malloc（sizeof（struct freeblock））;
snode->FBbegin=addr;
snode->num=p->next->size;
snode->state='F';
if（FBhead->next==NULL）
{
FBhead->next=snode;
snode->next=NULL;
}
else
{
snode->next=FBhead->next;
FBhead->next=snode; } }
struct *q;
q=p->next;//除该文件
p->next=p->next->next;
free（q）; break; } }
if（flag==0）
printf（"没有该文件!
\n"）;
else {
printf（"文件删除成功!
\n"）; }
int dispfree（）//显示磁盘空闲区表
{
int i=1;
struct freeblock *p=FBhead;
printf（"\n磁盘空闲区表\n"）;
printf（"序号\t起始空闲块号\t空闲块个数\t 状态\n"）;
for（p=FBhead->next;p!
=NULL;p=p->next）
{
if（（p->state）=='F'）
printf（" %d\t %d\t\t %d\t\t未分配\n",i++,p->FBbegin,p->num）;
else
printf（" %d\t\t\t\t\t空表目\n",i++）; } }
int dispfile（）
{
char name[10];
struct *p=; printf（"输入要查瞧的文件名:
"）;
scanf（"%s",&name）;
for（p=>next;p!
=NULL;p=p->next）
{
if（strcmp（p->name,name）==0） {
printf（"该文件的物理地址:
\n柱面号\t磁道号\t物理块号\n "）;
printf（" %d\t %d\t %d\n",p->addr_cylinder,p->addr_track,p->addr_note）; break; } }
if（p==NULL）
printf（"没有该文件!
\n"）; }
int main（） {
int n,i,A[MAX],B[MAX];//A[MAX]表示起始空闲块号,B[MAX]表示空闲块个数
char ch;
struct freeblock *pnew;
FBhead=（struct freeblock *）malloc（sizeof（struct freeblock））;
FBhead->next=NULL;
printf（"输入磁盘空闲区个数:
"）;
scanf（"%d",&n）;
for（i=1;i<=n;i++） {
pnew=（struct freeblock *）malloc（sizeof（struct freeblock））;
pnew->next=NULL;
pnew->next=FBhead->next;
FBhead->next=pnew;
printf（"起始空闲块号:
"）;
scanf（"%d",&pnew->FBbegin）;
printf（"空闲块个数:
"）;
scanf（"%d",&pnew->num）; pnew->state='F'; pnew=pnew->next; }
（struct *）malloc（sizeof（struct ））;
>next=NULL;
do {
system（"cls"）;
printf（"\n\t\t ********** 主菜单 **********\n\n"）;
printf（"\t\t\t1、新建文件\n"）;
printf（"\t\t\t2、删除文件\n"）;
printf（"\t\t\t3、查瞧磁盘\n"）;
printf（"\t\t\t4、查瞧文件\n"）;
printf（"\t\t\t5、退出\n"）; printf（"请选择:
"）;
scanf（"%c",&ch）;
switch（ch） {
case '1':
getmalloc（）;system（"pause"）;break;
case '2':
deletelfree（）;system（"pause"）;break;
case '3':
dispfree（）;system（"pause"）;break;
case '4':
dispfile（）;system（"pause"）;break;
case '5':
exit
（1）;break;
default:
printf（"输入错误!
请重新输入、\n"）;
}
printf（"\n"）;
getchar（）; }
while（ch!
=4）;
return 0;
2、题二源代码:
#include
#include
void Initbitmap（int map[8][8]） {
int cylinder,track,sector;
char choice='Y';
printf（"初始化位视图、、、\n"）;
while（choice=='y'||choice=='Y'） {
p
升级会员 