计算机操作系统第八章-磁盘存储器的管理

1、第八章 磁盘存储器的管理第一节 文件的物理结构和外存的分配方式一、概述磁盘是一种可直接存取的随机存储器(这一点与内存相似)，一个逻辑盘可以看作一片连续的存储空间。确定外存空间的分配方式 (组织文件的物理结构)主要考虑：提高文件的访问速度、有效地利用外存空间。常用的外存分配方法有：连续分配、链接分配、索引分配。二、磁盘存储空间的结构磁盘说明图1盘块(扇区)是磁盘上的最小存储分配单位，每个盘块有唯一编号；地址是：磁道(柱面)号+扇区号+盘面号；从盘块编号到地址的转换由硬件完成，在OS中一个盘块的地址就是盘块编号。一般一个盘块的大小与内存分页中页(内存块)的大小一致，一页存放到一个盘块中。三、连续分

2、配1、思想方法为每个文件分配一组位置相邻接的盘块(磁盘上的地址连续/盘块编号连续的盘块)，文件中的逻辑页被顺序地存放到邻接的各物理盘块中。这保证了文件中的逻辑顺序与文件占用盘块顺序的一致性。这样物理结构的文件称为顺序文件；每个文件都从分配给它的一个盘块的第一个字节开始存放。文件地址：在文件的目录中，存放该文件的第一个记录所在的盘块号和文件的长度(共占多少块)。图 8-1 磁盘空间的连续分配 2、优缺点u 存取容易，存取速度较快；u 必须事先知道文件的长度，不利于文件的动态增长；u 存放一个文件要求足够大的连续存储空间；u 存储空间的管理存在“碎片”问题，须定时整理。四、链接分配1、思想方法：为

3、每个文件分配一组位置离散的盘块，每个盘块中存放文件的一个逻辑页；通过给每个盘块设置一个指针，将属于同一个文件的盘块链接在一起，链接的顺序和文件的逻辑页的顺序一致。这样物理结构的文件称为链接文件。保存链接指针的方式有两种，形成了隐式链接和显式链接。2、隐式链接-链接指针如何存放页块号下一页下一页的指针(块号)091161162121310310425425无-1图 8-2 磁盘空间的链接式分配文件的每一个盘块内都含有指向下一个逻辑页存放地址的指针(盘块号)。文件地址：在文件的目录中，存放指向文件第一个盘块的指针和文件长度。隐式链接的问题： P553、显式链接-链接指针如何存放每个磁盘(逻辑盘)有

4、一张文件分配表(FAT)，它是记录磁盘分配使用情况的数据结构(记录文件的链接指针序列)。磁盘包含N个盘块，FAT就有N个表项。表项顺序编号0N-1，对应盘块的编号0N-1。文件地址：每个文件占用的第一个盘块的编号存放在文件目录中；文件占用的其他盘块的编号存放在FAT中；文件占用的每一个盘块对应的FAT表项，其中存放指向该文件的下一个盘块的指针(即盘块编号)；文件占用的最后一个盘块对应的FAT表项中存放文件结束标志；(文件的FCB+FAT表为每个文件记录的两个信息)目录和FAT一起记录了哪些盘块分给了这个文件，以及这些盘块中内容的逻辑顺序。例如，MS-DOS的文件物理结构图8-4 MS-DOS的

5、文件物理结构5、优缺点优点：l 与内存的分页式存储管理相似，提高了磁盘空间利用率l 不存在外存碎片问题l 有利于文件动态扩充缺点：u 较多的寻道次数和寻道时间，存取速度相对慢些u 存在可靠性问题，如指针出错u 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。 u FAT需占用较大的存储空间。6、从FAT12到FAT32，NTFS：P61-62，65，68，70-72五、索引分配1、思想方法为每个文件分配一组位置离散的盘块，每个盘块中存放文件的一个逻辑页；为每个文件建立一个物理结构的索引表(类似于内存管理的页表)，记录分配给该文件的物理盘块，以及这些

6、盘块和文件逻辑页顺序的对应关系。建立一个文件时，要初始化它的索引表，并将索引表的地址放到文件的目录中。打开一个文件时，文件的索引表也被同时读入内存。这样物理结构的文件称为索引文件。这种结构的文件，支持直接访问。图8-6 索引分配方式2、单级索引每个文件一张索引表，这张索引表放在一个盘块中(因此也称索引块，索引表的长度不能超过一块的容量)。缺点：u 要花费一定的外存空间存放索引表；u 文件的长度受到了限制。3、多级索引对于一个长文件的长索引表(单个盘块放不下)，可以将它存放在若干个离散的盘块中。再为这些索引块建立一个索引表，存放在一个盘块中，这样就形成了一个文件的两级索引。同理，还可以构造多级索

7、引。图 6-12 两级索引分配4、混合索引文件系统混合使用多种分配方式。文件的目录中可以存放不同形式的地址信息：l 直接地址，文件数据的盘块号；l 一次间接地址，文件索引块的盘块号；l 二次间接地址，文件二级索引块的盘块号。图 6-13 混合索引方式 5、索引分配的优缺点l 优点：保持了链接结构的优点，又解决了其缺点：既能顺序存取，又能随机存取，满足了文件动态增长缩短、插入删除的要求，也能充分利用外存空间。u 缺点：较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间。第二节 文件存储空间管理一、文件存储空间管理涉及到的问题1、外存上的空闲块按什么方式组织起来(存储管理

8、的数据结构)2、如何为一个文件分配存储空间3、怎样回收被释放的存储空间注意：文件存储器基本的分配和回收单位是磁盘块、簇，而不是字节。二、空闲表(空白文件目录)管理法1、空闲块的组织：将磁盘空间上每一片连续空闲区(包含若干个连续编号的空闲块)看作一个“空白文件”，系统建立一个空闲表(空白文件目录)，每个空白文件在表中占一行。序号第一空闲盘块号空闲盘块数124293315542、存储空间的分配与回收方法与内存的动态分区分配类似(连续分配)，也有首次适应算法、循环首次适应算法、最佳适应算法等。这样的存储分配方法，文件的物理结构是顺序文件。在内存管理上，连续分配方式很少采用，但在外存管理上，由于它具有

9、较高的分配速度，磁盘访问速度也较快，这种管理方法仍然可能被采用。三、空闲链表法1、空闲块链法：将磁盘上所有的空闲块拉成一条链，在链首设一个分配指针，在链尾设一个回收指针。空闲块的分配与回收分别在链的首尾进行。2、空闲区链法：将磁盘上所有的空闲区(包含若干连续空闲块)拉成一条链，空闲区中要记录本区包含的空闲块数，链收尾分别设分配、回收指针。存储空间的分配与回收与内存的动态分区分配类似。四、位示图法1、空闲块的组织：为每一个文件存储器(逻辑盘)建立一张位示图。磁盘的每一个物理块都有一个二进制位与之对应。该位值是“0”为空闲、“1”为已分配。开机后位示图常驻内存，存在连续若干个字中。2、存储空间的分

10、配与回收 位示图需要多少个字，取决于一个逻辑盘包含的盘块数(簇)。 分配物理块时，可以在位示图中顺序查找一个或若干其值为0的位，计算并返回每位对应的物理块号，分配物理块，并将位示图中对应的位置“1”； P130 回收物理块时，将回收的物理块号逆计算，得出块在位示图中的位置，并将对应的位置“0”。 P131五、成组链法图8-11 空闲盘块的成组链接法1、空闲块的组织： 将系统的所有空白块每N个形成一组(例如N=100；这N个空白块位置不必连续)； 将所有的空白块组链接起来。链接的方法是：每一组的第一个空白块存放前一组的盘块总数和包含的每一个盘块号； 由于第一组的前面已无其他组存在，因此，第一组的

11、块数为N-1块； 由于存储设备的空间块不一定正好是N的整倍数，因而最后一组可能不足N块。由于该组后面已无另外的空闲块组，所以，该组的盘块号与总块数组织成堆栈，放在管理文件存储设备用的文件资源表中； 系统在初启时把文件资源表复制到内存，从而使文件资源表中存放有最后一组空闲块的块号与总块数的堆栈被进入内存，空闲块的分配与释放在内存进行。2、存储空间的分配 堆栈指针i的初值等于最后一组的空闲块数。 当申请者提出空闲块需求时，按照后进先出的原则，分配程序取走i所指的块号，将对应盘块分配出去，然后再做一次i=i-1操作，并将空闲块数减1。 这个过程一直持续到本次任务所要求的块都已分配完毕或堆栈中只剩下最

12、后一个空闲块的块号。 当堆栈中只剩下最后一个空闲块号时，系统启动I/O管理程序，将该块中存放的前一组的块号与总块数读入内存堆栈中，之后将该块分配给申请者。然后，系统重新设置i指针，分配程序继续为申请者进程分配空闲块，直到满足本次任务。3、存储空间的回收 在系统回收空闲盘块时，盘块回收过程首先进行i=i+1操作，将回收盘块的盘块号记入堆栈的顶部，并执行空闲盘块数加1操作。 当堆栈中空闲盘块数目已达到N时，表示栈已满、本组回收已结束。如果这时如果又有一个新的空闲盘块待回收，便将目前堆栈中的内容(N个盘块号和盘块总数)，记入新回收的盘块中；然后重置i值为1、空闲盘块数初值1，再将新回收的盘块号存进栈

13、底，另起一个组。 存放空闲块号与块总数的堆栈是一个临界资源，应该互斥访问。第三节 提高磁盘I/O速度的途径一、提高文件系统的访问速度，可以从三方面着手： P263二、磁盘高速缓存目前，磁盘的访问速度远低于内存访问速度，磁盘I/O成为了计算机系统的瓶颈。于是，出现了磁盘的高速缓存。这里的高速缓存是在内存中为磁盘的盘块设置一个缓冲区，在其中保存某些盘块的副本。对信息进出内存，采取提前读和推迟写。 P2631、磁盘高速缓存的形式在内存中高速缓存可分成两种形式： 第一种是在内存中开辟一个单独的存储空间，作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响； 第二种是将所有空闲的内存空间供请求分页

14、系统和磁盘高速缓存共享。此时高速缓存的大小不再是固定的。当磁盘I/O较频繁时，该缓冲区可能包含更多的内存空间；而在应用程序运行得较多时，该缓冲区可能只剩下很少的内存空间。2、数据交付： P178系统可以采取两种数据交付方式： 数据交付。这是直接将高速缓存中的数据复制到请求者进程的内存工作区中。 指针交付。只将指向高速缓存中某区域的指针(地址)， 交付给请求者进程。后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存空间到进程的内存工作区的时间。3、置换算法高速缓存的容量是有限的，满了以后再继续使用，也需要进行存储块的置换。这里解决的是缓冲区中的盘块内容，何时往磁盘上写。常用的算法与页面

15、置换算法基本相同。除了考虑到最近最久未使用这一原则外，还考虑了以下几点：(1) 访问频率。(2) 可预见性。(3) 数据的一致性。4、周期性地回写磁盘根据置换算法，高速缓存中经常被访问的块会一直存放在其中，不会有机会被换出(写回磁盘)。而内存是易失性存储器。为了保证数据不丢失，OS要经常主动将数据写回磁盘上。例如：在UNIX系统中专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30s。这样，因系统故障所造成的工作损失不会超过30 s的劳动量

16、。而在MS-DOS中所采用的方法是：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透高速缓存”(write-through cache)。MS-DOS所采用的写回方式，几乎不会造成数据的丢失， 但须频繁地启动磁盘。三、提高磁盘I/O速度的其他方法 提前读 P187 推迟写 P188 优化一个文件所分配磁盘物理块的分布 虚拟盘(要注意它和缓冲区的区别) P191第四节 磁盘容错技术一、磁盘容错技术的定义：是通过增加冗余的磁盘驱动器、磁盘控制器、数据结构等方法，来提高磁盘系统可靠性的一种技术。它分为三个级别：SFT-I； SFT-II； SFT-III。二、第一级

17、容错：防止因磁盘表面缺陷而造成的数据丢失。主要技术有： 双份目录、双份文件分配表(FAT)； P152 写后读校验； P154 热修复重定向； P153三、第二级容错：防止磁盘驱动器故障和磁盘控制器故障造成的数据丢失。主要技术有： 磁盘镜像； P155图 6-26 磁盘镜像示意 磁盘双工； P157四、第三级容错：高级系统容错技术 P159-167第五节 数据一致性控制一、什么是数据一致性数据一致性是指存放在不同位置的同一个数据(如不同文件内的同一个数据)，在数据处理的过程中要保持一致。为实现数据一致性，OS中要配置相应的软件，并需要一定的硬件支持。数据一致性的硬件支持，主要是在系统中配置一个

18、稳定存储器。通常采用磁盘双工来实现。二、事务1、什么是事务： 事务是访问和修改各种数据项的一个程序单位(一个程序段或一个读、写操作的序列)。 事务尤其是指对存放在不同位置的同一个数据的一套访问和修改操作的程序单位。例如，一个银行账号对应一卡一折，此情况下的存取款过程。 对事务进行操作所具有“原子性”。一个事务的执行，要么全部完成-所有的操作成功执行完毕，用修改后的数据去替代原有的数据；要么“夭折”-只要有一个操作没有成功，就要将事务前面进行的操作废除，将数据恢复成原来的值(一个都不改)。例如：2、事务记录如何实现“恢复”呢？通常要借助于一种数据结构-事务记录，来记录在事务运行时数据被修改的全过

19、程。事务记录以表的形式被存放在稳定存储器中。事物记录不强调永久保存，但强调安全保存。 事务运行的每一次数据访问操作都被记录在事务记录表中，形成一条事务记录。(1) 事务记录的结构 事务名： 用于标识该事务的惟一名字 数据项名： 它是被修改的那个数据项的惟一名字 旧值： 修改前数据项的值 新值： 修改后数据项将具有的值(2) 访问操作的记录过程： 事务Ti执行开始，标记被记入事务记录表； 事务Ti每进行一次数据访问，就形成一条事务记录； 事务Ti执行结束，标记被记入事务记录表。(3) 当出现故障时，就调用恢复算法，检查事物记录表中的每个事物，进行事务清理。事务清理可以使用以下两个过程： undo

20、(Ti)：将所有被某事务Ti修改过的数据恢复成修改前的值；(并注释该事物的记录) redo(Ti)：将所有被某事务Ti修改过的数据确认为新值；(并注释该事物的记录)事物清理：对于尚未完成的事物，用undo(Ti)；对已经完成的事物，用redo(Ti)。(4) 在没有发生故障时，也应该定时清理事务。这样，一旦系统出现故障，恢复算法就只需要清理最后一个检查点之后的事务记录。检查点就是系统进行定时事务清理的时间点。检查点到来时，就进行事物清理：对于尚未完成的事物，用undo(Ti)；对已经完成的事物，用redo(Ti)。 P176设置了定时清理的系统，新的恢复算法：恢复例程首先查找事务记录表，确定在最近一个检查点之前执行的最后一个事务Ti；只对所有Ti之后开始的事物进行清理，对所有Ti之前开始