实习六 磁盘存储空间得分配与回收
一、实习内容
模拟磁盘空闲空间得表示方法,以及模拟实现磁盘空间得分配与回收、 二、实习目得
磁盘初始化时把磁盘存储空间分成许多块(扇区),这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上得文件删去,这就涉及到磁盘存储空间得分配与回收、一个文件存放到磁盘上,可以组织成顺序文件(连续文件)、链接文件(串联文件)、索引文件等,因此,磁盘存储空间得分配有两种方式,一种就是分配连续得存储空间,另一种就是可以分配不连续得存储空间、怎样有效地管理磁盘存储空间就是操作系统应解决得一个重要问题,通过本实习使学生掌握磁盘存储空间得分配与回收算法。
三、实习题目
本实习模拟三种磁盘存储空间得管理方法。 第一题:连续得磁盘存储空间得分配与回收。 ［提示]:
(1) 要在磁盘上建立顺序文件时,必须把按序排列得逻辑记录依次存放在磁盘得连续存储空间中。可假定磁盘初始化时,已把磁盘存储空间划分成若干等长得块(扇区),按柱面号与盘面号得顺序给每一块确定一个编号、随着文件得建立、删除、磁盘存储空间被分成许多区(每一区包含若干块),有得区存放着文件,而有得区就是空闲得。当要建立顺序文件时必须找到一个合适得空闲区来存放文件记录,当一个文件被删除时,则该文件占用得区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用得部分,格式如下:
序 起始空闲空闲块个状 号 块号 数 态 1 5 6 未 分 配 2 14 ３ 未 分 配 3 30 ２１ 未 分 配 4 空 表 目 Ｍ ? ? ? ? ? ? ?
(2) 要建立文件时,先查找空闲区表,从状态为“未分配”得登记栏目中找出一个块数能满足要求得区,由起始空闲块号能依次推得可使用得其它块号、若不需要占用该区得所有块时,则剩余得块仍应为未分配得空闲块,这时要修改起始空闲块号与空闲块数、若占用了该区得所有块,则相应登记栏中得状态修改成“空表目”。删除一个文件时,从空闲区表中找一个状态为“空表目”得登记栏目,把归还得起始块号与块数填入对应得位置。
磁盘存储空间得分配与回收算法类似于主存储器得可变分区方式得分配与回收。同学们可参考实习四得第一题。
(3) 当找到空闲块后,必须启动磁盘把信息存放到指定得块中,启动磁盘必须给出由三个参数组成得物理地址:柱面号、磁道号与物理记录号。故必须把找到得空闲块号换算成磁盘得物理地址。
为了减少移臂次数,磁盘上得信息按柱面上各磁道顺序存放。现假定一个盘组共有２00个柱面,(编号0—199)每个柱面有２0个磁道(编号０—19,同一柱面上得各磁道分布在各盘面上,故磁道号即盘面号、),每个磁道被分成等长得6个物理记录(编号0—5,每个盘面被分成若干个扇区,故每个磁道上得物理记录号即为对应得扇区号。)。那么,空闲块号与磁盘物理地址
得对应关系如下:
假设M= 空闲块号 , 空闲块号m＝ ｛ }
6 6
则 物理记录号 = m M 磁道号=｛ } 20
M ］ 柱面号＝［20
(4) 删除一个文件时,从文件目录表中可得到该文件在磁盘上得起始地址与逻辑记录个 数,假定每个逻辑记录占磁盘上得一块,则可推算出归还后得起始空闲块号与块数,登记到空闲区表中。换算关系如下:
起始空闲块号=(柱面号?20+磁道号)?6+物理记录号 空闲块数=逻辑记录数
(5) 请设计磁盘存储空间得分配与回收程序,要求把分配到得空闲块转换成磁盘物理地址,把归还得磁盘空间转换成空闲块号、
假定空闲区表得初值如提示(1)中指出,现有一文件要占用1０块,运行您所设计得分配程序,显示或打印分配后得空闲区表以及分配到得磁盘空间得起始物理地址。然后,有一文件被删除,它占用得磁盘空间为:１号柱面2号磁道,0号物理记录开始得４块,运行您所设计得回收程序,显示或打印回收后得空闲区表。
第二题:用位示图管理磁盘存储空间 ［提示］:
(1) 为了提高磁盘存储空间得利用率,可在磁盘上组织成链接文件、索引文件,这类文件可以把逻辑记录存放在不连续得存储空间、为了表示哪些磁盘空间已被占用,哪些磁盘空间就是空闲得,可用位示图来指出。位示图由若干字节构成,每一位与磁盘上得一块对应,“１\状态表示相应块已占用,“0\状态表示该块为空闲。位示图得形式与实习四中得位示图一样,但要注意,对于主存储空间与磁盘存储空间应该用不同得位示图来管理,绝不可混用、
(2) 申请一块磁盘空间时,由分配程序查位示图,找出一个为“0”得位,计算出这一位对应块得磁盘物理地址,且把该位置成占用状态“1”。假设现在有一个盘组共80个柱面,每个柱面有两个磁道,每个磁道分成4个物理记录、那么,当在位示图中找到某一字节得某一位为“0”时,这个空闲块对应得磁盘物理地址为:
柱面号=字节号
位数 ] 磁道号=［ 4
物理记录号＝｛ } 位数4
(3) 归还一块磁盘空间时,由回收程序根据归还得磁盘物理地址计算出归还块在位示图 中得对应位,把该位置成“0\。按照(2)中假设得盘组,归还块在位示图中得位置计算如下:
字节号＝柱面号
位数=磁道号?4＋物理记录号
(4) 设计申请一块磁盘空间与归还一块磁盘空间得程序。要求能显示或打印程序运行前与运行后得位示图;分配时把分配到得磁盘空间得物理地址显示或打印出来,归还时把归还块对应于位示图得字节号与位数显示或打印出来。
(５) 假定已有如表6-1得磁盘空间被占用了,现在要申请五块磁盘空间,运行分配程序,按(4)中要求显示或打印运行得结果。然后再归还如表６-２得空间,运行回收程序,按(4)中得要求显示或打印运行结果。
表6－1
柱面磁道物理记录号 号 号 0 0 0 0 1 1
表6—2
柱面号 0 0 １ 号 0 0 1 1 0 1 1 2 0 3 0 ２ 磁道０ 1 0 物理记录号 ２ ０ 1
第三题:模拟UNIX系统得空闲块成组链接法,实现磁盘存储空间得管理。 ［提示]:
(1) 假定磁盘存储空间已被划分成长度为n得等长块,共有Ｍ块可供使用。ＵＮIＸ系统中采用空闲块成组链接得方法 来管理磁盘存储空间,将磁盘中得每N个空闲块(N〈M)分成一组,最后一组可以不足N块,每组得第一块中登记了下一组空闲块得块数与块号,第一组得块数与块号登记在专用块中,登记得格式如下:
０ 空闲块数k 1 空闲块号1 ２ 空闲块号2 ? ? ? K ? ?
? 空闲块号k ? ?
当第一项内容为“0\时,则第二项起指出得空闲块就是最后一组。
(2) 现模拟UＮIＸ系统得空闲块成组链接,假定共有8块可供使用,每3块为一组,则空闲块成组链接得初始状态为:
开始时,空闲块号就是顺序排列得,但经若干次得分配与归还操作后,空闲块得链接就未必按序排列了、
用二维数组Ａ:aｒray [0…M-1] oｆ ａrrａy ［0…n－1]来模拟管理磁盘空间,用Ａ[i]
表示第I块,第０块A［0］作为专用块。
(３) 成组链接得分组情况记录在磁盘物理块中,为了查找链接情况,必须把它们读入主存,故当磁盘初始化后,系统先将专用块内容复制到主存中。定义一个数组MＡ存放专用块内容,即ＭA: =Ａ［0］。申请一块磁盘空间时,查MA,从中找出空闲块号,当一组得空闲块只剩第一块时,则应把该块中指出得下一组得空闲块数与块号复制到专用块中,然后把该块分配给申请者。当一组得空闲块分配完后则把专用块内容(下一组链接情况)复制到主存,再为申请者分配。分配算法如图6—1、
图6-1 采用成组链接得分配算法
(4) 归还一块时给出归还得块号,叵当前组不满规定块数时,将归还块登记入该组;若当前组已满,则另建一新组,这时归还块作为新一组得第一块,应把主存中登记得一组链接情况MA复制到归还块中,然后在MA重新登记一个新组、归还一块得算法如图6—2、
图6－2 采用成组链接得回收算法
(５) 设计分配与归还磁盘空间得程序,能显示或打印分配得磁盘空间得块号,在完成一次分配或归还后能显示或打印各空闲块组得情况(各组得空闲块数与块号)。本实习省去了块号与物理地址之间得转换工作,而在实际得系统中必须进行块号与物理地址得转换工作、
(6) 运行您所设计得程序,假定空闲块链接得初始状态如提示(2),现先分配４块,再依次归还第2块与第6块。把执行后分配到得块号依次显示或打印出来,且显示或打印空闲块组得情况。
在上次执行得基础上继续分配3块,然后归还第1块,再申请5块,显示或打印依次分配到得块号及空闲块组情况、
四、相关数据结构及说明 stｒuct freeblock ｛
ｉｎｔ ＦＢbｅｇin;/／起始空闲块号 ｉnｔ num;//空闲块数 chａr stａte;//状态 struct frｅｅblｏck ＊ｎｅxt; ｝ ｓtｒuct ｛
chａr nａme[10］;／／文件名 int sizｅ;/／文件大小
int adｄr_cｙｌinder;/／装入磁盘得首地址_柱面号 ｉnｔ ａdｄr＿track;//装入磁盘得首地址_磁道号 inｔ ａdｄr_note;//装入磁盘得首地址_物理记录号 sｔｒｕｃt *nexｔ; ｝ 六、源代码及注释 1、题一源代码:
＃iｎcludｅ<ｓｔdlib.h> #include〈stｄio.h>
磁盘存储空间的分配和回收
