2022年磁盘存储空间的分配和回收.pdf

《2022年磁盘存储空间的分配和回收.pdf》由会员分享，可在线阅读，更多相关《2022年磁盘存储空间的分配和回收.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、磁盘存储空间的分配与回收实习六磁盘存储空间的分配与回收一、实习内容模拟磁盘空闲空间的表示方法,以及模拟实现磁盘空间的分配与回收。二、实习目的磁盘初始化时把磁盘存储空间分成许多块(扇区 ),这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去,这就涉及到磁盘存储空间的分配与回收。一个文件存放到磁盘上,可以组织成顺序文件(连续文件 )、链接文件(串联文件 )、索引文件等 ,因此 ,磁盘存储空间的分配有两种方式,一种就是分配连续的存储空间,另一种就是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间就是操作系统应解决的一个重要问题,通过本实习使学生掌握

2、磁盘存储空间的分配与回收算法。三、实习题目本实习模拟三种磁盘存储空间的管理方法。第一题 :连续的磁盘存储空间的分配与回收。提示: (1) 要在磁盘上建立顺序文件时,必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时,已把磁盘存储空间划分成若干等长的块(扇区 ),按柱面号与盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、 磁盘存储空间被分成许多区(每一区包含若干块),有的区存放着文件,而有的区就是空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录,当一个文件被删除时,则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分

3、,格式如下 : 序号起 始 空 闲块号空 闲 块 个数状态1 5 6 未分配2 14 3 未分配3 21 30 未分配4 空表目(2) 要建立文件时 ,先查找空闲区表,从状态为“未分配”的登记栏目中找出一个块数能满足要求的区 ,由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时,则剩余的块仍应为未分配的空闲块,这时要修改起始空闲块号与空闲块数。若占用了该区的所有块 ,则相应登记栏中的状态修改成“空表目”。删除一个文件时,从空闲区表中找一个状态为“空表目”的登记栏目,把归还的起始块号与块数填入对应的位置。磁盘存储空间的分配与回收算法类似于主存储器的可变分区方式的分配与回收。同学

4、们可参考实习四的第一题。(3) 当找到空闲块后,必须启动磁盘把信息存放到指定的块中,启动磁盘必须给出由三个参数组成的物理地址:柱面号、磁道号与物理记录号。故必须把找到的空闲块号换算成磁盘的物理地址。为了减少移臂次数,磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面 ,(编号 0-199)每个柱面有20 个磁道 (编号 0-19,同一柱面上的各磁道分布在各盘面上,故磁道号即盘面号。),每个磁道被分成等长的6 个物理记录 (编号 0-5,每个盘面被分成若干个扇区 ,故每个磁道上的物理记录号即为对应的扇区号。)。那么 ,空闲块号与磁盘物理地址的对精品资料 - - - 欢迎下载 -

5、- - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收空闲块号6 M 20 M 20 位数4 位数4 应关系如下 : 假设 M= , m= 则物理记录号= m 磁道号 = 柱面号 = (4) 删除一个文件时,从文件目录表中可得到该文件在磁盘上的起始地址与逻辑记录个数,假定每个逻辑记录占磁盘上的一块,则可推算出归还后的起始空闲块号与块数,登记到空闲区表中。换算关系如下: 起始空闲块号 =(柱面号20+磁道号 ) 6+物理记录号空闲块数 =逻辑记录数(5) 请设计磁

6、盘存储空间的分配与回收程序,要求把分配到的空闲块转换成磁盘物理地址,把归还的磁盘空间转换成空闲块号。假定空闲区表的初值如提示(1)中指出 ,现有一文件要占用10 块,运行您所设计的分配程序,显示或打印分配后的空闲区表以及分配到的磁盘空间的起始物理地址。然后,有一文件被删除 ,它占用的磁盘空间为:1 号柱面 2 号磁道 ,0 号物理记录开始的4 块,运行您所设计的回收程序 ,显示或打印回收后的空闲区表。第二题 :用位示图管理磁盘存储空间提示: (1) 为了提高磁盘存储空间的利用率,可在磁盘上组织成链接文件、索引文件,这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用,哪些

7、磁盘空间就是空闲的 ,可用位示图来指出。位示图由若干字节构成,每一位与磁盘上的一块对应,“1”状态表示相应块已占用,“0”状态表示该块为空闲。位示图的形式与实习四中的位示图一样,但要注意 ,对于主存储空间与磁盘存储空间应该用不同的位示图来管理,绝不可混用。(2) 申请一块磁盘空间时,由分配程序查位示图,找出一个为 “0”的位 ,计算出这一位对应块的磁盘物理地址,且把该位置成占用状态“1”。假设现在有一个盘组共80 个柱面 ,每个柱面有两个磁道 ,每个磁道分成4 个物理记录。 那么 ,当在位示图中找到某一字节的某一位为“ 0”时,这个空闲块对应的磁盘物理地址为: 柱面号 =字节号磁道号 = 物理

8、记录号 = (3) 归还一块磁盘空间时,由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位 ,把该位置成“ 0”。按照 (2)中假设的盘组 ,归还块在位示图中的位置计算如下: 字节号 =柱面号位数 =磁道号4+物理记录号(4) 设计申请一块磁盘空间与归还一块磁盘空间的程序。要求能显示或打印程序运行前与运行后的位示图;分配时把分配到的磁盘空间的物理地址显示或打印出来,归还时把归还块对应于位示图的字节号与位数显示或打印出来。(5) 假定已有如表6-1 的磁盘空间被占用了,现在要申请五块磁盘空间,运行分配程序,按(4)中要求显示或打印运行的结果。然后再归还如表6-2 的空间 ,运行回收程

9、序,按(4)中的要求显示或打印运行结果。表 6-1 柱面号磁道号物理记录号空闲块号6 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收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

10、块可供使用。 UNIX系统中采用空闲块成组链接的方法来管理磁盘存储空间,将磁盘中的每N 个空闲块 (NM) 分成一组 ,最后一组可以不足N 块,每组的第一块中登记了下一组空闲块的块数与块号,第一组的块数与块号登记在专用块中,登记的格式如下: 0 空闲块数 k 1 空闲块号 1 2 空闲块号 2 K 空闲块号 k 当第一项内容为“0”时 ,则第二项起指出的空闲块就是最后一组。(2) 现模拟 UNIX 系统的空闲块成组链接,假定共有8 块可供使用 ,每 3 块为一组 ,则空闲块成组链接的初始状态为: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 -

11、 - - - - - - - - -第 3 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收开始时 ,空闲块号就是顺序排列的,但经若干次的分配与归还操作后,空闲块的链接就未必按序排列了。用二维数组A:array 0M-1 of array 0n-1 来模拟管理磁盘空间,用 Ai 表示第 I 块,第 0 块 A0 作为专用块。(3) 成组链接的分组情况记录在磁盘物理块中,为了查找链接情况,必须把它们读入主存,故当磁盘初始化后,系统先将专用块内容复制到主存中。定义一个数组MA 存放专用块内容,即 MA: =A0。申请一块磁盘空间时,查 MA, 从中找出空闲块号,当

12、一组的空闲块只剩第一块时,则应把该块中指出的下一组的空闲块数与块号复制到专用块中,然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容(下一组链接情况)复制到主存 ,再为申请者分配。分配算法如图6-1。图 6-1 采用成组链接的分配算法精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收(4) 归还一块时给出归还的块号,叵当前组不满规定块数时,将归还块登记入该组;若当前组已满 ,则另建一新组 ,这时归还块作为新一组的

13、第一块,应把主存中登记的一组链接情况MA复制到归还块中,然后在 MA 重新登记一个新组。归还一块的算法如图6-2。图 6-2 采用成组链接的回收算法(5) 设计分配与归还磁盘空间的程序,能显示或打印分配的磁盘空间的块号,在完成一次分配或归还后能显示或打印各空闲块组的情况(各组的空闲块数与块号)。本实习省去了块号与物理地址之间的转换工作,而在实际的系统中必须进行块号与物理地址的转换工作。(6) 运行您所设计的程序,假定空闲块链接的初始状态如提示(2),现先分配4 块,再依次归还第 2 块与第 6 块。把执行后分配到的块号依次显示或打印出来,且显示或打印空闲块组的情况。在上次执行的基础上继续分配3

14、 块,然后归还第1 块,再申请 5 块,显示或打印依次分配到的块号及空闲块组情况。四、相关数据结构及说明struct freeblock int FBbegin;/ 起始空闲块号int num;/ 空闲块数char state;/状态struct freeblock *next; struct char name10;/ 文件名 int size;/ 文件大小 int addr_cylinder;/ 装入磁盘的首地址_柱面号 int addr_track;/ 装入磁盘的首地址_磁道号int addr_note;/ 装入磁盘的首地址_物理记录号struct *next; 六、源代码及注释1、题一

15、源代码 : #include #include int getmalloc()/ 分配磁盘空间 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收 int flag=0; struct freeblock *p=FBhead; struct *File; File=(struct *)malloc(sizeof(struct ); printf( 输入要装入的文件名:); scanf(%s,File-name); prin

16、tf( 输入所需的磁盘空间大小:); scanf(%d,&File-size); for(p=FBhead-next;p!=NULL;p=p-next) if(File-size)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)num)/修改该快的起始地址与块数 p-FBbegin=p-FBbegin+File

17、-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( %dt %dt %dn,File-addr_cylinder,File-addr_track,File-addr_note); int deletelfree()/ 回收磁盘空间 char name10; int flag=0; struct *p; printf( 输入要删除

18、的文件名:); 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;

19、 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; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收

20、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(f

21、union=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-

22、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( %dt %dtt %dtt未分配 n,i+,p-FBbegin,p-num); el

23、se 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收 printf( %dttttt空表目 n,i+); int dispfile() char name10; struct *p=; printf( 输入要查瞧的文件名:); scanf(%s,&name); for(p=next;p!=NULL;p=p-next) if(strcmp(p-name,name)=0) printf( 该文件的物理地址:n 柱面号 t

24、磁道号 t 物理块号 n ); printf( %dt %dt %dn,p-addr_cylinder,p-addr_track,p-addr_note); break; if(p=NULL) printf( 没有该文件 !n); int main() int n,i,AMAX,BMAX;/AMAX表示起始空闲块号,BMAX 表示空闲块个数char ch; struct freeblock *pnew; FBhead=(struct freeblock *)malloc(sizeof(struct freeblock); FBhead-next=NULL; printf( 输入磁盘空闲区个数:

25、); scanf(%d,&n); for(i=1;inext=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(ntt * 主菜单 *nn); printf(ttt1 、新建文件 n); prin

26、tf(ttt2 、删除文件 n); printf(ttt3 、查瞧磁盘 n); printf(ttt4 、查瞧文件 n); printf(ttt5 、退出 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);b

27、reak; default:printf( 输入错误 !请重新输入、n); printf(n); getchar(); while(ch!=4); return 0; 2、题二源代码: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收#include #include void Initbitmap(int map88) int cylinder,track,sector; char choice=Y; printf(

28、初始化位视图、n); while(choice=y|choice=Y) printf( 柱面号 :); scanf(%d,&cylinder); printf( 磁道号 :); scanf(%d,&track); printf( 物理记录号 :); scanf(%d,§or); mapcylinder4*track+sector=1; printf(contiune?); getchar(); scanf(%c,&choice); void allocate(int map88) int i,j; int flag=0; int cylinder,track,sector; for(i

29、=0;i8;i+) for(j=0;j8;j+) if(mapij=0) mapij=1; flag=1; break; if(flag=1) break; if(flag=1) cylinder=i; track=j/4; sector=j%4; printf( 分配到的柱面号、磁道号、物理记录数); printf(%dt%dt%d,cylinder,track,sector); printf(n); else printf( 空间不足 ,分配失败 !); void reclaim(int map88) int cylinder,track,sector; printf( 柱面号 :); s

30、canf(%d,&cylinder); printf( 磁道号 :); scanf(%d,&track); printf( 物理记录号 :); scanf(%d,§or); if(mapcylinder4*track+sector=0) printf( 此块为未分配块！回收出错！); getchar(); else mapcylinder4*track+sector=0; printf( 回收块对应的字节号:%4dt 位数 :%4dn,cylinder,4*track+sector); void main() int bitmap88; int i,j; int choice; or(

31、i=0;i8;i+) for(j=0;j8;j+) bitmapij=0; Initbitmap(bitmap); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收while(1) printf(n 请输入选择 :); printf(1- 分配 ,2-回收 ,3-显示位示图 ,0-退出 n); scanf(%d,&choice); switch(choice) case 1:allocate(bitmap);break;

32、 case 2:reclaim(bitmap);break; case 3:for(i=0;i8;i+) for(j=0;j8;j+) printf(%8d,bitmapij); printf(n); break; case 0:exit(0); default:printf( 错误选择！ );break; 3、第三题源程序: #include int MA4; /*空闲块数组 */ int A94=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 mark9; /*存

33、放已分配的块*/ int No=0; /* 已分配的块数*/ void display1() int i,j,temp,count, No=0; if(MA1!=0) i=MA0; printf(ngroup1:); for(j=1;j=i;j+) printf(%d ,MAj); mark+No=MAj; temp=MA1; count=2; while(Atemp1!=0) printf(ngroup%d:,count); i=Atemp0; for(j=1;j=i;j+) printf(%d ,Atempj); mark+No=Atempj; count+; temp=Atemp1; p

34、rintf(ngroup%d:,count); i=Atemp0; for(j=2;j0) printf(%d ,Atempj); mark+No=Atempj; else i=MA0; if(i=1) printf(nThe blocks are all assigned); else printf(ngroup1:); for(j=2;j=i;j+) printf(%d ,MAj); mark+No=MAj; void display() /*显示分组情况*/ int i,j; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - -

35、- - - - - -第 10 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收if(MA0!=0) display1(); else i=MA1; for(j=0;j1) /*若该组不止一个空闲块*/ i=MA0; s=MAi; MA0-; printf(nnumber of the block:%d,s); else if(MA0=1) /*只剩一个空闲块*/ if(MA1!=0) /*还有其它空闲块组*/ s=MA1; for(i=0;i=3;i+) A0i=Asi; MA0-; printf(nnumber of the block:%d,s); el

36、se /*没有其它空闲块组*/ printf(nThere isnt any space); return; else /*当前组已分配完*/ for(i=0;i=3;i+) MAi=A0i; 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(m

37、arktemp=j) break; if(tempNo+1) /*若该空闲块已在,退出 */ printf(nThe block is in the disk); return; if(MA03) /*当前组不满3 块 */ i=MA0; MAi+1=j; MA0+; else /*已有 3 块*/ for(i=0;i=3;i+) Aji=MAi; MA0=1; MA1=j; display(); /* 显示 */ void menu() /*功能选择函数*/ int choice; char judge; printf(ninput your choice:(1-assign,2-callb

38、ack):); scanf(%d,&choice); getchar(); if(choice=1) assign(); else if(choice=2) callback(); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收else printf(ninvalid command!); printf(ncontinue or not (y-Yes,n-Not):); scanf(%c,&judge); getch

39、ar(); if(judge=y) menu(); else printf(nNow the graph is:); display(); printf(npress any key to quit); getchar(); int main() int i; for(i=0;i=3;i+) MAi=A0i; display(); menu(); 七、运行结果1、题一运行结果: 2、题二运行结果: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收3、题三运行结果: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 14 页 - - - - - - - - - - 磁盘存储空间的分配与回收精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 14 页 - - - - - - - - - -