第7章 文件系统2

操作系统原理PrinciplesofOperatingSystem,主讲：孔宪君,2,7.5外存空间管理,7.5.1磁盘存储器磁盘的三个重要参数是磁道、扇区、柱面（对应磁头），根据磁盘的三个重要参数可以把磁盘中一个逻辑块的号转化成相应的包含磁道、扇区、磁头的磁盘地址。扇区是磁盘存储器中一个很重要的概念扇区通常的容量是512byte磁盘的容量CylindersHeadsSector512byte,7.5.2空闲区表,当系统需要给文件分配存储空间时，系统依次扫描空闲区域记录，有合适的空闲区域记录，就进行分配。如果文件需求存储空间和空闲区域相等则删除该表目，否则修改适当内容。一个文件被用户撤销时，就将其存储区收回，此时系统又依次扫描空闲区域记录，如果有与该区相邻的空闲文件可合并之。否则另外找一空白记录，将释放的区填上作为又一空闲区域记录。这种方法适合于建立连续文件。,7.5.3空闲块链表空闲块链表把磁盘上所有的空闲块链接起来，当系统需要给文件分配存储空间时，就从链头上依次取下若干块来，然后调整链首指针。而撤销文件时则回收的空闲存储块，把释放的空闲块逐个插入链首，然后调整链首指针。这种方法只需在系统中保留一个链首指针，令其指向第一个空闲块。这种方法的优点是简单，但工作效率较低，每次在链上添加和移出空闲块时，需要做I/O操作。例如把一空闲块插入链时，要把链首指针(原指向第一个空闲块)写该空闲块中，然后让链首指针指向该空闲块。从链中摘取空闲块时也要读取下一个空闲块的指针。,7.5.4位示图,系统为磁盘建立一张位示图(bitmap)，在位示图中按物理块的顺序排列。每一个比特位对应文件存储器上的一个物理块，并表示物理块的状态，“1”表示对应的物理块已占用，“0”表示空闲。如360KB的软盘，每个物理块为512字节，640个物理块，每个字32位，位示图只占用20个字。位示图中的某位置mapi，j对应第i字，第j位。n代表字长，转换公式如下：转换公式如下：物理块号b=ni+ji=b/nj=b%n修改位示图。令mapi，j1。,6,7.5.5成组链接法,成组链接法原理如下：,7,7.6文件共享和文件安全,7.6.1文件共享文件共享有以下两种形式：静态共享：文件被多个用户使用，用相同或不同的名字来访问同一文件，可以由存取权限控制访问级别。动态共享：文件被多个进程使用，各自使用自己的读写指针或共享读写指针。,8,1.基于索引节点的共享方式,为了便于文件的共享，采用文件名和文件说明分离的目录结构有利于实现文件共享。UNIX操作系统就是将文件说明分为目录项和索引节点两部分，基于索引节点的共享方式分为静态共享和动态共享两种。,9,2.利用符号链实现文件共享,不利于文件主删除它拥有的文件,10,符号链接是另一种链接方法。共享某文件时，系统为共享的用户创建一个link类型的新文件，将这新文件登记在该用户共享目录项中，这个link型文件包含链接文件的路径名。该方式中，只有文件主拥有指向其索引节点的指针，其它共享的用户只有该文件的路径名。当用户要访问共享文件时，首先读取link型文件，操作系统根据link文件类型将文件读出的内容作为路径名去访问真正的共享文件。采用符号链接可以跨越文件系统，甚至可以通过计算机网络链接到世界上任何地方的机器中的文件，此时只需提供该文件所在机器的地址以及在该机器中的文件路径。,11,7.6.2文件系统的可靠性,文件系统的可靠性是指文件系统抵抗和预防各种物理性破坏和人为性破坏的能力。如果文件系统被破坏了，在很多情况下是无法恢复的。特别是对于那些程序文件、客户档案、市场计划或其他数据文件丢失的客户来说，这不亚于一场大的灾难。1.磁盘坏块问题2.转储和恢复静态转储和动态转储海量转储和增量转储日志文件,7.6.3事务和检查点,1.事务的定义事务是用于访问和修改各种数据项的一个程序单位，事务也可以被看作是一系列相关读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，只有对分布在不同位置的同一数据所进行的读和写操作全部完成时，才能再以托付操作(CommitOperation)来终止事务。只要有一个读或写操作失败，便须执行夭折操作。一个夭折的事务，通常已执行了一些操作，因而可能已对某些数据做了修改。为使夭折的事务不会引起数据的不一致性，须将该事务内刚被修改的数据项恢复成原来的情况，使系统中各数据项与该事务未执行时的数据项内容完全相同。该事务需要被退回(rolledback)。事务操作具有原子性，一个事务在对一批数据执行修改操作时，要么全部完成，并用修改后的数据去代替原来的数据，要么一个也不修改。,2.事务处理为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现。这些数据结构被放在稳定存储器中，用来记录在事务运行时数据项修改的全部信息，故又称为运行记录。该记录中包括有下列字段：事务名：用于标识该事务的惟一名字。数据项名：它是被修改数据项的惟一名字。旧值：修改前数据项的值。新值：修改后数据项将具有的值。在事务记录表中的每一记录，描述了在事务运行中的重要事务操作，如修改操作、开始事务、托付事务或夭折事务等。在一个事务Ti开始执行时，Ti开始记录被写入事务记录表中。在Ti执行期间，在Ti的任何一个写操作之前，便写一个适当的新记录到事务记录表中，当Ti进行托付时，把一个Ti托付记录写入事务记录表中。,由于一组被事务Ti修改的数据以及它们被修改前和修改后的值，都能在事务记录表中找到，因此，利用事务记录，系统能处理任何故障而不致使故障造成非易失性存储器中信息的丢失。恢复算法可利用以下两个过程：undo(Ti)。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。redo(Ti)。该过程能把所有被事务Ti修改过的数据，设置为新值。如果系统发生故障，系统应对以前所发生的事务进行清理。通过查找事务记录表，可以把尚未清理的事务分成两类。已全部完成的事务。确定为这一类事务的依据是，在事务运行记录中，既包含了Ti开始记录，又包含了Ti托付记录。此时系统利用redo(Ti)过程，把所有已被修改的数据设置成新值。未全部完成的事务。对于事务Ti，如果在运行记录中只有Ti开始记录而无Ti托付记录，则便属于这类事务。此时，系统便利用undo(Ti)过程，将所有已被修改的数据，恢复为修改前的值。,3.检查点当系统发生故障时，必须去检查整个运行记录，以确定哪些事务需要利用redo(Ti)过程去设置新值，而哪些事务需要利用undo(Ti)过程去恢复数据的旧值。引入检查点(CheckPoints)的主要目的是使对事务记录表中事务记录的清理工作经常化，即每隔一定时间便做一次下述工作：首先是将驻留在内存中的当前事务记录表中的所有记录，输出到稳定存储器中。其次是将驻留在内存中的所有已修改数据，输出到稳定存储器中。然后是将事务记录表中的检查点记录，输出到稳定存储器中。最后是每当出现一个检查点记录时，系统便执行的恢复操作，利用redo(Ti)和undo(Ti)过程实现恢复功能。在引入检查点后，可以大大减少恢复处理的开销。因为在发生故障后，并不需要对事务记录表中的所有事务记录进行处理，而只需对最后一个检查点之后的事务记录进行处理。因此，恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti，在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo(Ti)和undo(Ti)过程对它们进行处理。,16,7.6.4文件系统的一致性,1.块的一致性检查在进行块的一致性检查时，检测程序构造一张计数器表，表中为每个块设立两个计数器，初始化都为0。一个计数器跟踪该块在文件中出现的次数，一个跟踪该块在空闲表中出现的次数。检测程序读取全部的文件索引表，每当读到一个块号时，第一个计数器加1；然后检测程序检查空闲块链表或位图，查找全部未使用的块，每当找到一个空闲块，则第二个计数器加1。,17,数据不一致的异常情况，可能会导致如下几种情况：块丢失重复数据块空闲表中有重复块,18,7.6.6文件系统可恢复性,由于磁盘速度远远低于内存与CPU的速度，磁盘读写就成为计算机整体速度的瓶颈。为此可通过使用磁盘高速缓存来改善性能，虽然文件读操作不会破坏磁盘一致性，但是由于文件