第9章 磁盘存储器管理new.ppt

1、内容磁盘I/O外部内存分配方法管理可用存储空间磁盘容错技术改进文件系统性能数据一致性控制，第九章磁盘内存管理，提高I/O速度的主要方法：选择性能良好的磁盘，并使用适当的调度算法设置磁盘缓存9.1.1磁盘性能简述9.1.2磁盘调度算法，9.1磁盘I/O，数据盘片的组织磁盘最基本的组件是由硬金属制成并涂有磁介质的磁盘，不同容量硬盘中的磁盘数量各不相同。每个光盘都有两面，可以记录信息。以光盘中心为中心的光盘表面上半径不同的同心圆称为轨道。扇区磁盘被分成许多扇区，每个扇区称为一个扇区，硬盘的每个扇区可以存储512字节的信息。在FAT32模式下，每个扇区的容量为4KB。每个扇区的大小相当于一个磁盘块。磁

2、头每个磁盘的每一侧都有一个读写磁头，用来读取相应磁盘表面的内容。用于通过头部号码进行区分。9.1.1磁盘性能简介9.1.1磁盘性能简介柱面由不同磁盘上半径相同的磁道组成的柱面称为柱面。轨道和圆柱是半径不同的圆。在许多情况下，履带和油缸可以互换使用。扇区、磁道(或柱面)和磁头数量构成硬盘结构的基本参数，有助于获得硬盘的容量。基本计算公式为：存储容量、磁头数、磁道数(柱面)、扇区数、每个扇区的字节数，1.44M=28018512。这种类型的磁盘在固定磁头磁盘的每个磁道上都有一个读/写磁头，所有的磁头都装入一个磁臂，通过这些磁头访问所有的磁道。并行读写主要用于移动大容量磁盘的磁头。每个磁盘表面只有一

3、个磁头，它安装在一个磁臂上，可以访问磁盘表面的所有磁道。磁头必须移动才能寻道，只能串行读写，导致输入输出速度慢，结构简单。它广泛用于中小型磁盘。微型计算机上的硬盘和软盘都采用移动磁头的结构。9.1.1磁盘性能的简要描述。磁盘访问时间寻道时间(Ts)将磁头从当前位置移动到指定磁道所需的时间通常为230毫秒，平均约为10毫秒。ts=m * n s s-磁盘启动时间，约3 msm-移动一个磁道所用的时间，对于普通磁盘：m 0.3毫秒，对于高速磁盘：m 0.1毫秒；n-移动轨迹的数量；9.1.1磁盘性能的简要说明，旋转延迟时间(tr)指定扇区在磁头下移动的时间。Tr=1/2r(平均来说，它需要旋转半圈

4、)r盘的旋转速度，单位为秒。如果硬盘转速为7200转/分，旋转延迟时间为60100720024.17毫秒。一个5400 (rpm)的硬盘，旋转延迟时间是601000540025.56毫秒。300/600 (rpm)软盘的平均旋转延迟时间为6010003002100毫秒和601000600250毫秒。9.1.1磁盘性能简要说明，传输时间Tt从磁盘读取数据或向磁盘写入数据所需的时间约为十分之几毫秒，可以忽略不计。Ttb/rN b字节读和写r磁盘旋转速度(以秒为单位)n字节一个磁道访问时间Ta=Ts Tr Tt=(m*n s) 1/2r b/rN，9.1.1磁盘性能简要说明，移动磁头磁道可完成哪个过

5、程，旋转磁盘扇区可完成哪个过程，目标可完成哪个过程。也就是说，移动的轨道的平均数量)最小。9.1.2磁盘调度算法，首先提供最简单的FCFS(先到先得)磁盘调度算法，并根据进程请求访问磁盘的顺序进行调度。优点是公平简单，每个流程的请求可以依次处理，使得某个流程不能长时间得到满足。缺点：寻道未优化，平均寻道时间可能较长。9.1.2磁盘调度算法，9.1.2磁盘调度算法，最短寻道时间优先SSTF(最短寻道时间优先)选择要访问的磁道和当前磁头所在的磁道之间距离最近的进程。优点：每次寻道时间最短。缺点不能保证最短的平均寻道时间。在SSTF，进程“饥饿”发生在9.1.2磁盘调度算法、9.1.2磁盘调度算法和

6、扫描算法中。如果新的进程不断出现，并且它们所访问的轨道接近前一个轨道，那么这些进程将被优先执行，而旧的进程永远不会得到满足。扫描算法不仅考虑被访问磁道与当前磁道之间的距离，而且优先考虑磁头的当前移动方向，也称为电梯调度算法。它具有更好的寻道性能和防止进程饥饿的优点。它广泛应用于大、中、小型计算机和网络中的磁盘调度，这可能会严重延迟请求的处理。9.1.2磁盘调度算法、9.1.2磁盘调度算法、9.1.2磁盘调度算法、9.1.2磁盘调度算法和循环扫描算法CSCAN(循环扫描)规定磁头在一个方向上移动，即使是最小的磁道。9.1.2磁盘调度算法，N步扫描算法，N步扫描，并改进了以前的算法，磁头可能在磁道

7、上静止不动，导致其他进程无法及时执行磁盘输入/输出。磁盘输入输出请求队列被分成长度为n的子队列，每次都使用FCFS来处理这些子队列。在每个队列中，扫描算法用于处理N个请求。当n较大时，该算法的性能接近扫描算法。当N=1时，算法退化为FCFS算法。双队列扫描算法FSCAN简化了N步扫描算法，即将磁盘I/O请求分成两个队列，将当前请求磁盘I/O的进程放入一个队列，将新生成的磁盘I/O请求放入另一个队列。交替使用扫描算法来处理队列。9.2外部存储分配方法，即文件物理组织模式，其目标是：有效地利用外部存储空间来提高文件访问速度9.2.1连续分配9.2.2链接分配9.2.3索引分配9.2.1连续分配，这

8、就要求每个文件有一组相邻的磁盘。优点顺序存取容易：连续空间顺序存取快；一个或相邻轨道上的缺点需要连续的存储空间；形成外部碎片；在运行时修改或删除时，很容易形成外部片段。文件的长度必须事先知道：加载的要求；预估计小于实际文件，因此停止复制并重新估计；如果文件动态增长，应该保留空间，但这会导致空间使用效率低下。9.2.1连续分配，9.2.2链接分配，简介：类似于内存管理：进程占用连续的内存空间(内部和外部分数)，并离散地占用内存空间；文件占用连续的外部存储空间(碎片)，并离散地占用外部存储空间；解决方案：在每个磁盘块上设置一个链接指针，将属于同一个文件的多个离散的磁盘块链接到一个链表中，从而形成一

9、个物理文件来链接文件。外部碎片被消除，可以动态添加、删除和修改。9.2.2链接分配，隐式链接包含指向文件目录的每个目录条目FCB中链接文件的第一个和最后一个磁盘块的指针，这仅适用于顺序访问，但对于随机访问来说效率极低且可靠性差。改进：几个磁盘块被分组到一个集群中，该集群分布在集群中，并且链接文件的元素也在集群中，这可以减少搜索时间和指针占用的存储空间，但是增加了内部碎片。9.2.2链路分配，9.2.2链路分配。显式链接将用于链接文件物理块的指针显式存储在内存中的链接表中，即文件分配表FAT。P266不能支持对FAT的有效直接访问，因为FAT占用了很大的内存空间。9.2.2链路分配，FCB A、

10、FCB B、FAT、MS-DOS/Windows 98 FAT表结构，MS-DOS文件系统的文件物理结构采用FAT表结构。在这种结构中，为了克服从链接文件中随机读取任何逻辑块需要许多磁盘输入/输出操作的缺点，每个磁盘块中的链接指针存储在磁盘的开头，形成一个称为FAT表的表。FAT表中的每个条目存储一个链接指针(下一个簇号)，并且每个FAT表条目占用12位或16位，这被称为FAT12或FAT16。对于软盘，由于其容量小和簇少，使用12位FAT表，对于硬盘，使用16位FAT表。FAT表文件系统最初是为小型硬盘的目录结构设计的。由于簇的数量最多只能用16位来表示，即最多只能有64K个簇，为了用FAT

11、表来管理大的磁盘分区，每个簇中包含的扇区数量只能增加，簇的大小一般根据磁盘的类型和容量来确定，如下表所示。当然，每个簇中包含的扇区数量增加，这导致内部部分的浪费，这对于小文件来说尤其严重。为了减少窗口98中另一个头的浪费，每个簇的数量可以用32位表示，并且每个簇中包括的扇区数量可以减少，这被称为FAT32。FAT16和FAT32文件系统的群集和扇区关系也显示在下表中。1，9.2.3索引分配，单级索引分配为每个文件分配一个索引表，并在索引表中记录分配给该文件的磁盘号。在文件目录中，填写指向索引表的指针。优点：支持直接访问，没有外部碎片。缺点：索引表在外部内存空间，索引块需要匹配小文件。9.2.3

12、索引分配，0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23多级索引分配P268，二级索引，磁盘空间，360，740，1125，主索引，9.2.3索引分配，3。混合分配模式由于80以上的文件都是小文件，为了解决高速访问小文件和管理大文件之间的矛盾，UNIX将直接寻址，一级索引和二级索引UNIX系统V在UNIX系统V的索引节点有13个地址项di_addr13，将存储的地址项分为两类，其中最后三个地址项分别是一级索引、二级索引和三级索引的指针。 而前十个地址项是直接寻址的，即文件逻辑块的第09个块的磁盘号。 例如，当每个磁盘块

13、的大小为4KB时，当文件小于40KB时，文件的所有磁盘块号都可以直接从索引节点中读取，因此读取小文件的速度很快；如果文件大于40KB，系统将逐步增加主索引、次索引和三级索引，使最大管理文件为40 KB 4 GB 4 TB，达到管理大文件的目的。例如，文件系统中有一个20MB的大文件和一个20KB的小文件。当分别采用连续、链接、单级索引、二级索引和UNIX系统V分配方案时(每个块的大小为4096B，每个块的地址用4B表示)，要求3360 1。每个文件系统管理的最大文件是什么？2.每个方案需要多少个特殊块来记录文件的物理地址(解释每个块的用途)？3如果您需要读取一个大文件的前5.5KB和后5.5K

14、B(16M 5.5KB)信息，每个方案需要多少个磁盘输入/输出操作？本示例旨在帮助读者深入比较文件物理组织的各种方案：连续文件的连续分配、链接文件的链接分配、二级索引分配、链接索引分配和UNIX直接与间接混合分配，并阐明各种分配方案的优缺点和UNIX分配方案的设计特点。示例-解决方案，1。各种分配方案的文件系统可以管理的最大文件连续分配：它是无限制的，可以与整个磁盘文件区域一样大。链接分配：同上。单层指数：同上。辅助索引：因为磁盘块的大小是4KB，每个地址用4B表示，所以一个磁盘块可以存储1K个索引条目，辅助索引管理的最大文件容量是4KB1K1K4GB。如果您想管理较大的文件，您需要使用三重索

15、引，它可以管理4TB大小的文件。UNIX混合分配：最大可管理文件为40KB4MB 4GB4TB。2.每个分配方案需要多少个特殊块来记录文件的物理地址？连续分配：对于大文件和小文件，只需要在文件控制块FCB中设置两个项目，一个是第一个物理块的块号，另一个是文件总数。不需要特殊的块来记录文件的物理地址。示例-解决方案，链接分配：对于大文件和小文件，只需要在文件控制块FCB中设置两个项目，一个是第一个物理块的块号，另一个是文件总数；同时，在用于存储文件的每个物理块中设置用于存储下一个块的块号的指针。单级索引：一个20KB的小文件只有五个物理块，因此只需要一个特殊的物理块作为索引块来保存文件每个物理块

16、的块号。一个20MB的文件有5K个物理块。由于链接索引的每个索引块只能保存(1K1)个物理块号(并且一个条目被用作索引块链接指针)，因此它需要6个特殊的物理块作为链接索引块来存储文件的每个块的物理地址。二级索引：对于20KB的小文件，一个作为一级索引，另一个作为二级索引，两个特殊的物理块作为索引块；对于20MB的大文件，一个用作一级索引，五个用作二级索引，六个特殊物理块用作索引块。示例-解决方案，UNIX混合分配：对于20KB的小文件，在文件控制块FCB的i_addr13中仅使用前五个条目来存储文件的物理块号，不需要特殊的物理块。对于20MB的大文件，FCB的i_addr13使用前10个条目来

17、存储大文件的前10个物理块的块号，使用第一级索引块来存储大文件的下一个1K块号，并且还使用第二级索引来存储大文件之后的块号。二级索引使用一个一级索引和四个二级索引。总共需要6个特殊的物理块来存储文件的物理地址。3.读取大文件之前的5.5 KB和之后的5.5KB需要多少磁盘输入/输出操作？连续分配：为了读取大文件的前后信息，需要计算文件中信息的相对块数。前信息的相对逻辑块数为5.5K4K=1，后信息的相对逻辑块数为(16M5.5K)/4K=4097。然后计算物理块号文件相对于逻辑块号的第一块号，最后通过磁盘输入输出操作读出块信息。示例-解决方案，链接分配：要在大型文件前读取5.5千字节的信息，只需读取一次标题块以获取信息所在块的块号，然后读取一次第一个逻辑块以获取所需信息。在读取大文件后面的16MB5.5KB信息时，需要按顺序读出信息所在块前面的块，并且需要4097次磁盘输入输出操作才能获得信息所在块的块号。最后，执行一次输入/输出操作以读出块信息。因此，总共需要4098个磁盘操作系统来读取(16MB 5.5KB)字节的信息。单级索引：要读取大文件前面的5.5KB信息，只需读取第一个索引块一