搜索
11第六章文件管理6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制26.5文件存储空间的管理6.5.1空闲表法和空闲链表法1.空闲表法空闲盘块表序号第一空闲盘块号空闲盘块数12429331554——3存储空间的分配与回收空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如:在为新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再分配该盘区并修改空闲表。在回收用户所释放的存储空间时，也类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，并对相邻接者应予以合并。42.空闲链表法(1)空闲盘块链。将磁盘上的所有空闲空间，以盘块为单位组织成一个链表。(2)空闲盘区链磁盘上的所有空闲空间，以盘区为单位组织成一个链表。每个盘区含有指示下一个空闲盘区的指针每个盘区说明本盘区大小(盘块数)的信息56.5.2位示图法1.位示图利用二进制的一位来表示磁盘中一个盘块的使用情况。位示图62.盘块的分配(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3)修改位示图，令map［i,j］=1。73.盘块的回收(1)将回收盘块的盘块号转换成位示图中的行号和列号。i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示图。令map［i,j］=1。86.5.3成组链接法1.100400399301300100300299…202201299…100400399…201301………9907999790179007899…78017999…7901空闲盘块号栈S.free019899空闲盘块的成组链接法9(1)空闲盘块号栈存放当前可用的一组空闲盘块的盘块号，以及栈中尚有的空闲盘块号的数量。图中栈向下生长，栈顶为s.free(99)(2)文件区中所有的空闲盘块以100个为单位分组。图中第一组盘块号为201~300，第二组301~400,…(3)将每组盘块总数和该组所有的盘块号即如前一组的第一个盘块中。注意各组第一个盘块分别是第300，400，…7900号盘块，而不是201，301，…这样的盘块(4)将第一组的盘块总数和所有盘块号记入空闲盘块号栈中，以供当前分配空闲盘块使用。(5)最后一组有99个空闲盘块和一个空闲盘块链结束标志。102.空闲盘块的分配(1)当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。(2)首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号。(3)若该盘块号不是位于栈底，则将与之对应的盘块分配给用户。然后将栈顶指针下移一格，栈中的空闲盘块数减1并返回。(4)若该盘块号已是栈底，为了接续空闲盘块链，须先调用磁盘读过程，将栈底盘块号所对应盘块的内容（下一组盘块号）读入栈中，然后将原栈底盘块号所对应的盘块分配出去。113.空闲盘块的回收(1)在系统回收空闲盘块时，须调用盘块回收过程进行回收。(2)将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。(3)当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中。再将其盘块号作为新栈底。图中从空闲盘块链的结束标志开始，7999号、7998号盘块…，依次往前回收，可得此空闲盘块链。12文件共享：系统允许多个用户（进程）共享同一份文件。为了节省存储空间，可以在系统中只保留共享文件的一份副本。6.6文件共享与文件保护13AABBBBBCCCCC根目录?CCC包含有共享文件的文件系统14(1)树型目录中，将共享文件或子目录链接到两个（或多个）用户的目录中，才能方便地找到该文件。(2)问题在于如果文件的盘块发生了变化，例如执行了Append操作，这些新增加的内容只会出现在执行了操作的目录中。(3)可以采用索引结点，将文件的物理地址等属性不再存放于目录项中，而是放在索引节点中。(4)在文件目录中只设置文件名及指向相应索引结点的指针，如下图所示。(5)索引结点中的链接计数变量count，表示链接到本结点的用户目录项的数量。6.6文件共享与文件保护6.6.1基于索引结点的共享方式15基于索引结点的共享方式Wang用户文件目录TestrLee用户文件目录Testrcount＝2文件物理地址索引结点Test16进程B链接前后的情况C的目录owner＝ccount＝1链接前C的目录owner＝ccount＝2建立链接后B的目录B的目录owner＝ccount＝1拥有者删除文件后176.6.2利用符号链实现文件共享(1)为了使用户B能共享用户C的一个文件F，系统可以创建一个LINK类型的新文件，也取名F，并将记入B的目录中。(2)新文件F只包含被链接文件F的路径名，此路径名被看作符号链。(3)只有文件主才拥有指向其索引结点的指针；共享该文件的其他用户，并不拥有指向其索引结点的指针。(4)不会发生在文件主删除共享文件后留下悬空指针的情况。186.6.2利用符号链实现文件共享(5)共享文件被删除后，其他用户试图通过符号链去访问一个这个文件时，会访问失败；于是再将符号链删除，此时不会产生任何影响。(6)符号链共享方式的问题：读取共享文件时，根据给定的文件路径名，逐个分量（名）地读取目录文件并查找目录，直至找到该文件的索引结点。多次读磁盘，速度慢。(7)符号链共享方式的优点：可以方便的链接网络中其它计算机中的共享文件。196.6.3磁盘容错技术(1)通过存取控制机制来防止由人为因素所造成的文件不安全性。(2)通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。(3)通过“后备系统”来防止由自然因素所造成的不安全性。201.第一级容错技术SFT-Ⅰ1)在磁盘上存放的文件目录和文件分配表FAT，是文件管理所用的重要数据结构。若这些表格被破坏，将导致磁盘上的部分或全部文件成为不可访问的，等效于文件的丢失。可在不同的磁盘上或在磁盘的不同区域中，分别建立主、备两份目录表和FAT。212)热修复重定向和写后读校验热修复重定向保留磁盘容量的一部分（2%~3%），用作存放磁盘缺陷区域的待写数据写后读校验1）每次从内存缓冲区向磁盘写入一个数据块后，立即从磁盘上读出该块内容，并作比较。2）若不一致，则重写。3）若重写后仍不一致，则将应写入该盘块的数据写入到热修复重定向区。222.第二级容错技术SFT-Ⅱ(1)磁盘镜像(DiskMirroring)。磁盘镜像示意23(2)磁盘双工(DiskDuplexing)。磁盘双工示意246.7数据一致性控制6.7.1事务1.事务的定义(1)事务是用于访问和修改各种数据项的一个程序单位，事务也可以被看作是一系列相关读和写操作。(2)只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以Commit操作来终止事务。(3)只要有一个读、写或修改操作失败，便须执行Abort操作，使系统中各数据项恢复至事务执行前的状态。事务原子性252.事务记录(TransactionRecord)事务记录存放于高度可靠的存储器中，用来记录事务运行时数据项修改的全部信息，又称为运行记录(Log)。包括如下信息：·事务名：·数据项名：·旧值：·新值：修改后数据项将具有的值。263.恢复算法(1)undo〈Ti〉。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。(2)redo〈Ti〉。该过程能把所有被事务Ti修改过的数据，设置为新值。如果系统发生故障，系统应对以前所发生的事务进行清理。276.7.2检查点1.检查点(CheckPoints)的作用作用是对事务记录表中事务记录的清理工作经常化。•首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中。•其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；•然后是将事务记录表中的〈检查点〉记录，输出到稳定存储器中；发生故障时，检查点之前commit的事务不必redo。286.7.3并发控制1.利用互斥锁实现“顺序性”2.利用互斥锁和共享锁实现顺序性3.互斥锁和共享锁的区别互斥锁仅允许一个事务对相应对象执行读或写操作共享锁允许多个事务对相应对象执行读操作，不允许其中任何一个事物执行写操作296.7.4重复数据的数据一致性问题1.重复文件的一致性UNIX类型的目录302.盘块号一致性的检查检查盘块号一致性情况31检查盘块号一致性情况323.链接数一致性检查配置一张计数器表，每个文件占一个表项。在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较。如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。