第9章 磁盘存储器管理(2)

计算机操作系统 汤子瀛教材的课件

§9.2 外存分配方法(5)

§9.2 外存分配方法

9.2.3 索引分配混合分配方式混合分配方式，是指将多种分配方式相结合而形成的一种分配方式。 例如，系统既采用直接地址，又采用了一级索引或两级索引，甚至是三级 索引分配方式。UNIX系统中采用的混合分配方式：把所有的地址项分成 两类，即直接地址和间接地址。 直接地址：在索引结点中设臵10个直接地址项iaddr(0)~iaddr(9)来存放 直接地址(存放文件的盘块的盘块号),以提高文件的检索速度。 一次间接地址：利用索引结点中的地址项iaddr(10)来提供一次间接地 址(索引块地址)。 多次间接地址：用地址项iaddr(11)提供二次间接地址(记录所有一次间 址块的盘块号的二次间址块地址);用地址项iaddr(12)提供三次间接地址 (记录所有二次间址块的盘块号的三次间址块地址)。

计算机操作系统 汤子瀛教材的课件

§9.3 空闲存储空间的管理(1)

§9.3 空闲存储

空间的管理

为了实现存储空间的分配，首先必须记住空闲存 储空间的情况。为此需要： 系统应为分配存储空间而设臵相应的数据结构； 系统应提供对存储空间进行分配和回收的功能。

下面是几种常用的文件存储空间管理方法： 空闲表法； 空闲链表法； 位示图法； 成组链接法。

计算机操作系统 汤子瀛教材的课件

§9.3 空闲存储空间的管理(2)

§9.3 空闲存储空间的管理

9.3.1 空闲表法空闲表法属于连续分配方式。它与内存管理中的动态分区分配方式 雷同，为每个文件分配一个连续的存储空间。系统为外存上的所有空闲区 建立一张空闲表，每个空闲区对应于一个空闲表项。空闲表中包括：序号、 该空闲区的第一个盘块号、该区的空闲盘块数等信息。应将所有空闲区按 其起始盘块号递增的次序排列，形成空闲盘块表。 空闲盘区的分配同样可采取首次适应算法、循环首次适应算法、最 佳适应算法及最坏适应算法等算法。经验证明，首次适应算法和最佳适应 算法，对存储空间的利用率大体上相当，而首次适应算法更快；它们在存 储在间的利用求问分队速度上，都优于最坏适应算法。系统在为某个新创 建的文件分配它闲盘区时，应顺序检索交闲表的各个表项，直至找到第一 个其大小能满足要求的空闲盘区。将该区分配该用户，同时修改空闲表。 系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方 法。 应该说明，在内存分配上，虽然很少采用连续分配方式；然而在外存 管理上，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它 在诸多分配方式中仍占一席之地。当文件较小时，便采用连续分配方法为 文件分配相邻接的几个盘块；当文件较大时，便采用索引分配方式。在前 面所介绍的对换方式中，对换空间一般都采用连续分配方式。

计算机操作系统 汤子瀛教材的课件

§9.3 空闲存储空间的管理(3)

§9.3 空闲存储空间的管理

9.3.2 空闲链表法空闲链表法是将所有的空闲盘区拉成一条空闲链。根据构成链的基本 元素的不同。可有两种链表形式： 空闲盘块链：它是将磁盘上的所有空闲存储空间，以盘块为基本元素 拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始， 依次摘下适当数目的空闲盘块分配给用户；当用户因删除文件而释放存储 空间时，系统将回收的盘块，依次链入空闲盘块链的尾部。

空闲盘区链：这是将磁盘上的所有空闲盘区(每个盘区可包含若干个

– 优点是用于分配和回收一个盘块的过程非常简单； – 缺点是空闲盘块链可能很长。

盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指

针 外，还应标有指明本盘区大小(盘块数)的信息。盘区的分配方法与内存 的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要 将与回收区邻接的空闲盘区与之合并。在采用首次适应算法时，为了提高 对空闲盘区的检索速度，可以采用显式链接方式，即在内存中为空闲盘区 建立一张链表。

– 优点是分配和回收过程较复杂； – 缺点是但空闲盘区链较短。

计算机操作系统 汤子瀛教材的课件

§9.3 空闲存储空间的管理(4)

§9.3 空闲存储空间的管理

9.3.3 位示图法

位示图：利用二进制的一位来表示磁盘中一个盘块的使用情况。当其

值为“0”时，表尔对应的盘块空闲；为“1”时表示已分配，磁盘上的所有 盘块都由一个二进制位与之对应。这样，由所有盘块所对应的位构成一个 集合，称为位示图。通常可用m×n个位数来构成位示图，也可描述为一 个二维数组——Var map:array[1…m, 1…n] of bit 。 盘块的分配：根据位示图进行盘块分配时，可分三步进行： 顺序扫描位示图，从中找出一个或一组其值均为“0”的二进制位； 将所找到的二进制位，转换成与之相应的盘块号。如找到的二进 制位位于位示图的第i 行、第j 例，则其相应的盘块号为：b=n*(i-1)+j; 修改位示图，今array[i, j]=1 。 盘块的回收：可分两步： 将回收盘块的盘块号转换成位于图中的行号和列号。转换公式为： i=(b-1)/n+1 ,j=mod[(b-1), n]+1 ; 修改位示图，今array[i, j]=0 。 这种方法的主要优点，是从位示图中很容易找到一个或一组相邻接的 空闲盘块。此外，由了位示图很小，占用空间少，因而可将它保存在内存 中，从而在每次进行盘区分配时，无需首先把磁盘分配表读入内存，从而 省掉许多磁盘的启动操作。

– – – – –

计算机操作系统 汤子瀛教材的课件

§9.3 空闲存储空间的管理(5)

§9.3 空闲存储空间的管理

9.3.4 成组链接法空闲表法和空闲链法，都不适合用在大型文件系统中，因为这会使空 闲表或空闲链太长。在UNIX系统中采用的成组链接法是上述两种方法相 结合而形成的一种空闲盘块管理方法，它兼备了两种方法的优点丽克服了 两种方法均有的、表太长的缺点。

空闲盘块的组织

空闲盘块号栈：它被用来存放当前可用的一组空闲盘块的盘块号(最

多100个号),以及栈中尚有的空闲盘块号数N。N还可兼作栈顶指针用。 栈是临界资源，每次只允许一个进程访问，故系统为该栈设臵了一把锁。 文件区中的所有空闲盘块，被分成若干个组，如每100个盘块作为一组。 将每一组含有的盘块总数N 和该组所有的盘块号，记入其前一组的第 一个盘块的中。这样，由各组的第一个盘块可链成一条链。 将

第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当 前可供分配的空闲盘块(号)。 最末一组只有99个盘块，其盘块号分别记入其前一组第一个盘块的 S.free(1)~S.free(99)中，而在S.free(0)中存放“0”,作为空闲盘块链的结 束标志。

计算机操作系统 汤子瀛教材的课件

§9.3 空闲存储空间的管理(6)

§9.3 空闲存储空间的管理

9.3.4 成组链接法空闲盘块的分配与回收

分配过程：当系统要为用户分配文件所需的盘块时，需调用盘块分 配过程来完成。该过程首先检查空闲盘块号是否上锁。如未上锁，便从栈顶取出一空闲盘块号，将其对应的盘块分配给用户；然后将栈顶指针下移 一格，亦即做空闲盘块号数N的减1操作。若该盘块号已是栈底，即 S.free(0),这是栈中最后一个可分配的盘块号。由于在该盘块号所对应的 盘块中，记 …… 此处隐藏：2327字，全部文档内容请下载后查看。喜欢就下载吧 ……