操作系统第六章文件管理

1、1第六章第六章 文件管理文件管理n6.1 文件和文件系统n6.2 文件的逻辑结构n6.3 外存分配方式n6.4 目录管理n6.5 文件存储空间的管理 n6.6 文件共享与文件保护n6.7 数据一致性控制6.5 文件存储空间的管理文件存储空间的管理 6.5.1 空闲表法和空闲链表法空闲表法和空闲链表法 1. 空闲表法空闲表法 空闲盘块表 序号第一空闲盘块号空闲盘块数12429331554 存储空间的分配与回收存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如: 在为新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小

2、能满足要求的空闲区，再分配该盘区并修改空闲表。在回收用户所释放的存储空间时，也类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，并对相邻接者应予以合并。 2. 空闲链表法空闲链表法 空闲盘块链。 将磁盘上的所有空闲空间，以盘块为单位组织成一个链表。 (2) 空闲盘区链 磁盘上的所有空闲空间，以盘区为单位组织成一个链表。 每个盘区含有指示下一个空闲盘区的指针 每个盘区说明本盘区大小(盘块数)的信息6.5.2 位示图法位示图法 位示图位示图 利用二进制的一位来表示磁盘中一个盘块的使用情况。位示图 2. 盘块的分配盘块的分配 (1) 顺序扫描位示图，从中找出一个或一组其值为

3、“0”的二进制位(“0”表示空闲时)。 (2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j式中， n代表每行的位数。 (3) 修改位示图， 令mapi,j=1。 3. 盘块的回收盘块的回收 (1) 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修改位示图。 令map i,j=1。 6.5.3 成组链接法成组链接法 1. 空闲盘块的组织空闲盘块的组织 1004003993013001003

4、002992022012991004003992013019907999790179007899780179997901空闲盘块号栈S.free019899空闲盘块的成组链接法 空闲盘块的组织空闲盘块的组织 空闲盘块号栈存放当前可用的一组空闲盘块的盘块号，以及栈中尚有的空闲盘块号的数量。 图中栈向下生长，栈顶为s.free(99)(2) 文件区中所有的空闲盘块以100个为单位分组。 图中第一组盘块号为201300，第二组301400,(3) 将每组盘块总数和该组所有的盘块号即如前一组的第一个盘块中。 注意各组第一个盘块分别是第注意各组第一个盘块分别是第300，400，7900号盘块号盘块，而不

5、是，而不是201，301，这样的盘块这样的盘块(4) 将第一组的盘块总数和所有盘块号记入空闲盘块号栈中，以供当前分配空闲盘块使用。(5) 最后一组有99个空闲盘块和一个空闲盘块链结束标志。 2. 空闲盘块的分配空闲盘块的分配当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。 (2) 首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号。(3) 若该盘块号不是位于栈底，则将与之对应的盘块分配给用户。然后将栈顶指针下移一格，栈中的空闲盘块数减1并返回。(4) 若该盘块号已是栈底，为了接续空闲盘块链，须先调用磁盘读过程，将栈底盘块号所对应盘块的内容（下一组盘块号）读入栈中，然

6、后将原栈底盘块号所对应的盘块分配出去。 3. 空闲盘块的回收空闲盘块的回收在系统回收空闲盘块时，须调用盘块回收过程进行回收。 (2)将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。(3)当栈中空闲盘块号数目已达100时， 表示栈已满，便将现有栈中的100个盘块号， 记入新回收的盘块中。再将其盘块号作为新栈底。 图中从空闲盘块链的结束标志开始，7999号、7998号盘块，依次往前回收，可得此空闲盘块链。 文件共享：系统允许多个用户（进程）共享同一份文件。 为了节省存储空间，可以在系统中只保留共享文件的一份副本。6.6 文件共享与文件保护文件共享与文件保护AABBBBBCCCC

7、C根目录?CCC包含有共享文件的文件系统 树型目录中，将共享文件或子目录链接到两个（或多个）用户的目录中，才能方便地找到该文件。(2) 问题在于如果文件的盘块发生了变化，例如执行了Append操作，这些新增加的内容只会出现在执行了操作的目录中。(3) 可以采用索引结点，将文件的物理地址等属性不再存放于目录项中，而是放在索引节点中。(4) 在文件目录中只设置文件名及指向相应索引结点的指针，如下图所示。(5) 索引结点中的链接计数变量count，表示链接到本结点的用户目录项的数量。6.6 文件共享与文件保护文件共享与文件保护6.6.1 基于索引结点的共享方式基于索引结点的共享方式 基于索引结点的共

8、享方式 Wang用户文件目录Test rLee用户文件目录Test rcount2文件物理地址索引结点Test进程B链接前后的情况 C的目录ownerccount1链接前C的目录ownerccount2建立链接后B的目录B的目录ownerccount1拥有者删除文件后6.6.2 利用符号链实现文件共享利用符号链实现文件共享 为了使用户B能共享用户C的一个文件F，系统可以创建一个LINK类型的新文件，也取名F，并将记入B的目录中。(2) 新文件F只包含被链接文件F的路径名，此路径名被看作符号链。只有文件主才拥有指向其索引结点的指针；共享该文件的其他用户，并不拥有指向其索引结点的指针。不会发生在文

9、件主删除共享文件后留下悬空指针的情况。6.6.2 利用符号链实现文件共享利用符号链实现文件共享 共享文件被删除后， 其他用户试图通过符号链去访问一个这个文件时，会访问失败；于是再将符号链删除，此时不会产生任何影响。 符号链共享方式的问题： 读取共享文件时，根据给定的文件路径名，逐个分量（名）地读取目录文件并查找目录，直至找到该文件的索引结点。多次读磁盘，速度慢。符号链共享方式的优点： 可以方便的链接网络中其它计算机中的共享文件。6.6.3 磁盘容错技术磁盘容错技术 (1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。 (2) 通过磁盘容错技术， 来防止由磁盘部分的故障所造成的文件不安

10、全性。 (3) 通过“后备系统”来防止由自然因素所造成的不安全性。 1. 第一级容错技术第一级容错技术SFT- 1) 双份目录和双份文件分配表在磁盘上存放的文件目录和文件分配表FAT，是文件管理所用的重要数据结构。若这些表格被破坏，将导致磁盘上的部分或全部文件成为不可访问的，等效于文件的丢失。可在不同的磁盘上或在磁盘的不同区域中，分别建立主、备两份目录表和FAT。 2) 热修复重定向和写后读校验 热修复重定向 保留磁盘容量的一部分（ 2 %3%），用作存放 磁盘缺陷区域的待写数据 写后读校验 1）每次从内存缓冲区向磁盘写入一个数据块后，立即从磁盘上读出该块内容，并作比较。 2） 若不一致，则重

11、写。 3）若重写后仍不一致，则将应写入该盘块的数据写入到热修复重定向区。 2. 第二级容错技术第二级容错技术SFT- (1) 磁盘镜像(Disk Mirroring)。 磁盘镜像示意 (2) 磁盘双工磁盘双工(Disk Duplexing)。 磁盘双工示意 6.7 数据一致性控制数据一致性控制 6.7.1 事务事务 1. 事务的定义事务的定义 (1) 事务是用于访问和修改各种数据项的一个程序单位，事务也可以被看作是一系列相关读和写操作。 (2) 只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以Commit操作来终止事务。 (3)只要有一个读、写或修改操作失败，便须

12、执行Abort操作，使系统中各数据项恢复至事务执行前的状态。事务原子性2. 事务记录事务记录(Transaction Record) 事务记录存放于高度可靠的存储器中，用来记录事务运行时数据项修改的全部信息，又称为运行记录(Log)。包括如下信息： 事务名： 用于标识该事务的惟一名字； 数据项名： 它是被修改数据项的惟一名字； 旧值： 修改前数据项的值； 新值： 修改后数据项将具有的值。 3. 恢复算法恢复算法 恢复算法可利用以下两个过程： (1) undoTi。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。 (2) redoTi。该过程能把所有被事务Ti修改过的数据，设置为新值。 如

13、果系统发生故障， 系统应对以前所发生的事务进行清理。 6.7.2 检查点检查点 1. 检查点检查点(Check Points)的作用的作用 作用是对事务记录表中事务记录的清理工作经常化。 首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中。 其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中； 然后是将事务记录表中的检查点记录，输出到稳定存储器中； 发生故障时，检查点之前commit的事务不必redo。 6.7.3 并发控制并发控制 利用互斥锁实现利用互斥锁实现“顺序性顺序性”2. 利用互斥锁和共享锁实现顺序性利用互斥锁和共享锁实现顺序性 3. 互斥锁和共享锁的区别互斥锁和共享锁的区别 互斥锁仅允许一个事务对相应对象执行读或写操作 共享锁允许多个事务对相应对象执行读操作，不允许其中任何一个事物执行写操作6.7.4 重复数据的数据一致性问题重复数据的数据一致性问题 1. 重复文件的一致性重复文件的一致性 UNIX类型的目录 2. 盘块号一致性的检查盘块号一致性