实习3 磁盘存储空间的分配和回收
实习三 磁盘存储空间的分配和回收
一、实习题目
连续磁盘存储空间的分配和回收。
二、实习目的
磁盘初始化时把磁盘存储空间分成许多块(扇区),这些空间可以被多个用户共享。用
户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去,这就涉
及到磁盘存储空间的分配和回收。一个文件存放到磁盘上,可以组织成顺序文件(连续
文件)、链接文件(串联文件)、索引文件等,因此,磁盘存储空间的分配有两种方式,
一种是分配连续的存储空间,另一种是可以分配不连续的存储空间。怎样有效地管理磁
盘存储空间是操作系统应解决的一个重要问题,通过本实习使学生掌握磁盘存储空间的
分配和回收算法。
三、实习内容
模拟磁盘空闲空间的表示方法,以及模拟实现磁盘空间的分配和回收。 四、
思想
1.设计思路
(1) 要在磁盘上建立顺序文件时,必须把按序排列的逻辑记录依次存放在磁盘的连续存
储空间中。可假定磁盘初始化时,已把磁盘存储空间划分成若干等长的块(扇区),按
柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空
间被分成许多区(每一区包含若干块),有的区存放着文件,而有的区是空闲的。当要
建立顺序文件时必须找到一个合适的空闲区来存放文件记录,当一个文件被删除时,
则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未
占用的部分,格式如下:
序 号 起始空闲块号 空闲块个数 状 态
1 5 6 未 分 配
2 14 3 未 分 配
3 21 30 未 分 配
4 空 表 目
1
(2) 建立文件时,先查找空闲区表,从状态为“未分配”的表项中找出一个块数能满足要求的区,由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时,则剩余的块仍应为未分配的空闲块,这时要修改起始空闲块号和空闲块数。若占用了该区的所有块,则相应登记栏中的状态修改成“空表目”。删除一个文件时,需要考虑空闲块的合并情况。
磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。 (3) 当找到空闲块后,必须启动磁盘把信息存放到指定的块中,启动磁盘必须给出由三个参数组成的物理地址:盘面号、柱面号和物理记录号(即扇区号)。故必须把找到的空闲块号换算成磁盘的物理地址。
为了减少移臂次数,磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面,(编号0-199)每个柱面有20个磁道(编号0-19,同一柱面上的各磁道分布在各盘面上,故磁道号即盘面号。),每个磁道被分成等长的6个物理记录(编号0-5,每个盘面被分成若干个扇区,故每个磁道上的物理记录号即为对应的扇区号)。那么,空闲块号与磁盘物理地址的对应关系如下:
则 物理记录号 = 空闲块号 % 6
磁道号=(空闲块号 / 6 )% 20
柱面号=(空闲块号 / 6)/20
(4) 删除一个文件时,从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数,假定每个逻辑记录占磁盘上的一块,则可推算出归还后的起始空闲块号和块数,登记到空闲区表中。换算关系如下:
起始空闲块号=(柱面号,20+磁道号),6+物理记录号
空闲块数=逻辑记录数
(5) 请设计磁盘存储空间的分配和回收程序,要求把分配到的空闲块转换成磁盘物理地址,把归还的磁盘空间转换成空闲块号。
2.主要数据结构
struct freeblock
{
2
int FBbegin;//起始空闲块号
int num;//空闲块数
char state;//状态
struct freeblock *next; }
struct filetowrite
{
char name[10];//文件名
int size;//文件大小
int addr_cylinder;//装入磁盘的首地址_柱面号
int addr_track;//装入磁盘的首地址_磁道号
int addr_note;//装入磁盘的首地址_物理记录号
struct filetowrite *next; }
3.主要代码结构及代码段分析
int getmalloc()//分配磁盘空间
{
int flag=0;
struct freeblock *p=FBhead;
struct filetowrite *File;
File=(struct filetowrite *)malloc(sizeof(struct filetowrite));
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;
3
File->addr_track=((p->FBbegin)/6)%20;
File->addr_note=(p->FBbegin)%6;
File->next=Filehead->next;//加入文件链表
Filehead->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 filetowrite *p;
printf("输入要删除的文件名:");
scanf("%s",&name);
for(p=Filehead;p->next!=NULL;p=p->next)
{
if(strcmp(p->next->name,name)==0)//找到该文件
4
{
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;
5
break;
}
else
{
qnode->num=qnode->num+pnode->num;
tnode=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;
6
FBhead->next=snode;
}
}
struct filetowrite *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()
7
{
char name[10];
struct filetowrite *p=Filehead;
printf("输入要查看的文件名:");
scanf("%s",&name);
for(p=Filehead->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;
8
pnew->next=FBhead->next;
FBhead->next=pnew;
printf("起始空闲块号:");
scanf("%d",&pnew->FBbegin);
printf("空闲块个数:");
scanf("%d",&pnew->num);
pnew->state='F';
pnew=pnew->next;
}
Filehead=(struct filetowrite *)malloc(sizeof(struct filetowrite));
Filehead->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");
9
}
printf("\n");
getchar();
}while(ch!=4);
return 0;
}
五、上机实习所用平台及相关软件
本程序在windows平台(xp)下,使用Dev-C++编译器编写,并已编译通过。 六、调试过程
测试数据:(磁盘空间大小为100)
文件 请求磁盘空间大小
a 10
b 20
c 30
d 50
测试结果:
七、
(1)磁盘空闲区表和文件的数据结构我均使用了单链表来构建,用p->next表示当前
节点,则p表示其前驱节点,这样方便链表节点的删除操作。
(2)在程序中充分考虑到出错处理。比如在功能选择菜单中,若用户出入非法字符则
提示“输入错误!请重新输入”;在用户申请磁盘空间时,若要求的空间大于空闲的空间,
10
则提示“抱歉!目前没有足够的磁盘空间分配给该文件”;在回收磁盘空间时,若用户输入的文件名不存在,则提示“没有该文件”。这样提高了程序的健壮性。 3)在回收磁盘空间时,分情况讨论空闲区的合并。先考虑和后面的空闲区或许可以(
合并的情况,再考虑和前面的空闲区或许可以合并的情况。如果没有和前面的或者后面的空闲区进行合并,则新建一个表目。这样程序清晰,逻辑性强。
(4)通过本实验,我进一步加深了对连续磁盘空间的分配回收过程的理解,同时也得到了将系统理论实践的机会,锻炼了我的编程能力。
11