第8章磁盘存储器的管理

1、第八章第八章 磁盘存储器的管理磁盘存储器的管理n重点重点n磁盘调度算法。磁盘调度算法。n外存组织的连续组织、链接组织、索引组织方外存组织的连续组织、链接组织、索引组织方式。式。n空闲空间管理的功能。空闲空间管理的功能。n知识点知识点n掌握：磁盘调度算法、外存的组织方式。掌握：磁盘调度算法、外存的组织方式。n理解：空闲空间的管理。理解：空闲空间的管理。n了解：提高磁盘了解：提高磁盘I/O速度的途径，提高磁盘可速度的途径，提高磁盘可靠性的技术，数据一致性控制方法等。靠性的技术，数据一致性控制方法等。第八章磁盘存储器的管理 6.8磁盘存储器的性能和调度磁盘存储器的性能和调度8.1外存的组织方式外存的

2、组织方式8.2空闲空闲空间空间的管理的管理8.3提高磁盘提高磁盘I/O速度的途径速度的途径8.4提高磁盘可靠性的技术提高磁盘可靠性的技术8.5数据一致性控制数据一致性控制 磁盘存储器管理的主要任务磁盘存储器管理的主要任务n为文件分配存储为文件分配存储空间空间n合理地组织文件的存储方式，以提高合理地组织文件的存储方式，以提高磁盘的访问磁盘的访问速度速度n提高磁盘存储空间的利用率提高磁盘存储空间的利用率n提高磁盘提高磁盘I/O速度，改善文件性能速度，改善文件性能n确保文件系统的确保文件系统的可靠性可靠性（备份）（备份）6.8 磁盘存储器的性能和调度磁盘存储器的性能和调度n6.8.1 磁盘性能简述磁

3、盘性能简述n6.8.2 早期的磁盘调度算法早期的磁盘调度算法n6.8.3 基于扫描的磁盘调度算法基于扫描的磁盘调度算法6.8.1 磁盘性能简述磁盘性能简述n数据的组织和格式数据的组织和格式 n磁盘磁盘包括一个或多个包括一个或多个盘片盘片，每片分，每片分2面；面；n每面可分成若干条磁道，各磁道之间有间隙，每面可分成若干条磁道，各磁道之间有间隙，每条磁道上可存储相同数目的二进制位；每条磁道上可存储相同数目的二进制位；n磁盘磁盘密度密度即每英寸之中所存储的位数。即每英寸之中所存储的位数。n显然内层磁道的密度较外层磁道的密度大。显然内层磁道的密度较外层磁道的密度大。6.8.1 磁盘性能简述磁盘性能简述

4、6.8.1 磁盘性能简述磁盘性能简述6.8.1 磁盘性能简述磁盘性能简述n数据的组织和格式数据的组织和格式n盘片盘片（1个或多个）、盘面、磁道、扇区个或多个）、盘面、磁道、扇区n扇区有扇区有标识符字段标识符字段和和数据字段数据字段Gap102031292293Field Gap Field Gap Gap Field Gap Field Gap17741515201774151520IDDataIDDataGap1292293Field Gap Field1774151520IDDataSectorPhysical Sector 0Physical Sector 1Physical Secto

5、r 29BytesSynchByteTrack#Head#Sector#Bytes 1211CRC2SynchByteDataCRC15122600 Bytes/SectorGap存储相同数目存储相同数目的二进制位的二进制位间隙间隙定界符定界符段校验段校验6.8.1 磁盘性能简述磁盘性能简述n磁盘的类型磁盘的类型n固定头磁盘固定头磁盘n在在每条磁道上都有一读每条磁道上都有一读/写磁头写磁头，所有的磁头都被装，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道，在一刚性磁臂中。通过这些磁头可访问所有各磁道，并进行并进行并行读并行读/写写，有效地，有效地提高了磁盘的提高了磁盘的I/O速度

6、速度。这种结构的磁盘主要用于这种结构的磁盘主要用于大容量磁盘大容量磁盘上。上。n移动头磁盘移动头磁盘n每一个盘面仅配有一个磁头每一个盘面仅配有一个磁头，也被装入磁臂中。为，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以进行寻道。可见，移动磁头仅能以串行方式读串行方式读/写写，致使其致使其I/O速度较慢速度较慢；但由于其结构简单，；但由于其结构简单， 故仍广故仍广泛应用于泛应用于中小型磁盘中小型磁盘设备中。设备中。6.8.1 磁盘性能简述磁盘性能简述n磁盘访问时间磁盘访问时间n寻道时间寻道时间Tsn把磁臂把

7、磁臂(磁头磁头)移动到指定磁道上所经历的时移动到指定磁道上所经历的时间。该时间是启动磁臂的时间间。该时间是启动磁臂的时间s与磁头移动与磁头移动n条磁道所花费的时间之和，条磁道所花费的时间之和， 即即Ts=mn+sn旋转延迟时间旋转延迟时间Tn指定扇区旋转到磁头下面所经历的时间。如：指定扇区旋转到磁头下面所经历的时间。如：7200r/min 每转每转=60000ms/7200r=8.33ms 平均旋转延迟平均旋转延迟=（0+8.33)/2=4.16启动磁臂时间启动磁臂时间2ms常数，与磁盘驱常数，与磁盘驱动器的速度有关动器的速度有关一般：一般：0.2ms高速：高速：=0.1ms6.8.1 磁盘性

8、能简述磁盘性能简述n磁盘访问时间磁盘访问时间n传输时间传输时间Ttn把数据从磁盘读出或向磁盘写入数据所经历把数据从磁盘读出或向磁盘写入数据所经历的时间。的时间。 其大小与每次所读其大小与每次所读/写的字节数写的字节数b和和旋转速度有关旋转速度有关nr为磁盘每秒钟的转数；为磁盘每秒钟的转数；N为一条磁道上的字为一条磁道上的字节数节数nT和和Tt相同，则访问时间相同，则访问时间=Ts + T+ TtrNbNbrTt1如如b=N/2，则，则T=1/(2r)=Tt可见，寻道时间可见，寻道时间TS和旋转和旋转延迟时间延迟时间T基本上都与所基本上都与所读读/写数据的字节数无关，写数据的字节数无关，而且它通

9、常占据了访问时而且它通常占据了访问时间中的大部分间中的大部分目前磁盘的传输速率已达到目前磁盘的传输速率已达到80MB/s以上，数据传输时间所占以上，数据传输时间所占的比例更低。可见，适当地集中数据传输，将有利于提高传输的比例更低。可见，适当地集中数据传输，将有利于提高传输效率效率6.8.1 磁盘性能简述磁盘性能简述寻道寻道时间时间旋转旋转延迟延迟时间时间传输传输时间时间6.8.1 磁盘性能简述磁盘性能简述n磁盘访问时间磁盘访问时间寻道时间寻道时间: 20ms磁盘通道传输速率磁盘通道传输速率: 1MB/s转速转速r=3600rpm每扇区每扇区512字节字节每磁道每磁道32 扇区扇区目标：读目标：

10、读 128k 数据数据1.寻道时间寻道时间TS：TS=m*n+S；2.旋转延时间旋转延时间Tr：Tr1/2r3.数据传输时间数据传输时间Tt ：Ttb/rN 访问时间：访问时间：Ta=Ts+1/2r+b/rN60*16k=960k1MB/s顺序组织顺序组织(208.316.7)(8.316.7)7220(ms)随机组织随机组织(208.30.5)2567373(ms)6.8.2 早期的磁盘调度算法早期的磁盘调度算法n先来先服务先来先服务FCFS(First-Come, First Served)n根据进程请求访问磁盘的先后次序进行调度根据进程请求访问磁盘的先后次序进行调度优点优点：简单、公平，

11、：简单、公平，不会出现请求长期得不会出现请求长期得不到满足；不到满足；缺点缺点：未优化，：未优化，平均寻道时间平均寻道时间长。长。6.8.2 早期的磁盘调度算法早期的磁盘调度算法n最短寻道时间优先最短寻道时间优先SSTF(Shortest Seek Time First) n请求访问的磁道与磁头所在的磁道距离最近。请求访问的磁道与磁头所在的磁道距离最近。优点优点：使每次寻道时：使每次寻道时间最短；间最短；缺点缺点：不能保证平均：不能保证平均寻道时间最短；寻道时间最短；6.8.3 基于扫描的磁盘调度算法基于扫描的磁盘调度算法n扫描扫描(SCAN)算法算法 n进程进程“饥饿饥饿”现象现象nSSTF

12、算法可能导致某个进程发生算法可能导致某个进程发生“饥饥饿饿”(Starvation)现象。现象。0501606.8.3 基于扫描的磁盘调度算法基于扫描的磁盘调度算法n扫描扫描(SCAN)算法算法n算法过程算法过程n 磁臂从磁盘的一端开始移动；磁臂从磁盘的一端开始移动；n 向另一端移动；向另一端移动；n 同时当磁头移过每个柱面时，处理位于该柱面上同时当磁头移过每个柱面时，处理位于该柱面上的服务请求；的服务请求；n 当到达另一端时，磁头改变移动方向，处理继续；当到达另一端时，磁头改变移动方向，处理继续；n 磁头在磁盘上来回扫描。磁头在磁盘上来回扫描。n又称又称“电梯电梯”算法。算法。6.8.3 基

13、于扫描的磁盘调度算法基于扫描的磁盘调度算法6.8.3 基于扫描的磁盘调度算法基于扫描的磁盘调度算法n循环扫描循环扫描(CSCAN)算法算法nSCAN方法的缺点方法的缺点n刚移过的磁道的等待时间长。刚移过的磁道的等待时间长。n解决方法解决方法n规定磁头单向移动。减少刚移过的磁道的等规定磁头单向移动。减少刚移过的磁道的等待时间。待时间。6.8.3 基于扫描的磁盘调度算法基于扫描的磁盘调度算法6.8.3 基于扫描的磁盘调度算法基于扫描的磁盘调度算法nN-Step-SCAN和和FSCAN调度算法调度算法 nN-Step-SCAN算法算法n在在SSTF、 SCAN及及CSCAN中，中， 都可能出现磁臂停

14、都可能出现磁臂停留在某处不动，称为留在某处不动，称为“磁臂粘着磁臂粘着”(Armstickiness)。nN步步SCAN算法：将磁盘请求队列分成若干个长度为算法：将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按的子队列，磁盘调度将按FCFS算法依次处理这些算法依次处理这些子队列。子队列。 而每处理一个队列时又是按而每处理一个队列时又是按SCAN算法，算法，对一个队列处理完后，再处理其他队列。对一个队列处理完后，再处理其他队列。nFSCAN算法算法nN步步SCAN算法的简化，算法的简化， 即其只将磁盘请求队列分即其只将磁盘请求队列分成两个子队列。一是由当前所有请求成两个子队列。一是由当前所

15、有请求I/O的进程形成的进程形成的队列，由磁盘调度按的队列，由磁盘调度按SCAN算法进行处理。在扫算法进行处理。在扫描期间，新出现的所有请求描期间，新出现的所有请求I/O的进程，的进程， 则放入另则放入另一个等待处理的请求队列。一个等待处理的请求队列。当当N值很大时，值很大时，N步扫步扫描性能接近于描性能接近于SCAN性性能；能；N=1， N步扫描性步扫描性能便退化为能便退化为FCFS8.1 外存的组织方式外存的组织方式n文件的结构文件的结构n文件的逻辑结构文件的逻辑结构(File Logical Structure)。n文件的物理结构，文件的物理结构， 又称为文件的存储结构，又称为文件的存储

16、结构， 文件在外存上的存储组织形式。文件在外存上的存储组织形式。n 问题问题n如何才能有效地利用外存空间如何才能有效地利用外存空间?n如何提高对文件的访问速度如何提高对文件的访问速度?8.1 外存的组织方式外存的组织方式n外存的特点外存的特点n容量大，断电后仍可保存信息，速度较慢，成容量大，断电后仍可保存信息，速度较慢，成本较低本较低n两部分组成：驱动部分两部分组成：驱动部分+ +存储介质存储介质n种类很多种类很多n外存空间组织、地址与存取方式非常复杂外存空间组织、地址与存取方式非常复杂nI/O过程方式非常复杂过程方式非常复杂8.1 外存的组织方式外存的组织方式n对外存的要求对外存的要求方便、

17、效率、安全方便、效率、安全n在读写外存时不涉及硬件细节，使用逻辑地址在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作。和逻辑操作。n存取速度尽可能快，容量大且空间利用率高存取速度尽可能快，容量大且空间利用率高n外存上存放的信息安全可靠，防止来自硬件的外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权。故障和他人的侵权。n方便地共享，动态扩缩，携带拆卸，了解存储方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况。情况和使用情况。n以尽可能小的代价完成上述要求。以尽可能小的代价完成上述要求。8.1 外存的组织方式外存的组织方式n文件的物理结构文件的物理结构n指逻辑文件指逻辑文件在存储设

18、备在存储设备（外存）上的（外存）上的存储组织形式存储组织形式，它与存储介，它与存储介质的存储特性有关质的存储特性有关n一个文件存储介质，格式化后就分成许多大小相等的单一个文件存储介质，格式化后就分成许多大小相等的单位位存储块（物理盘块），一般来说，每个物理块是一存储块（物理盘块），一般来说，每个物理块是一个磁盘的扇区，个磁盘的扇区，512B。并给每个存储块有个编号，称为。并给每个存储块有个编号，称为物理块号。物理块号。n物理块是物理块是分配和传输分配和传输信息的信息的基本单位基本单位，其与外存设备有关，其与外存设备有关，但与逻辑记录大小无关，如但与逻辑记录大小无关，如扇区、簇。扇区、簇。n文件

19、在逻辑上都可看作是连续的，但在物理设备上存放时文件在逻辑上都可看作是连续的，但在物理设备上存放时却有不同的方式，如却有不同的方式，如连续结构（顺序结构）、链接结构连续结构（顺序结构）、链接结构（串联结构）、索引结构、（串联结构）、索引结构、HASH文件文件等等8.1 外存的组织方式外存的组织方式。把逻辑文件中的记录顺序地存储到。把逻辑文件中的记录顺序地存储到连续的物理盘块中。连续的物理盘块中。文件中的各个记录可以存放在不相。文件中的各个记录可以存放在不相邻接的各个物理盘块中，通过物理块中的链接邻接的各个物理盘块中，通过物理块中的链接指针，将它们连接成一个链表。指针，将它们连接成一个链表。文件中

20、的各个记录可存储在不相邻。文件中的各个记录可存储在不相邻接的各个物理块中。接的各个物理块中。8.1 外存的组织方式外存的组织方式n8.1.1 连续组织方式连续组织方式n8.1.2 链接组织方式链接组织方式n8.1.3 FAT技术技术n8.1.4 NTFS技术技术n8.1.5 索引组织方式索引组织方式8.1.1 连续组织方式连续组织方式n每个文件分配每个文件分配一组相邻接的盘块一组相邻接的盘块。一组盘。一组盘块定义了磁盘上的一段线性地址。又称为块定义了磁盘上的一段线性地址。又称为连续分配方式。连续分配方式。n把逻辑文件中的记录顺序地存储到邻接的把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这

21、样所形成的文件结构称各物理盘块中，这样所形成的文件结构称为为顺序文件结构顺序文件结构，此时的物理文件称为，此时的物理文件称为顺顺序文件。序文件。8.1.1 连续组织方式连续组织方式8.1.1 连续组织方式连续组织方式n连续组织方式的主要优缺点连续组织方式的主要优缺点n优点优点n结构简单，容易实现。结构简单，容易实现。n支持顺序存取和随机存取。支持顺序存取和随机存取。n顺序存取速度快。顺序存取速度快。n所需的磁盘寻道次数和寻道时间最少。所需的磁盘寻道次数和寻道时间最少。n缺点缺点n要求有连续的存储空间，不利于动态扩充。要求有连续的存储空间，不利于动态扩充。n容易形成容易形成碎片，空间利用不充分。

22、碎片，空间利用不充分。n必须事先知道文件的长度，用户不方便。必须事先知道文件的长度，用户不方便。8.1.2 链接组织方式链接组织方式n基本方法基本方法n通过在每个盘块上的链接指针，将同属于一个通过在每个盘块上的链接指针，将同属于一个文件的多个文件的多个离散的离散的盘块链接成一个盘块链接成一个链表链表，把这，把这样形成的物理文件称为样形成的物理文件称为链接文件链接文件n特点：特点：不要求连续存放不要求连续存放n对于记录式文件一块中可包含一个或多个逻辑记对于记录式文件一块中可包含一个或多个逻辑记录，也可以若干物理块包含一个逻辑记录。录，也可以若干物理块包含一个逻辑记录。n链接方式链接方式n隐式链接

23、隐式链接n显式链接显式链接8.1.2 链接组织方式链接组织方式n隐式链接隐式链接文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录01234567891011121314151617181920212223242526272829303111016-1258.1.2 链接组织方式链接组织方式n隐式链接隐式链接n每个物理块的最末一个字每个物理块的最末一个字(或第一个字或第一个字)作为链作为链接字，它指出后继块的物理地址。链首指针存接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为放在该文件目录中。文件的结尾块的指针为“”。n优点优点n离散存储，空间利用

24、率高；离散存储，空间利用率高；n顺序存取效率高。顺序存取效率高。n缺点缺点n随机存取效率太低，若要访问第随机存取效率太低，若要访问第i个物理块，个物理块，必须读出前必须读出前i-1个。个。8.1.2 链接组织方式链接组织方式n显式链接显式链接n为了克服链接文件的存取效率太低的问题，提为了克服链接文件的存取效率太低的问题，提出出文件映照的技术文件映照的技术，即把链接文件中的链接字，即把链接文件中的链接字集中在一结构中，集中在一结构中，这样既保持了链接文件的优这样既保持了链接文件的优点，也克服了其缺点点，也克服了其缺点，DOS、WINDOWS系统系统就采用了这样结构。就采用了这样结构。n文件分配表

25、（文件分配表（File Allocation Table, FAT）n在在FAT中每个物理块占一个表项，增加一个指中每个物理块占一个表项，增加一个指针指向下一个物理块，最末一个物理块的指针针指向下一个物理块，最末一个物理块的指针为为“”。8.1.2 链接组织方式链接组织方式n显式链接显式链接8.1.2 链接组织方式链接组织方式n主要优缺点主要优缺点n优点优点n消除了外部碎片，提高外存利用率；消除了外部碎片，提高外存利用率；n文件动态增长时，可动态地为它分配盘块；文件动态增长时，可动态地为它分配盘块；n文件的增删改方便，不需事先知道文件长。文件的增删改方便，不需事先知道文件长。n缺点缺点n存取速

26、度慢；存取速度慢；n只适于只适于顺序存取顺序存取，不适于随机存取；不适于随机存取；n可靠性差，若某一块可靠性差，若某一块指针指针出错，则链断开；出错，则链断开；n更多的寻道次数和寻道时间；更多的寻道次数和寻道时间；n链接指针占用一定的空间。链接指针占用一定的空间。8.1.3 FAT技术技术n文件分配表（文件分配表（File Allocation Table, FAT）n磁盘格式化后建立，从磁盘的第二个开始，有磁盘格式化后建立，从磁盘的第二个开始，有两个相同的两个相同的FAT。n用于记录外存分配状况，每个盘块（或簇）占用于记录外存分配状况，每个盘块（或簇）占一项，放在内存中，整个系统一张一项，放

27、在内存中，整个系统一张FAT。n表的序号为物理盘块号或簇号，从表的序号为物理盘块号或簇号，从0至至N-1。n分配给一个文件的所有物理块都在该表中标出，分配给一个文件的所有物理块都在该表中标出，文件的第一个盘块号记入文件的文件的第一个盘块号记入文件的FCB中。中。8.1.3 FAT技术技术8.1.3 FAT技术技术区名区名内容内容 软盘软盘 占扇区数占扇区数 扇区号扇区号保留区保留区引导记录与磁引导记录与磁盘参数表盘参数表 1 0控制区控制区FAT1文件分文件分配表配表 2 12FAT2 2 34FDT文件目录文件目录表表 7 511文件区文件区 文件内容文件内容 余下部分余下部分 128.1.

28、3 FAT技术技术nDOSDOS磁盘访问操作流程磁盘访问操作流程8.1.3 FAT技术技术nFAT12n簇的基本概念簇的基本概念n簇是一组连续的扇区，在簇是一组连续的扇区，在FAT中它是作为一个虚拟中它是作为一个虚拟扇区，簇的大小一般是扇区，簇的大小一般是2n (n为整数为整数)个盘块，在个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区、两个扇区(1 KB)、四个扇区、四个扇区(2 KB)、八个、八个扇区扇区(4 KB)等。等。n一个簇应包含扇区的数量与磁盘容量的大小直接有一个簇应包含扇区的数量与磁盘容量的大小直接有关。

29、例如，当一个簇仅有一个扇区时，磁盘的最大关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为容量为2 MB；当一个簇包含两个扇区时，磁盘的最；当一个簇包含两个扇区时，磁盘的最大容量可以达到大容量可以达到4 MB；当一个簇包含了八个扇区时，；当一个簇包含了八个扇区时，磁盘的最大容量便可达到磁盘的最大容量便可达到16 MB。8.1.3 FAT技术技术nFAT12nFAT12存在的问题存在的问题n对所允许的磁盘容量存在着严重的限制，通对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但簇的大小来提高所允

30、许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。片也将随之成倍地增加。n它只能支持它只能支持8+3格式的文件名。格式的文件名。 8.1.3 FAT技术技术nFAT16n将将FAT表的宽度增至表的宽度增至16位，最大表项数将增至位，最大表项数将增至65536个，此时便能将一个磁盘分区分为个，此时便能将一个磁盘分区分为65 536(216)个簇。把具有个簇。把具有16位表宽的位表宽的FAT表称为表称为FAT16。在。在FAT16的每个簇中可以有的盘块数的每个簇中可以有的盘块数为为4、8、16、32直到直到64，由此得出，由此得出

31、FAT16可以可以管理的最大分区空间为管理的最大分区空间为 216 64 512 = 2048 MB。8.1.3 FAT技术技术nFAT32n每一簇在每一簇在FAT表中的表项占据表中的表项占据4字节字节(232)，FAT表可以表示表可以表示4 294 967 296项，即项，即FAT32允许管允许管理比理比FAT16更多的簇。这样就允许在更多的簇。这样就允许在FAT32中中采用较小的簇，采用较小的簇，FAT32的每个簇都固定为的每个簇都固定为4 KB，即每簇用即每簇用8个盘块代替个盘块代替FAT16的的64个盘块，每个盘块，每个盘块仍为个盘块仍为512字节，字节，FAT32分区格式可以管分区格

32、式可以管理的单个最大磁盘空间大到理的单个最大磁盘空间大到 4 KB232 = 16 TB（实际（实际2TB）8.1.3 FAT技术技术nFAT中簇的大小与最大分区的对应关系中簇的大小与最大分区的对应关系8.1.4 NTFS技术技术nNTFS (New Technology File System)新特征新特征n专门为专门为Windows NT开发的、全新的文件系统，并适用开发的、全新的文件系统，并适用于于Windows 2000/XP及以后的系统。及以后的系统。n 使用使用64位磁盘地址，理论上可以支持位磁盘地址，理论上可以支持264字节的磁字节的磁盘分区；盘分区； n 可以很好地支持长文件名

33、，单个文件名限制在可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为个字符以内，全路径名为32 767个字符；个字符； n 具有系统容错功能，即在系统出现故障或差错时，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行；仍能保证系统正常运行； n 提供了数据的一致性功能；提供了数据的一致性功能；n 提供了文件加密、文件压缩等功能提供了文件加密、文件压缩等功能。8.1.4 NTFS技术技术n磁盘组织磁盘组织n以簇作为磁盘空间分配和回收的基本单位。以簇作为磁盘空间分配和回收的基本单位。n一个文件占用若干个簇，一个簇只属于一个文一个文件占用若干个簇，一个簇只属于一个文

34、件。件。n通过簇来间接管理磁盘，可以不需要知道盘块通过簇来间接管理磁盘，可以不需要知道盘块(扇区扇区)的大小，使的大小，使NTFS具有了与磁盘物理扇区具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是大小无关的独立性，很容易支持扇区大小不是512字节的非标准磁盘，从而可以根据不同的字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。磁盘选择匹配的簇大小。8.1.4 NTFS技术技术n卷因子卷因子n卷中簇的大小。在磁盘格式化时确定的，一个簇包含卷中簇的大小。在磁盘格式化时确定的，一个簇包含2n(n为整数为整数)个盘块。个盘块。n簇的大小可由格式化命令或格式化程序按磁盘容量和簇的大

35、小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为应用需求来确定，可以为512 B、1 KB、2 KB，最，最大可达大可达64 KB。对于小磁盘。对于小磁盘(512 MB)，默认簇大小为，默认簇大小为512字节；对于字节；对于1 GB磁盘，默认簇大小为磁盘，默认簇大小为1 KB；对于；对于2 GB磁盘，则默认簇大小为磁盘，则默认簇大小为4 KB。事实上，为了在传输。事实上，为了在传输效率和簇内碎片之间进行折中，效率和簇内碎片之间进行折中，NTFS在大多数情况下在大多数情况下都是使用都是使用4 KB。8.1.4 NTFS技术技术n簇的定位簇的定位n逻辑簇号逻辑簇号LCN(Logica

36、l Cluster Number)：以卷为单：以卷为单位，将整个卷中所有的簇按顺序进行简单的编号。位，将整个卷中所有的簇按顺序进行简单的编号。n地址映射过程：通过卷因子与地址映射过程：通过卷因子与LCN的乘积，便可算的乘积，便可算出卷上的物理字节偏移量，从而得到文件数据所在出卷上的物理字节偏移量，从而得到文件数据所在的物理磁盘地址。的物理磁盘地址。n虚拟簇号虚拟簇号VCN(Virtual Cluster Number)：为了方便：为了方便文件中数据的引用，以文件为单位，将属于某个文文件中数据的引用，以文件为单位，将属于某个文件的簇按顺序进行编号。件的簇按顺序进行编号。n地址映射过程地址映射过程

37、 ：文件开始的簇地址，将：文件开始的簇地址，将VCN映射到映射到LCN。8.1.4 NTFS技术技术n文件的组织文件的组织n以卷为单位，将一个卷中的所有文件信息、目以卷为单位，将一个卷中的所有文件信息、目录信息、可用的未分配空间信息，以文件记录录信息、可用的未分配空间信息，以文件记录的方式记录在的方式记录在主控文件表主控文件表MFT(Master File Table)中。中。nMFT表是表是NTFS 卷结构的中心，从逻辑上讲，卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在卷中的每个文件作为一条记录，在MFT 表中表中占有一行，其中还包括占有一行，其中还包括MFT 自己的这一行。自己

38、的这一行。每行大小固定为每行大小固定为1 KB，每行称为该行所对应文，每行称为该行所对应文件的元数据件的元数据(metadata)，也称为，也称为文件控制字文件控制字。8.1.5 索引组织方式索引组织方式n链接组织方式存在的问题链接组织方式存在的问题n不能支持高效的直接存取不能支持高效的直接存取，要对一个，要对一个较大的文较大的文件件进行进行直接存取直接存取，需首先在，需首先在FAT中顺序地查找中顺序地查找许多盘块号。许多盘块号。nFAT需需占用较大占用较大的的内存内存空间。空间。n索引表索引表n文件数据存放的存储介质上的物理块号与文件文件数据存放的存储介质上的物理块号与文件的逻辑块号一一对应

39、。的逻辑块号一一对应。n第第i i个条目指向文件的第个条目指向文件的第i i个逻辑块。对应的物个逻辑块。对应的物理块号记录在该块中。理块号记录在该块中。8.1.5 索引组织方式索引组织方式n单级索引组织方式单级索引组织方式n为为每个文件分配一个索引块每个文件分配一个索引块，把分配给该文件，把分配给该文件的所有盘块号都记录在该索引块中；的所有盘块号都记录在该索引块中；n在建立一个文件时，便为之建立的目录项中填在建立一个文件时，便为之建立的目录项中填上指向该索引块的指针。上指向该索引块的指针。n支持直接访问支持直接访问n对于大文件而言，该方式优于链式分配方式。对于大文件而言，该方式优于链式分配方式

40、。8.1.5 索引组织方式索引组织方式012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目录文件目录Jeep 19 916 11025 -1 -1 -1198.1.5 索引组织方式索引组织方式n单级索引组织方式单级索引组织方式n主要问题主要问题n可能要花费较多的外存空间，尤其是对于小可能要花费较多的外存空间，尤其是对于小文件。文件。n文件大小受盘块大小限制。文件大小受盘块大小限制。n例，若每个盘块大小为例，若每个盘块大小为1KB，每个盘块号占，每个盘块号占4B，则索引块中可存放则索引块中可存放256

41、个盘块号，即采用这种索个盘块号，即采用这种索引方式时每个文件引方式时每个文件大小不能大小不能超过超过256KB。n解决方法解决方法n使用多个索引块，而对索引块再建索引。使用多个索引块，而对索引块再建索引。8.1.5 索引组织方式索引组织方式n多级索引组织方式多级索引组织方式8.1.5 索引组织方式索引组织方式n多级索引组织方式多级索引组织方式n若每个盘块大小为若每个盘块大小为1KB，每个盘块号占，每个盘块号占4B，则，则一级索引块中可存放一级索引块中可存放256个盘块号，即对应个盘块号，即对应256个二级索引块个二级索引块n每个二级索引块可对应每个二级索引块可对应256个物理磁盘块，采个物理磁

42、盘块，采用这种索引方式时每个文件大小不能超过用这种索引方式时每个文件大小不能超过256*256*1KB=64MBn若每个盘块大小为若每个盘块大小为4K，则最大文件大小为，则最大文件大小为1K*1K*4K=4GB8.1.5 索引组织方式索引组织方式n混合索引组织方式混合索引组织方式n直接地址直接地址提高文件的检索速度提高文件的检索速度n在索引结点中设置在索引结点中设置10个直接地址项，个直接地址项， 即用即用iaddr(0)iaddr(9)来存放直接地址来存放直接地址n一次间接地址一次间接地址n对于大、对于大、 中型文件，可再利用索引结点中的地址项中型文件，可再利用索引结点中的地址项iaddr(

43、10)来提供一次间接地址。这种方式的实质就来提供一次间接地址。这种方式的实质就是一级索引分配方式是一级索引分配方式n多次间接地址多次间接地址n当文件长度大于当文件长度大于4 MB+40 KB时时(一次间址与一次间址与10个直个直接地址项接地址项)， 系统还须采用二次间址分配方式。这系统还须采用二次间址分配方式。这时，用地址项时，用地址项iaddr(11)提供二次间接地址。该方式提供二次间接地址。该方式的实质是两级索引分配方式。的实质是两级索引分配方式。8.1.5 索引组织方式索引组织方式直接地址直接地址物理盘块物理盘块索引块索引块8.1.5 索引组织方式索引组织方式n优缺点优缺点n优点：优点：

44、n保持了链接结构的优点保持了链接结构的优点, ,又解决了其缺点：又解决了其缺点：即能顺序存取即能顺序存取, ,又能随机存取，满足了文件又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用动态增长、插入删除的要求，也能充分利用外存空间。外存空间。n缺点：缺点：n较多的寻道次数和寻道时间，索引表本身增较多的寻道次数和寻道时间，索引表本身增加系统开销，如：内外存空间，存取时间。加系统开销，如：内外存空间，存取时间。8.1 外存的组织方式外存的组织方式n文件物理结构的比较文件物理结构的比较n连续文件的连续文件的优点优点是不需要额外的空间开销，只要在文是不需要额外的空间开销，只要在文件目录中指

45、出文件的大小和首块的块号即可，对顺序件目录中指出文件的大小和首块的块号即可，对顺序的访问效率很高。适应于顺序存取。的访问效率很高。适应于顺序存取。缺点缺点是动态地增是动态地增长和缩小系统开销很大；文件创建时要求用户提供文长和缩小系统开销很大；文件创建时要求用户提供文件的大小；存储空间浪费较大。件的大小；存储空间浪费较大。n链式文件克服了连续文件的不足之处，但文件的随机链式文件克服了连续文件的不足之处，但文件的随机访问系统开销较大。适应于顺序访问。访问系统开销较大。适应于顺序访问。DOS系统中改系统中改造了链式文件的结构，使其克服了链式文件的不足，造了链式文件的结构，使其克服了链式文件的不足，但

46、增加了系统的危险性。但增加了系统的危险性。8.1 外存的组织方式外存的组织方式n文件物理结构的比较文件物理结构的比较n索引文件既适应于顺序存访问，也适应于随机索引文件既适应于顺序存访问，也适应于随机访问，是一种比较好的文件物理结构，但要有访问，是一种比较好的文件物理结构，但要有用于索引表的空间开销和文件索引的时间开销。用于索引表的空间开销和文件索引的时间开销。UNIX系统是使用索引结构成功的例子。系统是使用索引结构成功的例子。n在当前流行的一些在当前流行的一些UNIX操作系统的版本中，操作系统的版本中，同时支持连续文件结构和索引文件结构。同时支持连续文件结构和索引文件结构。DOS、WINDOW

47、S系统支撑类似于文件映照结构。系统支撑类似于文件映照结构。8.2 空闲空间的管理空闲空间的管理n解决的问题：解决的问题：n如何为新创建的文件分配存储空间？如何为新创建的文件分配存储空间？n解决的方法：解决的方法：n（分配的基本单位都是磁盘块）。（分配的基本单位都是磁盘块）。n分配方式：分配方式：n连续分配：访问速度高，但会产生外存零头。连续分配：访问速度高，但会产生外存零头。n离散分配：访问速度慢，但能有效利用外存空间。离散分配：访问速度慢，但能有效利用外存空间。n分配时数据结构分配时数据结构n分配回收算法分配回收算法8.2 空闲空间的管理空闲空间的管理n8.2.1 空闲表法和空闲链表法空闲表

48、法和空闲链表法n8.2.2 位示图法位示图法n8.2.3 成组链接法成组链接法8.2.1 空闲表法和空闲链表法空闲表法和空闲链表法n空闲表法空闲表法连续分配方式连续分配方式n与内存的动态分配方式相同，为每个文件分配一与内存的动态分配方式相同，为每个文件分配一个连续的存储空间。个连续的存储空间。n为外存上的所有空闲区建立一张空闲表，每个空为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个闲表项，将所有空闲区按起始盘闲区对应于一个闲表项，将所有空闲区按起始盘块号递增的顺序排列块号递增的顺序排列n存储空间的分配与回收可采用存储空间的分配与回收可采用首次适应算法、循首次适应算法、循环首次适应算法

49、环首次适应算法等等n如对换方式中对如对换方式中对对换空间对换空间的分配就采用连续分配，的分配就采用连续分配，主要目的是提高速度。主要目的是提高速度。n系统中的系统中的较小文件较小文件也也采用连续采用连续分配方式，如分配方式，如“簇簇”8.2.1 空闲表法和空闲链表法空闲表法和空闲链表法n空闲表法空闲表法分配与回收分配与回收n空闲盘区的分配与内存的动态分配类似，同样空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。是采用首次适应算法、循环首次适应算法等。8.2.1 空闲表法和空闲链表法空闲表法和空闲链表法n空闲链表法空闲链表法n将所有空闲盘区，拉成一条空闲链。将所有

50、空闲盘区，拉成一条空闲链。n将磁盘上所有空闲区空间，以盘块为单位拉成一条将磁盘上所有空闲区空间，以盘块为单位拉成一条链，当用户因创建文件而请求分配存储空间时，系链，当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块链给统从链首开始，依次摘下适当数目的空闲盘块链给用户。当用户因删除文件而释放存储空间时，系统用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。将回收的盘块依次插入空闲盘块链的末尾。：分配和回收一个盘块的过程非常简单。分配和回收一个盘块的过程非常简单。：但在为一个文件分配盘块时，可能要重复多但在为一个文件分配盘块时，可能要重

51、复多次操作。次操作。8.2.1 空闲表法和空闲链表法空闲表法和空闲链表法n空闲链表法空闲链表法n将磁盘上所有空闲盘区拉成一条链，在每个盘将磁盘上所有空闲盘区拉成一条链，在每个盘区上包含若干用于指示下一个空闲盘区的指针，区上包含若干用于指示下一个空闲盘区的指针，指明盘区大小的信息。指明盘区大小的信息。n分配盘块时，通常采用首次适应算法（显式链分配盘块时，通常采用首次适应算法（显式链接法）。接法）。n在回收时，将回收区与空闲盘区相合并在回收时，将回收区与空闲盘区相合并。8.2.2 位示图法位示图法n位示图位示图n用用二进制的一位二进制的一位来表示磁盘中一个盘块来表示磁盘中一个盘块的使用情况的使用情

52、况n0：盘块空闲；盘块空闲；n1：盘块已分配盘块已分配n由所有盘块所对应的二进制位构成的一由所有盘块所对应的二进制位构成的一个集合称为位示图，通常可用个集合称为位示图，通常可用mn个位个位数来构成位示图，并使数来构成位示图，并使mn等于磁盘总等于磁盘总块数。块数。8.2.2 位示图法位示图法内存中表示内存中表示外存中表示外存中表示8.2.2 位示图法位示图法n盘块的分配盘块的分配n顺序扫描位示图，从中找出一个或一组其值为顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位；的二进制位；n将所找到的一个或一组二进制位，将所找到的一个或一组二进制位， 转换成与之转换成与之相应的盘块号。假定找到

53、的其值为相应的盘块号。假定找到的其值为“0”的二进的二进制位，位于位示图的第制位，位于位示图的第i行、第行、第j列，则其相应列，则其相应的盘块号应按下式计算的盘块号应按下式计算b = n(i - 1) + jn修改位示图，修改位示图， 令令mapij=1。8.2.2 位示图法位示图法n盘块的回收盘块的回收n将回收盘块的盘块号转换成位示图中的行号和列号。将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为转换公式为i = (b - 1) DIV n + 1j = (b - 1) MOD n + 1n修改位示图，修改位示图， 令令map ij=0n如上例中，第如上例中，第16号物理块，可计算

54、得号物理块，可计算得ni = (16 - 1) DIV 16 + 1 = 1nj = (16 - 1) MOD 16 + 1 = 16n同理，第同理，第17块可计算得块可计算得ni = (17 - 1) DIV 16 + 1 = 2nj = (17 - 1) MOD 16 + 1 = 1 8.2.2 位示图法位示图法n主要优点主要优点n很容易找到一个或一组相邻接的空闲盘块。很容易找到一个或一组相邻接的空闲盘块。n例，需要找到例，需要找到6个相邻接的空闲盘块，这只需在位个相邻接的空闲盘块，这只需在位示图中找出示图中找出6个其值连续为个其值连续为“0”的位即可。的位即可。n由于位示图很小，占用空间

55、少，因而可将它保由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行盘区分配时，存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，从而节省了无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。因此，常用于微型机和许多磁盘的启动操作。因此，常用于微型机和小型机中，如小型机中，如CP/M、Apple-DOS等等OS中。中。 8.2.3 成组链接法成组链接法n在大型文件系统中，空闲表或空闲链表太长，在在大型文件系统中，空闲表或空闲链表太长，在UNIX系统中，两种方法结合形成系统中，两种方法结合形成成组链接法。成组链接法。n空闲盘块的组织空闲盘块的组织n空闲

56、表空闲表和和空闲链表空闲链表结合形成的空闲盘块管理。结合形成的空闲盘块管理。n空闲盘块号栈空闲盘块号栈 用来存放当前可用的一组空闲盘块用来存放当前可用的一组空闲盘块号以及栈中尚有的空闲盘块数号以及栈中尚有的空闲盘块数N。n文件区中的所有空闲盘块被分成若干个组，如文件区中的所有空闲盘块被分成若干个组，如100块块/组。组。n将每组含的有盘块数和该组所有盘块号记入前一将每组含的有盘块数和该组所有盘块号记入前一组第一个盘块中。组第一个盘块中。n将第一组的空闲盘块数和所有盘块号记入空闲盘将第一组的空闲盘块数和所有盘块号记入空闲盘块号栈。块号栈。8.2.3 成组链接法成组链接法8.2.3 成组链接法成组

57、链接法n空闲盘块的分配与回收空闲盘块的分配与回收n分配分配n检查空闲盘块号栈是否上锁，如未上锁，便从栈顶检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格然后将栈顶指针下移一格n若该盘块号已是栈底，若该盘块号已是栈底， 即即S.free(0)，当前栈中最后，当前栈中最后一个可分配的盘块号一个可分配的盘块号n调用磁盘读过程，将栈底盘块号所对应盘块的内容调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘

58、块分配出去对应的盘块分配出去n分配一相应的缓冲区分配一相应的缓冲区n把栈中的空闲盘块数减把栈中的空闲盘块数减1并返回并返回8.2.3 成组链接法成组链接法n空闲盘块的分配与回收空闲盘块的分配与回收n回收回收n将回收盘块的盘块号记入空闲盘块号栈的顶将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加部，并执行空闲盘块数加1操作；操作；n当栈已满时，记入新回收的盘块中，再将其当栈已满时，记入新回收的盘块中，再将其盘块号作为新栈底。盘块号作为新栈底。8.3 提高磁盘提高磁盘I/O速度的途径速度的途径n8.3.1 磁盘高速缓存磁盘高速缓存n8.3.2 提高磁盘提高磁盘I/O速度的其它方法速度的

59、其它方法n8.3.3 廉价磁盘冗余阵列廉价磁盘冗余阵列8.3.1 磁盘高速缓存磁盘高速缓存n磁盘高速缓存的形式磁盘高速缓存的形式读一个磁盘块写一个磁盘块复制到内存读/写数据8.3.1 磁盘高速缓存磁盘高速缓存n磁盘高速缓存的形式磁盘高速缓存的形式不受应用程序不受应用程序多少的限制多少的限制应用程序多时应用程序多时缓存可能很小缓存可能很小方式二：缓冲池方式二：缓冲池方式一：固定区域方式一：固定区域请求分页请求分页系统和磁系统和磁盘盘I/O时时共享共享8.3.1 磁盘高速缓存磁盘高速缓存n数据交付方式数据交付方式数据交付数据交付Data Delivery方式一：数据交互方式一：数据交互方式二：指针

60、交互方式二：指针交互复制复制8.3.1 磁盘高速缓存磁盘高速缓存n置换算法置换算法请求写请求写磁盘磁盘写写回回常用算法有常用算法有LRU、NRU、LFU等等n还需考虑以下几点还需考虑以下几点n访问频率访问频率n可预见性，如正在写数据的未满盘块可预见性，如正在写数据的未满盘块n数据的一致性数据的一致性将高速缓存中的所有盘块数据构成一个将高速缓存中的所有盘块数据构成一个LRU链，将会影响链，将会影响到数据一致性的盘块和到数据一致性的盘块和很久都不可能再用很久都不可能再用的盘块放在的盘块放在LRU链的链头，使其优先被写回磁盘，不久后还要再使用的盘链的链头，使其优先被写回磁盘，不久后还要再使用的盘块放