【操作系统】知识梳理（八）磁盘存储器的管理

8.1 外存的组织方式

1.连续组织方式

连续组织方式又称连续分配方式，它是指为每个文件分配-组相邻的物理块，并将文件中的信息按逻辑顺序依次存放在这些物理块中，文件首个物理块的地址被登记在它的FCB内。这样所形成的文件物理结构被称为顺序结构，相应的物理文件则称为顺序文件。连续组织方式管理简单，其顺序访问的存取速度很快，而且支持对文件的随机存取。但连续分配造成的碎片问题，会严重降低存储空间的利用率;而且连续分配还要求在分配前事先知道文件的长度，从而使得文件内容的增删以及文件的动态增长都不够方便。

2.链接组织方式

链接组织方式采取离散分配方式，它又可分成隐式链接和显式链接两种方式。
1)隐式链接
隐式链接方式将一个文件离散地存放在外存上，它的首个物理块的地址被登记在该文件FCB的物理地址字段中，而每个后续物理块的地址则登记在分配给它的前一个物理块中，从而使得存放同一个文件的所有物理块按信息的逻辑顺序形成一个链。
隐式链接解决了外部碎片以及存放文件前必须预知文件长度的问题，但它只支持顺序访问，不支持随机访问;而且，一旦文件的盘块链中任何-一个指针出现问题，就会导致整个链的断开，故其可靠性也较差。
2)显式链接
显式链接方式将链接各个物理块的指针显式地登记在系统的一张文件分配表FAT中。FAT的每个表项对应于文件存储空间的一一个物理块，表项的序号即对应物理块的块号，而表项的内容则是分配给文件的下- -个物理块的指针。如图8.1所示，分配给文件filel的物理块分别为: 4，6，11，而分配给文件file2的物理块则分别为: 9， 10， 5。

 

如果文件存储介质容量较小，则在文件操作时，可把整个FAT装入内存，从而可显著地提高检索的速度;而在整个文件卷中再设置- -个备份FAT,则可较好地增加文件系统的可靠性。但采用显式链接分配方式时，对较大文件的随机存取，须先在FAT中顺序查找许多盘块号，故它不能支持高效的随机存取;如果文件存储介质容量较大，则FAT也需占用较大的存储空间，此时将整个FAT装入内存显然是不现实的，这会进一步 影响到文件随机存取的效率。

3.索引组织方式

索引组织方式为每个文件建立一-个索引块(表)， 用来登记分配给该文件的所有物理块号，而文件FCB的物理地址字段中则填上指向该索引表的指针。图8.2示出了磁盘空间的索引分配图，其中分配给文件jeep的索引块的物理盘块是19，而分配给它存放文件内容的物理盘块则分别为9、16、 1、10和25。

 

若文件较大，则可能要分配给索引表多个物理块。此时，可为索引表本身再建立一个索引表，从而形成两级索引。如果文件非常大，还可用三级甚至更多级索引的方式。
采用索引组织方式，在打开文件时，可将索引表读入内存，以后便可在内存中查找分配给某个逻辑块的物理块号，因此该方式可支持高效的随机存取。但索引表本身可能要花费较多的外存空间，尤其是对中、小型文件，同样仍需为它们分配一个完整的物理块，从而会造成外存空间的严重浪费。

4.混合索引方式

UNIX系统中采用了一种特别的文件分配方式，它将多种索引分配方式结合在一起，故被称作混合索引方式，或增量式索引方式。如在UNIX SystemV中，用来存放文件的物理地址等属性信息的文件索引节点中，共设有如下13个地址项:
(1)直接地址。索引结点中的i addr[0]~i_ addr[9]共10个地址项，称为直接地址，其中可以存放分配给相应文件的前十个(第0~9个)物理块的地址。假如每个物理块的大小为4KB，当文件长度不超过40 KB时，便能直接从i节点中找到每个物理块的地址。
(2) 一一次间址。地址项i addr[ 10]称为一次间址， 其中存放的是分配给文件的一次间址块的地址，而在一次间址块中 则登记有分配给文件的第10个物理块及后续物理块的地址。如果每个物理块地址要用4个字节来描述，则4 KB的一次间址块中可以存放1K个物理块号，从而可存储长达40KB+1Kx4KB的文件。
(3) 多次间址。地址项i addr[1]称为二次间址，其中登记的是分配给文件的二次间址块的地址，在二次间址块中可登记1 K个一次间址块的地址，而每个一次间址块中又可登记分配给文件的1 K个物理块的地址。因此,使用二次间址,可存储最大长度达到40 KB +4MB +4GB的文件。同理，地址项i_ addr[12]作为三次间址，可存储最大长度达到40 KB +4MB+4GB +4TB的文件。
图8.3给出了混合索引分配方式的示意图。由于平时使用的大多数文件属于中、小型文件，因此，混合分配方式既能节省存储地址所占的存储空间，又可有较高的查找速度。

 

5. NTFS的文件组织方式

在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一-张 主控文件表MFT(Master File Table)中，该表是NTFS卷结构的中心。从逻辑上讲，卷中的每个文件作为- - 条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数(metadata)，也称为文件控制字。
在MFT表中，每个元数据都将其所对应文件的所有信息(包括文件的内容等),组织在所对应文件的一组属性中，文件的内容用其中的DATA属性描述，当文件较小时，可将文件的内容直接记录在元数据的DATA属性中，这样对文件数据的访问，仅需要对MFT表进行访问即可，减少了磁盘访问次数，显著地提高了对小文件存取的效率;而当文件较大时，则将文件的内容记录到卷中的其他可用区域中，并将这些区域的簇数和起始簇号保存在元数据的DATA属性中，从而可以方便地查到这些簇，完成对文件内容的访问。

 8.2 文件存储空间的管理

1.空闲表法

与内存动态分区分配方式类似，系统可用一张空闲表来管理空闲的文件存储空间，其中的每个表项对应于一个空闲区，并登记有该空闲区的起始块号和块数等信息。在进行存储空间的分配时，同样可采用首次适应、最佳适应等算法;而回收时，同样要进行空闲区的合并。空闲表法属f连续分配方式，它具有较高的分配速度，常用在对换空间管理等需要连续分配的合。

2.空闲链表法

这种方法将文件存储空间中的所有空闲区拉成一条空闲链。如果构成链的基本元素是盘块，则称之为空闲盘块链:如果构成链的基本元素是空闲盘区，则称之为空闲盘区链,此时，每个盘区中还必须给出本盘区的块数。
空闲盘块链只适合离散分配，分配时系统将从链首开始依次摘下适当数目的空闲块分配给用户，回收时将回收块依次插入链的末尾。空闲盘区链旺适合离散分配，也适合连续分配，对连续分配，它可采用首次适应、最佳适应等算法。为了提高文件存储器的利用率，通常将链接指针和盘块数目等信息登记在空闲盘块内，这样做的缺点是，从链上增加或减少空闲区需要进行大量的I/O操作。

3.位示图法

位示图是利用二进制的一-位来表示文件存储空间中的一个块的使用情况。一个m行n列的位示图，可用来描述mx n块的文件存储空间，当行号、列号和块号都是从0开始编号时，第i行、第j列的二进制位对应的物理块号为i x n+j。如果，“0”表示对应块空闲，“1”表示对应块已分配，则在进行存储空间的分配时，可顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位，将对应的块分配出去，并将这些位置1;而在回收某个块时，只需找到对应的位，并将其清0便可。位示图法既适合离散分配，也适合连续分配，它简单易行，而且位示图通常较小，故可将其读入内存，从而进-步加快文件存储空间分配和回收的速度。

4.成组链接法

成组链接法是UNIX系统采用的空闲盘块管理方式。它将一个文件卷的所有空闲盘块按固定大小(如每组100块)分成若干组，并将每一组的 盘块数和该组所有的盘块号记入前一组的最后一个盘块中，第一组的盘块数(可小于100)和该组所有的盘块号则记入超级块的空闲盘块号栈中。图8.4给出了一个成组链接法的例子，从中可以看出，最后一组虽然只有99个盘块，但加.上结束标记“0”后，仍将它算作100块。

 

当系统要为用户分配文件所需的盘块时，若第一组不只一块，则将超级块中的空闲盘块数减1,并将空闲盘块号栈栈顶的盘块分配出去:若第一组只剩一块且栈顶的盘块号不是结束标记0，则先将该块的内容(记录有下一组的盘块数和盘块号)读到超级块中，然后再将该块分配出去;否则，若栈顶的盘块号为结束标记0，则表示该磁盘上已无空闲盘块可供分配。
在系统回收空闲盘块时，若第一组不满 100块，则只需将回收块的块号填入超级块的空闲盘块号栈栈顶，并将其中的空闲盘块数加1;若第一-组已有100块，则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中，然后将盘块数1和回收块的块号记入超级块中。
超级块中的空闲盘块号栈是临界资源，对该栈的操作必须互斥地进行，因此，系统为空闲盘块号栈设置了-把锁，并通过上锁和解锁来实现对空闲盘块号栈的互斥操作。
成组链接法除了第一-组空闲 盘块外，其余空闲盘块的登记不占额外的存储空间;而超级块(即文件卷的第1块)已在安装磁盘时拷入内存，因此，绝大部分的分配和回收工作可在内存中进行，从而使之具有较高的效率。

8.3 提高磁盘I/O速度的途径

1.磁盘高速缓存(Disk Cache)

磁盘高速缓存是在内存中为磁盘块设置的一个缓冲区，其中存放有磁盘中某些盘块的副本。当有一进程请求访问某个盘块中的数据时，系统首先检查该盘块是否在磁盘高速缓存中，如果在，则无需读盘而可直接从高速缓存中提取数据交付给请求进程，从而使本次的访问速度提高4~6个数量级:否则，应先从磁盘中将所要访问的数据读入并交付给请求进程，同时将数据送高速缓存。

2.提前读

提前读是指在读当前盘块的同时，将下一个可能要访问到的盘块中的数据也读入缓冲区。这样，当要读下一个盘块中的数据时，由于它们已被提前读入缓冲区，便可直接从缓冲区中取得所需数据，而无需启动磁盘。用户对文件进行访问时，经常采用顺序访问的方式，因此，可采用提前读来有效地减少读数据的时间，从而提高磁盘I/O的速度。提前读功能目前已被各种操作系统广泛使用。

3.延迟写

在写盘块时，本应将对应缓冲中的数据立即写盘，但考虑到该盘块中的数据在不久之后可能还会被再次访问，因而并不立即将对应缓冲区中的数据写入磁盘，而只是将它置上“延迟写”标志并挂到空闲缓冲队列的末尾。当该缓冲区移到空闲缓冲队列的首部，并作为空闲缓冲被分配出去时，才将缓冲区中的数据写入磁盘。只要延迟写块仍在空闲缓冲队列中，任何要求访问该盘块的进程，都可直接从其中读出数据或将数据写入其中，而不必去访问磁盘，因此，可有效地提高磁盘I/O的速度。

4.优化物理块布局

另一种提高磁盘I/O速度的重要措施，是优化文件物理块的分布，从而使访问文件时，磁头的移动距离尽量的小。例如，操作系统中经常将同一条磁道上的若千个盘块组成一簇，并以簇为单位来分配文件存储空间，这样就可以保证在访问这几个盘块时，不必移动磁头，从而减少了磁头的平均移动距离，提高磁盘存取的速度。

5.虛拟盘

虚拟盘，又称为RAM盘，它是指利用内存空间去仿真磁盘。该盘的设备驱动程序，可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中，因此它们的速度也更快。用户完全可以像使用真正的磁盘-样使用虚拟盘。由于虚拟盘是易失性存储器，当系统或电源发生故障，或者系统重新启动时，其中的数据将会丢失，因此，虚拟盘通常只用来存放临时性的文件。

6.廉价磁盘冗余阵列(RAID)

廉价磁盘冗余阵列RAID是利用一台 磁盘阵列控制器,来统一管理和控制一组(几台到几十台)磁盘驱动器，从而组成-一个高度可靠的、快速的大容量磁盘系统。操作系统将RAID中的一-组物理磁盘驱动器，看做单个的逻辑磁盘驱动器，用户数据和系统数据可分布在阵列的所有磁盘中，并可采取并行传输的方式，因此可大大地减少数据的传输时间。
RAID的另一特点是高可靠性)RAID方案可分成RAID0~RAID7这几级，除了RAIDO外，其他各级都采用了容错技术。其中，RAID1采用了磁盘镜像功能，阵列中的每个磁盘都有一个镜像盘; RAID3 则专门使用一台奇偶校验盘，其中每一位用来存放根据其他磁盘中同一位置的数据位计算出来的奇偶校验码，从而使得某个磁盘发生故障时，可通过其余设备重新构造数据:RAIDS则将奇偶校验码以螺旋方式散布到各个数据盘中，其目的是避免奇偶校验码盘成为磁盘I/O的瓶颈:RAID6中采用了两种不同的校验算法计算校验码，并将它们保存在不同磁盘中，因此具有更高的可靠性。 

8.4 提高磁盘可靠性的技术

1.第一级容错技术SFT-I

第一级容错技术SFT-I又称低级磁盘容错技术, SFT-I主要用于防止因磁盘表面发生的缺陷而引起的数据丢失，常用的措施有:
(1)双份目录和双份文件分配表。它是指在不同的磁盘上或在磁盘的不同区域中，分别建立两份目录表和文件分配表FAT。- -旦由于磁盘表面的缺陷而造成主文件目录或FAT的损坏时，系统便可自动启用备份文件目录或FAT，从而使系统仍可访问磁盘上的数据;同时, .系统还必须将损坏区写入坏块表中，并在磁盘的其他区域再建立新的文件目录或FAT备份。
(2)热修复重定向。它将磁盘容量的一部分(例 如2%~3%)保留下来，作为热修复重定向区，以后当磁盘上某个块损坏时，便将待写的数据写入热修复重定向区的一个块中，并在坏块表中记录下它们的对应关系，以后，所有对该坏块的请求都将改为访问相应的热修复重定向块。
(3)写后读校验。它是指每次从内存缓冲区向磁盘写入一个数据块后，便立即将它读入内存的另一个缓冲区，并将这两个缓冲区的内容进行比较，以保证它们的一致，若两者不一致，则认为相应盘块有缺陷，此时，可将待写数据写到热修复重定向区中。

2.第二级容错技术SFT-II

第二级容错技术SFT-II又称中级磁盘容错技术,SFT-II主要用于防止由磁盘驱动器和磁盘控制器的故障所导致的数据损坏。
(1)磁盘镜像。它是在同一台磁盘控制器下，再增设一个完全相同的磁盘驱动器。在每次向主磁盘写数据后，都需要采用写后校验方式，将数据再同样写到备份磁盘上，使两个磁盘上具有完全相同的位像图，即用备份盘作为主盘的镜像。如果主驱动器发生故障，则立即启用备份驱动器，同时向用户发出警告，以尽快修复故障驱动器而恢复磁盘镜像功能。
(2)磁盘双工。为了防止因磁盘控制器或主机到磁盘控制器之间的通道发生故障，而造成两台磁盘机的同时失效，可将两台驱动器分别连接到两个磁盘控制器上，而两个控制器又分别连到两个通道上，每次写将同时将数据写到两个处于不同控制器下的磁盘上。如果某个通道或控制器发生故障，另-通道上的磁盘仍能正常工作，不会造成数据的丢失，但同时须立即发出警告，以便尽快恢复磁盘双工功能。由于每个磁盘有自己的独立通道，故可同时将数据写入磁盘，而读数据时，则可从相应快的通道上读取数据，因而加快了数据的读取速度。

3.基于集群技术的容错功能

高级系统容错技术SFTII是基于集群技术来实现容错的，所谓集群，是指由一组互连的自主计算机组成统一的计算机系统，给人们的感觉是，它们是一台机器。利用集群系统不仅可提高系统的并行处理能力,还可用于提高系统的可用性。其工作模式主要有以下三种方式:
(1) 双机热备份模式。系统中备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。平时主服务器运行，备份服务器则时刻监视着主服务器的运行，一旦主服务器出现故障，备份服务器便立即接替主服务器的工作而成为系统中的主服务器，修复后的服务器再作为备份服务器。
(2)双机互为备份模式。这种模式中，两台服务器均为在线服务器，它们各自完成自己的任务;同时它们还接收另一台服务器发来的备份数据，作为对方的备份服务器。如果其中的一台服务器发生故障，则由另一台服务器为客户机提供服务;当故障服务器修复并重新连到网上后，已被迁移到无故障服务器上的服务功能，将被返回，恢复正常工作。
(3)公用磁盘模式。为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公共磁盘被划分为若千个卷，每台计算机使用一个卷。如果某台计算机发生故障，此时系统将重新进行配置，根据某种调度策略来选择另-台替代计算机，后者对发生故障的计算机的卷拥有所有权，从而来接替故障计算机所承担的任务。

4.后备系统

后备系统利用系统程序将磁盘数据保存到另一存储设备，如磁带、光盘或另一个磁盘上。建立后备系统后，由于自然因素，或者系统发生故障或病毒感染而造成的数据错误和丢失时，便可从备份中进行恢复，从而保证系统的安全。

8.5 数据一致性控制

1.事务

当一数据被分散地存放在- -个文件的不同记录中，或多个文件中时，可采用事务来保证该数据的一致性。事务是用于访问和修改各种数据项的一-个程序单位， 它可以被看作是一系列的读和写操作。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能以托付操作来终止事务。只要有一个读和写操作失败，便须执行天折操作:为了保证数据的一致性， 此时，须将该事务内刚被修改的数据项恢复成原来的情况。可见，事务操作具有原子性。
事务操作的原子性须借助于存放在稳定存储器中的事务记录表来实现，其中的每条记录描述了事务运行中的重要操作，如修改操作、开始事务、托付事务和天折事务等。在一个事务Ti开始执行时，<Ti开始>记录被写入事务记录表中: Ti执行期间，在Ti的任何写(含修改)操作之前，便写一适当的新记录到事务记录表中，该记录中包含了事务名、被修改的数据项名、修改前的数据项旧值和修改后的数据项新值等信息;当进行T;托付时，把一个<Ti托付>记录写入事务记录表中。如果系统发生故障，系统便可通过事务记录表对以前所发生的事务进行清理。对事务T，如果在事务记录表中既包含了<Ti开始> 记录，又包含了<Ti托付>记录，则系统应执行redo <Ti> 过程，把所有已被事务修改过的数据设置成新值:如果在事务记录表中只包含了<Ti开始> 记录，而无<Ti托付>记录，则应执行undo <Ti> 过程，将所有已被修改过的数据，恢复成修改前的值。

2.重要数据结构的一致性检查

文件系统工作过程中，经常要读取磁盘块，进行修改后再写回磁盘。如果在修改过的磁盘块全部写回之前，系统发生故障，则文件系统有可能会处于不一致状态。当未被写回的内容涉及到索引结点、目录或空闲盘块表等重要数据结构时，该问题会显得更严重。因此，很多计算机都带有实用程序以检查文件系统的一致性， 在系统启动时，尤其是崩溃之后重新启动时，可运行该程序进行一致性的检查。
(1)盘块的一致性检查。为了对盘块进行一致性检查，检查程序可构造一张表，每个表项对应于一个磁盘块，其中有两个初值为0的计数器，分别用来登记该盘块在文件中出现的次数，以及它作为空闲盘块出现的次数。检查一个盘块在文件中出现的次数可通过读取FAT或索引结点(具体与文件的物理结构有关)来进行，而检查一个盘块作为空闲盘块出现的次数则可通过读取位示图或空闲盘块表或链(具体与文件存储空间中空闲盘块的管理方式有关)来进行。如果文件系统-致,则对应于每个盘块的两个计数器，要么第一个计数器的值为1，要么第二个计数器的值为1;否则便说明发生了某种错误，应采取相应措施进行处理，并向系统汇报情况。
(2)链接计数的一致性检查。在利用链接方式共享文件的系统中，对应于一个文件的目录项数与该文件的索引结点中的链接计数必须-致。检查程序可通过读取所有的目录来获得对应于每个文件的目录项数，并与相应文件索引结点中的链接计数进行比较，如果两者一致，表示是正确的:否则，便是发生了链接数据不一-致的错误， 应采取相应的处理措施，并进行汇报。

【操作系统】知识梳理（八）磁盘存储器的管理

8.1 外存的组织方式

1.连续组织方式

连续组织方式又称连续分配方式，它是指为每个文件分配-组相邻的物理块，并将文件中的信息按逻辑顺序依次存放在这些物理块中，文件首个物理块的地址被登记在它的FCB内。这样所形成的文件物理结构被称为顺序结构，相应的物理文件则称为顺序文件。连续组织方式管理简单，其顺序访问的存取速度很快，而且支持对文件的随机存取。但连续分配造成的碎片问题，会严重降低存储空间的利用率;而且连续分配还要求在分配前事先知道文件的长度，从而使得文件内容的增删以及文件的动态增长都不够方便。

2.链接组织方式

链接组织方式采取离散分配方式，它又可分成隐式链接和显式链接两种方式。
1)隐式链接
隐式链接方式将一个文件离散地存放在外存上，它的首个物理块的地址被登记在该文件FCB的物理地址字段中，而每个后续物理块的地址则登记在分配给它的前一个物理块中，从而使得存放同一个文件的所有物理块按信息的逻辑顺序形成一个链。
隐式链接解决了外部碎片以及存放文件前必须预知文件长度的问题，但它只支持顺序访问，不支持随机访问;而且，一旦文件的盘块链中任何-一个指针出现问题，就会导致整个链的断开，故其可靠性也较差。
2)显式链接
显式链接方式将链接各个物理块的指针显式地登记在系统的一张文件分配表FAT中。FAT的每个表项对应于文件存储空间的一一个物理块，表项的序号即对应物理块的块号，而表项的内容则是分配给文件的下- -个物理块的指针。如图8.1所示，分配给文件filel的物理块分别为: 4，6，11，而分配给文件file2的物理块则分别为: 9， 10， 5。

 

如果文件存储介质容量较小，则在文件操作时，可把整个FAT装入内存，从而可显著地提高检索的速度;而在整个文件卷中再设置- -个备份FAT,则可较好地增加文件系统的可靠性。但采用显式链接分配方式时，对较大文件的随机存取，须先在FAT中顺序查找许多盘块号，故它不能支持高效的随机存取;如果文件存储介质容量较大，则FAT也需占用较大的存储空间，此时将整个FAT装入内存显然是不现实的，这会进一步 影响到文件随机存取的效率。

3.索引组织方式

索引组织方式为每个文件建立一-个索引块(表)， 用来登记分配给该文件的所有物理块号，而文件FCB的物理地址字段中则填上指向该索引表的指针。图8.2示出了磁盘空间的索引分配图，其中分配给文件jeep的索引块的物理盘块是19，而分配给它存放文件内容的物理盘块则分别为9、16、 1、10和25。

 

若文件较大，则可能要分配给索引表多个物理块。此时，可为索引表本身再建立一个索引表，从而形成两级索引。如果文件非常大，还可用三级甚至更多级索引的方式。
采用索引组织方式，在打开文件时，可将索引表读入内存，以后便可在内存中查找分配给某个逻辑块的物理块号，因此该方式可支持高效的随机存取。但索引表本身可能要花费较多的外存空间，尤其是对中、小型文件，同样仍需为它们分配一个完整的物理块，从而会造成外存空间的严重浪费。

4.混合索引方式

UNIX系统中采用了一种特别的文件分配方式，它将多种索引分配方式结合在一起，故被称作混合索引方式，或增量式索引方式。如在UNIX SystemV中，用来存放文件的物理地址等属性信息的文件索引节点中，共设有如下13个地址项:
(1)直接地址。索引结点中的i addr[0]~i_ addr[9]共10个地址项，称为直接地址，其中可以存放分配给相应文件的前十个(第0~9个)物理块的地址。假如每个物理块的大小为4KB，当文件长度不超过40 KB时，便能直接从i节点中找到每个物理块的地址。
(2) 一一次间址。地址项i addr[ 10]称为一次间址， 其中存放的是分配给文件的一次间址块的地址，而在一次间址块中 则登记有分配给文件的第10个物理块及后续物理块的地址。如果每个物理块地址要用4个字节来描述，则4 KB的一次间址块中可以存放1K个物理块号，从而可存储长达40KB+1Kx4KB的文件。
(3) 多次间址。地址项i addr[1]称为二次间址，其中登记的是分配给文件的二次间址块的地址，在二次间址块中可登记1 K个一次间址块的地址，而每个一次间址块中又可登记分配给文件的1 K个物理块的地址。因此,使用二次间址,可存储最大长度达到40 KB +4MB +4GB的文件。同理，地址项i_ addr[12]作为三次间址，可存储最大长度达到40 KB +4MB+4GB +4TB的文件。
图8.3给出了混合索引分配方式的示意图。由于平时使用的大多数文件属于中、小型文件，因此，混合分配方式既能节省存储地址所占的存储空间，又可有较高的查找速度。

 

5. NTFS的文件组织方式

在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一-张 主控文件表MFT(Master File Table)中，该表是NTFS卷结构的中心。从逻辑上讲，卷中的每个文件作为- - 条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数(metadata)，也称为文件控制字。
在MFT表中，每个元数据都将其所对应文件的所有信息(包括文件的内容等),组织在所对应文件的一组属性中，文件的内容用其中的DATA属性描述，当文件较小时，可将文件的内容直接记录在元数据的DATA属性中，这样对文件数据的访问，仅需要对MFT表进行访问即可，减少了磁盘访问次数，显著地提高了对小文件存取的效率;而当文件较大时，则将文件的内容记录到卷中的其他可用区域中，并将这些区域的簇数和起始簇号保存在元数据的DATA属性中，从而可以方便地查到这些簇，完成对文件内容的访问。

 8.2 文件存储空间的管理

1.空闲表法

与内存动态分区分配方式类似，系统可用一张空闲表来管理空闲的文件存储空间，其中的每个表项对应于一个空闲区，并登记有该空闲区的起始块号和块数等信息。在进行存储空间的分配时，同样可采用首次适应、最佳适应等算法;而回收时，同样要进行空闲区的合并。空闲表法属f连续分配方式，它具有较高的分配速度，常用在对换空间管理等需要连续分配的合。

2.空闲链表法

这种方法将文件存储空间中的所有空闲区拉成一条空闲链。如果构成链的基本元素是盘块，则称之为空闲盘块链:如果构成链的基本元素是空闲盘区，则称之为空闲盘区链,此时，每个盘区中还必须给出本盘区的块数。
空闲盘块链只适合离散分配，分配时系统将从链首开始依次摘下适当数目的空闲块分配给用户，回收时将回收块依次插入链的末尾。空闲盘区链旺适合离散分配，也适合连续分配，对连续分配，它可采用首次适应、最佳适应等算法。为了提高文件存储器的利用率，通常将链接指针和盘块数目等信息登记在空闲盘块内，这样做的缺点是，从链上增加或减少空闲区需要进行大量的I/O操作。

3.位示图法

位示图是利用二进制的一-位来表示文件存储空间中的一个块的使用情况。一个m行n列的位示图，可用来描述mx n块的文件存储空间，当行号、列号和块号都是从0开始编号时，第i行、第j列的二进制位对应的物理块号为i x n+j。如果，“0”表示对应块空闲，“1”表示对应块已分配，则在进行存储空间的分配时，可顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位，将对应的块分配出去，并将这些位置1;而在回收某个块时，只需找到对应的位，并将其清0便可。位示图法既适合离散分配，也适合连续分配，它简单易行，而且位示图通常较小，故可将其读入内存，从而进-步加快文件存储空间分配和回收的速度。

4.成组链接法

成组链接法是UNIX系统采用的空闲盘块管理方式。它将一个文件卷的所有空闲盘块按固定大小(如每组100块)分成若干组，并将每一组的 盘块数和该组所有的盘块号记入前一组的最后一个盘块中，第一组的盘块数(可小于100)和该组所有的盘块号则记入超级块的空闲盘块号栈中。图8.4给出了一个成组链接法的例子，从中可以看出，最后一组虽然只有99个盘块，但加.上结束标记“0”后，仍将它算作100块。

 

当系统要为用户分配文件所需的盘块时，若第一组不只一块，则将超级块中的空闲盘块数减1,并将空闲盘块号栈栈顶的盘块分配出去:若第一组只剩一块且栈顶的盘块号不是结束标记0，则先将该块的内容(记录有下一组的盘块数和盘块号)读到超级块中，然后再将该块分配出去;否则，若栈顶的盘块号为结束标记0，则表示该磁盘上已无空闲盘块可供分配。
在系统回收空闲盘块时，若第一组不满 100块，则只需将回收块的块号填入超级块的空闲盘块号栈栈顶，并将其中的空闲盘块数加1;若第一-组已有100块，则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中，然后将盘块数1和回收块的块号记入超级块中。
超级块中的空闲盘块号栈是临界资源，对该栈的操作必须互斥地进行，因此，系统为空闲盘块号栈设置了-把锁，并通过上锁和解锁来实现对空闲盘块号栈的互斥操作。
成组链接法除了第一-组空闲 盘块外，其余空闲盘块的登记不占额外的存储空间;而超级块(即文件卷的第1块)已在安装磁盘时拷入内存，因此，绝大部分的分配和回收工作可在内存中进行，从而使之具有较高的效率。

8.3 提高磁盘I/O速度的途径

1.磁盘高速缓存(Disk Cache)

磁盘高速缓存是在内存中为磁盘块设置的一个缓冲区，其中存放有磁盘中某些盘块的副本。当有一进程请求访问某个盘块中的数据时，系统首先检查该盘块是否在磁盘高速缓存中，如果在，则无需读盘而可直接从高速缓存中提取数据交付给请求进程，从而使本次的访问速度提高4~6个数量级:否则，应先从磁盘中将所要访问的数据读入并交付给请求进程，同时将数据送高速缓存。

2.提前读

提前读是指在读当前盘块的同时，将下一个可能要访问到的盘块中的数据也读入缓冲区。这样，当要读下一个盘块中的数据时，由于它们已被提前读入缓冲区，便可直接从缓冲区中取得所需数据，而无需启动磁盘。用户对文件进行访问时，经常采用顺序访问的方式，因此，可采用提前读来有效地减少读数据的时间，从而提高磁盘I/O的速度。提前读功能目前已被各种操作系统广泛使用。

3.延迟写

在写盘块时，本应将对应缓冲中的数据立即写盘，但考虑到该盘块中的数据在不久之后可能还会被再次访问，因而并不立即将对应缓冲区中的数据写入磁盘，而只是将它置上“延迟写”标志并挂到空闲缓冲队列的末尾。当该缓冲区移到空闲缓冲队列的首部，并作为空闲缓冲被分配出去时，才将缓冲区中的数据写入磁盘。只要延迟写块仍在空闲缓冲队列中，任何要求访问该盘块的进程，都可直接从其中读出数据或将数据写入其中，而不必去访问磁盘，因此，可有效地提高磁盘I/O的速度。

4.优化物理块布局

另一种提高磁盘I/O速度的重要措施，是优化文件物理块的分布，从而使访问文件时，磁头的移动距离尽量的小。例如，操作系统中经常将同一条磁道上的若千个盘块组成一簇，并以簇为单位来分配文件存储空间，这样就可以保证在访问这几个盘块时，不必移动磁头，从而减少了磁头的平均移动距离，提高磁盘存取的速度。

5.虛拟盘

虚拟盘，又称为RAM盘，它是指利用内存空间去仿真磁盘。该盘的设备驱动程序，可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中，因此它们的速度也更快。用户完全可以像使用真正的磁盘-样使用虚拟盘。由于虚拟盘是易失性存储器，当系统或电源发生故障，或者系统重新启动时，其中的数据将会丢失，因此，虚拟盘通常只用来存放临时性的文件。

6.廉价磁盘冗余阵列(RAID)

廉价磁盘冗余阵列RAID是利用一台 磁盘阵列控制器,来统一管理和控制一组(几台到几十台)磁盘驱动器，从而组成-一个高度可靠的、快速的大容量磁盘系统。操作系统将RAID中的一-组物理磁盘驱动器，看做单个的逻辑磁盘驱动器，用户数据和系统数据可分布在阵列的所有磁盘中，并可采取并行传输的方式，因此可大大地减少数据的传输时间。
RAID的另一特点是高可靠性)RAID方案可分成RAID0~RAID7这几级，除了RAIDO外，其他各级都采用了容错技术。其中，RAID1采用了磁盘镜像功能，阵列中的每个磁盘都有一个镜像盘; RAID3 则专门使用一台奇偶校验盘，其中每一位用来存放根据其他磁盘中同一位置的数据位计算出来的奇偶校验码，从而使得某个磁盘发生故障时，可通过其余设备重新构造数据:RAIDS则将奇偶校验码以螺旋方式散布到各个数据盘中，其目的是避免奇偶校验码盘成为磁盘I/O的瓶颈:RAID6中采用了两种不同的校验算法计算校验码，并将它们保存在不同磁盘中，因此具有更高的可靠性。 

8.4 提高磁盘可靠性的技术

1.第一级容错技术SFT-I

第一级容错技术SFT-I又称低级磁盘容错技术, SFT-I主要用于防止因磁盘表面发生的缺陷而引起的数据丢失，常用的措施有:
(1)双份目录和双份文件分配表。它是指在不同的磁盘上或在磁盘的不同区域中，分别建立两份目录表和文件分配表FAT。- -旦由于磁盘表面的缺陷而造成主文件目录或FAT的损坏时，系统便可自动启用备份文件目录或FAT，从而使系统仍可访问磁盘上的数据;同时, .系统还必须将损坏区写入坏块表中，并在磁盘的其他区域再建立新的文件目录或FAT备份。
(2)热修复重定向。它将磁盘容量的一部分(例 如2%~3%)保留下来，作为热修复重定向区，以后当磁盘上某个块损坏时，便将待写的数据写入热修复重定向区的一个块中，并在坏块表中记录下它们的对应关系，以后，所有对该坏块的请求都将改为访问相应的热修复重定向块。
(3)写后读校验。它是指每次从内存缓冲区向磁盘写入一个数据块后，便立即将它读入内存的另一个缓冲区，并将这两个缓冲区的内容进行比较，以保证它们的一致，若两者不一致，则认为相应盘块有缺陷，此时，可将待写数据写到热修复重定向区中。

2.第二级容错技术SFT-II

第二级容错技术SFT-II又称中级磁盘容错技术,SFT-II主要用于防止由磁盘驱动器和磁盘控制器的故障所导致的数据损坏。
(1)磁盘镜像。它是在同一台磁盘控制器下，再增设一个完全相同的磁盘驱动器。在每次向主磁盘写数据后，都需要采用写后校验方式，将数据再同样写到备份磁盘上，使两个磁盘上具有完全相同的位像图，即用备份盘作为主盘的镜像。如果主驱动器发生故障，则立即启用备份驱动器，同时向用户发出警告，以尽快修复故障驱动器而恢复磁盘镜像功能。
(2)磁盘双工。为了防止因磁盘控制器或主机到磁盘控制器之间的通道发生故障，而造成两台磁盘机的同时失效，可将两台驱动器分别连接到两个磁盘控制器上，而两个控制器又分别连到两个通道上，每次写将同时将数据写到两个处于不同控制器下的磁盘上。如果某个通道或控制器发生故障，另-通道上的磁盘仍能正常工作，不会造成数据的丢失，但同时须立即发出警告，以便尽快恢复磁盘双工功能。由于每个磁盘有自己的独立通道，故可同时将数据写入磁盘，而读数据时，则可从相应快的通道上读取数据，因而加快了数据的读取速度。

3.基于集群技术的容错功能

高级系统容错技术SFTII是基于集群技术来实现容错的，所谓集群，是指由一组互连的自主计算机组成统一的计算机系统，给人们的感觉是，它们是一台机器。利用集群系统不仅可提高系统的并行处理能力,还可用于提高系统的可用性。其工作模式主要有以下三种方式:
(1) 双机热备份模式。系统中备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。平时主服务器运行，备份服务器则时刻监视着主服务器的运行，一旦主服务器出现故障，备份服务器便立即接替主服务器的工作而成为系统中的主服务器，修复后的服务器再作为备份服务器。
(2)双机互为备份模式。这种模式中，两台服务器均为在线服务器，它们各自完成自己的任务;同时它们还接收另一台服务器发来的备份数据，作为对方的备份服务器。如果其中的一台服务器发生故障，则由另一台服务器为客户机提供服务;当故障服务器修复并重新连到网上后，已被迁移到无故障服务器上的服务功能，将被返回，恢复正常工作。
(3)公用磁盘模式。为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公共磁盘被划分为若千个卷，每台计算机使用一个卷。如果某台计算机发生故障，此时系统将重新进行配置，根据某种调度策略来选择另-台替代计算机，后者对发生故障的计算机的卷拥有所有权，从而来接替故障计算机所承担的任务。

4.后备系统

后备系统利用系统程序将磁盘数据保存到另一存储设备，如磁带、光盘或另一个磁盘上。建立后备系统后，由于自然因素，或者系统发生故障或病毒感染而造成的数据错误和丢失时，便可从备份中进行恢复，从而保证系统的安全。

8.5 数据一致性控制

1.事务

当一数据被分散地存放在- -个文件的不同记录中，或多个文件中时，可采用事务来保证该数据的一致性。事务是用于访问和修改各种数据项的一-个程序单位， 它可以被看作是一系列的读和写操作。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能以托付操作来终止事务。只要有一个读和写操作失败，便须执行天折操作:为了保证数据的一致性， 此时，须将该事务内刚被修改的数据项恢复成原来的情况。可见，事务操作具有原子性。
事务操作的原子性须借助于存放在稳定存储器中的事务记录表来实现，其中的每条记录描述了事务运行中的重要操作，如修改操作、开始事务、托付事务和天折事务等。在一个事务Ti开始执行时，<Ti开始>记录被写入事务记录表中: Ti执行期间，在Ti的任何写(含修改)操作之前，便写一适当的新记录到事务记录表中，该记录中包含了事务名、被修改的数据项名、修改前的数据项旧值和修改后的数据项新值等信息;当进行T;托付时，把一个<Ti托付>记录写入事务记录表中。如果系统发生故障，系统便可通过事务记录表对以前所发生的事务进行清理。对事务T，如果在事务记录表中既包含了<Ti开始> 记录，又包含了<Ti托付>记录，则系统应执行redo <Ti> 过程，把所有已被事务修改过的数据设置成新值:如果在事务记录表中只包含了<Ti开始> 记录，而无<Ti托付>记录，则应执行undo <Ti> 过程，将所有已被修改过的数据，恢复成修改前的值。

2.重要数据结构的一致性检查

文件系统工作过程中，经常要读取磁盘块，进行修改后再写回磁盘。如果在修改过的磁盘块全部写回之前，系统发生故障，则文件系统有可能会处于不一致状态。当未被写回的内容涉及到索引结点、目录或空闲盘块表等重要数据结构时，该问题会显得更严重。因此，很多计算机都带有实用程序以检查文件系统的一致性， 在系统启动时，尤其是崩溃之后重新启动时，可运行该程序进行一致性的检查。
(1)盘块的一致性检查。为了对盘块进行一致性检查，检查程序可构造一张表，每个表项对应于一个磁盘块，其中有两个初值为0的计数器，分别用来登记该盘块在文件中出现的次数，以及它作为空闲盘块出现的次数。检查一个盘块在文件中出现的次数可通过读取FAT或索引结点(具体与文件的物理结构有关)来进行，而检查一个盘块作为空闲盘块出现的次数则可通过读取位示图或空闲盘块表或链(具体与文件存储空间中空闲盘块的管理方式有关)来进行。如果文件系统-致,则对应于每个盘块的两个计数器，要么第一个计数器的值为1，要么第二个计数器的值为1;否则便说明发生了某种错误，应采取相应措施进行处理，并向系统汇报情况。
(2)链接计数的一致性检查。在利用链接方式共享文件的系统中，对应于一个文件的目录项数与该文件的索引结点中的链接计数必须-致。检查程序可通过读取所有的目录来获得对应于每个文件的目录项数，并与相应文件索引结点中的链接计数进行比较，如果两者一致，表示是正确的:否则，便是发生了链接数据不一-致的错误， 应采取相应的处理措施，并进行汇报。