【课程设计】操作系统课程设计之Linux磁盘空间管理.doc

实践教学
*******************

兰州理工大学

计算机与通信学院

2010年秋季学期

操作系统 课程设计

题 目：磁盘空间管理模拟实验
专业班级： 08级计算机1班
姓 名：
学 号：
指导教师： ******
成 绩：

目 录

摘 要 3
前 言 4
正 文 5
1. 实验目的 5
2. 设计思想 5
3. 实验结构图 6
4. 各模块的伪码算法 7
5. 测试分析 10
6. 测试结果 10
7. 源程序 14
总 结 20
参考文献 21
致 谢 22

摘 要
要把文件信息存放在存储介质上，必须先找出存储介质上可供使用的空闲块。存储介质上某个文件不再需要时，又要收回它所占的存储空间作为空闲块。用户作业在执行期间经常要求建立一个新文件或撤消一个不再需要的文件，因此，文件系统必须要为它们分配存储空间或收回它所占的存储空间。如何实现存储空间的分配和收回，取决于对空闲块的管理方法，主要有两种对磁盘存储空间的分配和收回的方法位示图法（用一张位示图（简称位图）来指示磁盘存储空间的使用情况），空闲块链接法（在UNIX操作系统中，把磁盘存储空间的空闲块成组链接）。

关键词：磁盘的分配和回收管理；位示图；成组链接。

前 言
通过该题目的设计过程，掌握磁盘存储管理的原理、软件开发方法并提高解决实际问题的能力。学习使用位示图管理磁盘空间的分配与回收，了解程序运行前和回收磁盘的物理地址过程。学会用模拟UNIX系统的成组链接法实现磁盘空间的管理。了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。希望通过本次设计过程可以提高自己的分析问题的能力和实际动手的能力，将学到的知识用于实践中。

正 文
1. 实验目的
磁盘格式化时,系统把磁盘存储空间分成许多磁道。每个磁道又分成若干个扇区(又叫做块)。这些空间就是用来存放用户文件的。当用户的文件不再需要时,就应该删除。把一个文件存放到磁盘上时,可以组织成连续文件,链接文件,索引文件等。因此,磁盘空间的分配方法也有两种,一种是连续空间的分配;一种是不连续空间的分配(又叫动态分配)。如何充分有效的利用磁盘空间,是操作系统应解决的重要课题之一。通过本实验,使学生对磁盘空间的分配与回收有一个较深入的理解。
2. 设计思想
Ø 位示图法：

一个简单的管理方法是用一张位示图（简称位图）来指示磁盘存储空间的使用情况。一个盘组的分块确定后，根据分配的总块数决定位图由多少个字组成,位图中的每一位与盘组分块一一对应。位示图是一张可以反映磁盘空间是否被占有的模拟图，用一个二维数组表示磁盘的空间，数组内每一个元素表示磁盘内相应的分块，数组元素为“1”表示该块已被占，“0”表示该块为空。数组元素位置与磁盘分块一一对应，即可描述出磁盘空间的利用情况。

Ø 成组链接法：

首先定义磁盘分配数组并初始化，9个一维数组分别表示9个空闲块，程序运行时，先将专用块A〔0〕复制到内存中，然后进行功能选择，分配时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，应把该块中指出的下一组的空闲块数和块号复制到专用块这，然后把该块分配给申请者，当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到内存，再为申请者分配。 回收时，输入待回收的块号，查找该块是否已被分配，若未分配，退出，否则，当前组不满规定块数时，将归还块登记入该组，若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把内存中登记的一组链接情况MA复制到归还块中，然后在MA这重新登记一个新组。显示分组情况。系统初始化时先将专用块内容读入 内存 ，当有申请空闲块要求时，就直接在内存专用块中找到哪些块是空闲的，每分配一块后把空闲块数减 1。但要把一组中第一块分配出去之前可以先把登记在该块中的下一组的块号保存在专用块中(此时 ，原专用块中的信息巳经无用了 ，因它指示的一组空闲块都已分配掉)。当中文组空闲块分配完后,则将下一组内容读入内存专用块中，以便继续分配时查找。
申请磁盘块
3. 实验结构图

查看位示图找位号等

是否找到

否：返回，磁盘已满,本次无法分配

是：由字位号计算相对块号和柱面号,磁道号,物理记录号,并输出这些 相应参数

返回
置位示图相应位为1

4. 各模块的伪码算法
1) 对位示图法

² 定义分配函数：

void assign()
{
unsigned int n=0,i,s=1,j,k,q,m,sq,zhm,cid;
for(i=0 ,k=0;i<5;i++)
{q=size[i] ;
j=0;
while(1)
{
j++ ;
if((q%2)==0)
{ if(j==1) size[i]+=1;
else
{for(m=1;m s*=2 ;
size[i]+=s;}
k=1;
break ;/*完成后退出*/
}
q=q/2;
}
if(k==1) /*将找到的位示图位转换成物理地址*/
{ if((j-1)/8==1)
{zhm=2*i+1;
cid=(j-9)/4;
sq=(j-9)%4;}
else
{zhm=2*i;
cid=(j-1)/4;
sq=(j-1)%4;
}
n=1;
break;/*退出for循环*/

}
}
if(n==0)
printf("没有空间可分配!\n");
else
{printf("分配成功!\n");/*输出物理地址*/
printf("柱面号为: %d\n",zhm);
printf("磁道号为: %d\n",cid);
printf("扇区号为: %d\n",sq);
}
printf("分配后的位示图为:\n");
out();
}

² 定义回收函数：

void callback()/*回收函数*/
{ unsigned int i,j,s=1,q,m,sq,zhm,cid;
printf("确定要回收块的柱面号、磁道号、扇区号:\n");
printf("请输入柱面号：");
scanf("%d",&zhm);
printf("\n请输入磁道号：");
scanf("%d",&cid);
printf("\n请输入扇区号：");
scanf("%d",&sq);
if(zhm%2==0)/*计算对应的位示图位置*/
{ i=zhm/2;
j=cid*4+sq+1;
}
else
{ i=(zhm-1)/2;
j=cid*4+sq+9;
}
q=size[i];
m=j-1;
while(m)
{q=q/2;
m--;}
if(q%2==1)/*判断该块是否被分配*/
{if(j==1)size[i]-1;/*将位示图对应为置零*/
else
{for(m=1;m

v 分配函数：

void assign()
{int s,i;
if(MA[0]>1) /*若该组不止一个空闲块*/
{ i=MA[0];
s=MA[i];
MA[0]--;
printf("\nnumber of the block:%d",s);
}
else if(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("\nnumber of the block:%d",s);
}
else /*没有其它空闲块组*/
{ printf("\nThere isn't any space");
return;
}
}
else /*当前组已分配完*/
{for(i=0;i<=3;i++)
MA[i]=A[0][i];
assign();
}
display(); /*显示分组情况*/
}
v 回收函数：
void callback()
{ int i,j,temp;
printf("\ninput the No. of the block you want to callback:");
scanf("%d",&j);
getchar(); /*得到待回收的空闲块号*/
for(temp=1;temp<=No;temp++)
{ if(mark[temp]==j)
break;}
if(temp出*/
{ printf("\nThe block is in the disk");
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(); /*显示*/
}
5. 测试分析
用位示图表示的磁盘空间可以很形象的反映出磁盘中空间的利用情况，不足之处在于每次分配与回收只可以对单一的分块进行操作，不能同时进行几个块的分配与回收，要进行多个块的分配时，只能单独分配，且块之间没有相互链接，对于大的空间分配只能在连续空间进行。
用成组链接法模拟的磁盘空间能够解决用位示图中存在的问题，它可以通过链表的形式存取信息，对于较大的空间分配，若一个磁盘空间不够，通过指针找到下一个空闲的分区，但操作过程比较复杂，没有位示图方便，简捷。
6. 测试结果
1) 位示图法

² 编译及连接时界面：

² 刚运行时界面：

² 分配空间时界面：

² 回收空间时界面：

2) 成组链接法

Ø 分配空间时界面：

Ø 回收空间时界面：

7. 源程序
Ø 位示图法：
#include
unsigned int size[5]={1,1,1,1,1};/*保存位示图*/
void out()/*输出位示图函数*/
{ unsigned int i,j,m;
for(j=0;j<5;j++)/*循环输出size的各个数的各个二进制位*/
{m=size[j];
for(i=0;i<16;i) /**/
{printf("%d ",m%2);
m=m/2;
if(i==7)
printf("\n");
}
printf("\n");
}
}
void callback()/*回收函数*/
{ unsigned int i,j,s=1,q,m,sq,zhm,cid;
printf("确定要回收块的柱面号、磁道号、扇区号:\n");
printf("请输入柱面号：");
scanf("%d",&zhm);
printf("\n请输入磁道号：");
scanf("%d",&cid);
printf("\n请输入扇区号：");
scanf("%d",&sq);
if(zhm%2==0)/*计算对应的位示图位置*/
{ i=zhm/2;
j=cid*4+sq+1;
}
else
{ i=(zhm-1)/2;
j=cid*4+sq+9;
}
q=size[i];
m=j-1;
while(m)
{q=q/2;
m--;}
if(q%2==1)/*判断该块是否被分配*/
{if(j==1)size[i]-=1;/*将位示图对应为置零*/
else
{for(m=1;m收后的位示图为:\n");
out();
}
else
printf("该块以被分配!");
}
void assign()
{
unsigned int n=0,i,s=1,j,k,q,m,sq,zhm,cid;
for(i=0 ,k=0;i<5;i++)
{q=size[i] ;
j=0;
while(1)
{
j++ ;
if((q%2)==0)
{ if(j==1) size[i]+=1;
else
{for(m=1;mq/2;
}
if(k==1) /*将找到的位示图位转换成物理地址*/
{ if((j-1)/8==1)
{zhm=2*i+1;
cid=(j-9)/4;
sq=(j-9)%4;}
else
{zhm=2*i;
cid=(j-1)/4;
sq=(j-1)%4;
}
n=1;
break;/*退出for循环*/
}
}
if(n==0)
printf("没有空间可分配!\n");
else
{printf("分配成功!\n");/*输出物理地址*/
printf("柱面号为: %d\n",zhm);
printf("磁道号为: %d\n",cid);
printf("扇区号为: %d\n",sq);
}
printf("分配后的位示图为:\n");
out();
}

void menu() /*功能选择函数*/
{ int choice;
char judge;
printf("\n请选择操作:(1--分配,2--回收):");
scanf("%d",&choice);
getchar();
if(choice==1)

assign();
else if(choice==2)
callback();
else
printf("\n没有此项!");
printf("\n继续还是退出?(y--继续,n--退出):");
scanf("%c",&judge);
getchar();
if(judge=='y')
menu();
else
{ printf("\n现在的位示图:\n");
out();
printf("\n按任意键退出！\n");
getchar();
}
}
main()
{
printf("\t\t————欢迎进入磁盘空间管理模拟实验———— \n");
printf( " \n");
printf("★★★★08级计算机一 08240128 李彦博★★★★\n");
printf("﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌\n");
out();
menu();
}

Ø 成组链接法：
#include
int MA[4]; /*空闲块数组*/
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}}; /*磁盘空间*/
int mark[9]; /*存放已分配的块*/
int No=0; /*已分配的块数*/
void display1()
{int i,j,temp,count;
No=0;
if(MA[1]!=0)
{i=MA[0];
printf("\ngroup1:");
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("\ngroup%d:",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("\ngroup%d:",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("\nThe blocks are all assigned");
else
{printf("\ngroup1:");
for(j=2;j<=i;j++)
{printf("%d ",MA[j]);
mark[++No]=MA[j];
}
}
}
}
void display() /*显示分组情况*/
{ int i,j;
if(MA[0]!=0)
display1();
else
{i=MA[1];
for(j=0;j<=3;j++)
MA[j]=A[i][j];
display1();
}
}
void assign() /*分配空闲块*/
{int s,i;
if(MA[0]>1) /*若该组不止一个空闲块*/
{ i=MA[0];
s=MA[i];
MA[0]--;
printf("\nnumber of the block:%d",s);
}
else if(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("\nnumber of the block:%d",s);
}
else /*没有其它空闲块组*/
{ printf("\nThere isn't any space");
return;
}
}
else /*当前组已分配完*/
{for(i=0;i<=3;i++)
MA[i]=A[0][i];
assign();
}
display(); /*显示分组情况*/
}
void callback() /*回收空闲块*/
{ int i,j,temp;
printf("\ninput the No. of the block you want to callback:");
scanf("%d",&j);
getchar(); /*得到待回收的空闲块号*/
for(temp=1;temp<=No;temp++)
{ if(mark[temp]==j)
break;
}
if(temp当前组不满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(); /*显示*/
}
void menu() /*功能选择函数*/
{ int choice;
char judge;
printf("\n做出选择:(1--分配,2--回收):");
scanf("%d",&choice);
getchar();
if(choice==1)
assign();
else if(choice==2)
callback();
else
printf("\n错误请求!");
printf("\ncontinue or not (y--Yes,n--Not):");
scanf("%c",&judge);
getchar();
if(judge=='y')
menu();
else
{ printf("\nNow the graph is:");
display();
printf("\npress any key to quit");

}
}
main()
{ int i;
for(i=0;i<=3;i++)
MA[i]=A[0][i];
display();
menu();
}

总 结
经过本次课程设计，完成题目“磁盘空间管理模拟实验”， 熟悉了UNIX/LINUX的常用基本命令，理解并掌握了UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。
做课程设计是为了对平时学习的理论知识与实际操作相结合，在理论和实践上进一步巩固已学基本理论及应用知识并加以综合提高，学会将知识应用于实际的方法，提高分析和解决问题的能力。在做课程设计的过程中，深深感觉到自身所学知识的有限。有些题目书本上没有提及，所以就没有去研究过，做的时候突然间觉得自己真的有点无知，虽然现在去看依然可以解决问题，但还是浪费了许多，这一点是必须在以后的学习中加以改进的地方，同时也要督促自己在学习的过程中不断的完善自我。在设计过程中的思考和讨论，对现有知识能够运用计算机来解决现实生活中的实际问题确立了信心，对模块化程序设计思想有了比较清晰的印象，为今后的程序设计奠定了一定的心理和技术上的准备。
这次课程设计加强了我对计算机操作系统的认识，对我个人而言是对所学课程内容掌握情况的一次自我验证。通过课程设计提高了我对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考，在分析问题、解决问题的过程中，更是获得一种成功的喜悦。

参考文献
1) 汤子瀛，哲凤屏.《计算机操作系统》.西安电子科技大学学出版社.
2) 王清，李光明.《计算机操作系统》.冶金工业出版社.
3) 孙钟秀等. 操作系统教程. 高等教育出版社
4) 曾明.  Linux操作系统应用教程. 陕西科学技术出版社.
5) 张丽芬，刘利雄.《操作系统实验教程》. 清华大学出版社.
6) 孟静， 操作系统教程－－原理和实例分析. 高等教育出版社
7) 周长林，计算机操作系统教程. 高等教育出版社
8) 张尧学，计算机操作系统教程，清华大学出版社
9) 任满杰，操作系统原理实用教程，电子工业出版社

致 谢
完成项目以后，我了解了“团结”、“耐心”、“基础”、“效率”、“沟通”的重要性。在此，我衷心的感谢王旭阳老师对我细心的指导，她在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术；也诚挚感谢我的操作系统刘嘉老师对我的认真教导，她使我了解到了好多关于操作系统方面的知识；最后我要感谢我的同学，在课设过程中，给了我很大的帮助。

28