第8章__磁盘存储器管理1new

1、第8章 磁盘存储器管理外存组织方式方法空闲存储空间的管理磁盘容错技术文件系统性能的改善数据一致性控制2022-3-1728.1 外存的组织方式n连续组织方式n链接(串联)组织方式n索引组织方式常用的三种外存组织方式方式：常用的三种外存组织方式方式：2022-3-1738.1.1 连续组织方式n连续组织方式：为每个文件组织方式相邻的物理块（数据块/盘块/扇区）。n组织方式给文件的首物理块的地址被登记在它的目录项内。n由连续组织方式方式形成的文件物理结构被称为顺序文件结构，相应的物理文件则称为顺序文件(Sequential File)。2022-3-174 磁盘空间的连续组织方式0 01 12 2

2、3 34 45 56 67 78 89 91010111112121313141415151616171718181919202021212222232324242525262627272828292930303131文件名文件名 始址始址 块数块数count 0 2count 0 2tr 14 3tr 14 3mail 19 6mail 19 6list 28 4list 28 4f 6 2 f 6 2 文件目录文件目录countcountf ft tr rmaimail llislist t2022-3-175连续组织方式优缺点优点(Strongpoint) ：顺序访问容易顺序存取速度快缺

3、点(Disadvantage) ：要求连续的存储空间。易产生外存碎片，空间利用率降低须事先知道文件长度。不利于文件动态增长2022-3-1768.1.2 链接组织方式 (Linked Allocation)n一种离散组织方式方式。n通过每个盘块上的链接指针，将同一个文件的多个离散的盘块链接成一个链表。n可分为隐式链接和显示链接两种方式。1. 隐式链接隐式链接：将一文件离散地存放在外存上，：将一文件离散地存放在外存上，并将下一个物理块的地址登记在组织方式并将下一个物理块的地址登记在组织方式给它的前一个物理块中。给它的前一个物理块中。2022-3-177某个链接文件示意2022-3-178 磁盘空

4、间的链接式组织方式文件名文件名 始址始址 末址末址jeep 9 25jeep 9 25文件目录文件目录0 01 12 23 34 45 56 67 78 89 910101111121213131414151516161717181819192020212122222323242425252626272728282929303031311 110101616-1-125252022-3-179隐式链接优缺点优点：n消除了外部碎片，提高利用率n允许作业动态增长。缺点：n可靠性差：一个指针出现问题，导致整个链断开只适合于顺序访问，不适合随机访问。2022-3-17102. 显示链接 将文件离散地存

5、放，并将链接各个物理块的指针显式地登记在内存的一张文件组织方式表FAT(File Allocation Table)中。2022-3-1711显示链接特点优点：显著提高检索速度缺点：不支持大文件随机存取FAT需要占用较大的内存空间2022-3-1712思 考如果硬盘是16G空间，盘块大小为4K，一个FAT表项占多少位？FAT表需占用多少空间？如果文件A占用硬盘的第11，12，16，14四个盘块，试画出文件A中各盘块间的连接及FAT的情况。2022-3-17138.1.3 索引组织方式n也属于离散组织方式方式，它在存放文件同时，为每个文件建立一个索引表（盘块），以登记物理块号，并在文件目录项的地

6、址字段中填上指向该索引表的指针。2022-3-1714索引组织方式方式0 01 12 23 34 45 56 67 78 89 91010111112121313141415151616171718181919202021212222232324242525262627272828292930303131文件名文件名 索引表地址索引表地址文件目录文件目录Jeep 19Jeep 19 9 91616 1 110102525 -1 -1 -1 -1 -1 -119192022-3-17158.1.3 索引组织方式优缺点 (Strongpoint and Disadvantage)优点：支持高效的随

7、机存取消除了外部碎片允许文件动态增长。缺点：索引表本身也要花费较多外存空间，造成外存空间浪费。2022-3-171601210510625435635798510510625474035635711259853607401125主索引主索引360第二级索引第二级索引磁盘空间磁盘空间2022-3-1717总结三种外存组织方式n连续组织方式n链接组织方式n索引组织方式思考题：各种组织方式方式的优缺点是什么？2022-3-17188.2文件存储空间的管理v为对文件存储空间进行管理，常用以下几种方法进行：n空闲表法n空闲链表法n位示图法n成组链接法2022-3-17198.2.1 空闲表法和空闲链表法

8、n空闲表法：属于连续组织方式方式，为每个文件组织方式一块连续空间。系统为外存上的所有区建立一张空闲表，每个空闲区对应一个空闲表项，每个表项包括表项序号、空闲区的第一个盘块号和空闲区的盘块数。优点：空闲区组织方式与回收容易。缺点：空闲表也会浪费很大存储空间。2022-3-1720序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数1242933155图图6-216-21空闲盘快表空闲盘快表2022-3-17212 空闲链表法：将文件存储空间中的所 有空闲区拉成一条空闲链表。v根据构成链的基本元素是空闲盘块或空闲盘区，再分为空闲盘块链或空闲盘区链。2022-3-17228.2.2 位示图法n位

9、示图法：利用二进制的一位来表示文件存储空间中的一个盘块的使用情况。其值为0表示空闲，为1表示组织方式，这样由所有盘块所对应的位构成一个集合，称为位示图。2022-3-17231. 位示图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16123451100011100100110000111111000011111100011111100002022-3-17242. 盘块的组织方式 n(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。n(2) 将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，

10、位于位示图的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+jn式中， n代表每行的位数。n(3) 修改位示图， 令mapi,j=1。2022-3-17253. 盘块的回收 n(1) 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为：i=(b-1)DIV n+1 j=(b-1)MOD n+1n(2) 修改位示图。 令mapi,j=0。 2022-3-17278.2.3 成组链接法nUNIX系统中空闲盘块管理方法n将一个文件卷的所有空闲盘块分成固定大小的组（如100个盘块），将每一组的盘块号和盘块数记入前一组的最后一个盘块中，第一组的盘块数和盘块号记入空闲盘块栈中。2

11、022-3-17281004003993013001003002992022012991004003992013019907999790179007899780179997901空闲盘块号栈S.free0198992022-3-17308.3 提高磁盘IO速度v高速缓存。v提前读，延迟写。v优化物理块分布优化物理块分布v虚拟盘。2022-3-1731思考题 2n假设磁盘转速为20ms/圈，磁盘格式化时每个磁道被划分成10个扇区，今有10个逻辑记录（每个记录大小刚好与扇区大小相等）存放在同一条磁道上，处理程序每次从磁道读出一个记录要花费4ms进行处理，先要求顺序处理这10个记录，若磁头现在处于首

12、个逻辑记录的起始位置。n按逆时针安排10个逻辑记录（磁盘顺时针方向旋转）处理程序处理完这10条记录花费的时间是多少？1.按优化分布重新安排这10条记录，计算所需要的时间2022-3-1732思考题 3n假定磁盘的移动臂现在处于第8柱面，有如下6个请求者等待访问磁盘，请你列出最省时间的响应次序：序号 柱面号 磁头号 扇区号1 9 6 32 7 5 63 15 20 64 9 4 45 20 9 56 7 15 28.4 磁盘容错技术磁盘容错技术 (1) 通过存取控制机制来防止由人为因素所造成的文件通过存取控制机制来防止由人为因素所造成的文件不安全性。不安全性。 (2) 通过磁盘容错技术，通过磁盘

13、容错技术， 来防止由磁盘部分的故障所造来防止由磁盘部分的故障所造成的文件不安全性。成的文件不安全性。 (3) 通过通过“后备系统后备系统”来防止由自然因素所造成的不安来防止由自然因素所造成的不安全性。全性。 1. 第一级容错技术第一级容错技术SFT- 1) 双份目录和双份文件组织方式表双份目录和双份文件组织方式表 在磁盘上存放的文件目录和文件组织方式表在磁盘上存放的文件目录和文件组织方式表FAT， 是是文件管理所用的重要数据结构。如果这些表格被破坏，文件管理所用的重要数据结构。如果这些表格被破坏， 将将导致磁盘上的部分或全部文件成为不可访问的，因而也就导致磁盘上的部分或全部文件成为不可访问的，

14、因而也就等效于文件的丢失。为了防止这类情况发生，可在不同的等效于文件的丢失。为了防止这类情况发生，可在不同的磁盘上或在磁盘的不同区域中，分别建立磁盘上或在磁盘的不同区域中，分别建立(双份双份)目录表和目录表和FAT。 其中，一份被称为主目录及主其中，一份被称为主目录及主FAT； 把另一份称为把另一份称为备份目录及备份备份目录及备份FAT。 2) 热修复重定向和写后读校验热修复重定向和写后读校验 热修复重定向热修复重定向(Hot-Redirection)。 (2) 写后读校验写后读校验(Read after write Verification)方式。方式。 2. 第二级容错技术第二级容错技术S

15、FT- (1) 磁盘镜像磁盘镜像(Disk Mirroring)。 磁盘控制器主机通道磁盘驱动器图图 6-26 磁盘镜像示意磁盘镜像示意 (2) 磁盘双工磁盘双工(Disk Duplexing)。 图图 6-27 磁盘双工示意磁盘双工示意 主机磁盘控制器磁盘控制器通道通道磁盘驱动器2022-3-17388.5 数据一致性v一个数据同时出现在多个不同的对象中时，即可能会出现数据一致性问题。v事务v检查点v并发控制v硬件稳定存储器的支持2022-3-17398.5.1 事务n事务：它是一种原子性操作，是用于访问和修改各种数据项的一个程序单位，可被看作一系列的读和写操作。n事务的原子性操作须借助于存

16、放在稳定存储器中的事务记录表（log)来实现，表中的每条记录描述了事务运行中的重要操作，一旦出现错误，便立即回滚。2022-3-17402. 事务记录(Transaction Record) n事务名： 用于标识该事务的惟一名字；n数据项名： 它是被修改数据项的惟一名字；n旧值： 修改前数据项的值；n新值： 修改后数据项将具有的值。2022-3-17413. 恢复算法 恢复算法可利用以下两个过程： (1) undoTi。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。(2) redoTi。该过程能把所有被事务Ti修改过的数据，设置为新值。 如果系统发生故障， 系统应对以前所发生的事务进行

17、清理。 2022-3-17428.5.2 检查点检查点：主要目的是使对事务记录表中事务记录的清理工作经常化。2022-3-1743n首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中；n其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；n然后是将事务记录表中的检查点记录，输出到稳定存储器中； n最后是每当出现一个检查点记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。2022-3-17448.5.3 并发控制n由信号量实现一个事务执行完再执行另一个事务，实现了事务的顺序性。2022-3-17458.5.4 重复数

18、据的数据一致性问题1. 重复文件的一致性 2022-3-17462. 盘块号一致性的检查2022-3-17473. 链接数一致性检查n配置一张计数器表，为每个文件建立一个表项，其中含有该索引结点号的计数值。n 在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。n当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较，如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。 2022-3-1748习 题 1n请分别解释在连续组织方式、链接组织方式、索引组织方式方式中如何将

19、文件的字节偏移量3500转换为物理块号和块内位移量(假设盘块大小为1KB，盘块号需占4个字节)2022-3-1749习 题 2n存放在某个磁盘上的文件系统采用混合索引组织方式方式，其FCB中共有13个地址项，第0-9个地址项为直接地址，第10个地址项为一次间址，第11个地址项为二次间址，第12个地址项为三次间址。如果每个盘块的大小为512字节，若盘块号需要3个字节描述，每个盘块最多存放170个盘块地址，则（1）该文件系统允许文件的最大长度？（2）将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移？（3）假设文件的FCB已经在内存，但其他信息均在外存，为了访问该文件中某

20、个位置的内容，最少需要几次访问磁盘，最多几次访问磁盘？2022-3-1750习 题 3n某系统采用成组链接法管理磁盘的空闲空间，目前磁盘的状态如图所示。n（1）该磁盘中目前还有多少个空闲盘块n（2）简述磁盘的组织方式过程n（3）在为某个文件组织方式3个盘块后，系统要删除另一个文件，并回收他的5个盘块，他们的盘块号依次为700、711、703、788、701清画出回收后的盘块链接图五、例 一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、链接、单级索引、二级索引和UNIX Sytem V 组织方式方案时(每块大小为4096B,每块地址用4B表示)，问:1.各文件系统管理的最

21、大的文件是多少? 2.每种方案对大、小二文件各需要多少专用块来记录文件的物理地址(说明各块的用途) ?3如需要读大文件前面第5.5KB和后面（16M5.5KB）信息，则每个方案各需要多少次盘I/O操作? 这个范例是帮助读者深入比较文件物理组织的各种方案：顺序文件的连续组织方式、链接文件的链接组织方式、二级索引组织方式、链接索引组织方式和UNIX的直接间接混合组织方式，明确各种组织方式方案的优缺点和UNIX组织方式方案的设计特点。例-解答1.各种组织方式方案的文件系统可管理的最大文件n 连续组织方式：不受限制，可大到整个磁盘文件区。n 链接组织方式：同上。n单级索引：同上。n 二级索引：由于盘块

22、大小为4KB，每个地址用4B表示，一个盘块可存1K个索引表目，二级索引可管理的最大文件容量为4KB1K1K4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件。n UNIX混合组织方式：可管理的最大文件为40KB4MB+4GB4TB。2.每种组织方式方案对20MB大文件和20KB小文件各需要多少专用块来记录文件的物理地址?n连续组织方式：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件总块数，不需专用块来记录文件的物理地址。例-解答n 链接组织方式：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件总块数；同时在每块存文件的物

23、理块中设置存贮下一块块号的指针。n单级索引：对20KB小文件只有5个物理块大小，所以只需一块专用物理块来作索引块，用来保存文件的各块物理块块号。对于20MB大文件有5K个物理块大小，由于链接索引的每个索引块只能保存（1K1）个物理块块号（还有一个表目作索引块链接指针），所以它需要6块专用物理块来作链接索引块，用于保存文件各块的物理地址。n 二级索引：对大小文件都固定要用二级索引，对20KB小文件，用一块作第一级索引，用另一块作二级索引，共用二块专用物理块作索引块，对于20MB大文件，用一块作第一级索引，用5块作第二级索引，共用六块专用物理块作索引块。范例-解答 UNIX的混合组织方式：对20K

24、B小文件只需在文件控制块FCB的i_addr13中使用前5个表目存放文件的物理块号，不需专用物理块。对20MB大文件，FCB的i_addr13中使用前10个表目存放大文件前10块物理块块号，用一级索引块一块保存大文件接着的1K块块号，还要用二级索引存大文件以后的块号，二级索引使用第一级索引1块，第二级索引4块。总共也需要6块专用物理块来存放文件物理地址。3.为读大文件前面第5.5KB和后面（16M5.5KB）信息需要多少次盘I/O操作?n连续组织方式：为读大文件前面和后面信息都需先计算信息在文件中相对块数，前面信息相对逻辑块号为5.5K4K=1，后面信息相对逻辑块号为（16M5.5K）/4K=

25、4097。再计算物理块号文件首块号相对逻辑块号，最后化一次盘I/O操作读出该块信息。例-解答n链接组织方式：为读大文件前面5.5.KB的信息，只需先读一次文件头块得到信息所在块的块号，再读一次第1号逻辑块得到所需信息。而读大文件后面16MB5.5KB的信息，要先把该信息所在块前面块顺序读出，共化费4097次盘IO操作，才能得到信息所在块的块号，最后化一次I/O操作读出该块信息。所以总共需要4098次盘IO才能读取（16MB+5.5KB）字节信息。n单级索引：为读大文件前面5.5KB的信息，只需先读一次第一块索引块得到信息所在块的块号，再读一次第1号逻辑块得到所需信息，共化费2次盘IO操作。为读大文件后面（16MB+5.5KB）的信息，需要先化5次盘IO操作依次读出各索引块，才能得到信息所在块的块号，再化一次盘I/O操作读出该块信息。共化费6次盘IO操作。例-解