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