第9章--磁盘存储器管理

1、第第7章章 磁盘存储器管理磁盘存储器管理 计算机系统中，计算机系统中，文件文件是存放在外存中的，是存放在外存中的，文件系统文件系统必须实必须实现磁盘存储空间的管理、文件名到文件存储空间的映射等功能；现磁盘存储空间的管理、文件名到文件存储空间的映射等功能；另一方面，另一方面，虚拟存储器虚拟存储器的实现也需要容量大、存取速度快的磁的实现也需要容量大、存取速度快的磁盘存储器，故如何提高磁盘存储器的性能，直接影响到整个计盘存储器，故如何提高磁盘存储器的性能，直接影响到整个计算机性能的提高。算机性能的提高。 本章重点介绍磁盘存储器管理的下面几个主要任务：本章重点介绍磁盘存储器管理的下面几个主要任务： 为

2、文件分配必要的存储空间；为文件分配必要的存储空间； 合理地组织文件的存取方式，以提高对文件的访问速度；合理地组织文件的存取方式，以提高对文件的访问速度； 提高磁盘存储空间的利用率；提高磁盘存储空间的利用率； 提高对磁盘的提高对磁盘的I/O速度，以改善文件系统的性能；速度，以改善文件系统的性能； 采取必要的冗余措施，来确保文件系统的可靠性。采取必要的冗余措施，来确保文件系统的可靠性。 磁盘磁盘I/O速度的高低，将直接影响到文件系统的性能。提高磁盘速度的高低，将直接影响到文件系统的性能。提高磁盘I/O速度的主要途径有：速度的主要途径有： 选择性能好的磁盘；选择性能好的磁盘； 采用好的磁盘调度算法；

3、采用好的磁盘调度算法； 设置磁盘高速缓冲区。设置磁盘高速缓冲区。 7.1 磁盘I/O（1）7.1 磁盘磁盘I/O7.1.1 磁盘性能简述磁盘性能简述 数据的组织数据的组织 磁盘包含一或多个磁盘包含一或多个盘片盘片，每片分，每片分两面两面，每面又可分成若干条，每面又可分成若干条磁道磁道，磁道之间留有必要的磁道之间留有必要的空隙空隙。 为简单起见，在每条磁道上存储为简单起见，在每条磁道上存储相同数目相同数目的二进制位。因而，内的二进制位。因而，内层磁道的层磁道的存储密度存储密度（每英寸所存储的位数）较外层磁道的密度高。每（每英寸所存储的位数）较外层磁道的密度高。每条磁通又分成若干个条磁通又分成若干

4、个扇区扇区，每个扇区的大小相当于一个盘块，各扇区，每个扇区的大小相当于一个盘块，各扇区之间保留一定的间隙。之间保留一定的间隙。 在磁盘存储数据前要在磁盘存储数据前要格式化格式化磁盘。磁盘。7.1 磁盘I/O（2）9.1 磁盘磁盘I/O7.1.1 磁盘性能简述磁盘性能简述 磁盘的类型磁盘的类型 磁盘可以从不同的角度进行分类：硬盘和软盘、单片盘和多片盘、磁盘可以从不同的角度进行分类：硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头磁盘等。固定头磁盘和活动头磁盘等。 固定头磁盘：每条磁道固定头磁盘：每条磁道都有一个读都有一个读/写磁头，可对磁道写磁头，可对磁道并行并行读读/写，写，I/O速度快，适用于

5、大容量磁盘。速度快，适用于大容量磁盘。 移动头磁盘：每个盘面移动头磁盘：每个盘面一个磁头，该磁头能移动以进行寻道。只能一个磁头，该磁头能移动以进行寻道。只能进行进行串行串行读读/写，写， I/O速度较慢，但结构简单，速度较慢，但结构简单，曾经曾经广泛用于中、小型广泛用于中、小型磁盘设备中。磁盘设备中。 磁盘的访问时间磁盘的访问时间 寻道时间寻道时间Ts：是把磁臂从当前位置移动到指定磁道上所经历的时间。是把磁臂从当前位置移动到指定磁道上所经历的时间。 旋转延迟时间旋转延迟时间Tr：是指定扇区移动到磁头下面所经历的时间。是指定扇区移动到磁头下面所经历的时间。 传输时间传输时间Tt：指数据从磁盘读出

6、，或向磁盘写入数据所经历的时间。指数据从磁盘读出，或向磁盘写入数据所经历的时间。 在访问时间中，寻道时间和旋转延迟时间，基本上都与所读在访问时间中，寻道时间和旋转延迟时间，基本上都与所读/写数写数据的多少无关，而且它通常是占据了访问时间的大头。可见，据的多少无关，而且它通常是占据了访问时间的大头。可见，适当地适当地集中数据（不要太零散）传输，将有利于提高传输效率。集中数据（不要太零散）传输，将有利于提高传输效率。 7.1 磁盘I/O（3）7.1 磁盘磁盘I/O7.1.2 早期的磁盘调度算法早期的磁盘调度算法 当有多个进程都请求访问磁盘时，应使各进程对磁盘的当有多个进程都请求访问磁盘时，应使各进

7、程对磁盘的平均访平均访问时间问时间（主要是寻道）（主要是寻道） 最小。因此，磁盘调度的最小。因此，磁盘调度的目标目标应是使磁盘的平应是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有：先来先服务；最均寻道时间最少。目前常用的磁盘调度算法有：先来先服务；最短寻道时间优先；扫描算法；循环扫描算法等。短寻道时间优先；扫描算法；循环扫描算法等。 先来先服务先来先服务 根据进程请求访问磁盘的根据进程请求访问磁盘的先后次序先后次序进行调度。进行调度。优点：优点：公平、简单，公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期

8、得不到满足的情况。得不到满足的情况。缺点：缺点：未对寻道进行优化，致使平均寻道时间可未对寻道进行优化，致使平均寻道时间可能较长。仅适用于请求磁盘能较长。仅适用于请求磁盘I/O的的进程数目进程数目较少的场合。较少的场合。 最短寻道时间优先最短寻道时间优先 算法选择要求访问的磁道与当前磁头所在的磁道算法选择要求访问的磁道与当前磁头所在的磁道距离最近距离最近的进程，的进程，以使每次的寻道时问最短。以使每次的寻道时问最短。存在的问题：存在的问题：可能导致某些进程发生可能导致某些进程发生“饥饥饿饿”。因为只要不断有所要访问的磁道与磁头当前所在磁道的距离较。因为只要不断有所要访问的磁道与磁头当前所在磁道的

9、距离较近的新进程到达，就会出现近的新进程到达，就会出现“老进程饥饿老进程饥饿”现象。这种调度算法不能现象。这种调度算法不能保证保证平均寻道时间平均寻道时间最短。最短。 7.1 磁盘I/O（4）7.1 磁盘磁盘I/O7.1.3 各种扫描算法各种扫描算法 扫描（扫描（SCAN）算法）算法 SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先更优先考虑的是磁头的考虑的是磁头的当前移动方向当前移动方向。在磁头正在自里向外移动时，所选择。在磁头正在自里向外移动时，所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离的下一个访问对象应是其欲访

10、问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向，自外向里移动。这时，每次选择即其要访问的磁道，在将磁臂换向，自外向里移动。这时，每次选择即其要访问的磁道，在当前磁道之内且距离最近者这样的进程来调度。当前磁道之内且距离最近者这样的进程来调度。 SCAN算法中磁头移动的规律似电梯的运行，又称为算法中磁头移动的规律似电梯的运行，又称为电梯调度算电梯调度算法法。算法既能获得较好的寻道性能，又能防止进程饥饿，被广泛用于。算法既能获得较好的寻道性能，又能防止进程饥饿，被广泛用于大、中、小型

11、机和网络中的磁盘调度。大、中、小型机和网络中的磁盘调度。 存在的问题：存在的问题：当磁头刚从里向外移动过某一磁道时，恰有一进程当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，然后再从请求访问此磁道，这时该进程必须等待，待磁头从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被严重地推迟。程的请求被严重地推迟。 7.1 磁盘I/O（5）7.1 磁盘磁盘I/O7.1.3 各种扫描算法各种扫描算法 循环扫描循环扫描CSCAN 为了减少请求进程的延迟，为了减少

12、请求进程的延迟，CSCAN算法规定磁头算法规定磁头单单向移动向移动。若规定只自里向外移动，当磁头移到最外的被访。若规定只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。道号紧接着最大磁道号构成循环，进行扫描。 采用循环扫描方式后，上述请求进程的请求延迟，将采用循环扫描方式后，上述请求进程的请求延迟，将从原来的从原来的2T减为减为T+Smax，其中，其中，T为由里向外（或相反）为由里向外（或相反）扫描完所有要访问的磁道所需的寻道时间，而扫描完所有要访问的磁道所需的寻道时间

13、，而Smax是将磁是将磁头从最外面被访问的磁道直接移到最里边欲访问的磁道所头从最外面被访问的磁道直接移到最里边欲访问的磁道所需的寻道时间。需的寻道时间。 7.1 磁盘I/O（6）7.1 磁盘磁盘I/O7.1.3 各种扫描算法各种扫描算法 N-Step-SCAN和和FSCAN调度算法调度算法 N-Step-SCAN算法：算法：SSTF、SCAN、CSCAN几种调度算法几种调度算法都可能出现磁臂停留在某处不动的情况，称为都可能出现磁臂停留在某处不动的情况，称为磁臂粘着磁臂粘着。在高。在高密度盘上更容易出现此情况。密度盘上更容易出现此情况。N-Step-SCAN算法将磁盘请求队算法将磁盘请求队列分成

14、若干个长度为列分成若干个长度为N的的子队列子队列。磁盘调度将按。磁盘调度将按FCFS算法依次算法依次处理这些子队列，而每处理一个队列时，又是按处理这些子队列，而每处理一个队列时，又是按SCAN算法。算法。这样就可避免出现粘着现象。这样就可避免出现粘着现象。N值取得很大时，其性能接近值取得很大时，其性能接近SCAN算法；算法；N=1时，则退化为时，则退化为FCFS算法。算法。 FSCAN算法：算法：本算法是本算法是N-Step-SCAN算法的简化。它只将磁算法的简化。它只将磁盘请求访问队列分成两个子队列。盘请求访问队列分成两个子队列。 一是当前所有请求磁盘一是当前所有请求磁盘I/O的进程形成的队

15、列，由磁盘调度按的进程形成的队列，由磁盘调度按SCAN算法进行处理；另一算法进行处理；另一个则是在扫描期间，新出现的所有请求磁盘个则是在扫描期间，新出现的所有请求磁盘I/O进程组成的等待进程组成的等待处理的请求队列。从而使处理的请求队列。从而使所有的新请求所有的新请求都将被推迟到下一次扫都将被推迟到下一次扫描时处理。描时处理。 连续分配要求为每一个文件分配一组连续分配要求为每一个文件分配一组相邻接相邻接的盘块。一组盘块的地址定的盘块。一组盘块的地址定义了磁盘上的一段线性地址，通常都位于一条磁道上，在进行读义了磁盘上的一段线性地址，通常都位于一条磁道上，在进行读/写时，不写时，不必移动磁头。必移

16、动磁头。 连续分配时，可把逻辑文件中的记录，顺序地存储到邻接的各物理盘块连续分配时，可把逻辑文件中的记录，顺序地存储到邻接的各物理盘块中，形成称为中，形成称为顺序文件顺序文件的物理文件。这种分配方式保证了逻辑文件中的记录的物理文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。在目录项的顺序与存储器中文件占用盘块的顺序的一致性。在目录项的“文件物理地址文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度（以字段中，记录该文件第一个记录所在的盘块号和文件长度（以盘块盘块进行计进行计量）。量）。 连续分配的主要连续分配的主要优点优点如下：顺序访问容易，支持

17、直接存取。顺序访如下：顺序访问容易，支持直接存取。顺序访问速度快，磁头的移动距离最少。问速度快，磁头的移动距离最少。 缺点缺点：要求有连续的存储空间，会产生出许多外部碎片，需花费大量：要求有连续的存储空间，会产生出许多外部碎片，需花费大量的机器时间定期地利用紧凑的方法来消除碎片。必须事先知道文件的长度。的机器时间定期地利用紧凑的方法来消除碎片。必须事先知道文件的长度。在存储空间中找出一块其大小足够的存储区将文件装入。对于那些动态增长在存储空间中找出一块其大小足够的存储区将文件装入。对于那些动态增长的文件会使大量的存储空间长期地空闲。的文件会使大量的存储空间长期地空闲。 7.2 外存分配方法（1

18、）7.2 外存分配方法外存分配方法7.2.1 连续分配连续分配 在为文件分配外存空间时所要考虑的主要在为文件分配外存空间时所要考虑的主要问题问题有：有： 怎样才能有效地利用外存怎样才能有效地利用外存空间空间； 提高对文件的访问提高对文件的访问速率速率。 常用的外存分配常用的外存分配方法方法有：连续分配；有：连续分配； 链接分配；索引分配。在链接分配；索引分配。在一个系统中，通常仅采用其中的一种方法来为文件分配外存空间。一个系统中，通常仅采用其中的一种方法来为文件分配外存空间。 7.2 外存分配方法（2）7.2 外存分配方法外存分配方法7.2.2 链接分配链接分配 思想：思想：将逻辑文件存储到外

19、存上时，并不要求为整个文件分配一块连将逻辑文件存储到外存上时，并不要求为整个文件分配一块连续的空问，而是将文件装到多个续的空问，而是将文件装到多个离散离散的盘块中。通过的盘块中。通过链接指针链接指针，将同属于，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成称为一个文件的多个离散的盘块链接成一个链表，由此所形成称为链接文件链接文件的的物理文件。物理文件。 显然这种方式消除了显然这种方式消除了外碎片外碎片，既不需事先知道文件的长度，而且对文，既不需事先知道文件的长度，而且对文件的增、修、删也很方便。链接方式又可分为隐式链接和显式链接两种。件的增、修、删也很方便。链接方式又可分为隐式链接

20、和显式链接两种。 隐式链接隐式链接 在文件目录的每个目录项中，都须含有指向链接文件在文件目录的每个目录项中，都须含有指向链接文件第一个第一个盘块和盘块和最最后一个后一个盘块的指针。而在盘块的指针。而在每个盘块每个盘块中都含有一个指向下一个盘块的指针中都含有一个指向下一个盘块的指针（每个盘块中可供用户使用的字节为盘块大小减去指针占用的字节）。（每个盘块中可供用户使用的字节为盘块大小减去指针占用的字节）。 存在问题：存在问题：只适合于顺序访问，只适合于顺序访问，随机访问随机访问极其低效；极其低效；可靠性可靠性较差，任较差，任何一个指针出现问题，都会导致整个链的断开。何一个指针出现问题，都会导致整个

21、链的断开。 改进：改进：将几个盘块组成一个簇。以将几个盘块组成一个簇。以簇簇为单位进行盘块分配，链接文为单位进行盘块分配，链接文件中的每个元素也是以簇为单位。这种改进成倍地减小查找指定块的时间，件中的每个元素也是以簇为单位。这种改进成倍地减小查找指定块的时间，也可减小指针占用的存储空间，但却增大了也可减小指针占用的存储空间，但却增大了内部碎片内部碎片。 7.2 外存分配方法（3）7.2 外存分配方法外存分配方法7.2.2 链接分配链接分配显式链接显式链接 把用于链接文件各物理块的指针，显式地存放在内存的把用于链接文件各物理块的指针，显式地存放在内存的一张一张链接表链接表（每个磁盘仅设置一张）中

22、，该表的序号是物理（每个磁盘仅设置一张）中，该表的序号是物理盘块号，表项中存放链接指针。该表称为盘块号，表项中存放链接指针。该表称为文件分配表文件分配表FAT。每一个链的链首指针所对应的盘块号，均作为文件地址被填每一个链的链首指针所对应的盘块号，均作为文件地址被填入相应文件入相应文件FCB的的“物理地址物理地址”字段中。字段中。 查找记录的过程在内存中进行，显著地提高了查找记录的过程在内存中进行，显著地提高了检索速度检索速度，大大减少了访问磁盘的次数。大大减少了访问磁盘的次数。 链接分配链接分配存在的问题存在的问题： 不能支持高效地直接存取。不能支持高效地直接存取。 FAT占用较大的内存空间。

23、占用较大的内存空间。 安全性较差。安全性较差。 7.2 外存分配方法（4）7.2 外存分配方法外存分配方法7.2.3 索引分配索引分配单级索引分配单级索引分配 思想：思想：将文件占用盘块的的盘块号集中地存放在一起。索引分配为将文件占用盘块的的盘块号集中地存放在一起。索引分配为每个文件分配一个索引块（表），记录分配给该文件的所有盘块号。在文每个文件分配一个索引块（表），记录分配给该文件的所有盘块号。在文件的目录项中填指向该索引块的指针。件的目录项中填指向该索引块的指针。 优点：优点：支持直接访问；不会产生外部碎片。支持直接访问；不会产生外部碎片。 存在问题：存在问题：每个文件的索引块花费较多的外

24、存空间。小文件的索引块每个文件的索引块花费较多的外存空间。小文件的索引块利用率极低。利用率极低。 多级索引分配多级索引分配 当文件很大，其索引块太多时，可以通过当文件很大，其索引块太多时，可以通过链接指针链接指针将各索引块按序链将各索引块按序链接起来，但效率较低；此时系统可以再分配一个索引块，为这些索引块再接起来，但效率较低；此时系统可以再分配一个索引块，为这些索引块再建立一级索引，如果文件非常大时，还可用三级、四级索引分配方式。建立一级索引，如果文件非常大时，还可用三级、四级索引分配方式。7.2 外存分配方法（5）7.2 外存分配方法外存分配方法7.2.3 索引分配索引分配混合分配方式混合分

25、配方式 混合分配方式，是指将多种分配方式混合分配方式，是指将多种分配方式相结合相结合而形成的一种分配方式。而形成的一种分配方式。例如，系统既采用直接地址，又采用了一级索引或两级索引，甚至是三级例如，系统既采用直接地址，又采用了一级索引或两级索引，甚至是三级索引分配方式。索引分配方式。UNIX系统中采用的混合分配方式：把所有的地址项分成系统中采用的混合分配方式：把所有的地址项分成两类，即两类，即直接地址直接地址和和间接地址间接地址。 直接地址：直接地址：在索引结点中设置在索引结点中设置10个直接地址项个直接地址项iaddr(0)iaddr(9)来存放来存放直接地址（存放文件的盘块的盘块号），以提

26、高文件的检索速度。直接地址（存放文件的盘块的盘块号），以提高文件的检索速度。 一次间接地址：一次间接地址：利用索引结点中的地址项利用索引结点中的地址项iaddr(10)来提供一次间接地址来提供一次间接地址（索引块索引块地址）。地址）。 多次间接地址：多次间接地址：用地址项用地址项iaddr(11)提供提供二次二次间接地址（记录所有一次间间接地址（记录所有一次间址块的盘块号的二次间址块地址）；用地址项址块的盘块号的二次间址块地址）；用地址项iaddr(12)提供提供三次三次间接地址间接地址（记录所有二次间址块的盘块号的三次间址块地址）。（记录所有二次间址块的盘块号的三次间址块地址）。 7.3 空

27、闲存储空间的管理（1）7.3 空闲存储空间的管理空闲存储空间的管理 为了实现存储空间的分配，首先必须记住空闲存为了实现存储空间的分配，首先必须记住空闲存储空间的情况。为此需要：储空间的情况。为此需要： 系统应为分配存储空间而设置相应的系统应为分配存储空间而设置相应的数据结构数据结构； 系统应提供对存储空间进行系统应提供对存储空间进行分配和回收分配和回收的功能。的功能。 下面是几种常用的文件存储空间管理方法：下面是几种常用的文件存储空间管理方法： 空闲表法；空闲表法； 空闲链表法；空闲链表法； 位示图法；位示图法； 成组链接法。成组链接法。 空闲表法属于空闲表法属于连续分配连续分配方式。它与内存

28、管理中的方式。它与内存管理中的动态分区动态分区分配方式分配方式雷同，为每个文件分配一个连续的存储空间。系统为外存上的所有空闲区雷同，为每个文件分配一个连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项。空闲表中包括：建立一张空闲表，每个空闲区对应于一个空闲表项。空闲表中包括：序号序号、该空闲区的该空闲区的第一个盘块号第一个盘块号、该区的、该区的空闲盘块数空闲盘块数等信息。应将所有空闲区按等信息。应将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表。其起始盘块号递增的次序排列，形成空闲盘块表。 空闲盘区的分配同样可采取空闲盘区的分配同样可采取首次适应算法首

29、次适应算法、循环首次适应算法循环首次适应算法、最最佳适应算法佳适应算法及及最坏适应算法最坏适应算法等算法。经验证明，首次适应算法和最佳适应等算法。经验证明，首次适应算法和最佳适应算法，对存储空间的利用率大体上相当，而首次适应算法更快；它们在存算法，对存储空间的利用率大体上相当，而首次适应算法更快；它们在存储在间的利用求问分队速度上，都优于最坏适应算法。系统在为某个新创储在间的利用求问分队速度上，都优于最坏适应算法。系统在为某个新创建的文件分配它闲盘区时，应顺序检索交闲表的各个表项，直至找到第一建的文件分配它闲盘区时，应顺序检索交闲表的各个表项，直至找到第一个其大小能满足要求的空闲盘区。将该区个

30、其大小能满足要求的空闲盘区。将该区分配分配该用户，同时修改空闲表。该用户，同时修改空闲表。系统在对用户所释放的存储空间进行系统在对用户所释放的存储空间进行回收回收时，也采取类似于内存回收的方时，也采取类似于内存回收的方法。法。 应该说明，在内存分配上，虽然很少采用连续分配方式；然而在外存应该说明，在内存分配上，虽然很少采用连续分配方式；然而在外存管理上，由于它具有较高的分配速度，可减少访问磁盘的管理上，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它频率，故它在诸多分配方式中仍占一席之地。当文件在诸多分配方式中仍占一席之地。当文件较小较小时，便采用连续分配方法为时，便采用连续分配方法

31、为文件分配相邻接的几个盘块；当文件文件分配相邻接的几个盘块；当文件较大较大时，便采用时，便采用索引分配索引分配方式。在前方式。在前面所介绍的对换方式中，面所介绍的对换方式中，对换空间对换空间一般都采用连续分配方式。一般都采用连续分配方式。 7.3 空闲存储空间的管理（2）7.3 空闲存储空间的管理空闲存储空间的管理7.3.1 空闲表法空闲表法7.3 空闲存储空间的管理（3）7.3 空闲存储空间的管理空闲存储空间的管理7.3.2 空闲链表法空闲链表法 空闲链表法是将所有的空闲盘区拉成一条空闲链表法是将所有的空闲盘区拉成一条空闲链空闲链。根据构成链的基本。根据构成链的基本元素的不同。可有两种链表形

32、式：元素的不同。可有两种链表形式： 空闲盘块链：空闲盘块链：它是将磁盘上的所有空闲存储空间，以盘块为基本元素它是将磁盘上的所有空闲存储空间，以盘块为基本元素拉成一条链。当用户因创建文件而请求拉成一条链。当用户因创建文件而请求分配分配存储空间时，系统从链首开始，存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户；当用户因删除文件而释放存储依次摘下适当数目的空闲盘块分配给用户；当用户因删除文件而释放存储空间时，系统将空间时，系统将回收回收的盘块，依次链入空闲盘块链的尾部。的盘块，依次链入空闲盘块链的尾部。 优点优点是用于分配和回收一个盘块的是用于分配和回收一个盘块的过程非常简单过程非

33、常简单； 缺点缺点是空闲盘块链可能很长。是空闲盘块链可能很长。 空闲盘区链：空闲盘区链：这是将磁盘上的所有空闲盘区（每个盘区可包含若干个这是将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针盘块）拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应标有指明外，还应标有指明本盘区大小本盘区大小（盘块数）的信息。盘区的（盘块数）的信息。盘区的分配分配方法与内存方法与内存的的动态分区动态分区分配类似，通常采用分配类似，通常采用首次适应算法首次适应算法。在。在回收回收盘区时，同样也要盘区时，同样也要将与回收区邻接的空闲盘区与之合并

34、。在采用首次适应算法时，为了提高将与回收区邻接的空闲盘区与之合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用对空闲盘区的检索速度，可以采用显式链接显式链接方式，即在内存中为空闲盘区方式，即在内存中为空闲盘区建立一张链表。建立一张链表。 优点优点是分配和回收过程较复杂；是分配和回收过程较复杂； 缺点缺点是但空闲盘区链较短。是但空闲盘区链较短。 位示图：位示图：利用二进制的一位来表示磁盘中一个盘块的使用情况。当其利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为值为“0”时，表尔对应的盘块空闲；为时，表尔对应的盘块空闲；为“1”时表示已分配，磁盘上的所有时表示已分配，磁盘上

35、的所有盘块都由一个二进制位与之盘块都由一个二进制位与之对应对应。这样，由所有盘块所对应的位构成一个。这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用集合，称为位示图。通常可用mn个位数来构成位示图，也可描述为一个位数来构成位示图，也可描述为一个个二维数组二维数组Var map：array1m, 1n of bit 。 盘块的分配：盘块的分配：根据位示图进行盘块分配时，可分三步进行：根据位示图进行盘块分配时，可分三步进行： 顺序扫描位示图，从中找出一个或一组其值均为顺序扫描位示图，从中找出一个或一组其值均为“0”的二进制位；的二进制位； 将所找到的二进制位，转换成与之相应的盘块号。如

36、找到的二进将所找到的二进制位，转换成与之相应的盘块号。如找到的二进制位位于位示图的第制位位于位示图的第i 行、第行、第j 例，则其相应的盘块号为：例，则其相应的盘块号为：b=n*(i-1)+j； 修改位示图，今修改位示图，今arrayi, j=1 。 盘块的回收：盘块的回收：可分两步：可分两步： 将回收盘块的盘块号转换成位于图中的行号和列号。转换公式为：将回收盘块的盘块号转换成位于图中的行号和列号。转换公式为：i=(b-1)/n+1 ，j=mod(b-1), n+1 ； 修改位示图，今修改位示图，今arrayi, j=0 。 这种方法的主要这种方法的主要优点优点，是从位示图中，是从位示图中很容

37、易找到很容易找到一个或一组相邻接的一个或一组相邻接的空闲盘块。此外，由了位示图很小，占用空间少，因而可将它保存在内存空闲盘块。此外，由了位示图很小，占用空间少，因而可将它保存在内存中，从而在每次进行盘区分配时，无需首先把磁盘分配表读入内存，从而中，从而在每次进行盘区分配时，无需首先把磁盘分配表读入内存，从而省掉省掉许多磁盘的启动操作。许多磁盘的启动操作。 7.3 空闲存储空间的管理（4）7.3 空闲存储空间的管理空闲存储空间的管理7.3.3 位示图法位示图法7.3 空闲存储空间的管理（5）7.3 空闲存储空间的管理空闲存储空间的管理7.3.4 成组链接法成组链接法 空闲表法和空闲链法，都不适合

38、用在大型文件系统中，因为这会使空空闲表法和空闲链法，都不适合用在大型文件系统中，因为这会使空闲表或空闲链太长。在闲表或空闲链太长。在UNIX系统中采用的成组链接法是上述两种方法相系统中采用的成组链接法是上述两种方法相结合而形成的一种空闲盘块管理方法，它兼备了两种方法的优点丽克服了结合而形成的一种空闲盘块管理方法，它兼备了两种方法的优点丽克服了两种方法均有的、表太长的缺点。两种方法均有的、表太长的缺点。空闲盘块的组织空闲盘块的组织 空闲盘块号栈：空闲盘块号栈：它被用来存放它被用来存放当前当前可用的一组空闲盘块的盘块号（最可用的一组空闲盘块的盘块号（最多多100个号），以及栈中尚有的空闲盘块号数个

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

40、第一组的盘块总数和所有的盘块号，记入空闲盘块号栈空闲盘块号栈中，作为当中，作为当前前可供分配可供分配的空闲盘块（号）。的空闲盘块（号）。 最末一组只有最末一组只有99个盘块，其盘块号分别记入其前一组第一个盘块的个盘块，其盘块号分别记入其前一组第一个盘块的S.free(1)S.free(99)中，而在中，而在S.free(0)中存放中存放“0”，作为空闲盘块链的，作为空闲盘块链的结结束束标志。标志。7.3 空闲存储空间的管理（6）7.3 空闲存储空间的管理空闲存储空间的管理7.3.4 成组链接法成组链接法 空闲盘块的分配与回收空闲盘块的分配与回收 分配过程：分配过程：当系统要为用户分配文件所需的

41、盘块时，需调用盘块分当系统要为用户分配文件所需的盘块时，需调用盘块分配过程来完成。该过程首先检查空闲盘块号是否配过程来完成。该过程首先检查空闲盘块号是否上锁上锁。如未上锁，便从栈。如未上锁，便从栈顶取出一空闲盘块号，将其对应的盘块分配给用户；然后将栈顶指针顶取出一空闲盘块号，将其对应的盘块分配给用户；然后将栈顶指针下移下移一格，亦即做空闲盘块号数一格，亦即做空闲盘块号数N的减的减1操作。若该盘块号已是栈底，即操作。若该盘块号已是栈底，即S.free(0)，这是栈中，这是栈中最后最后一个可分配的盘块号。由于在该盘块号所对应的一个可分配的盘块号。由于在该盘块号所对应的盘块中，记有下一组可用的盘块号

42、，因此，便调用磁盘读过程，将栈底盘盘块中，记有下一组可用的盘块号，因此，便调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的块号所对应盘块的内容读入栈中，作为新的盘块号栈盘块号栈的内容；并把栈底对的内容；并把栈底对应的盘块分配出去（其中的有用数据已读入栈中）。然后，再分配一相应应的盘块分配出去（其中的有用数据已读入栈中）。然后，再分配一相应缓冲区（作为该盘块的缓冲）。最后，把栈中的空闲盘块数减缓冲区（作为该盘块的缓冲）。最后，把栈中的空闲盘块数减1并返回。并返回。 回收过程：回收过程：在系统回收空闲盘块时，需调用盘块回收过程进行回收。在系统回收空闲盘块时，需调用盘块回收过程进行回收

43、。它是将回收盘块的盘块号，记入空闲盘块号栈的顶部，并执行空闲盘块数它是将回收盘块的盘块号，记入空闲盘块号栈的顶部，并执行空闲盘块数加加1操作。当栈中空闲盘块号数目已达操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中时，表示栈已满，便将现有栈中的的100个盘块号，记入新回收的盘块中，再将其盘块号作为新的栈底。个盘块号，记入新回收的盘块中，再将其盘块号作为新的栈底。7.4 磁盘容错技术（1）7.4 磁盘容错技术磁盘容错技术 容锗技术容锗技术是通过在系统中设置是通过在系统中设置冗余冗余部件来提高系统可靠部件来提高系统可靠性的一种技术。磁盘容错技术则是通过性的一种技术。磁盘容错技术则是

44、通过增加增加冗余的磁盘驱动冗余的磁盘驱动器、磁盘控制器等，来提高磁盘系统的可靠性。即当磁盘系器、磁盘控制器等，来提高磁盘系统的可靠性。即当磁盘系统的某部分出现缺陷或故障时，磁盘仍能统的某部分出现缺陷或故障时，磁盘仍能正常正常工作，且不致工作，且不致造成数据的错误和丢失。造成数据的错误和丢失。 目前，不论是在中、小型机系统，还是目前，不论是在中、小型机系统，还是LAN中，都广泛中，都广泛采用磁盘容错技术来改善磁盘系统的可靠性，从而也就构成采用磁盘容错技术来改善磁盘系统的可靠性，从而也就构成了实际上的稳定存储器系统。了实际上的稳定存储器系统。 磁盘容错技术也称为磁盘容错技术也称为系统容错技术系统容

45、错技术SFT（System Fault Tolerance）。它可分为三个级别：）。它可分为三个级别： SFT-是低级磁盘容错技术，主要用于防止磁盘表面发生是低级磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢失；缺陷所引起的数据丢失； SFT-是中级磁盘容错技术，主要用于防止磁盘驱动器和是中级磁盘容错技术，主要用于防止磁盘驱动器和磁盘控制器故障所引起的系统不能正常工作；磁盘控制器故障所引起的系统不能正常工作； SFT-是高级系统容错技术。是高级系统容错技术。 7.4 磁盘容错技术（2）7.4 磁盘容错技术磁盘容错技术 7.4.1 第一级容错技术第一级容错技术双份目录和双份文件分配双份

46、目录和双份文件分配 在磁盘上存放的文件目录和文件分配表在磁盘上存放的文件目录和文件分配表FAT，是文件管，是文件管理所用的重要数据结构，如果这些表格被破坏，将导致磁盘理所用的重要数据结构，如果这些表格被破坏，将导致磁盘上的部分或全部文件成为不可访问的，为了防止这类情况发上的部分或全部文件成为不可访问的，为了防止这类情况发生，可在生，可在不同的磁盘不同的磁盘上或磁盘的上或磁盘的不同区域不同区域中，分别建立两份中，分别建立两份目录表和目录表和FAT。其中，一份称为。其中，一份称为主目录主目录及及主主FAT；另一份则称；另一份则称为为备份目录备份目录及及备份备份FAT。 一旦由于磁盘表面缺陷而造成文

47、件目录或一旦由于磁盘表面缺陷而造成文件目录或FAT损坏时，损坏时，系统便自动启用备份文件目录及备份系统便自动启用备份文件目录及备份FAT。从而可以保证磁。从而可以保证磁盘上的数据仍是可访问的，并将损坏区写入坏块表中；系统盘上的数据仍是可访问的，并将损坏区写入坏块表中；系统还要在磁盘的其它区域在建立新的文件目录或还要在磁盘的其它区域在建立新的文件目录或FAT，作为备，作为备份。在系统每次加电启动时，都要对两份目录和两份份。在系统每次加电启动时，都要对两份目录和两份FAT进进行检查，以验证它们的一致性。行检查，以验证它们的一致性。7.4 磁盘容错技术（3）7.4 磁盘容错技术磁盘容错技术 7.4.

48、1 第一级容错技术第一级容错技术热修复重定向和写后读校验热修复重定向和写后读校验 由于磁盘价格较贵，因而只有在磁盘上有较多缺陷或完全损坏时，才由于磁盘价格较贵，因而只有在磁盘上有较多缺陷或完全损坏时，才换一个新盘；而对于磁盘表面有少量缺陷的情况，则多是采取其它补救措换一个新盘；而对于磁盘表面有少量缺陷的情况，则多是采取其它补救措施后继续使用。补救措施主要用于施后继续使用。补救措施主要用于防止防止将数据写入有缺陷的盘块中。将数据写入有缺陷的盘块中。 热修复重定向热修复重定向（Hox-Fix Redirection）：系统将一定的磁盘容量（例如）：系统将一定的磁盘容量（例如2%3%）作为热修复）作

49、为热修复重定向区重定向区，用于存放当发现盘块有缺陷时的，用于存放当发现盘块有缺陷时的代写代写数数据，并对写入该区的所有数据进行登记，以便于以后对数据进行访问。据，并对写入该区的所有数据进行登记，以便于以后对数据进行访问。 写后读校验方式写后读校验方式（Read after Write Verification）：为了保证所有写入）：为了保证所有写入磁盘的数据都能写入到完好的盘块中，应该在每次从内存缓冲区向磁盘中磁盘的数据都能写入到完好的盘块中，应该在每次从内存缓冲区向磁盘中写入一个数据块后，又立即从磁盘上读出该数据块，送到另一缓冲区中，写入一个数据块后，又立即从磁盘上读出该数据块，送到另一缓冲

50、区中，再将该缓冲区中内容与内存缓冲区中在写后仍保留的数据进行再将该缓冲区中内容与内存缓冲区中在写后仍保留的数据进行比较比较，如两，如两者一致，便认为此次写入成功，可继续写下一个盘块；否则，再者一致，便认为此次写入成功，可继续写下一个盘块；否则，再重写重写。若。若重写后两者仍不一致，则认为该盘块有重写后两者仍不一致，则认为该盘块有缺陷缺陷，此时，便将应写入该盘块的，此时，便将应写入该盘块的数据写入热修复重定向区中，并将该损坏盘块的地址，记录在坏盘块中。数据写入热修复重定向区中，并将该损坏盘块的地址，记录在坏盘块中。7.4 磁盘容错技术（4）7.4 磁盘容错技术磁盘容错技术 7.4.2 第二级容错

51、技术第二级容错技术磁盘镜像（磁盘镜像（Disk Mirroring） SFT-只能用于防止由磁盘表面部分故障造成的数据丢失。但如果磁只能用于防止由磁盘表面部分故障造成的数据丢失。但如果磁盘驱动器发生故障，则盘驱动器发生故障，则SFT-级容错便无能为力，于是仍可能造成数据丢级容错便无能为力，于是仍可能造成数据丢失。为了避免在这种情况下的数据丢失，便增设了失。为了避免在这种情况下的数据丢失，便增设了磁盘镜像磁盘镜像功能。为实现功能。为实现该功能，需在该功能，需在同一磁盘控制器同一磁盘控制器下，再增设一个下，再增设一个完全相同完全相同的磁盘驱动器。的磁盘驱动器。 若采用磁盘镜像工作方式，则在每次向文

52、件服务器的主磁盘写入数据若采用磁盘镜像工作方式，则在每次向文件服务器的主磁盘写入数据后，都要采用后，都要采用写后读校验写后读校验方式，将数据再同样地写到备份磁盘上，使两个方式，将数据再同样地写到备份磁盘上，使两个磁盘上有着完全相同的位像图。或者说，可把备份磁盘看做是主磁盘的一磁盘上有着完全相同的位像图。或者说，可把备份磁盘看做是主磁盘的一面镜子。当其中一个磁盘驱动器发生故障时，由于有备份磁盘的存在，在面镜子。当其中一个磁盘驱动器发生故障时，由于有备份磁盘的存在，在进行进行切换切换后，文件服务器仍能正常工作，从而不会造成数据的丢失，这便后，文件服务器仍能正常工作，从而不会造成数据的丢失，这便是第

53、二级容错技术是第二级容错技术SFT- 。在一个磁盘驱动器发生故障时，必须立即发。在一个磁盘驱动器发生故障时，必须立即发出警告，尽快修复，以恢复磁盘镜像功能。出警告，尽快修复，以恢复磁盘镜像功能。 磁盘镜像虽然实现了容错功能，但并未能使服务器的磁盘磁盘镜像虽然实现了容错功能，但并未能使服务器的磁盘I/O速度得速度得到提高，相应地，磁盘的利用率仅为到提高，相应地，磁盘的利用率仅为50。 7.4 磁盘容错技术（5）7.4 磁盘容错技术磁盘容错技术 7.4.2 第二级容错技术第二级容错技术磁盘双工（磁盘双工（Disk Dupluxing） 磁盘镜像功能虽能有效地解决在一台磁盘机故障时的数据保护问题，磁

54、盘镜像功能虽能有效地解决在一台磁盘机故障时的数据保护问题，但如果控制这两台磁盘驱动器的磁盘控制器或主机到磁盘控制器之间的通但如果控制这两台磁盘驱动器的磁盘控制器或主机到磁盘控制器之间的通道，发生了故障，则此时将使这两台磁盘机同时失效，于是，磁盘镜像功道，发生了故障，则此时将使这两台磁盘机同时失效，于是，磁盘镜像功能便再也起不到数据保护作用。正因如此，在第二级容错技术中，又增加能便再也起不到数据保护作用。正因如此，在第二级容错技术中，又增加了了磁盘双工磁盘双工功能，以在磁盘控制器发生故障时，起到数据保护作用。所谓功能，以在磁盘控制器发生故障时，起到数据保护作用。所谓磁盘双工，是指将两台磁盘驱动器

55、磁盘双工，是指将两台磁盘驱动器分别分别接到接到两个磁盘控制器两个磁盘控制器上，同样地使上，同样地使这两台磁盘机这两台磁盘机镜像成对镜像成对。 在磁盘双工时，文件服务器同时将数据写到两个处于不同控制器下的在磁盘双工时，文件服务器同时将数据写到两个处于不同控制器下的磁盘上，使两者有着完全相同的位像图。如果某个通道或控制器发生故障磁盘上，使两者有着完全相同的位像图。如果某个通道或控制器发生故障时，另一通道上的磁盘仍能正常工作，这样使不会造成数据的丢失，同时时，另一通道上的磁盘仍能正常工作，这样使不会造成数据的丢失，同时须立即发出警告，以便尽早恢复磁盘双工功能。在磁盘双工时，由于每一须立即发出警告，以

56、便尽早恢复磁盘双工功能。在磁盘双工时，由于每一个磁盘都有着自己的独立通道，故可同时（个磁盘都有着自己的独立通道，故可同时（并行并行）地将数据写入磁盘。在）地将数据写入磁盘。在读数据时，可采取读数据时，可采取分离搜索分离搜索（Split Seek ）技术，从响应快的通道上取得）技术，从响应快的通道上取得数据，因而加快了对数据的读取速度。数据，因而加快了对数据的读取速度。 磁盘廉价磁盘冗余阵列磁盘廉价磁盘冗余阵列RAID是在是在1987年由美国加利福尼年由美国加利福尼亚大学伯克莱分校提出的，现在已开始广泛地应用于大、中亚大学伯克莱分校提出的，现在已开始广泛地应用于大、中型计算机系统和计算机网络中。

57、它是利用一台型计算机系统和计算机网络中。它是利用一台磁盘阵列控制磁盘阵列控制器器，来统一管理和控制一组（几台到，几十台）磁盘驱动器，来统一管理和控制一组（几台到，几十台）磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。组成一个高度可靠的、快速的大容量磁盘系统。7.4 磁盘容错技术（6）7.4 磁盘容错技术磁盘容错技术 7.4.3 廉价磁盘冗余阵列廉价磁盘冗余阵列 并行交叉存取并行交叉存取 为了提高对磁盘的访问速度，已把在大、中型机中应用为了提高对磁盘的访问速度，已把在大、中型机中应用的的交叉存取交叉存取（Interleave）技术，应用到磁盘存储系统中。在）技术，应用到磁盘存储系统中。在

58、该系统中。有多台磁盘驱动器，系统将每一盘块中的数据该系统中。有多台磁盘驱动器，系统将每一盘块中的数据分分为为若干个盘块数据，再把每一个子盘块的数据分别存储到各若干个盘块数据，再把每一个子盘块的数据分别存储到各个个不同磁盘不同磁盘中的中的相同位置相同位置。在以后，当要将一个盘块中的效。在以后，当要将一个盘块中的效据传送到内存时，采取据传送到内存时，采取并行并行传输方式，将各个盘块中的子盘传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。块数据同时向内存中传输，从而使传输时间大大减少。7.4 磁盘容错技术（7）7.4 磁盘容错技术磁盘容错技术 7.4.3 廉价磁盘冗余阵列

59、廉价磁盘冗余阵列 RAID的分级的分级 RAID 0 级：级：仅提供仅提供并行交叉存取并行交叉存取，虽能有效地提高磁盘，虽能有效地提高磁盘I/O速度，但并速度，但并无冗余校验功能，致使磁盘系统的可靠性不好。无冗余校验功能，致使磁盘系统的可靠性不好。 RAID 1 级：级：具有具有磁盘镜像磁盘镜像功能，可利用功能，可利用并行读并行读、写写特性，特数据分块特性，特数据分块并同时写入主盘和镜像盘，故比传统的镜像速度快，但它的磁盘容量的利并同时写入主盘和镜像盘，故比传统的镜像速度快，但它的磁盘容量的利用率只有用率只有50，它是以牺牲磁盘容量为代价的。，它是以牺牲磁盘容量为代价的。 RAID 3 级：级

60、：这是具有这是具有并行传输并行传输功能的磁盘阵列。它利用一台功能的磁盘阵列。它利用一台奇偶校验奇偶校验盘盘来完成容错功能，比起磁盘镜像，它减少了所需要的冗余磁盘数。来完成容错功能，比起磁盘镜像，它减少了所需要的冗余磁盘数。 RAID 5 级：级：这是一种具有这是一种具有独立传送功能独立传送功能的磁盘阵列，每个驱动器都各有的磁盘阵列，每个驱动器都各有自己独立的数据通路，独立地进行读、写，且自己独立的数据通路，独立地进行读、写，且无无专门的专门的校验盘校验盘。用来进行。用来进行纠错的校验信息，是以螺旋方式散布在所有数据盘上。纠错的校验信息，是以螺旋方式散布在所有数据盘上。 RAID 6 级级和和R