第六章 文件管理.

Presentation on theme: "第六章 文件管理."— Presentation transcript:

1 第六章 文件管理

2 6.1 文件和文件系统 6.1.1 文件、记录和数据项 1. 数据项 基本的数据单位，用于描述一个对象的某种属性 (1) 基本数据项
文件、记录和数据项 1. 数据项 基本的数据单位，用于描述一个对象的某种属性 (1) 基本数据项 (2) 组合数据项

3 2. 记录 记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。 关键字是惟一能标志一个记录的数据项

4 3. 文件 ★文件是指由创建者所定义的、 具有文件名的一组相关元素的集合 ★可分为有结构文件和无结构文件两种 ★在有结构的文件中，文件由若干个相关记录组成 ★无结构文件则被看成是一个字符流 ★文件在文件系统中是一个最大的数据单位，它描述了一个对象集 ★文件具有属性

5 文件、 记录和数据项之间的层次关系

6 6.1.2 文件类型和文件系统模型 2. 文件系统模型

7 6.1.3 文件操作 ★创建文件 ★删除文件 ★读文件 ★写文件 ★截断文件 ★设置文件的读/写位置

8 6.2 文件的逻辑结构 两种形式的结构： (1) 文件的逻辑结构(File Logical Structure)：又称文件组织
(2) 文件的物理结构， 又称为文件的存储结构， 是指文件在外存上的存储组织形式

9 文件逻辑结构的基本要求 ★能提高检索速度 ★便于修改 ★降低文件存储费用

10 6.2.1 文件逻辑结构的类型 有结构文件：由一个以上的纪录构成的文件，又称记录式文件 分类：按记录长度 定长记录 变长记录 按组织方式
顺序文件 索引文件 索引顺序文件

11 2. 无结构文件 ★由字符流构成的文件，又称流式文件 ★长度以字节为单位 ★采用读写指针来指出下一个要访问的字符 ★可以把流式文件看作是记录式文件的一个特例

12 顺序文件 1. 逻辑记录的排序 ★串结构： 各记录之间的顺序与关键字无关 ★顺序结构：指文件中的所有记录按关键字(词)排列

13 2. 对顺序文件(Sequential File)的读/写操作

14 3. 顺序文件的优缺点 ★最佳应用场合，是在对诸记录进行批量存取时， 即每次要读或写一大批记录
★只有顺序文件才能存储在磁带上， 并能有效地工作 ★交互应用的场合，当用户(程序)要求查找或修改单个记录时， 顺序文件所表现出来的性能就可能很差， 尤其是当文件较大时， 情况更为严重 ★如果想增加或删除一个记录， 都比较困难

15 6.2.3 索引文件 定长记录文件第i个记录相对于第一个记录首址的地址： Ai=i×L
可变长度记录的文件假定在每个记录前用一个字节指明该记录的长度，则： 对变长记录难以实现直接存取

16 索引表 ★为变长纪录文件建立索引表，主文件的每个记录，在索引表中设有相应的表项，用于记录该记录的长度L及指向该记录的指针
★索引表本身是定长记录的顺序文件

17 索引表 ★索引文件的检索：关键字查找 ★索引文件的使用场合：对信息处理的及时性要求较高 ★增加了存储开销

18 6.2.4 索引顺序文件 记录分组，一组一个索引项

19 直接文件和哈希文件 1. 直接文件 直接文件根据给定的记录键值，直接获得指定记录的物理地址。即记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直接文件的关键， 在于用什么方法进行从记录值到物理地址的转换。

20 直接文件和哈希文件 2. 哈希(Hash)文件 利用Hash函数将记录键值转换为相应记录的地址

21 6.3 外存分配方式 ★外存分配方法：外存空间的利用率、文件访问速度 ★外存分配方式与文件物理结构有关

22 6.3.1 连续分配

23 6.3.1 连续分配 ★连续分配方式形成的文件为顺序文件结构，此时的物理文件称为顺序文件
★保证了逻辑文件中的记录顺序与存储器中占用盘块的顺序的一致性 ★紧凑

24 2. 连续分配的主要优缺点 优点： (1) 顺序访问容易。 (2) 顺序访问速度快。 缺点： (1) 要求有连续的存储空间。 (2) 必须事先知道文件的长度。

25 6.3.2 链接分配 ★在每个盘块上设置链接指针，将同属于一个文件的多个离散的盘块链接成一个链表——链接文件 ★离散分配方式
★无需事先知道文件大小 ★对文件的增、删、改非常方便

26 1. 隐式链接

27 1. 隐式链接 ★只适合顺序访问 ★可靠性差 ★簇的概念

28 2. 显式链接 ★文件分配表

29 2. 显式链接 FAT的大小的计算（FAT表项占的字节数是以0.5字节为单位的）

30 6.3.3 索引分配 链接分配方式虽然解决了连续分配方式所存在的问题， 但又出现了另外两个问题， 即：
(1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。 (2) FAT需占用较大的内存空间。

31 1. 单级索引分配

32 2. 多级索引分配

33 2. 混合索引分配 直接地址 一次间接地址 二次间接地址

34 6.4 目录管理 对目录管理的要求如下： (1) 实现“按名存取”：最基本的功能，提供的最基本的服务 (2) 提高对目录的检索速度。
6.4 目录管理 对目录管理的要求如下： (1) 实现“按名存取”：最基本的功能，提供的最基本的服务 (2) 提高对目录的检索速度。 (3) 文件共享。 (4) 允许文件重名。

35 6.4.1 文件控制块和索引结点 MS-DOS的文件控制块 2字节，第0～4位：为2x秒(0~29) 第5～10位：分(0~59)
第11～15位：时(0~23) 2字节，第0～4位：日(1~31) 第5～8位：月(1~12) 第9～15位：年(1980年基准) 8字节文件名 3字节扩展名 01H—只读、02H—隐含、04H—系统文件、08H—卷标、10H子目录、20H—存档文件。可组合成复合属性，如27H—已存档、系统文件、隐含、只读

36 2. 索引结点 1) 索引结点的引入 文件名 索引结点编号 文件名1 文件名2 … …

37 2) 磁盘索引结点 (1) 文件主标识符 (2) 文件类型 (3) 文件存取权限 (4) 文件物理地址 (5) 文件长度 (6) 文件连接计数 (7) 文件存取时间

38 3) 内存索引结点 (1) 索引结点编号：用于标识内存索引结点。 (2) 状态：指示i结点是否上锁或被修改。 (3) 访问计数：每当有一进程要访问此i结点时， 将该访问计数加1， 访问完再减1。 (4) 文件所属文件系统的逻辑设备号。 (5) 链接指针：设置有分别指向空闲链表和散列队列的指针。

39 6.4.2 目录结构 1. 单级目录结构 文件名 物理地址 文件说明 状态位 文件名1 文件名2 …

40 1. 单级目录结构 单级目录的优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一些缺点： (1) 查找速度慢 (2) 不允许重名 (3) 不便于实现文件共享

41 2. 两级目录

42 2. 两级目录 具有以下优点： (1) 提高了检索目录的速度 (2) 在不同的用户目录中， 可以使用相同的文件名。 (3) 不同用户还可使用不同的文件名来访问系统中的同一个共享文件

43 3. 多级目录结构 (1) 目录结构

44 (2) 路径名 在树形目录结构中， 从根目录到任何数据文件， 都只有一条惟一的通路。 在该路径上从树的根(即主目录)开始， 把全部目录文件名与数据文件名，依次地用“/”连接起来， 即构成该数据文件的路径名(path name)。 系统中的每一个文件都有惟一的路径名。

45 (3) 当前目录(Current Directory)
从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)； 从树根开始的路径名称为绝对路径名(absolute path name)。

46 4. 增加和删除目录 (1) 不删除非空目录 (2) 可删除非空目录

47 6.4.3 目录查询技术 1. 线性检索法

48 2. Hash方法 处理“冲突”的有效规则是：
(2) 如果目录项中的文件名与指定文件名相匹配， 则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。 (3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值， 再返回到第一步重新开始查找。

49 6.5 文件存储空间的管理 6.5.1 空闲表法和空闲链表法 1. 空闲表法 序号 第一空闲盘块号 空闲盘块数 1 2 4 9 3 15 5
—

50 1. 空闲表法 存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等 系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法， 即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。

51 2. 空闲链表法 (1) 空闲盘块链 (2) 空闲盘区链

52 6.5.2 位示图法 1. 位示图

53 2. 盘块的分配 (1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。 (2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j 式中， n代表每行的位数。 (3) 修改位示图， 令map［i,j］=1。

54 3. 盘块的回收 (1) 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修改位示图。 令map ［i,j］=1。

55 A）过程如下：a、顺序检索位示图，从中找到第一个值为0的二进制位，得到其行号i1=2，列号j1=2；第二个值为0的二进制位的行号i2=3，列号j2=6。
b、计算出找到的两个空闲块的盘块号： b1=i1*16+j1+1= b2=i2*16+j2+1=55 c、修改位示图，令map[2,2]=map[3,6]=1，并将35，55分配出去 例 B）过程如下：a、计算出磁盘第300块所对应得二进制位的行号i和列号j：i=(300-1)/16=18; j=(300-1)%16=11 b、修改位示图，令map[18,11]=0 有一计算机系统利用如图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块，如果盘块从1开始编号，每个盘块大小为1KB。则： 现要为文件分配两个盘块，试具体说明分配过程。 若要释放磁盘的第300块，应如何处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

56 6.5.3 成组链接法 1. 空闲盘块的组织

57 2. 空闲盘块的分配与回收 当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。 然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。

58 2. 空闲盘块的分配与回收 在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时， 表示栈已满，便将现有栈中的100个盘块号， 记入新回收的盘块中，再将其盘块号作为新栈底。

59 6.6 文件共享与文件保护 1、基于索引结点的共享方式

60 1、基于索引结点的共享方式

61 1、基于索引结点的共享方式

62 2 利用符号链实现文件共享 在利用符号链方式实现文件共享时， 只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。这样， 也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。 当文件的拥有者把一个共享文件删除后， 其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。

63 6.6.3 磁盘容错技术 (1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。
磁盘容错技术 (1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。 (2) 通过磁盘容错技术， 来防止由磁盘部分的故障所造成的文件不安全性。 (3) 通过“后备系统”来防止由自然因素所造成的不安全性。

64 1. 第一级容错技术SFT-Ⅰ 1) 双份目录和双份文件分配表 在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和FAT。 其中，一份被称为主目录及主FAT； 把另一份称为备份目录及备份FAT。 2) 热修复重定向和写后读校验 (1) 热修复重定向(Hot-Redirection) (2) 写后读校验(Read after write Verification)方式

65 2. 第二级容错技术SFT-Ⅱ (1) 磁盘镜像(Disk Mirroring)。

66 (2) 磁盘双工(Disk Duplexing)

67 6.7 数据一致性控制 6.7.1 事务 1. 事务的定义 事务是用于访问和修改各种数据项的一个程序单位。 事务也可以被看作是一系列相关读和写操作 只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以托付操作(Commit Operation)来终止事务。 只要有一个读、写或修改操作失败，便须执行夭折操作(Abort Operation)

68 2. 事务记录(Transaction Record)
★事务名： 用于标识该事务的惟一名字； ★数据项名： 它是被修改数据项的惟一名字； ★旧值： 修改前数据项的值； ★新值： 修改后数据项将具有的值。

69 3. 恢复算法 恢复算法可利用以下两个过程： (1) undo〈Ti〉。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。 (2) redo〈Ti〉。该过程能把所有被事务Ti修改过的数据，设置为新值。 如果系统发生故障， 系统应对以前所发生的事务进行清理。

70 6.7.2 检查点 1. 检查点(Check Points)的作用
检查点 1. 检查点(Check Points)的作用 引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化， 即每隔一定时间便做一次下述工作： 首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中；其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；然后是将事务记录表中的〈检查点〉记录，输出到稳定存储器中； 最后是每当出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。

71 2. 新的恢复算法 只需对最后一个检查点之后的事务记录进行处理

72 6.7.3 并发控制 1. 利用互斥锁实现“顺序性” 2. 利用互斥锁和共享锁实现顺序性

73 6.7.4 重复数据的数据一致性问题 1. 重复文件的一致性

74 2. 盘块号一致性的检查

75 3. 链接数一致性检查 为每个盘块建立一个表项，其中含有该索引结点号的计数值。 在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时， 便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较， 如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。