操作系统实验6-磁盘存储空间管理精编版.doc

操作系统实验6_磁盘存储空间管理

实验五 磁盘存储空间管理

一、实验内容
模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。
二、实验目的
磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实验使学生掌握磁盘存储空间的分配和回收算法。
三、实验题目
本实验模拟三种磁盘存储空间的管理方法。
第一题：连续的磁盘存储空间的分配和回收。
[提示]：
(1) 要在磁盘上建立顺序文件时，必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时，已把磁盘存储空间划分成若干等长的块（扇区），按柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有的区存放着文件，而有的区是空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时，则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分，格式如下：

序 号
起始空闲块号
空闲块个数
状 态
1
5
6
未 分 配
2
14
3
未 分 配
3
21
30
未 分 配
4

空 表 目
M
M

M
M

M
M

M
M

(2) 要建立文件时，先查找空闲区表，从状态为“未分配”的登记栏目中找出一个块数能满足要求的区，由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时，则剩余的块仍应为未分配的空闲块，这时要修改起始空闲块号和空闲块数。若占用了该区的所有块，则相应登记栏中的状态修改成“空表目”。删除一个文件时，从空闲区表中找一个状态为“空表目”的登记栏目，把归还的起始块号和块数填入对应的位置。
磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。同学们可参考实验四的第一题。
(3) 当找到空闲块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三个参数组成的物理地址：柱面号、磁道号和物理记录号。故必须把找到的空闲块号换算成磁盘的物理地址。
为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面，（编号0-199）每个柱面有20个磁道（编号0-19，同一柱面上的各磁道分布在各盘面上，故磁道号即盘面号。），每个磁道被分成等长的6个物理记录（编号0-5，每个盘面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号。）。那么，空闲块号与磁盘物理地址的对应关系如下：
空闲块号
6

空闲块号
6

假设M= ， m= { }

M
20

则 物理记录号 = m
磁道号={ }
M
20

柱面号=[ ]

(4) 删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑记录占磁盘上的一块，则可推算出归还后的起始空闲块号和块数，登记到空闲区表中。换算关系如下：
起始空闲块号=（柱面号´20+磁道号）´6+物理记录号
空闲块数=逻辑记录数
(5) 请设计磁盘存储空间的分配和回收程序，要求把分配到的空闲块转换成磁盘物理地址，把归还的磁盘空间转换成空闲块号。
假定空闲区表的初值如提示（1）中指出，现有一文件要占用10块，运行你所设计的分配程序，显示或打印分配后的空闲区表以及分配到的磁盘空间的起始物理地址。然后，有一文件被删除，它占用的磁盘空间为：1号柱面2号磁道，0号物理记录开始的4块，运行你所设计的回收程序，显示或打印回收后的空闲区表。
第二题：用位示图管理磁盘存储空间
[提示]：
(1) 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。位示图的形式与实验四中的位示图一样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。
(2) 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共80个柱面，每个柱面有两个磁道，每个磁道分成4个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：

柱面号=字节号
位数
4

磁道号=[ ]
位数
4

物理记录号={ }

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

表6-1
柱面号
磁道号
物理记录号
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块可供使用。UNIX系统中采用空闲块成组链接的方法 来管理磁盘存储空间，将磁盘中的每N个空闲块（N<M）分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第一组的块数和块号登记在专用块中，登记的格式如下：

0
空闲块数k
1
空闲块号1
2
空闲块号2
M
M
M
M
K
空闲块号k
M
M
M
M

当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。
(2) 现模拟UNIX系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲块成组链接的初始状态为：

开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。
用二维数组A：array [0…M-1] of array [0…n-1]来模拟管理磁盘空间，用A[i]表示第I块，第0块A[0]作为专用块。
(3) 成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即MA: =A[0]。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再为申请者分配。分配算法如图6-1。
图6-1 采用成组链接的分配算法
(4) 归还一块时给出归还的块号，叵当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在MA重新登记一个新组。归还一块的算法如图6-2。
图6-2 采用成组链接的回收算法

(5) 设计分配和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一次分配或归还后能显示或打印各空闲块组的情况（各组的空闲块数和块号）。本实验省去了块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。
(6) 运行你所设计的程序，假定空闲块链接的初始状态如提示（2），现先分配4块，再依次归还第2块和第6块。把执行后分配到的块号依次显示或打印出来，且显示或打印空闲块组的情况。
在上次执行的基础上继续分配3块，然后归还第1块，再申请5块，显示或打印依次分配到的块号及空闲块组情况。
四、实验报告
(1) 实验题目。
(2) 程序中使用的数据结构及符号说明。
(3) 流程图。
(4) 打印一份源程序并附上注释。
(5) 按照各题中给出的初值，把程序运行的结果按各题要求打印出来。为了检测程序的正确性，可自己再假设一组初值，运行设计的程序，检查运行结果。

several group number, then with b ± a, =c,c is is methyl b two vertical box between of accurate size. Per-2~3 measurement, such as proceeds of c values are equal and equal to the design value, then the vertical installation accurate. For example a, b, and c valueswhile on horizontal vertical errors for measurement, General in iron angle code bit at measurement level points grid errors, specific method is from baseline to methyl vertical box center line distance for a,, to b vertical box distance for b, list can measured11