计算机操作系统(第4版)汤小丹-第8章.ppt
,第八章 磁盘存储器的管理,8.1 外存的组织方式8.2 文件存储空间的管理8.3 提高磁盘I/O速度的途径8.4 提高磁盘可靠性的技术8.5 数据一致性控制习题,8.1 外存的组织方式如前所述，文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有：(1)连续组织方式。(2)链接组织方式。(3)索引组织方式。,8.1.1 连续组织方式连续组织方式又称连续分配方式，要求为每一个文件分配一组相邻接的盘块。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2，。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。,图8-1 磁盘空间的连续组织方式,连续组织方式的主要优点有：(1)顺序访问容易。(2)顺序访问速度快。,连续组织方式的主要缺点如下：(1)要求为一个文件分配连续的存储空间。(2)必须事先知道文件的长度。(3)不能灵活地删除和插入记录。(4)对于那些动态增长的文件。,8.1.2 链接组织方式如果可以将文件装到多个离散的盘块中，就可消除连续组织方式的上述缺点。在采用链接组织方式时，可为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。链接组织方式的主要优点是：(1)消除了磁盘的外部碎片，提高了外存的利用率。(2)对插入、删除和修改记录都非常容易。(3)能适应文件的动态增长，无需事先知道文件的大小。,1.隐式链接在采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。,图8-2 磁盘空间的链接式分配,2.显式链接这是指把用于链接文件各物理块的指针显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，如图8-3所示。,图8-3 显式链接结构,8.1.3 FAT技术1.FAT12 1)早期的FAT12文件系统 FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。,图8-4 MS-DOS的文件物理结构,2)以簇为单位的FAT12文件系统 稍加分析便可看出，如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。为此，引入了簇(cluster)的概念。,2.FAT16 FAT12对磁盘容量限制的原因在于，FAT12表中的表项有限制，亦即最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。,3.FAT32由于FAT16表的长度只有65535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零，也就应当增加FAT表的长度，为此需要再增加FAT表的宽度，这样也就由FAT16演变为FAT32。,图8-5 FAT中簇的大小与最大分区的对应关系,8.1.4 NTFS的文件组织方式1.NTFS新特征NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows 2000/XP及后续的Windows OS。,2.磁盘组织NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即使NTFS具有了与磁盘物理块大小无关的独立性。,3.文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。,8.1.5 索引组织方式1.单级索引组织方式链接组织方式虽然解决了连续组织方式所存在的问题(即不便于随机访问)，但又出现了另外两个问题，即：不能支持高效的直接存取，要对一个较大的文件进行存取，须在FAT中顺序地查找许多盘块号；FAT需占用较大的内存空间，由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。,图8-6 索引分配方式,2.多级索引组织方式在为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS须再为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。,图8-7 两级索引分配,3.增量式索引组织方式1)增量式索引组织方式的基本思想为了能较全面地照顾到小、中、大及特大型作业，可以采取多种组织方式来构成文件的物理结构。如果盘块的大小为1KB或4KB，对于小文件(如1KB10KB或4KB40KB)而言，最多只会占用10个盘块，为了能提高对数量众多的小型作业的访问速度，最好能将它们的每一个盘块地址都直接放入文件控制块FCB(或索引结点)中，这样就可以直接从FCB中获得该文件的盘块地址。,2)UNIX System V的组织方式在UNIX System V的索引结点中设有13个地址项，即i.addr(0)i.addr(12)，如图8-8所示。(1)直接地址。(2)一次间接地址。(3)多次间接地址。,图8-8 混合索引方式,8.2 文件存储空间的管理8.2.1 空闲表法和空闲链表法1.空闲表法1)空闲表空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表，如图8-9所示。,图8-9 空闲盘块表,2)存储空间的分配与回收空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法和最佳适应算法等，它们对存储空间的利用率大体相当，都优于最坏适应算法。在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。,2.空闲链表法1)空闲盘块链这是将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。2)空闲盘区链这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。,8.2.2 位示图法1.位示图位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。,图8-10 位示图,2.盘块的分配根据位示图进行盘块分配时，可分三步进行：(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3)修改位示图，令mapi,j=1。,3.盘块的回收盘块的回收分两步：(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i=(b-1)DIV n+1j=(b-1)MOD n+1(2)修改位示图。令mapi,j=0。,8.2.3 成组链接法1.空闲盘块的组织(1)空闲盘块号栈，用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块(号)数N。顺便指出，N还兼作栈顶指针用。,图8-11 空闲盘块的成组链接法,(2)文件区中的所有空闲盘块被分成若干个组，比如，将每100个盘块作为一组。假定盘上共有10000个盘块，每块大小为1 KB，其中第2017999号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为79017999；次末组为78017900，倒数第二组的盘块号为301400；第一组为201300，如图8-11所示。(3)将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)S.free(99)中。这样，由各组的第一个盘块可链成一条链。,(4)将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。(5)最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为99，不应是100，因为这是指可供使用的空闲盘块。其编号应为(199)，0号中放空闲盘块链的结尾标志。),2.空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。,8.3 提高磁盘I/O速度的途径(1)改进文件的目录结构以及检索目录的方法来减少对目录的查找时间；(2)选取好的文件存储结构，以提高对文件的访问速度；(3)提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。其中的第1和第2点已在上一章或本章作了较详细的阐述，本节主要对如何提高磁盘的I/O速度作一简单介绍。,8.3.1 磁盘高速缓存(Disk Cache)在设计磁盘高速缓存时需要考虑的问题有：(1)如何将磁盘高速缓存中的数据传送给请求进程；(2)采用什么样的置换策略；(3)已修改的盘块数据在何时被写回磁盘。,1.数据交付(Data Delivery)方式如果I/O请求所需要的数据能从磁盘高速缓存中获取，此时就需要将磁盘高速缓存中的数据传送给请求进程。所谓的数据交付就是指将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式将数据交付给请求进程：(1)数据交付(2)指针交付,2.置换算法现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：(1)访问频率。(2)可预见性。(3)数据的一致性。,3.周期性地写回磁盘还有一种情况值得注意，那就是根据LRU算法，那些经常要被访问的盘块数据可能会一直保留在高速缓存中，长期不会被写回磁盘。,8.3.2 提高磁盘I/O速度的其它方法能有效地提高磁盘I/O速度的方法还有许多，如提前读、延迟写等，现介绍如下：1.提前读2.延迟写3.优化物理块的分布,4.虚拟盘由于访问内存的速度远高于访问磁盘的速度，于是有人试图利用内存空间去仿真磁盘，形成所谓虚拟盘，又称为RAM盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行不是在磁盘上而是在内存中。这对用户都是透明的。,8.3.3 廉价磁盘冗余阵列(RAID)1.并行交叉存取这是把在大、中型机中，用于提高访问内存速度的并行交叉存取技术应用到磁盘存储系统中，以提高对磁盘的I/O速度。在该系统中，有多台磁盘驱动器，系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。以后当要将一个盘块的数据传送到内存时，采取并行传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。,图8-12 磁盘并行交叉存取方式,2.RAID的分级RAID在刚被推出时，是分成6级的，后来又增加了RAID 6级和RAID 7级。(1)RAID 0级。(2)RAID 1级。(3)RAID 3级。(4)RAID 5级。(5)RAID 6级和RAID 7级。,3.RAID的优点(1)可靠性高，除了RAID 0级外，其余各级都采用了容错技术。当阵列中某一磁盘损坏时，并不会造成数据的丢失。此时可根据其它未损坏磁盘中的信息来恢复已损坏的盘中的信息。其可靠性比单台磁盘机高出一个数量级。(2)磁盘I/O速度高，由于采取了并行交叉存取方式，可使磁盘I/O速度提高N-1倍。(3)性能/价格比高，RAID的体积与具有相同容量和速度的大型磁盘系统相比，只是后者的1/3，价格也只是后者的1/3，且可靠性高。换言之，它仅以牺牲1/N的容量为代价，换取了高可靠性。,8.4 提高磁盘可靠性的技术8.4.1 第一级容错技术SFT-第一级容错技术(SFT-)是最基本的一种磁盘容错技术，主要用于防止因磁盘表面缺陷所造成的数据丢失。它包含双份目录、双份文件分配表及写后读校验等措施。,1.双份目录和双份文件分配表在磁盘上存放的文件目录和文件分配表FAT，是文件管理所用的重要数据结构。为了防止这些表格被破坏，可在不同的磁盘上或在磁盘的不同区域中分别建立(双份)目录表和FAT。其中一份为主目录及主FAT，另一份为备份目录及备份FAT。一旦由于磁盘表面缺陷而造成主文件目录或主FAT的损坏时，系统便自动启用备份文件目录及备份FAT，从而可以保证磁盘上的数据仍是可访问的。,2.热修复重定向和写后读校验由于磁盘价格昂贵，在磁盘表面有少量缺陷的情况下，则可采取某种补救措施后继续使用。一般主要采取以下两个补救措施：(1)热修复重定向。(2)写后读校验方式。,8.4.2 第二级容错技术SFT-1.磁盘镜像(Disk Mirroring)为了避免磁盘驱动器发生故障而丢失数据，便增设了磁盘镜像功能。为实现该功能，须在同一磁盘控制器下，再增设一个完全相同的磁盘驱动器，如图8-13所示。,2.磁盘双工(Disk Duplexing)如果控制这两台磁盘驱动器的磁盘控制器发生故障，或主机到磁盘控制器之间的通道发生故障，磁盘镜像功能便起不到数据保护的作用。因此，在第二级容错技术中，又增加了磁盘双工功能，即将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘机镜像成对，如图8-14所示。,图8-13 磁盘镜像示意图,图8-14 磁盘双工示意图,8.4.3 基于集群技术的容错功能1.双机热备份模式如图8-15所示，在这种模式的系统中，备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。,图8-15 双机热备份模式,2.双机互为备份模式在双机互为备份模式中，平时，两台服务器均为在线服务器，它们各自完成自己的任务，例如，一台作为数据库服务器，另一台作为电子邮件服务器。为了实现两者互为备份的功能，在两台服务器之间，应通过某种专线将其连接起来。如果希望两台服务器之间能相距较远，最好利用FDDI单模光纤来连接两台服务器。在此情况下，最好再通过路由器将两台服务器互连起来，作为备份通信线路。图8-16示出了双机互为备份系统的情况。,图8-16 双机互为备份系统的示意图,3.公用磁盘模式为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公共磁盘被划分为若干个卷。每台计算机使用一个卷。如果某台计算机发生故障，此时系统将重新进行配置，根据某种调度策略来选择另一台替代机器，后者对发生故障的机器的卷拥有所有权，从而可接替故障计算机所承担的任务。这种模式的优点是消除了信息的复制时间，因而减少了网络和服务器的开销。,8.4.4 后备系统1.磁带机它是最早作为计算机系统的外存储器。但由于它只适合存储顺序文件，故现在主要把它作为后备设备。磁盘机的主要优点是容量大，一般可达数GB至数十GB，且价格便宜，故在许多大、中型系统中都配置了磁带机。其缺点是只能顺序存取且速度也较慢，为数百KB到数MB，为了将一个大容量磁盘上的数据拷贝到磁带上，需要花费很多时间。,2.硬盘(1)移动磁盘。(2)固定硬盘驱动器。,图8-17 利用大容量硬盘兼做后备系统,3.光盘驱动器光盘驱动器是现在最流行的多媒体设备，可将它们分为如下两类：(1)只读光盘驱动器CD-ROM和DVD-ROM。(2)可读写光盘驱动器。,8.5 数据一致性控制在实际应用中，经常会在多个文件中都含有同一个数据。所谓数据一致性问题是指，保存在多个文件中的同一数据，在任何情况下都必需能保证相同。,8.5.1 事务1.事务的定义事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看做是一系列相关读和写操作。,2.事务记录(Transaction Record)为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现。这些数据结构被放在一个非常可靠的存储器(又称稳定存储器)中，用来记录在事务运行时数据项修改的全部信息，故又称为运行记录(Log)。,3.恢复算法由于一组被事务Ti修改的数据以及它们被修改前和修改后的值都能在事务记录表中找到，因此，利用事务记录表系统能处理任何故障而不致使故障造成非易失性存储器中信息的丢失。恢复算法可利用以下两个过程：(1)undoTi。该过程把所有被事务Ti修改过的数据恢复为修改前的值。(2)redoTi。该过程能把所有被事务Ti修改过的数据设置为新值。,8.5.2 检查点1.检查点(Check Points)的作用如前所述，当系统发生故障时，必须去检查整个Log表，以确定哪些事务需要利用redoTi过程去设置新值，而哪些事务又需要利用undoTi过程去恢复数据的旧值。由于在系统中可能存在着许多并发执行的事务，因而在事务记录表中就会有许多事务执行操作的记录。随着时间的推移，记录的数据也会愈来愈多。因此，一旦系统发生故障，在事务记录表中的记录清理起来就非常费时。,2.新的恢复算法在引入检查点后，可以大大减少恢复处理的开销。因为在发生故障后，并不需要对事务记录表中的所有事务记录进行处理，而只需对最后一个检查点之后的事务记录进行处理。因此，恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。,8.5.3 并发控制(Concurrent Control)1.利用互斥锁实现“顺序性”实现顺序性的一种最简单的方法，是设置一种用于实现互斥的锁，简称为互斥锁(Exclusive Lock)。在利用互斥锁实现顺序性时，应为每一个共享对象设置一把互斥锁。当某一事务Ti要去访问某对象时，应先获得该对象的互斥锁。若成功，便用该锁将该对象锁住，于是事务T便可对该对象执行读或写操作；而其它事务由于未能获得该锁，因而不能访问该对象。如果Ti需要对一批对象进行访问，则为了保证事务操作的原子性，Ti应先获得这一批对象的互斥锁，以将这些对象全部锁住。,2.利用互斥锁和共享锁实现顺序性利用互斥锁实现顺序性的方法简单易行。目前有不少系统都是采用这种方法来保证事务操作的顺序性，但这却存在着效率不高的问题。因为一个共享文件虽然只允许一个事务去写，但却允许多个事务同时去读；而在利用互斥锁来锁住文件后，则只允许一个事务去读。为了提高运行效率而又引入了另一种形式的锁共享锁(Shared Lock)。共享锁与互斥锁的区别在于：互斥锁仅允许一个事务对相应对象执行读或写操作，而共享锁则允许多个事务对相应对象执行读操作，但不允许其中任何一个事务对对象执行写操作。,8.5.4 重复数据的数据一致性问题1.重复文件的一致性我们以UNIX类型的文件系统为例来说明如何保证重复文件的一致性问题。对于通常的UNIX文件目录，其每个目录项中含有一个ASCII码的文件名和一个索引结点号，后者指向一个索引结点。当有重复文件时，一个目录项可由一个文件名和若干个索引结点号组成，每个索引结点号都是指向各自的索引结点。图8-18示出了UNIX类型的目录和具有重复文件的目录。,图8-18 UNIX类型的目录,2.链接数一致性检查在UNIX类型的文件目录中，其每个目录项内都含有一个索引结点号，用于指向该文件的索引结点。对于一个共享文件，其索引结点号会在目录中出现多次。,习 题 1.目前常用的外存有哪几种组织方式?2.由连续组织方式所形成的顺序文件的主要优缺点是什么?它主要应用于何种场合?3.在链接式文件中常用哪种链接方式?为什么?4.在文件分配表中为什么要引入“簇”的概念?以“簇”为基本的分配单位有什么好处?5.简要说明为什么要从FAT12发展为FAT16?又进一步要发展为FAT32?,6.试解释逻辑簇号和虚拟簇号这两个名词，NTFS是如何将它们映射到文件的物理地址上的?7.在MS-DOS中有两个文件A和B，A占用11、12、16和14四个盘块；B占用13、18和20三个盘块。试画出在文件A和B中各盘块间的链接情况及FAT的情况。8.NTFS文件系统中的文件所采用的是什么样的物理结构?9.假定一个文件系统的组织方式与MS-DOS相似，在FAT中可有64K个指针，磁盘的盘块大小为512B，试问该文件系统能否指引一个512MB的磁盘?,10.为了快速访问，又易于更新，当数据为以下形式时，应选用何种文件组织方式?(1)不经常更新，经常随机访问；(2)经常更新，经常按一定顺序访问；(3)经常更新，经常随机访问。11.在UNIX 中，如果一个盘块的大小为1KB，每个盘块号占4 个字节，即每块可放256个地址。请转换下列文件的字节偏移量为物理地址：(1)9999；(2)18000；(3)420000。12.什么是索引文件?为什么要引入多级索引?13.试说明增量式索引组织方式。,14.有一计算机系统利用图8-19所示的位示图来管理空闲盘块。盘块的大小为1KB，现要为某文件分配两个盘块，试说明盘块的具体分配过程。,图8-19 某计算机系统的位示图,15.某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理盘空间，试问：(1)位示图需多少个字?(2)第i字第j位对应的块号是多少?(3)给出申请/归还一块的工作流程。16.对空闲磁盘空间的管理常采用哪几种分配方式?在UNIX系统中是采用何种分配方式?17.可从哪几方面来提高对文件的访问速度?18.何谓磁盘高速缓存?在设计磁盘高速缓存时需要考虑哪些问题?,19.可以采取哪几种方式将磁盘高速缓存中的数据传送给请求者进程?20.何谓提前读和延迟写?21.试说明廉价磁盘冗余阵列RAID的主要优点。22.在第一级系统容错技术中，包括哪些容错措施?什么是写后读校验?23.在第二级系统容错技术中，包括哪些容错措施?请画图说明之。24.具有容错功能的集群系统的主要工作模式有哪几种?请简要说明之。,25.为什么要在系统中配置后备系统?目前常用做后备系统的设备有哪几种?26.何谓事务?如何保证事务的原子性?27.引入检查点的目的是什么?引入检查点后又如何进行恢复处理?28.为何引入共享锁?如何用互斥锁或共享锁来实现事务的顺序性?29.当系统中有重复文件时，如何保证它们的一致性?30.如何检查盘块号的一致性?检查时可能出现哪几种情况?,
