每一个可以努力的日子，都是一份厚礼。
连续磁盘存储空间的分配和回收
2008-12-24 15:17
一、实习内容
模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。
二、实习目的
磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习来掌握磁盘存储空间的分配和回收算法。
三、实习题目
连续磁盘存储空间的分配和回收
四、设计思想
1.设计思路
（1）要在磁盘上建立顺序文件时，必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时，已把磁盘存储空间划分成若干等长的块（扇区），按柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有的区存放着文件，而有的区是空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时，则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分，格式如下：
序号 起始空闲块号 空闲块个数 状态
1 5 6 未 分 配
2 14 3 未 分 配
3 21 30 未 分 配
4 空 表 目
（2）建立文件时，先查找空闲区表，从状态为“未分配”的表项中找出一个块数能满足要求的区，由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时，则剩余的块仍应为未分配的空闲块，这时要修改起始空闲块号和空闲块数。若占用了该区的所有块，则相应登记栏中的状态修改成“空表目”。删除一个文件时，需要考虑空闲块的合并情况。
（3）当找到空闲块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三个参数组成的物理地址：盘面号、柱面号和物理记录号（即扇区号）。故必须把找到的空闲块号换算成磁盘的物理地址。
为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面，（编号0-199）每个柱面有20个磁道（编号0-19，同一柱面上的各磁道分布在各盘面上，故磁道号即盘面号），每个磁道被分成等长的6个物理记录（编号0-5，每个盘面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号）。那么，空闲块号与磁盘物理地址的对应关系如下：
物理记录号 = 空闲块号 % 6
磁道号 = （空闲块号 / 6 ）% 20
柱面号 = （空闲块号 / 6）/ 20
（4）删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑记录占磁盘上的一块，则可推算出归还后的起始空闲块号和块数，登记到空闲区表中。换算关系如下：
起始空闲块号 = （柱面号20 + 磁道号）6 + 物理记录号
空闲块数 = 逻辑记录数
（5）设计磁盘存储空间的分配和回收程序，把分配到的空闲块转换成磁盘物理地址，把归还的磁盘空间转换成空闲块号。
2.主要数据结构
struct FreeBlockMenu
{
long FBbegin;//起始空闲块号
long num;//空闲块个数
struct FreeBlockMenu *next;
struct FreeBlockMenu *front;
};
struct FiletoWrite
{
char name[10];//装入的文件名，供回收磁盘空间时查找
long size;//文件大小
long addr_zhumian;//装入磁盘的首地址_柱面号
long addr_cidao;//装入磁盘的首地址_磁道号
long addr_jilu;//装入磁盘的首地址_物理记录号
struct FiletoWrite *next;
struct FiletoWrite *front;
};
3.主要代码结构及代码段分析
//分配磁盘空间
int getMalloc()
{
int flag = 0;
struct FreeBlockMenu *p = FBhead;
struct FiletoWrite *File;
File = (struct FiletoWrite *)malloc(sizeof(struct FiletoWrite));
printf("请输入装入的文件名：\n");
scanf("%10s",File->name);
printf("请输入所需要的磁盘空间大小：\n");
scanf("%d",&File->size);
for(p = FBhead->next;p != NULL;p = p->next)
{
flag = 1;
if(p->num >= File->size )
{
//分配空间，块号转化为物理地址
File->addr_zhumian = (p->FBbegin/6)/20;
File->addr_cidao = (p->FBbegin/6)%20;
File->addr_jilu = p->FBbegin%6;
//加入文件链表中
File->next = Filehead->next;
if(Filehead->next != NULL)
Filehead->next->front = File;
Filehead->next = File;
File->front = Filehead;
if(p->num > File->size)
{
//修改该块的起始地址和块数
p->FBbegin = p->FBbegin + File->size;
p->num = p->num - File->size;
}
else if(p->num == File->size)
{
//从空闲块表中删除该结点
if(p->front != NULL)
{
if(p->next != NULL)
{
p->front->next = p->next;
p->next->front = p->front;
free(p);
}
else
{
p->front->next = p->next;
free(p);
}
}
else
{
p->next->front = p->front;
free(p);
}
}
printf("\n分配磁盘成功！\n该文件的物理地址为：(柱面号 磁道号 物理块号)\n");
printf(" %d %d %d\n",File->addr_zhumian,File->addr_cidao,File->addr_jilu);
}
}
if(flag == 0)
{
printf("对不起，目前没有足够的磁盘空间分配给该文件。");
return 0;
}
}
int showDisk();
//回收磁盘空间
int setFree()
{
char name[10];
int flag = 0;
struct FiletoWrite *p = Filehead;
printf("请输入要删除的文件名：\n");
scanf("%10s",&name);
for(p = Filehead;p != NULL;p = p->next)
{
if(strcmp(p->name , name)==0)//找到该文件
{
flag = 1;
int houhebing=0,qianhebing=0;
long m = p->addr_zhumian;
long n = p->addr_cidao;
long k = p->addr_jilu;
long addr =120*m + 6*n + k;//块号
//先考虑和后面的部分或许会有合并的情况
long int tail=addr+p->size;
struct FreeBlockMenu *pNode,*qNode;
pNode=FBhead->next;
while(pNode!=NULL)
{
if(pNode->FBbegin==tail)
{
pNode->FBbegin=addr;
pNode->num=pNode->num+p->size;
houhebing=1;
qNode=pNode;
break;
}
pNode=pNode->next;
}
//再考虑是否可以和前面的进行合并
pNode=FBhead->next;
while(pNode!=NULL)
{
if(pNode->FBbegin+pNode->num==addr)
{
if(houhebing==0)
{
pNode->num=pNode->num+p->size;
qianhebing=1;
break;
}
else if(houhebing==1)
{
pNode->num+=qNode->num;
pNode=FBhead;
while(pNode->next!=qNode)
pNode=pNode->next;
pNode->next=qNode->next;
free(qNode);
qianhebing=1;
break;
}
}
pNode=pNode->next;
}
//如果没有和前面的或者后面的进行合并，则新建一个表目
if(qianhebing==0 && houhebing==0)
{
pNode=(struct FreeBlockMenu*)malloc(sizeof(struct FreeBlockMenu));
pNode->FBbegin=addr;
pNode->num=p->size;
if(FBhead->next==NULL)
{
FBhead->next=pNode;
pNode->front=FBhead;
pNode->next=NULL;
FBhead->front=NULL;
}
else
{
pNode->next=FBhead->next;
FBhead->next->front=pNode;
FBhead->next=pNode;
pNode->front=FBhead;
}
}
//在文件链表中删除该文件
struct FiletoWrite *pPrev=p->front;
if(p->next==NULL)
{
pPrev->next=NULL;
free(p);
}
else
{
pPrev->next=p->next;
p->next->front=pPrev;
}
}
}
if(flag == 0)
printf("没有该文件！\n");
else
printf("删除文件成功！\n");
}
//显示磁盘空闲区表
int showDisk()
{
struct FreeBlockMenu *p = FBhead;
printf("\n磁盘空闲块表\n");
printf("起始地址 空闲块大小\n");
for(p = FBhead->next;p != NULL;p = p->next)
printf(" %ld %ld\n",p->FBbegin,p->num);
}
int main()
{
char choose;
FBhead = (struct FreeBlockMenu *)malloc(sizeof(struct FreeBlockMenu));
if(FBhead == NULL)
{
printf("error in allocating...\n");
}
else
printf("successed\n");
struct FreeBlockMenu *pNew=(struct FreeBlockMenu*)malloc(sizeof(struct FreeBlockMenu));
pNew->FBbegin = 0;
pNew->num = 24000;
pNew->next = pNew->front = NULL;
FBhead->next=pNew;
FBhead->front=NULL;
pNew->front=FBhead;
pNew->next=NULL;
Filehead = (struct FiletoWrite *)malloc(sizeof(struct FiletoWrite));
Filehead->next = Filehead->front = NULL;
char buf[128];
do
{
system("clear");
printf("---------------------------\n");
printf("1.请求磁盘空间\n");
printf("2.回收磁盘空间\n");
printf("3.显示磁盘空闲区表\n");
printf("4.退出\n");
printf("---------------------------\n");
printf("请选择：");
scanf("%c",&choose);
switch(choose)
{
case '1':
getMalloc();
gets(buf);break;
case '2':
setFree();
gets(buf);break;
case '3':
showDisk();
gets(buf);break;
case '4':
exit(1);break;
default:
gets(buf);
printf("输入错误！请重新输入。\n");
break;
}
printf("\n");
getchar();
}while(choose != '4');
}
五、上机实习所用平台及相关软件
本程序在Linux平台（Ubuntu8.04.1）下，使用vi编辑器编写，g++编译通过。
六、调试过程
测试数据：
文件名 请求磁盘空间大小
aaa 20
bbb 1000
ccc 2000
ddd 3000
测试结果：
截图（略）
七、总结
（1）磁盘空闲区表和文件的数据结构我均使用了双链表来构建，这样可以很方便地访问到前驱节点，更容易进行链表节点的删除操作，节省了很多时间。
（2）在程序中充分考虑到出错处理。比如在功能选择菜单中，若用户输入非法字符则提示“输入错误！请重新输入”；在用户申请磁盘空间时，若要求的空间大小大于空闲空间大小，则提示“没有足够的磁盘空间”；在回收磁盘空间时，若用户输入的文件名不存在，则提示“没有该文件”。这样提高了程序的健壮性。
（3）在回收磁盘空间时，分情况讨论空闲块的合并。先考虑和后面的空闲块或许会有合并的情况，再考虑是否可以和前面的块进行合并，如果没有和前面或者后面的空闲块进行合并，则新建一个表目。这样程序结构清晰，逻辑性强。
（4）通过本实验，我进一步加深了对连续磁盘空间的分配回收过程的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。
| 这篇文章由lovelucy于2008-12-24 15:17发表在后端架构。你可以订阅RSS 2.0 也可以发表评论或引用到你的网站。除特殊说明外文章均为本人原创，并遵从署名-非商业性使用-相同方式共享创作协议，转载或使用请注明作者和来源，尊重知识分享。 |
批评不自由
则赞美无意义
大约12年前
要是调试的话还少什么。比如头文件什么的。