操作系统总结之磁盘管理

磁盘存储器具有容量大、存取速度快、支持随机存取的特点，因此被广泛应用于计算机系统中。对于操作系统来说，管理好磁盘的三大要求和目标是：

（1）合理有效利用磁盘：采用合理的文件存储空间分配算法，尽量减少磁盘碎片，提高硬盘的利用率；
（2）提高磁盘的I/O速度：采用缓存等技术，提供访问速度；
（3）提高磁盘可靠性：采用冗余和纠错检错等技术，保证磁盘的数据不会被破坏。

1. 外存的组织方式
  文件是存放在磁盘上的，而磁盘是以盘块为基本的分配单位的，那么一个文件是怎么存放在磁盘上的呢，这就是外存的组织方式，主要有以下三种：

    1.连续组织方式
    2.链接组织方式
    3.索引组织方式

文件的物理结构与外存分配方式有关，在采用连续分配方式时的文件物理结构是顺序式的文件结构，在采用链接分配方式将形成链接式文件结构，而索引分配方式将形成索引式文件结构。

1.1 连续组织方式：
  要求为每一个文件分配一组相邻接的(也就是连续的)盘块。就好像分配一个连续的数组给文件使用一样，不过数组元素是磁盘的盘块。它的优点在于（1）顺序访问容易，（2）访问速度快，因为都放在 相邻或者同一个磁道 上，寻道时间很小。缺点为容易产生外部碎片，难以知道文件长度，难以为其分配空间，不利于删除和插入记录。

1.2 链接组织方式：
  为每个文件分配不连续的磁盘空间，通过链接指针将一个文件的所有盘块链接在一起，由此形成链式文件结构。这种方式可以克服连续组织方式的缺点，分为隐式链接和显式链接两种形式。

1.2.1 隐式链接：
  其中隐式链接的目录项需要包含文件的第一个盘块和最后一个盘块号，每一个盘块都有一个指向下一块盘块的指针（最后一个盘块除外）。但是这样只能顺序查找，速度慢。 此外，其可靠性较差，任何一个指针出现问题，都会导致整个链的断开。可以将几个盘块组成一个簇，然后以簇为单位进行分配，会减少查找指定块的时间，但是会增加内部碎片。

1.2.2 显式链接：
  **用于链接文件各物理块的指针显式地存放在内存的一张链接表中，该表在整个磁盘中仅设置一张。而文件第一个盘块号作为文件的物理地址存放在FCB中。**而那个链接表则叫做文件分配表（FAT:file allocation table）。

    那么查找的时候，将会把该表拷贝至内存中，大大减少访问磁盘速度，提高了检索的速度。 
1
  
  说明：表的序号从0开始，直至N-1，N为盘块总数，在每个表项中存放链接指针，即下一个盘块号，在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应的文件的FCB(File Control Block)的物理地址字段中，由于查找记录的过程是在内存中进行的，因而提高了检索速度，减少了访问磁盘的次数，由于分配给文件的所有盘块号都在该表中，故把该表称为文件分配表FAT（File Allocation Table）。

  缺点：不能支持高效的直接存储（要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找很多盘块号）；FAT需要占用较大的内存空间（由于一个文件所占用的盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证FAT中找到一个文件的所有盘块号，当磁盘容量较大时，FAT占用的容量更大）

1.2 索引组织方式：
事实上，在打开某个文件时，只需要把该文件占用的盘块号的编号调入内存即可，完全没有必要把整个FAT调入内存，为此，应该将每个文件所对应的盘块号集中地放在一起，索引分配方式就是基于这种想法所形成的一种分配方式。其为每个文件分配一个索引块（表），再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多磁盘块号的数组。在建立一个文件时，只需要在为之建立的目录项中填上指向该索引块的指针（单级索引）。
　　

说明：**索引方式支持直接访问，可在索引块中找到第i个盘块，索引方式也不会产生外部碎片，**当文件较大时，索引分配方式要优于链接分配方式。其主要问题在于：可能需要花费较多的外存空间，每当建立一个文件时，便须为之分配一个索引块，将分配给该文件的所有盘块号记录其中。对于小文件而言，索引块的利用率非常低。

当OS为一个大文件分配磁盘空间时，如果所分配的盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中，以此类推，然后再通过链指针将各索引块按序链接起来，当文件太大时，索引块太多，效率是低效的。此时，应该为这些索引块再建立一级索引，称为第一级索引，还可再建立索引，称为第二级索引等等。称为多级索引分配。
　　
　　　说明：在二级索引分配方式下，若每个盘块的大小为1KB，每个盘块号占4个字节，则在一个索引块可以存放256个盘块号，这样，在两级索引时，最多可以包括存放文件的盘块号总数为64K(256 * 256)个盘块号，所允许文件最大文件大小为64MB，若盘块号为4KB，则一级索引的最大文件大小为4MB，二级索引的最大文件大小为4GB。

索引块 == 特殊的盘块，所以还是1KB == 1024B == 4*256 B 　　　
1
1.2.1 伟大的 Linux 系统所采用的索引组织方式之混合索引分配方式
思想：
④ 将多种索引分配方式相结合而形成的一种分配方式：

 小文件：
1
（1）直接地址（在FCB中设置10个直接地址项，每项中所存放的是该文件数据所在盘块的盘块号，假如每个盘块大小为4KB，当文件不大于40KB时，可以直接从FCB中读出该文件的全部盘号）

 中等文件：
1
（2）一次间接地址（**为文件建立一个索引表，然后将该表首地址放入FCB中，需要时找到索引表的首地址，从而通过索引表找到所有的盘块号 。**其实质就是一级索引分配方式）

 大文件或者特大文件：
1
（3）多次间接地址（当文件大于4MB + 40KB时，系统采用二次间址分配方式，其实质是两级索引分配方式，采用二次间址的最大文件大小为4GB，同理，可采用三次间接地址，允许文件最大大小为4TB）。

实现：
每个文件的索引结点含13个地址项 i.addr(0)~ i.addr(12), 每项2个字节; 前10项存放直接地址(物理块号), 若文件大于40kB，则用i.addr(10)指向单级索引块进行一次间接寻址,该块中最多可放1k个物理块号,文件可长达4MB; 还可用 i.addr(11) 和 i.addr(12) 作为二次和三次间接寻址, 文件最大长度分别可达4GB和4TB。

2. 磁盘空闲盘块的管理
在上面的外存组织方式中，为一个文件分配空闲盘块，就需要知道哪些盘块是空闲的，记录磁盘有哪些空闲盘块有以下方法：
（1）空闲表法：为外存上所有区域建立一张空闲表，每个空闲区对应于一个空闲表项，空闲表项里面有表项的序号、空闲区的第一个盘块号、空闲盘块数等信息：

对于空闲表法的空间分配和回收跟内存空间的动态分区分配类似，同样可以采用首次适应、最佳适应等算法，回收时，也会考虑回收区间相邻的空间，进行适当的拼接。
（2）空闲链表法：将所有空闲盘块区拉成一条空闲链。这种方法对分配和回收比较简单，但是空闲盘块链可能会很长。
（3）位示图法：利用磁盘空间的每一位来表示磁盘一个盘块是否空闲：

位示图法的分配和回收就是把相应的位置为0或者1，这种方法占用的空间小，适合保存在内存中，就不需要每次都访问磁盘。
（4）成组链接法：（略）。

3.提高磁盘I/O速度的途径
                         磁盘高速缓存
1
磁盘的读取速度跟内存的读取速度相差4~6个数量级，为了提高磁盘访问速度，我们可以在内存中为磁盘盘块设置一个缓冲区，称为磁盘高速缓存，在缓冲区中保存一些盘块的副本，当有一个磁盘请求时，先在缓冲区里面查找是否有该盘块，若有，直接从缓冲区获取数据；如果没有再启动磁盘读入，并将内容送至缓冲区，以便下次访问。

4.廉价磁盘冗余阵列（RAID）
    设置多台磁盘存储器，并行地读取磁盘内容，加快I/O速度，同时采用容错技术提高可靠性。