磁盘存储器的管理

外存的组织方式

• 磁盘的物理地址(盘块号)是(柱面号,盘面号,扇区号)

• 磁盘存储器中用t表示每个柱面上的磁道数(盘面数),

• 用s表示每个磁道.上的扇区数,

• 根据块号可以确定该块在磁盘上的位置

  • 每个柱面.上有: sxt个磁盘块

  • 计算第p块在磁盘上的位置,可以令d=sxt,则有:

  • i柱面(磁道)号=[p/d]

  • j盘面号=[(p mod d)/s]

  • k扇区号=(pmodd)mods

• 文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有:

  • 顺序组织方式:早期文件系统使用，现今仅在磁盘文件对换区的使用上还能看到 其影子。

    • 连续分配方式要求每个文件在磁盘上占有一-组连续的块。

    • (逻辑块号,块内地址) →(物理块号,块内地址)。只需转换块号就行,块内地址保持不变

    • 优点:

      • 顺序访问容易,支持定长记录文件随机存取;

      • 顺序访问速度快。

    • 缺点:

      • 要求为一个文件分配连续的存储空间，产生外部碎片。

      • 必须事先知道文件的长度。

      • 不能灵活地删除和插入记录。

      • 文件的动态增长困难。

  • 链接组织方式:分为隐式链接和显式链接两类。FAT12、 FAT16、FAT32文件系统使用的就是显式链接方式

    • 采用链接分配方式时，可通过在每个盘块.上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表， 把这样形成的文件称为链接文件。

    • 链接组织方式的主要优点:

      • 消除了磁盘的外部碎片，提高了外存的利用率。

      • 对插入、删除和修改记录都非常容易。

      • 能适应文件的动态增长，无需事先知道文件的大小。

    • 链接方式又可分为两种形式:

      • 隐式链接

        • 隐式链接分配方式的主要问题:

          • 它只适合于顺序访问，对随机访问是及其低效的

          • 可靠性差

        • 为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。在进行盘块分配时，是以簇为单位进行的。同样,链接文件也是以簇为单位的。

      • 显式链接

        • 把用于链接文件各物理块的指针显式地存放在一-张表中。 即文件分配表(FATFile Allocation Table)

        • 注意:一个磁盘仅设置一张FAT

        • 开机时,将FAT读入内存，并常驻内存

        • 逻辑块号转换成物理块号的过程不需要读磁盘操作

        • 文件分配表可同时管理磁盘的空闲盘块

    • FAT技术

      • FAT12:每个FAT表项为12位,

        • 每个FAT表最多允许4096 (212) 个表项，如果每个盘块大小为512 (29)B,则每个磁盘分区容量最大为2MB。

        • 以簇为分配的基本单位，如果一簇包含8个扇区， 则每个磁盘分区容量为1 6MB,但是簇内碎片也会增加。

      • FAT16:每个FAT表项为1 6位

        • 最大表项数增值65536 (216) 个，每个簇中有最多有64个扇区，最大分区空间为216x64x 512=2048MB

      • FAT32

        • 最大支持磁盘分区为2TB

    • 链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题:

      • 不能支持高效的直接存取。要对一个文件进行直接存取，需首先在FAT中顺序的查找许多盘块号。

      • FAT需占用较大的内存空间。当磁盘容量较大时，FAT可能要占用数MB以上的内存空间。这是令人难以忍受的。

  • 索引组织方式: ext2、ext3、 ext4等UNIX文件系统采用该方式。

    • 单级索引

      • 索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表

      • 索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表)。

      • 索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

      • 优点:

        • 能顺序存取,又能直接存取

        • 满足了文件动态增长、插入删除的要求

        • 没有外碎片，外存空间利用率较高

      • 缺点

        • 索引表本身需要存储空间

        • 文件比较小时，索引表利用率低

    • 多级索引

      • 将一个大文件的所有索引表(二级索引)的地址放在另一个索引表(一级索引)中(原理类似于多级页表)。如果文件非常大，还可用三级、四级。

      • 访问目标数据块,需要多次磁盘I/O

      • 对与中小文件，访问磁盘次数过多

    • 增量式索引

      • 多种索引分配方式的结合。例如，一个文件的索引结点中,既包含直接地址(直接指向数据块),又包含一次间接地址(指向单层索引表)、还包含多次间接地址(指向两层索引表)

      • 在UNIX System V的索引结点中设有13个地址项，即i.addr(0) ~i.addr(12)

文件存储空间管理

• 磁盘管理要解决的重要问题之一是如何为新创建的文件分配存储空间。 其解决方法与内存的分配情况有许多相似之处

  • 连续分配方式

    • 空闲表法

      • 与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表， 每个空闲区对应于一个空闲表项,再将所有空闲区按其起始盘块号递增的次序排列

  • 离散分配方式

    • 空闲盘块链

      • 这是将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。

    • 空闲盘区链

      • 这是将磁盘上的所有空闲盘区拉成一条链。 在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。

  • 位示图法（连续离散都适用）

    • 利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为0时表示对 应的盘块空闲，为1时表示已分配(Linux)。 有的系统则相反。

    • 磁盘上的所有盘块都有一个二进制位与之对应，这样由所有盘块所对应的位构成一个集合，称为位示图。

    • 通常可用m*n个位数来构成位示图，并使m*n等磁盘的总块数。

• 存储空间的基本分配单位都是磁盘块而非字节。

• 为了实现存储空间的分配，首先必须记住空闲存储空间的使用情况。

  • 数据结构

  • 分配和回收功能

    • 根据位示图进行盘块分配时，可分三步进行:

      • 顺序扫描位示图，从中找出一个或一组其值为 “0”的二进制位( “0”表示空闲时)

      • 将所找到的一个或-组二进制位转换成与之相应的盘块号。假定找到的其值为”0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算:b=n(i-1) +j式中，n代表每行的位数

      • 修改位示图，令map[i, j] = 1

    • 盘块的回收分两步:

      • 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为: i= (b-1)DIV n+ 1 j=(b-1)MODn+1

      • 修改位示图。令map[i,j] = 0