磁盘存储器管理new.ppt

内容 磁盘I/O 外存分配方法 空闲存储空间的管理 磁盘容错技术 文件系统性能的改善 数据一致性控制,第九章 磁盘存储器管理,提高I/O速度的主要途径： 选择性能好的磁盘 采用适当的调度算法 设置磁盘高速缓冲区 9.1.1 磁盘性能简述 9.1.2 磁盘调度算法,9.1 磁盘I/O,数据的组织 盘片（Platter ） 磁盘最基本的组成部分是由坚硬金属材料制成的涂以磁 性介质的盘片，不同容量硬盘的盘片数不等。每个盘片有两 面，都可记录信息。 磁道 (Tracks) 盘片表面上以盘片中心为圆心，不同半径的同心圆称为 磁道。 扇区(Sectors) 盘片被分成许多扇形的区域，每个区域叫一个扇区，硬 盘每个扇区可存储512字节信息。FAT32模式下，每个扇区的 容量为4KB。每个扇区的大小相当与一个盘块。 磁头(Heads) 每个盘片的每一面都会有一个读写头（read-write head ），来读取相应盘面的内容。习惯用磁头号来区分。,9.1.1 磁盘性能简述,9.1.1 磁盘性能简述,柱面 (Cylinders) 不同盘片相同半径的磁道所组成的圆柱称为柱面。磁道 与柱面都是表示不同半径的圆，在许多场合，磁道和柱面 可以互换使用。 扇区，磁道（或柱面）和磁头数构成了硬盘结构的基本 参数，帮这些 参数可以得到硬盘的容量，基计算公式为： 存储容量磁头数磁道（柱面）数每道扇区数每扇区字节数 1.44M =28018512,磁盘的类型 固定头磁盘 每条磁道上都有一个读/写磁头，所有的磁头被装入一个磁臂 通过这些磁头可以访问所有磁道，并进行并行读写 主要用于大容量磁盘 移动头磁盘 每个盘面仅有一个磁头，被装入一个磁臂中 为能访问盘面上的所有磁道，该磁头必须移动以进行寻道 只能串行读/写，致使I/O速度较慢 结构简单，广泛应用中、小型磁盘，微机上的硬盘和软盘，都采 用移动磁头结构,9.1.1 磁盘性能简述,磁盘访问时间 寻道时间（seek time）Ts 把磁头从当前位置移到指定磁道所经历的时间，一般为230毫秒，平均约为10毫秒。 Ts=m*n+s s-磁盘的启动时间,大约3ms； m-每移动一条磁道所经历的时间，对一般磁盘：m 0.3ms，对高速磁盘：m0.1ms； n-移动的磁道数目；,9.1.1 磁盘性能简述,旋转延迟时间（rotational latency time）Tr 指定扇区移动到磁头下所经历的时间。 Tr=1/2r （平均情况下，需要旋转半圈） r磁盘以秒计的旋转速度 一个7200（转/每分钟）的硬盘，则旋转延迟时间为 601000720024.17毫秒。 一个5400（转/每分钟）的硬盘，旋转延迟时间为 601000540025.56毫秒。 一个300/600（转/每分钟）软盘，平均旋转延迟时间为 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 磁盘性能简述,移动磁头磁道为哪个进程服务 旋转磁盘扇区为哪个进程服务 目标各进程对磁盘的平均访问时间（主要是平均寻 道时间，即平均移动的磁道数目）最小,9.1.2 磁盘调度算法,先来先服务FCFS（First-Come,First-Served） 最简单的磁盘调度算法，根据进程请求访问磁盘的先后次 序进行调度。 优点 公平、简单，每个进程的请求都能依次得到处理，不会 出现某个进程长时间得不到满足的情况。 缺点 未对寻道进行优化，平均寻道时间可能较长,9.1.2 磁盘调度算法,9.1.2 磁盘调度算法,最短寻道时间优先 SSTF（Shortest Seek Time First） 选择要访问的磁道与当前磁头所在的磁道距离最近的进程 优点 每次的寻道时间最短 缺点 不能保障平均寻道时间最短,出现进程“饥饿”现象,9.1.2 磁盘调度算法,9.1.2 磁盘调度算法,扫描算法SCAN 进程“饥饿”现象 在SSTF中，若不断有新进程到来，且其访问的磁道与当 前磁道的距离较近，这种进程被优先执行，而老进程一直得 不到满足。 SCAN算法 不仅考虑访问的磁道与当前磁道的距离，更优先考虑的 是磁头的当前移动方向，又称电梯调度算法。 优点 较好的寻道性能，又能防止进程“饥饿”现象，被广泛应用与大 、中、小型机及网络中的磁盘调度 缺点 可能使进程的请求被严重推迟,9.1.2 磁盘调度算法,9.1.2 磁盘调度算法,9.1.2 磁盘调度算法,循环扫描算法CSCAN(Circular SCAN) 规定磁头单向移动，即使最小磁道号与最大磁道号紧邻， 形成循环。,9.1.2 磁盘调度算法,N步扫描算法N-Step-SCAN、 改进前几种算法可能出现磁头静止在一个磁道上，导致其 它进程无法及时进行磁盘I/O。 把磁盘I/O请求队列分成长度为N的子队列，每次使用FCFS处理子队列，每个队列内部，使用SCAN算法处理N个请求。 当N很大时，该算法的性能接近于SCAN算法。 当N=1时，该算法退化为FCFS算法。 双队列扫描算法FSCAN 对N步扫描算法的简化，即把磁盘I/O请求分成两个队列， 当前请求磁盘I/O的进程放入一个队列，新生成的磁盘I/O请求放 入另一队列中。交替使用SCAN算法处理一个队列。,9.2 外存分配方法,即文件物理组织方式，其目标： 有效利用外存空间 提高文件的访问速度 9.2.1 连续分配 9.2.2 链接分配 9.2.3 索引分配,9.2.1 连续分配,连续分配（Continuous Allocation）要求为每一 个文件分配一组相邻的盘块。 优点 顺序访问容易：连续的空间 顺序访问速度快：一条或相邻的磁道上 缺点 要求有连续的存储空间：形成外碎片；运行时进行修改、删除也易形成外碎片。 必须事先知道文件的长度：装入时要求；预估计小于实际文件，需中止COPY，重新估计；若文件动态增长，应该预留空间，但会造成空间使用效率低。,9.2.1 连续分配,9.2.2 链接分配,引入： 与内存管理类似： 进程占有连续的内存空间（内、外零头）离散地占有内存空间； 文件占有连续的外存空间（碎片）离散地占有外存空间； 解决方法： 在每个盘块上设一链接指针，将同属于一个文件的多个离散盘块链接成一个链表，由此所形成的物理文件链接文件。 消除了外碎片，可以动态增、删、改。,9.2.2 链接分配,隐式链接 在文件目录的每个目录项FCB中含有指向链接文件第一和最后一个盘块的指针 只适用于顺序访问，对随机访问效率极低，可靠性差。 改进：将几个盘块组成一个簇（Cluster）,在进行分配时 以簇为单位进行，链接文件的元素也以簇为单位，这样可以成 倍减少查找时间，也可减少指针占用的存储空间，但增大了内 碎片。,9.2.2 链接分配,9.2.2 链接分配,显式链接 把用于链接文件各物理块的指针，显式的存放在内存的一 张链接表中，即文件分配表FAT（File Allocation Table）。P266 不能支持高效的直接存取 FAT占用较大的内存空间,9.2.2 链接分配,FCB A,FCB B,FAT,MS-DOS / Windows98 FAT表结构,MS-DOS文件系统的文件物理结构采用FAT表结构。该结构为了克服链接文件随机读取任一逻辑块需要化费多次盘I/O操作的不足，将各盘块中的链接指针集中存放在盘的开始部分，构成一张表，称为FAT表。FAT表每一项存放链接指针（下一个簇号），每个FAT表项占12位或16位，称为FAT12或FAT16。对于软盘因为容量小，簇数也少，采用12位FAT表，对于硬盘则采用16位FAT表。 FAT表文件系统原为小硬盘的目录结构而设计，由于簇的数目最多只能用16位表示，即最多只能有64K个簇，要用FAT表管理大的磁盘分区，只能采取增大每簇所包含的扇区数，一般根据磁盘的类型和容量大小来决定簇的大小，如下表所示。当然每簇包含扇区数增加，带来内零头的浪费，这对小文件特别严重。 Windows98为了减少内另头的浪费，可采取每簇的数目用32位表示，减少每簇包含扇区数，这称为FAT32。 FAT16 、FAT32文件系统簇和扇区关系也见下表所示。,MS-DOS / Windows98 FAT表结构-1,9.2.3 索引分配,单级索引分配 为每个文件分配一个索引表，把分配给该文件的盘块号， 记录在该索引表中。文件目录中，填上指向该索引表的指针。 优点 支持直接访问 不产生外碎片 缺点 索引表在外存空间，需为小文件也匹配索引块。,9.2.3 索引分配,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,9.2.3 索引分配,多级索引分配 P268,第二级索引,磁盘空间,360,740,1125,主索引,9.2.3 索引分配,3.混合分配方式 由于80以上文件是小文件，为了解决能高速存取小文件和管理大文件的矛盾，UNIX将直接寻址、一级索引、二级索引和三级索引结合起来，形成了混合寻址方式，如下图所示。,UNIX System V 混合寻址方式,在UNIX S V的索引结点中设有13个地址项di_addr13,它们把所存的地址项分成两类，其中最后三个地址项分别是一级索引、二级索引和三级索引的指针，而前面10个为直接寻址的地址项，即存放文件逻辑块第09块的盘块号。 如每个盘块大小为4KB时，当文件不大于40KB时，便可直接从索引结点中读出该文件全部盘块号，这样读小文件时速度快；如文件大于 40KB时，系统再逐步增加一级索引、二级索引和三级索引，这样最大管理的文件为40KB4MB4GB4TB，达到管理大文件的目标。,五、例,一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、链接、单级索引、二级索引和UNIX Sytem V 分配方案时(每块大小为4096B,每块地址用4B表示)，问: 1.各文件系统管理的最大的文件是多少? 2.每种方案对大、小二文件各需要多少专用块来记录文件的物理地址(说明各块的用途) ? 3如需要读大文件前面第5.5KB和后面（16M5.5KB）信息，则每个方案各需要多少次盘I/O操作? 这个范例是帮助读者深入比较文件物理组织的各种方案：顺序文件的连续分配、链接文件的链接分配、二级索引分配、链接索引分配和UNIX的直接间接混合分配，明确各种分配方案的优缺点和UNIX分配方案的设计特点。,例-解答,1.各种分配方案的文件系统可管理的最大文件 连续分配：不受限制，可大到整个磁盘文件区。 链接分配：同上。 单级索引：同上。 二级索引：由于盘块大小为4KB，每个地址用4B表示，一个盘块可存1K个索引表目，二级索引可管理的最大文件容量为4KB1K1K4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件。 UNIX混合分配：可管理的最大文件为40KB4MB+4GB4TB。 2.每种分配方案对20MB大文件和20KB小文件各需要多少专用块来记录文件的物理地址? 连续分配：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件总块数，不需专用块来记录文件的物理地址。,例-解答,链接分配：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件总块数；同时在每块存文件的物理块中设置存贮下一块块号的指针。 单级索引：对20KB小文件只有5个物理块大小，所以只需一块专用物理块来作索引块，用来保存文件的各块物理块块号。对于20MB大文件有5K个物理块大小，由于链接索引的每个索引块只能保存（1K1）个物理块块号（还有一个表目作索引块链接指针），所以它需要6块专用物理块来作链接索引块，用于保存文件各块的物理地址。 二级索引：对大小文件都固定要用二级索引，对20KB小文件，用一块作第一级索引，用另一块作二级索引，共用二块专用物理块作索引块，对于20MB大文件，用一块作第一级索引，用5块作第二级索引，共用六块专用物理块作索引块。,范例-解答,UNIX的混合分配：对20KB小文件只需在文件控制块FCB的i_addr13中使用前5个表目存放文件的物理块号，不需专用物理块。对20MB大文件，FCB的i_addr13中使用前10个表目存放大文件前10块物理块块号，用一级索引块一块保存大文件接着的1K块块号，还要用二级索引存大文件以后的块号，二级索引使用第一级索引1块，第二级索引4块。总共也需要6块专用物理块来存放文件物理地址。 3.为读大文件前面第5.5KB和后面（16M5.5KB）信息需要多少次盘I/O操作? 连续分配：为读大文件前面和后面信息都需先计算信息在文件中相对块数，前面信息相对逻辑块号为5.5K4K=1，后面信息相对逻辑块号为（16M5.5K）/4K=4097。再计算物理块号文件首块号相对逻辑块号，最后化一次盘I/O操作读出该块信息。,例-解答,链接分配：为读大文件前面5.5.KB的信息，只需先读一次文件头块得到信息所在块的块号，再读一次第1号逻辑块得到所需信息。而读大文件后面16MB5.5KB的信息，要先把该信息所在块前面块顺序读出，共化费4097次盘IO操作，才能得到信息所在块的块号，最后化一次I/O操作读出该块信息。所以总共需要4098次盘IO才能读取（16MB+5.5KB）字节信息。 单级索引：为读大文件前面5.5KB的信息，只需先读一次第一块索引块得到信息所在块的块号，再读一次第1号逻辑块得到所需信息，共化费2次盘IO操作。为读大文件后面（16MB+5.5KB）的信息，需要先化5次盘IO操作依次读出各索引块，才能得到信息所在块的块号，再化一次盘I/O操作读出该块信息。共化费6次盘IO操作。,例-解答,二级索引：为读大文件前面和后面信息的操作相同，首先进行一次盘IO读第一级索引块，然后根据它的相对逻辑块号计算应该读第二级索引的那块，第一级索引块表目号=相对逻辑块号1K，对文件前面信息11K0，对文件后面信息40971K4，第二次根据第一级索引块的相应表目内容又花一次盘IO读第二级索引块，得到信息所在块块号，再花一次盘IO读出信息所在盘块，这样读取大文件前面或后面信息都只需要3次盘IO操作。,例-解答,UNIX混合分配：为读大文件前面5.5KB信息，先根据它的相对逻辑块号，在内存文件控制块FCB的i_addr13第二个表目中读取信息所在块块号，而只化费一次盘IO操作即可读出该块信息。为读大文件后在（16MB5。5KB）信息，先根据它的相对逻辑块号判断它是在UNIX二级索引管理范围，先根据i_addr11内容化一次盘IO操作读出第一级索引块，再计算信息所在块的索引块号在第一级索引块的表目号为（4097-9-1024）10243，根据第一级索引块第3个表目内容再化费一次盘IO操作，读出第二级索引块，就可以得到信息所在块块号，最后化一次盘IO读出信息所在盘块，这样总共需要3次盘IO操作才能读出文件后面的信息。,例-解答,9.3 空闲存储空间的管理,9.3.1 空闲表法 9.3.2 空闲链表法 9.3.3 位示图法 9.3.4 成组链接法,9.3.1 空闲表法,为外存上的所有空闲区建立一张空闲表，每个空闲区对 应一个表目，包括序号、该区的起始空闲盘块号、空闲盘块数 目等，按起始空闲盘块号排序。 分配：是一种连续分配方式，顺序查找空闲表，找到 第一个合适的空闲区，修改空闲表。 回收：将相应块按序填回表中，并与前后合并成大块。 特点：连续存放，易产生碎片。,9.3.2 空闲链表法,空闲盘块链 将磁盘上所有空闲存储空间，以盘块为单位链成 一个链表。 分配：从链首开始，依次摘下适当数目的空闲盘 块进行分配。 回收：依次链入链尾。 特点：分配、回收简单，空闲盘块链可能很长。 空闲盘区链 将磁盘上所有空闲存储空间，以盘区（包括若干 盘块）为单位链成一个链表。 分配：查找合适大小的盘区进行分配 回收：与前后盘区合并 特点：分配、回收复杂，空闲盘区链较短。,9.3.3 位示图法,位示图 系统为文件存储空间建立一张位示图，如下图。位示图 反映了整个存储空间的分配情况，其中每一位对应一个物理块 ，“1”表示对应块已被分配，“0”表示对应块为空白。,位 号,字 号,9.3.3 位示图法,盘块的分配 顺序扫描位示图，找到一个或一组为“0”的二进制位 将位号、字号转换为盘块号，进行分配： 块号=位数*字号+位号 修改位示图，置“1”。 盘块的回