磁盘存储器的管理课件

第八章磁盘存储器的管理8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制第八章磁盘存储器的管理8.1外存的组织方式文件的物理结构直接与外存的组织方式有关。

(1)连续组织方式

(2)链接组织方式

(3)索引组织方式

8.1外存的组织方式文件的物理结构直接与外存的组织方式有关。8.1外存的组织1.连续组织方式：为每一个文件分配一组相邻接的盘块，通常位于一条磁道上，读/写时不必移动磁头。8.1.1连续组织（分配）方式顺序文件1.连续组织方式：为每一个文件分配一组相邻接的盘块，图8-1磁盘空间的连续分配图8-1磁盘空间的连续分配2.连续分配的主要优缺点主要优点：

(1)简单,顺序访问容易，且支持顺序存取和随机存取

(2)顺序存取速度快，所需的磁盘寻道次数和寻道时间最少。主要缺点：

（1）要求有连续的存储空间。磁盘被无数次的划分后易形成外存的碎片，同样可用“紧凑”的方法解决。但花费大量机器时间。（2）必须事先知道文件的长度。

（3）不能灵活地删除和插入记录。

（4）对于那些动态增长的文件，很难知道文件的最终大小，很难为其分配空间；即使能知道最终大小，预分配会造成大量空间的长期闲置。2.连续分配的主要优缺点主要优点：主要缺点：概念:

一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。分类：隐式链接、显示链接。8.1.2链接组织（分配）方式1.隐式链接采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。

概念:8.1.2链接组织（分配）方式1.隐式链接图8-2磁盘空间的链接式分配文件图8-2磁盘空间的链接式分配文件缺点：只适合顺序访问随机访问效率极低，比如要访问文件的第100个盘块，则需要启动磁盘100次，每次需要几十ms。解决方法：以簇为单位，假设一个簇包含4个块，这样访问文件的第100个盘块，则需启动25次磁盘，查找时间成倍减少；但增加了内部碎片。缺点：2.显式链接图8-3显式链接结构（文件分配表）

文件分配表FAT——该表在整个磁盘仅设一张。把用于链接文件各物理块的指针显式地存放在内存的FAT表中。2.显式链接图8-3显式链接结构（文件分配表）MS-DOS的文件物理结构1011MS-DOS的文件物理结构1011优点:

（1）采取离散分配方式，消除了外部碎片问题，提高了磁盘空间利用率；（2）有利于文件动态增长，无须事先知道文件的大小。对文件的插入和删除也十分方便;缺点：（1）存取速度慢，不适于随机存取（直接存取）;

（2）可靠性问题，如指针出错;

（3）更多的寻道次数和寻道时间;

（4）链接指针占用一定的空间（隐式链接）;

（5）FAT需占用较大的内存空间（显式链接）；3.链接组织方式优缺点优点:3.链接组织方式优缺点8.1.3FAT技术

微软公司早、中期的操作系统采用FAT技术，主要有12位的FAT、16位的FAT、32位的FAT。引入“卷”的概念，一个卷即一个分区，最多可以有四个卷，每卷划出单独区域存放自己的目录、FAT表、逻辑驱动器字母。现代操作系统中，一个物理磁盘可以有多个卷，一个卷也可以由多个物理磁盘组成。8.1.3FAT技术1. FAT12

1)早期的FAT12文件系统

FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。1. FAT12

1)早期的FAT12文件系统图8-4MS-DOS的文件物理结构图8-4MS-DOS的文件物理结构

2)以簇为单位的FAT12文件系统

如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。为此，引入了簇(cluster)的概念。优点：能适应磁盘容量不断增大的情况，还可以减少FAT表中的项数，减少FAT所占的内存空间。缺点：增加了簇内的碎片2)以簇为单位的FAT12文件系统

如果把每个盘

2. FAT16

FAT12表中的表项最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。

3. FAT32

由于FAT16表的长度只有65535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加FAT表的长度，这样也就由FAT16演变为FAT32。2. FAT16

FAT12表中的表项最多第8章磁盘存储器的管理课件8.1.4NTFS的文件组织方式

1.NTFS新特征

NTFS(NewTechnologyFileSystem)是一个专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP及后续的WindowsOS。

（1）使用了64位磁盘地址；

（2）支持长文件名（单个文件255，绝对路径名32767）；

（3）具有系统容错功能；

（4）保证系统中数据的一致性。8.1.4NTFS的文件组织方式

1.NTFS新特

2.磁盘组织

NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即：使NTFS具有了与磁盘物理块大小无关的独立性。2.磁盘组织

NTFS是以簇作为磁盘空间分配和回收

3.文件的组织

在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(MasterFileTable)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。3.文件的组织

在NTFS中，以卷为单位，将一个卷8.1.5索引分配

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

(1)不能支持高效的直接（随机）存取。

(2)FAT需占用较大的内存空间。

解决方法：在打开某个文件时，只需把该文件占用的盘块号调入内存即可，没必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。——索引分配方法。

8.1.5索引分配问题的引入：链接分配方式虽然解1.单级索引组织方式

一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在该索引表中。1.单级索引组织方式

索引结构优缺点：优点：支持随机存取，满足了文件动态增长、插入删除的要求，不会产生外部碎片。缺点：索引表本身带来了系统开销且索引块空间利用率低，不适合于小文件。索引结构优缺点：优点：

多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。如：盘块大小1KB，每个盘块号占4B，单级索引允许的最大文件长度为：256*1KB=256KB二级索引允许的最大文件长度为：256*256KB=64MB2.多级索引组织方式多级索引:将一个大文件的所有索引表（二级索引)的地址放i.addr(9)…图8-8UNIXSystemV混合索引方式3.增量式索引组织方式（ P258）目的：照顾小、中、大、特大型作业i.addr(9)…图8-8UNIXSystemV混

（1）直接地址。

用i.addr(0)~i.addr(9)来存放直接地址。假如每个盘块的大小为4KB，支持的文件最大为40KB。（2）一次间接地址。

当文件长度大于40KB时，要利用索引结点中的地址项i.addr(10)来提供一次间接地址。假如在一次间址块中可存放1K个盘块号，因而允许文件长达4MB+40KB。（3）多次间接地址。当文件长度更大时，需采用二次间址分配方式。用地址项i.addr(11)提供二次间接地址。文件最大长度可达4GB+

4MB+40KB

。同理，采用地址项i.addr(12)作为三次间接地址，其所允许的文件最大长度可达4TB+4GB+

4MB+40KB

。（1）直接地址。8.2文件存储空间的管理1.空闲表法（空白文件目录）——连续分配方式

将所有空闲块记录在一个表中，即空闲块表。2.空闲链表法

把所有空闲块链成一个链。3.位示图法

用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,分配物理块为1，否则为0。4.成组链接法

空闲盘块分成若干组，然后将其链成一个链，利用空闲盘块号栈实现分配和回收。8.2文件存储空间的管理1.空闲表法（空白文件目录）—1.空闲表法

概念：属于连续分配方式。一个连续的未分配区域称为空闲区，将系统中所有空闲区的情况用一个表格记录。如：8.2.1空闲表法和空闲链表法1.空闲表法概念：属于连续分配方式。一个连续的未分

存储空间的分配：空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。存储空间的回收：当用户撤消一个文件时，系统回收该文件所占用的空间。类似于内存回收的方法。

优点：分配速度高、可减少访问磁盘的I/O频率。

应用：对换空间、文件较小时、多媒体文件。存储空间的分配：空闲盘区的分配与内存的动态分配类似，2.空闲链表法（1）空闲盘块链：把其中所有的“空闲盘块”链在一起。

优点：分配/回收一个盘块时简单。

缺点：为一个文件分配盘块时，可能要重复操作多次。（2）空闲盘区链：把所有的“空闲区”（每个空闲区包含多个空闲块）拉成一条链。盘区分配/回收方法与内存的动态分区分配类似。常采用首次适应算法，为提高检索速度，可用显示链接方法，即在内存中建一张链接表。回收时相邻的合并。2.空闲链表法（1）空闲盘块链：把其中所有的“空闲盘块”8.2.2位示图法1.位示图(P261)图8-10位示图

位示图，通常可用m*n个位数构成，并使m*n等于磁盘的总块数。用一串二进制位反映磁盘空间的分配使用情况,

每个物理块对应一位,“1”表示对应的物理块已分配，“0”表示其对应的块未分配。8.2.2位示图法1.位示图(P261)图8-12.盘块的分配(P261)

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

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

(3)修改位示图，令map［i,j］=1。2.盘块的分配(P261)(1)顺序扫描位示图3.盘块的回收(P261)步骤：

(1)将回收盘块的盘块号转换成位示图中的行号和列号。

i=(b-1)DIVn+1商数加1

j=(b-1)MODn+1余数加1

(2)修改位示图。令map［i,j］=0。优点：

(1)易找到一个或一组相邻接的空闲盘块（只需在位示图中找出几个连续为0的位即可）。

(2)位示图小、占用空间少，因而可保存在内存中。节省了许多磁盘启动操作。此法常用于微型机和小型机中。3.盘块的回收(P261)步骤：优点：8.2.3成组链接法（自看）1.空闲盘块的组织图8-11空闲盘块的成组链接法8.2.3成组链接法（自看）1.空闲盘块的组织图82.空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。2.空闲盘块的分配与回收

在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。在系统回收空闲盘块时，须调用盘块回收过程进行8.3提高磁盘I/O速度的途径1.磁盘高速缓存的形式

是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。高速缓存在内存中可分成两种形式。

第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。8.3.1磁盘高速缓存8.3提高磁盘I/O速度的途径1.磁盘高速缓存的形式2.数据交付方式

数据交付：是指将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式，将数据交付给请求进程：

(1)数据交付。这是直接将高速缓存中的数据，传送到请求者进程的内存工作区中。

(2)指针交付。只将指向高速缓存中某区域的指针，交付给请求者进程。后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存存储空间到进程的内存工作区的时间。2.数据交付方式数据交付：是指将磁盘高速缓存中的3.置换算法高速缓存满时，存在置换问题。较常用的置换算法仍然是最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU等。

由于请求调页中的联想存储器与高速缓存(磁盘I/O中)的工作情况不同，因而使得在置换算法中所应考虑的问题也有所差异。因此，现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：

(1)访问频率。(2)可预见性。(3)数据的一致性。3.置换算法高速缓存满时，存在置换问题。较常用的置基于上述考虑，在有的系统中便将高速缓存中的所有盘块数据拉成一条LRU链。

对于那些会严重影响到数据一致性的盘块数据放在LRU链的头部，使它们能被优先写回磁盘，以减少发生数据不一致性的概率。对于那些很久都可能不再使用的盘块数据，也放在LRU链的头部，使它们能被优先写回磁盘，可以尽早地腾出高速缓存的空间。对于那些可能在不久之后便要再使用的盘块数据，应挂在LRU链的尾部，以便在不久以后需要时，只要该数据块尚未从链中移至链首而被写回磁盘，便可直接到高速缓存中(即LRU链中)去找到它们。基于上述考虑，在有的系统中便将高速缓存中的所有盘块数据拉4.周期性地写回磁盘为防止那些经常被访问且已经被修改的数据丢失：

在UNIX系统中：专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。

而在MS-DOS中：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-throughcache)。优点：修改数据不会丢失不足：频繁地启动磁盘4.周期性地写回磁盘为防止那些经常被访问且已经被8.3.2提高磁盘I/O速度的其它方法

为了减少磁盘I/O的时间，除了在系统中设置磁盘高速缓存外，还有下面几种方法，它们已被许多系统采用。1．提前读(Read-ahead)因为用户(进程)对文件进行访问时，经常采用顺序访问方式，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式。优点：减少启动I/O的次数，大大减少了读数据的时间。这也就等效于提高了磁盘I/O的速度。“提前读”功能已被广泛采用，如在UNIX系统、OS/2，以及在3Plus和Netware等的网络OS中，都已采用该功能。8.3.2提高磁盘I/O速度的其它方法为了减少磁

2．延迟写空闲缓冲区链2．延迟写空闲缓冲区链

3．优化物理块的分布另一种提高磁盘I/O速度的重要措施是优化文件物理块的分布，使磁头的移动距离最小。

离散组织方式（链接、索引），如果安排的过于分散，会增加磁头的移动距离。3．优化物理块的分布

4．虚拟盘（RAM）所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。虚拟盘的主要问题是：它是易失性存储器，故一旦系统或电源发生故障，或系统再启动时，原来保存在虚拟盘中的数据将会丢失。因此，虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。

虚拟盘与磁盘高速缓存的主要区别在于:虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。4．虚拟盘（RAM）8.3.3廉价磁盘冗余阵列（RAID）它是利用一台磁盘阵列控制器，来统一管理和控制一组（几台到几十台）磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。数据的存取方式如下：

1．并行交叉存取

系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。8.3.3廉价磁盘冗余阵列（RAID）

2．RAID的分级

RAID被分为不同的等级，功能依次增强。在刚被推出时，是分成6级的，即RAID0级至RAID5级，后来又增加了RAID6级和RAID7级。

(1)RAID0级。本级仅提供了并行交叉存取。它虽能有效地提高磁盘I/O速度，但并无冗余校验功能，致使磁盘系统的可靠性不好。

(2)RAID1级。它具有磁盘镜像功能，故其比传统的镜像盘速度快，但其磁盘容量的利用率只有50%，它是以牺牲磁盘容量为代价的。2．RAID的分级（3）RAID2级。一般不用，与RAID3级相似，数据按位或字节拆分到各驱动器上。（4）RAID3级。具有并行传输功能的磁盘阵列。它利用一台奇偶校验盘。（5）RAID4级。数据按扇区拆分到各个驱动器上，是一种具有独立传送功能的磁盘阵列。每个驱动器都各有自己独立的数据通路，独立地进行读/写，用一台奇偶校验盘。（6）RAID5级。与RAID组是方式类似，无专门的校验盘。用来进行纠错的校验信息，是以螺旋(Spiral)方式散布在所有数据盘上。（3）RAID2级。一般不用，与RAID3级相似，数据按（7）RAID6级和RAID7级。这是强化了的RAID。在RAID6级的阵列中，设置了一个专用的、可快速访问的异步校验盘。RAID7级是对RAID6级的改进，在该阵列中的所有磁盘，都具有较高的传输速率和优异的性能，是目前最高档次的磁盘阵列，但其价格也较高。

3．RAID的优点

(1)可靠性高。

（2）磁盘I/O速度高。

（3）性能/价格比高。（7）RAID6级和RAID7级。这是强化了的RAID。8.4提高磁盘可靠性的技术影响文件安全性的主要因素：

(1)人为因素：通过存取控制机制来防止由人为因素所造成的文件不安全性。

(2)系统因素：通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。

(3)自然因素：通过“后备系统”来防止由自然因素(随着时间的推移磁盘上的数据可能发生溢出或逐渐消失）所造成的不安全性。

本小节讨论磁盘容错技术。8.4提高磁盘可靠性的技术影响文件安全性的主要因素：

容错技术：是通过在系统中设置冗余部件的方法，来提高系统可靠性的一种技术。

磁盘容错技术（系统容错技术SFT）：则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的一种技术。具体可分以下三个级别：容错技术：是通过在系统中设置冗余部件的方法，来提高系8.4.1第一级容错技术SFT-Ⅰ主要用于防止因磁盘表面缺陷所造成的数据丢失。

采取的措施：

1.双份目录和双份文件分配表

2.热修复重定向和写后读校验(1)热修复重定向(Hot-Redirection)。

在磁盘中划出一部分作为热修复重定向区，存放坏磁道的待写数据。(2)写后读校验(ReadafterwriteVerification)方式。

8.4.1第一级容错技术SFT-Ⅰ采取的措施：2.8.4.2第二级容错技术SFT-Ⅱ为了防止磁盘驱动器发生故障而造成的数据丢失。

采取的措施：1.磁盘镜像(DiskMirroring)

图8-13磁盘镜像示意

增设一个完全相同的磁盘驱动器（磁盘）。

优点：磁盘驱动器发生故障时切换，仍能正常工作。

缺点：磁盘的利用率为50％。8.4.2第二级容错技术SFT-Ⅱ采取的措施：图8-132.磁盘双工(DiskDuplexing)

图8-14磁盘双工示意

为防止磁盘控制器/通道发生故障，将两台磁盘驱动器分别接两个磁盘控制器/通道。2.磁盘双工(DiskDuplexing)图8-14自看3.基于集群技术的容错功能自看3.基于集群技术的容错功能8.5数据一致性控制8.5.1事务1.事务的定义

事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看作是一系列相关读和写操作。

数据一致性问题是指，保存在多个文件中的同一数据，在任何情况下都必需能保证相同。

如：某种商品的进价有错时，必须同时修改流水账、付费账、分类账及总账等一系列文件中的该商品价格。8.5数据一致性控制8.5.1事务事务的特性

（1）原子性。要么全部完成，要么一个都不改。

（2）一致性。事务完成时，必须使所有的数据都保持一致状态。

（3）隔离性。一个事务对数据所做的修改，必须与任何其他与之并发的事务相隔离。

（4）持久性。事务完成之后，它对系统的影响是永久性的。事务的特性

（1）原子性。要么全部完成，要么一个都不2.事务记录(TransactionRecord)概念：用来记录在事务运行时数据项修改的全部信息，故又称为“运行记录”（Log）。该记录包括以下字段：事务名：用于标识该事务的惟一名字；

数据项名：它是被修改数据项的惟一名字；

旧值：修改前数据项的值；新值：修改后数据项将具有的值。如果系统发生故障时，系统便可通过事务记录表对以前所发生的事务进行清理（redo(Ti)/undo(Ti)）。2.事务记录(TransactionRecord)概念3.恢复算法

利用事务记录表，系统能处理任何故障，不致造成存储器中信息的丢失。恢复算法可利用以下两个过程：

(1)undo〈Ti〉。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。

(2)redo〈Ti〉。该过程能把所有被事务Ti修改过的数据，设置为新值。如果系统发生故障，系统应对以前所发生的事务进行清理。3.恢复算法利用事务记录表，系统能处理任何故障，8.5.2检查点1.检查点(CheckPoints)的作用

引入检查点的主要目的，是为了避免系统发生故障时需清理大量记录，因此对事务记录表中事务记录的清理工作经常化，即每隔一定时间便做一次下述工作（建立检查点，保存系统状态）：

首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中；

其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；

然后是将事务记录表中的〈检查点〉记录，输出到稳定存储器中；

最后是把检查点记录在事务记录表中地址写入一个“重新开始文件”中。（每当出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。）由此推出新的恢复算法：8.5.2检查点1.检查点(CheckPoints2.新的恢复算法（？）

当系统出现故障时，恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。如果把所有在事务Ti以后开始执行的事务表示为事务集T，则新的恢复操作要求是：对所有在T中的事务TK,如果在事务记录表中出现了〈TK托付〉记录，则执行redo〈TK〉操作；反之，如果在事务记录表中并未出现〈TK托付〉记录，则执行undo〈TK〉操作。2.新的恢复算法（？）当系统出现故障时，恢复例8.5.3并发控制实现：除了信号量机制外，常用的是比较简单的、且较灵活的同步机制——锁。1.利用互斥锁实现“顺序性”仅允许一个事务对相应对象执行读或写操作。2.利用互斥锁和共享锁实现顺序性

共享锁允许多个事务对相应对象执行读操作，而不允许任何一个执行写操作。概念：在多用户系统和计算机网络环境下，由于事务具有原子性，使各个事务对数据项的修改是互斥的，即使各个事务按某种次序依次执行（顺序性）。8.5.3并发控制实现：除了信号量机制外，常用的是比较简8.5.4重复数据的数据一致性问题1.重复文件的一致性图8-18UNIX类型的目录8.5.4重复数据的数据一致性问题1.重复文件的一致性2.链接数一致性检查

为每个盘块建立一个表项，其中含有该索引结点号的计数值。在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值（共享文件的用户数）加以比较，如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。如果索引结点中的链接计数count值大于计数器表中相应索引结点号的计数值。如果出现count值小于计数器表中索引结点号计数值的情况时，就有潜在的危险。2.链接数一致性检查为每个盘块建立一个表项，其中第八章磁盘存储器的管理8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制第八章磁盘存储器的管理8.1外存的组织方式文件的物理结构直接与外存的组织方式有关。

(1)连续组织方式

(2)链接组织方式

(3)索引组织方式

8.1外存的组织方式文件的物理结构直接与外存的组织方式有关。8.1外存的组织1.连续组织方式：为每一个文件分配一组相邻接的盘块，通常位于一条磁道上，读/写时不必移动磁头。8.1.1连续组织（分配）方式顺序文件1.连续组织方式：为每一个文件分配一组相邻接的盘块，图8-1磁盘空间的连续分配图8-1磁盘空间的连续分配2.连续分配的主要优缺点主要优点：

(1)简单,顺序访问容易，且支持顺序存取和随机存取

(2)顺序存取速度快，所需的磁盘寻道次数和寻道时间最少。主要缺点：

（1）要求有连续的存储空间。磁盘被无数次的划分后易形成外存的碎片，同样可用“紧凑”的方法解决。但花费大量机器时间。（2）必须事先知道文件的长度。

（3）不能灵活地删除和插入记录。

（4）对于那些动态增长的文件，很难知道文件的最终大小，很难为其分配空间；即使能知道最终大小，预分配会造成大量空间的长期闲置。2.连续分配的主要优缺点主要优点：主要缺点：概念:

一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。分类：隐式链接、显示链接。8.1.2链接组织（分配）方式1.隐式链接采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。

概念:8.1.2链接组织（分配）方式1.隐式链接图8-2磁盘空间的链接式分配文件图8-2磁盘空间的链接式分配文件缺点：只适合顺序访问随机访问效率极低，比如要访问文件的第100个盘块，则需要启动磁盘100次，每次需要几十ms。解决方法：以簇为单位，假设一个簇包含4个块，这样访问文件的第100个盘块，则需启动25次磁盘，查找时间成倍减少；但增加了内部碎片。缺点：2.显式链接图8-3显式链接结构（文件分配表）

文件分配表FAT——该表在整个磁盘仅设一张。把用于链接文件各物理块的指针显式地存放在内存的FAT表中。2.显式链接图8-3显式链接结构（文件分配表）MS-DOS的文件物理结构1011MS-DOS的文件物理结构1011优点:

（1）采取离散分配方式，消除了外部碎片问题，提高了磁盘空间利用率；（2）有利于文件动态增长，无须事先知道文件的大小。对文件的插入和删除也十分方便;缺点：（1）存取速度慢，不适于随机存取（直接存取）;

（2）可靠性问题，如指针出错;

（3）更多的寻道次数和寻道时间;

（4）链接指针占用一定的空间（隐式链接）;

（5）FAT需占用较大的内存空间（显式链接）；3.链接组织方式优缺点优点:3.链接组织方式优缺点8.1.3FAT技术

微软公司早、中期的操作系统采用FAT技术，主要有12位的FAT、16位的FAT、32位的FAT。引入“卷”的概念，一个卷即一个分区，最多可以有四个卷，每卷划出单独区域存放自己的目录、FAT表、逻辑驱动器字母。现代操作系统中，一个物理磁盘可以有多个卷，一个卷也可以由多个物理磁盘组成。8.1.3FAT技术1. FAT12

1)早期的FAT12文件系统

FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。1. FAT12

1)早期的FAT12文件系统图8-4MS-DOS的文件物理结构图8-4MS-DOS的文件物理结构

2)以簇为单位的FAT12文件系统

如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。为此，引入了簇(cluster)的概念。优点：能适应磁盘容量不断增大的情况，还可以减少FAT表中的项数，减少FAT所占的内存空间。缺点：增加了簇内的碎片2)以簇为单位的FAT12文件系统

如果把每个盘

2. FAT16

FAT12表中的表项最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。

3. FAT32

由于FAT16表的长度只有65535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加FAT表的长度，这样也就由FAT16演变为FAT32。2. FAT16

FAT12表中的表项最多第8章磁盘存储器的管理课件8.1.4NTFS的文件组织方式

1.NTFS新特征

NTFS(NewTechnologyFileSystem)是一个专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP及后续的WindowsOS。

（1）使用了64位磁盘地址；

（2）支持长文件名（单个文件255，绝对路径名32767）；

（3）具有系统容错功能；

（4）保证系统中数据的一致性。8.1.4NTFS的文件组织方式

1.NTFS新特

2.磁盘组织

NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即：使NTFS具有了与磁盘物理块大小无关的独立性。2.磁盘组织

NTFS是以簇作为磁盘空间分配和回收

3.文件的组织

在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(MasterFileTable)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。3.文件的组织

在NTFS中，以卷为单位，将一个卷8.1.5索引分配

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

(1)不能支持高效的直接（随机）存取。

(2)FAT需占用较大的内存空间。

解决方法：在打开某个文件时，只需把该文件占用的盘块号调入内存即可，没必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。——索引分配方法。

8.1.5索引分配问题的引入：链接分配方式虽然解1.单级索引组织方式

一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在该索引表中。1.单级索引组织方式

索引结构优缺点：优点：支持随机存取，满足了文件动态增长、插入删除的要求，不会产生外部碎片。缺点：索引表本身带来了系统开销且索引块空间利用率低，不适合于小文件。索引结构优缺点：优点：

多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。如：盘块大小1KB，每个盘块号占4B，单级索引允许的最大文件长度为：256*1KB=256KB二级索引允许的最大文件长度为：256*256KB=64MB2.多级索引组织方式多级索引:将一个大文件的所有索引表（二级索引)的地址放i.addr(9)…图8-8UNIXSystemV混合索引方式3.增量式索引组织方式（ P258）目的：照顾小、中、大、特大型作业i.addr(9)…图8-8UNIXSystemV混

（1）直接地址。

用i.addr(0)~i.addr(9)来存放直接地址。假如每个盘块的大小为4KB，支持的文件最大为40KB。（2）一次间接地址。

当文件长度大于40KB时，要利用索引结点中的地址项i.addr(10)来提供一次间接地址。假如在一次间址块中可存放1K个盘块号，因而允许文件长达4MB+40KB。（3）多次间接地址。当文件长度更大时，需采用二次间址分配方式。用地址项i.addr(11)提供二次间接地址。文件最大长度可达4GB+

4MB+40KB

。同理，采用地址项i.addr(12)作为三次间接地址，其所允许的文件最大长度可达4TB+4GB+

4MB+40KB

。（1）直接地址。8.2文件存储空间的管理1.空闲表法（空白文件目录）——连续分配方式

将所有空闲块记录在一个表中，即空闲块表。2.空闲链表法

把所有空闲块链成一个链。3.位示图法

用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,分配物理块为1，否则为0。4.成组链接法

空闲盘块分成若干组，然后将其链成一个链，利用空闲盘块号栈实现分配和回收。8.2文件存储空间的管理1.空闲表法（空白文件目录）—1.空闲表法

概念：属于连续分配方式。一个连续的未分配区域称为空闲区，将系统中所有空闲区的情况用一个表格记录。如：8.2.1空闲表法和空闲链表法1.空闲表法概念：属于连续分配方式。一个连续的未分

存储空间的分配：空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。存储空间的回收：当用户撤消一个文件时，系统回收该文件所占用的空间。类似于内存回收的方法。

优点：分配速度高、可减少访问磁盘的I/O频率。

应用：对换空间、文件较小时、多媒体文件。存储空间的分配：空闲盘区的分配与内存的动态分配类似，2.空闲链表法（1）空闲盘块链：把其中所有的“空闲盘块”链在一起。

优点：分配/回收一个盘块时简单。

缺点：为一个文件分配盘块时，可能要重复操作多次。（2）空闲盘区链：把所有的“空闲区”（每个空闲区包含多个空闲块）拉成一条链。盘区分配/回收方法与内存的动态分区分配类似。常采用首次适应算法，为提高检索速度，可用显示链接方法，即在内存中建一张链接表。回收时相邻的合并。2.空闲链表法（1）空闲盘块链：把其中所有的“空闲盘块”8.2.2位示图法1.位示图(P261)图8-10位示图

位示图，通常可用m*n个位数构成，并使m*n等于磁盘的总块数。用一串二进制位反映磁盘空间的分配使用情况,

每个物理块对应一位,“1”表示对应的物理块已分配，“0”表示其对应的块未分配。8.2.2位示图法1.位示图(P261)图8-12.盘块的分配(P261)

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

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

(3)修改位示图，令map［i,j］=1。2.盘块的分配(P261)(1)顺序扫描位示图3.盘块的回收(P261)步骤：

(1)将回收盘块的盘块号转换成位示图中的行号和列号。

i=(b-1)DIVn+1商数加1

j=(b-1)MODn+1余数加1

(2)修改位示图。令map［i,j］=0。优点：

(1)易找到一个或一组相邻接的空闲盘块（只需在位示图中找出几个连续为0的位即可）。

(2)位示图小、占用空间少，因而可保存在内存中。节省了许多磁盘启动操作。此法常用于微型机和小型机中。3.盘块的回收(P261)步骤：优点：8.2.3成组链接法（自看）1.空闲盘块的组织图8-11空闲盘块的成组链接法8.2.3成组链接法（自看）1.空闲盘块的组织图82.空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。2.空闲盘块的分配与回收

在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。在系统回收空闲盘块时，须调用盘块回收过程进行8.3提高磁盘I/O速度的途径1.磁盘高速缓存的形式

是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。高速缓存在内存中可分成两种形式。

第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。8.3.1磁盘高速缓存8.3提高磁盘I/O速度的途径1.磁盘高速缓存的形式2.数据交付方式

数据交付：是指将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式，将数据交付给请求进程：

(1)数据交付。这是直接将高速缓存中的数据，传送到请求者进程的内存工作区中。

(2)指针交付。只将指向高速缓存中某区域的指针，交付给请求者进程。后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存存储空间到进程的内存工作区的时间。2.数据交付方式数据交付：是指将磁盘高速缓存中的3.置换算法高速缓存满时，存在置换问题。较常用的置换算法仍然是最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU等。

由于请求调页中的联想存储器与高速缓存(磁盘I/O中)的工作情况不同，因而使得在置换算法中所应考虑的问题也有所差异。因此，现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：

(1)访问频率。(2)可预见性。(3)数据的一致性。3.置换算法高速缓存满时，存在置换问题。较常用的置基于上述考虑，在有的系统中便将高速缓存中的所有盘块数据拉成一条LRU链。

对于那些会严重影响到数据一致性的盘块数据放在LRU链的头部，使它们能被优先写回磁盘，以减少发生数据不一致性的概率。对于那些很久都可能不再使用的盘块数据，也放在LRU链的头部，使它们能被优先写回磁盘，可以尽早地腾出高速缓存的空间。对于那些可能在不久之后便要再使用的盘块数据，应挂在LRU链的尾部，以便在不久以后需要时，只要该数据块尚未从链中移至链首而被写回磁盘，便可直接到高速缓存中(即LRU链中)去找到它们。基于上述考虑，在有的系统中便将高速缓存中的所有盘块数据拉4.周期性地写回磁盘为防止那些经常被访问且已经被修改的数据丢失：

在UNIX系统中：专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。

而在MS-DOS中：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-throughcache)。优点：修改数据不会丢失不足：频繁地启动磁盘4.周期性地写回磁盘为防止那些经常被访问且已经被8.3.2提高磁盘I/O速度的其它方法

为了减少磁盘I/O的时间，除了在系统中设置磁盘高速缓存外，还有下面几种方法，它们已被许多系统采用。1．提前读(Read-ahead)因为用户(进程)对文件进行访问时，经常采用顺序访问方式，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式。优点：减少启动I/O的次数，大大减少了读数据的时间。这也就等效于提高了磁盘I/O的速度。“提前读”功能已被广泛采用，如在UNIX系统、OS/2，以及在3Plus和Netware等的网络OS中，都已采用该功能。8.3.2提高磁盘I/O速度的其它方法为了减少磁

2．延迟写空闲缓冲区链2．延迟写空闲缓冲区链

3．优化物理块的分布另一种提高磁盘I/O速度的重要措施是优化文件物理块的分布，使磁头的移动距离最小。

离散组织方式（链接、索引），如果安排的过于分散，会增加磁头的移动距离。3．优化物理块的分布

4．虚拟盘（RAM）所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。虚拟盘的主要问题是：它是易失性存储器，故一旦系统或电源发生故障，或系统再启动时，原来保存在虚拟盘中的数据将会丢失。因此，虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。

虚拟盘与磁盘高速缓存的主要区别在于:虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。4．虚拟盘（RAM）8.3.3廉价磁盘冗余阵列（RAID）它是利用一台磁盘阵列控制器，来统一管理和控制一组（几台到几十台）磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。数据的存取方式如下：

1．并行交叉存取

系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。8.3.3廉价磁盘冗余阵列（RAID）

2．RAID的分级

RAID被分为不同的等级，功能依次增强。在刚被推出时，是分成6级的，即RAID0级至RAID5级，后来又增加了RAID6级和RAID7级。

(1)RAID0级。本级仅提供了并行交叉存取。它虽能有效地提高磁盘I/O速度，但并无冗余校验功能，致使磁盘系统的可靠性不好。

(2)RAID1级。它具有磁盘镜像功能，故其比传统的镜像盘速度快，但其磁盘容量的利用率只有50%，它是以牺牲磁盘容量为代价的。2．RAID的分级（3）RAID2级。一般不用，与RAID3级相似，数据按位或字节拆分到各驱动器上。（4）RAID3级。具有并行传输功能的磁盘阵列。它利用一台奇偶校验盘。（5）RAID4级。数据按扇区拆分到各个驱动器上，是一种具有独立传送功能的磁盘阵列。每个驱动器都各有自己独立的数据通路，独立地进行读/写，用一台奇偶校验盘。（6）RAID5级。与RAID组是方式类似，无专门的校验盘。用来进行纠错的校验信息，是以螺旋(Spiral)方式散布在所有数据盘上。（3）RAID2级。一般不用，与RAID3级相似，数据按（7）RAID6级和RAID7级。这是强化了的RAID。在RAID6级的阵列中，设置了一个专用的、可快速访问的异步校验盘。RAID7级是对RAID6级的改进，在该阵列中的所有磁盘，都具有较高的传输速率和优异的性能，是目前最高档次的磁盘阵列，但其价格也较高。

3．RAID的优点

(1)可靠性高。

（2）磁盘I/O速度高。

（3）性能/价格比高。（7）RAID6级和RAID7级。这是强化了的RAID。8.4提高磁盘可靠性的技术影响文件安全性的主要因素：

(1)人为因素：通过存取控制机制来防止由人为因素所造成的文件不安全性。

(2)系统因素：通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。

(3)自然因素：通过“后备系统”来防止由自然因素(随着时间的推移磁盘上的数据可能发生溢出或逐渐消失）所造成的不安全性。

本小节讨论磁盘容错技术。8.4提高磁盘可靠性的技术影响文件安全性的主要因素：

容错技术：是通过在系统中设置冗余部件的方法，来提高系统可靠性的一种技术。

磁盘容错技术（系统容错技术SFT）：则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的一种技术。具体可分以下三个级别：容错技术：是通过在系统中设置冗余部件的方法，来提高系8.4.1第一级容错技术SFT-Ⅰ主要用于防止因磁盘表面缺陷所造成的数据丢失。

采取的措施：

1.双份目录和双份文件分配表

2.热修复重定向和写后读校验(1)热修复重定向(Hot-Redirection)。

在磁盘中划出一部分作为热修复重定向区，存放坏磁道的待写数据。(2)写后读校验(ReadafterwriteVerification)方式。

8.4.1第一级容错技术SFT-Ⅰ采取的措施：2.8.4.2第二级容错技术SFT-Ⅱ为了防止磁盘驱动器发生故障而造成的数据丢失。

采取的措施：1.磁盘镜像(DiskMirroring)

图8-13磁盘镜像示意

增设一个完全相同的磁盘驱动器（磁盘）。

优点：磁盘驱动器发生故障