《操作系统设计与实现》 第5章 文件系统.

Presentation on theme: "《操作系统设计与实现》 第5章 文件系统."— Presentation transcript:

1 《操作系统设计与实现》 第5章 文件系统

2 引出文件 文件是辅助设备（磁盘驱动器）的基本抽象，用来永久保存数据和信息 计算机为什么需要文件? 数量原因——内存无法保存大量信息
时间原因——内存无法永久保存信息 应用原因——内存无法方便实现共享

3 三个抽象概念 进程 进程就是一个正在执行的程序 进程地址空间 地址空间：一个进程可用于寻址内存的一套地址集合。 文件
文件是进程创建的信息逻辑单元。

4 文件系统 文件的管理是由操作系统来实现的。因此，文件的组织结构、命名规则、存取控制、安全保护等等都是由操作系统设计时要考虑解决的，整个处理文件的模块称为文件系统（file system）。 文件系统的作用: 为应用程序提供逻辑抽象（虚拟机） 为磁盘空间提供管理机制（资源管理器）

5 文件系统 两方面看待文件系统 用户的观点 对于用户来说，关心文件系统所提供的对外接口(包括文件命名、如何保护、如何访问) 操作系统的观点
对于操作系统的设计者来说，关心如何实现与文件有关的各个功能的模块(包括空闲存储空间的管理、文件系统的布局、逻辑块的大小等)

6 第5章 文件系统 5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述
5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述 5.7 MINIX 3文件系统的实现

7 第5章 文件系统 5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述
5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述 5.7 MINIX 3文件系统的实现

8 5.1 文件 首先从用户的角度出发，介绍文件系统对外接口。 文件命名 文件结构 文件类型 文件存取 文件属性 文件操作

9 5.1.1 文件的命名 文件是一种抽象机制，把信息保存在磁盘等外部储存设 备上，并且便于以后访问的方法。
抽象机制体现：用户不必去关心具体的实现细节。 如：信息被存放的位置 如：如何存放以及磁盘的工作原理 抽象机制最重要的特性  管理对象的命名 创建文件时，必须指定一个名字 当进程终止时，这个文件继续存在，别的进程可以通 过他的名字访问它

10 5.1.1 文件的命名 无统一的标准: 系统不同则规则不同 相同点： 都支持1～8个字母组成的字符串作为合法文件名
数字和一些特殊字符可以用于文件名(2、urgent!、Fig2-14) 不同点： UNIX区分大小写(maria != Maria)，MS-DOS不区分(maria = Maria) Windows介于二者之间，Windows95和98基于MS-DOS，继承了它 的许多属性，如文件的构造方式 Windows NT，Windows2000和Windows XP都支持MS-DOS，还支 持文件系统NIFS，具有一些不同的属性，如Unicode文件名

11 5.1.1 文件的命名 许多操作系统支持两部分组成的文件名，两部分用句点隔开， 句点后面的称为文件扩展名（file extension）
通常表示文件类型有关的一些信息 比如: .c表示c语言源文件 MS-DOS,文件名由1~8个字符和1~3个字符的可选扩展名组 成 UNIX，文件扩展名长度由用户决定，甚至包含两个或多个 扩展名 比如: prog.c.bz2，其中bz2表明文件(prog.c)已经使用 bzip2算法压缩过

12 5.1.1 文件的命名 Windows和Unix差别： Unix
扩展名是一种惯例，file.txt的文件可能是文本文件，这个文件主要用于提醒用户，不是传递特别的信息 例外的情况，C编译器要求源文件必须.c结尾，否则拒绝编译 优势：C编译器可以编译链接多个文件：C文件(foo.c)、汇编语言文件(bar.s)、目标文件(other.o)等，此时扩展名十分重要，用于区分哪些是C文件、汇编语言文件或目标文件

13 5.1.1 文件的命名 Windows和Unix差别： Windows 十分重视扩展名，并且赋予了含义
用户(或进程)可以向操作系统注册扩展名，并且为 每种扩展名指定相应的应用程序 用户可以通过双击文件名，系统自动的运行相应的 程序，并且把文件名作为参数

14 5.1.1 文件的命名 《典型的文件扩展后缀名》 压缩文件 file.zip 一般文本文件 file.txt TEX格式程序的输入
file.tex PostScript文件 file.ps 可移植文档格式文件 file.pdf 目标文件(编译程序的输出，尚未链接) file.obj MPEG标准编码的电影 file.mpg MPEG layer 3编码的音频压缩格式 file.mp3 JPEG标准编码的静态图片 file.jpg WWW超文本链接标示语言文档 file.html 帮助文件 file.hlp 可交换的图像文件格式 file.gif C语言源程序 file.c 备份文件 file.bak 含义 扩展名

15 5.1.2 文件的结构 文件结构有多种形式。通常的三种： 字节序列（无结构字节序列） 记录序列（记录序列结构） 树（记录树结构）
对于无结构的字节序列，操作系统不知道也不关心文件中是什么。它所看到的全部都是字节。任何意义都必须由用户级程序指定。UNIX和Windows都使用该方式。 记录序列把文件看作定长的记录序列 树：用于商业数据处理

16 5.1.2 文件的结构 文件可由很多方式构成，常见的有三种： 字节序列 记录序列 树

17 5.1.3 文件的类型 操作系统支持多种文件类型： 常规文件：包含有用户信息的文件（与用户使用紧密相关的，包含有用户数据）
目录文件：用来管理文件系统结构的文件 字符设备文件：与输入/输出有关，用于处理各种串行I/O设备（终端、打印机、网络） 块设备文件:用于处理磁盘

18 5.1.3 文件的类型 常规文件—ASCII文件和二进制文件： ASCII文件 由一行一行的文本组成。
换行的时候可以用回车符，也可以用换行符，依系统而定，每行长度可不同。 优点 可以原样地显示和打印。 许多程序都以ASCII文件作为输入和输出，很容易的把一个程序的输出作为另一个程序的输入，如同shell管道一样。

19 5.1.3 文件的类型 常规文件—ASCII文件和二进制文件： 可执行的二进制文件： 由五部分（文件头、代码、数据、重定位和符号表）组成。
文件头以魔数(magic number)开始，表明该文件是一个可执行文件，程序装入内存后，根据这五部分的内容进行重定位，来运行程序。

20 5.1.3 文件的类型 常规文件—ASCII文件和二进制文件：
BSS：是“Block Started by Symbol” 的缩写，意为“以符号开始的块”。 BSS是Unix链接器产生的未初始化数据段。 其他的段分别是包含程序代码的“text” 段和包含已初始化数据的“data”段。 BSS段的变量只有名称和大小却没有值。

21 二进制文件 UNIX存档文件： 由一组编译过但未链接的库函数(模块)组成，每个模块以模块头开始，给出模块名、创建时间、拥有者、保护代码、模块长度等信息。

22 5.1.3 文件的类型 每个操作系统至少需要识别一种文件类型 该系统的可执行文件 许多的操作系统能识别更多的文件类型
老的TOPS-20系统（用与DECsystem 20）还会检 查每个即将执行的文件的创建时间，然后找到相 应的源文件，查看源文件是否被修改过。如果修 改过，重新编译源文件。

23 5.1.3 文件的类型 在UNIX实现类似的功能，通过make程序集成到了 shell中。这里文件的扩展名是强制规定的，这样操 作系统才能确定哪一个二进制程序是由哪一个源文 件生成的。 WINDOWS系统执行时，根据文件的扩展名来判断 该启动哪个应用程序，当扩展名不正确时，无法启 动那个应用程序，如果强制转换，那么修改后的文 件即使能启动程序，也不能正确的读取。???

24 5.1.4 文件的访问 早期：只能够顺序访问文件 顺序的读取文件中的所有字节或记录，但是不能够跳过（非顺序的读取）；
从文件的开始处读取文件中的信息，如果需要的话，就多次读取，这种方式非常适合磁带。 现代：利用磁盘来存储可以随机访问文件 可以以任意的顺序来读取文件 数据库系统中尤为重要 比如一个预定某次航班的机票，订票程序必须能直接访问该航班的记录，而不必先读出大量的其他航班的记录

25 5.1.4 文件的访问 随机访问文件的两种方式： 每次read操作，都给出此次操作的的起始位置
提供一个seek操作来设置当前位置，在执行seek后 文件的读取操作将从这个新的位置开始 在一些早期的大型操作系统中，当一个文件被创建时， 就要对他分类（分为顺序文件或随机访问文件）对于不 通的文件系统采用不通的技术 现代操作系统，通常不需要区分，所有文件都是随机访 问文件

26 5.1.5 文件的属性 每个文件都有文件名和文件数据 文件的属性(元数据)：文件除了文件名和数据外， 还有很多操作系统赋予的属性，创建日期、文件长 度等，这些额外的属性称为文件属性。 不同的系统，文件的属性差别很大，没有一个系统 是包含这些属性，但每一种属性都在每一种系统中 使用过。 具体的文件的属性如下页所示：

27 5.1.5 文件的属性 一些文件的属性 保护：谁可以存取文件、以什么方式存取文件 口令：存取文件需要的口令 创建者：文件的创建者ID
所有者：当前所有者 文件保护 只读标志：0表示读/写；1表示只读 隐藏标志：0表示正常；1表示不在列表中显示 系统标志：0表示普通文件；1表示系统文件 存档标志：0表示已经备份；1表示需要备份 ASCII/二进制标志：0表示ASCII文件；1表示二进制文件 随机存取标志：0表示只允许顺序存取；1表示随机存取 临时标志：0表示正常；1表示进程退出时删除文件 加锁标志：0表示未加锁；1表示已加锁 控制属性

28 5.1.5 文件的属性 一些文件的属性 记录长度：1个记录中的字节数 键的位置：每个记录中键的偏移量 键的长度：键字段的字节数
创建时间：文件创建的日期和时间 最后一次存取时间：文件上一次存取的日期和时间 最后一次修改时间：文件上一次修改的日期和时间 当前大小：文件的字节数 最大长度：文件可能增长到的字节数 时间字段 文件大小

29 5.1.6 文件的操作 文件操作：文件作为信息的载体，即为了存储也为了检索，系统不同，采用的手段也有差异。 Create Delete
Open Close Read Write Append Seek Get attribute Rename Lock 创建文件 删除文件 打开文件 关闭文件 读取数据 写入数据添加数据 随机访问 设置属性 重命名 锁定文件 申明文件的存在，设置相关属性 删除文件以释放存储空间 将文件的属性和磁盘地址存入内存 关闭文件释放内部表格空间 提供一个缓冲区来存放这些数据 一般从当前位置开始文件末尾-增加长度；文件中间-覆盖文件只能从末尾添加 指定开始读写数据的位置 文件创建之后，用户可以修改属性 改变现有文件名，或复制文件到一个带有新文件名的文件 锁定一个文件或文件的一部分，可以防止多个进程同时访问

30 使用文件系统调用的示例 /*文件复制程序。错误监测和报告已经尽可能地省略了。*/
#include <sys/types.h> /*包含必要的头文件*/ #include <fcntl.h> #include <stdlib.h> #include <unistd.h> int main(int argc, char *argv[]); /*ANSI 原型*/ #define BUF_SIZE /*使用的缓冲区大小为4096字节*/ #define OUTPUT_MODE /*输出文件的保护位*/ int main(int argc, char *argv[]) { int in_fd, out_fd, rd_count, wt_count; char buffer[BUF _SIZE]; if (argc != 3) exit(1); /*如果argc不是3，则语法错误*/

31 /*打开输入文件，并创建输出文件*/ in_fd = open(argv[1], O_RDONLY); /*打开源文件*/ if (in_fd < 0) exit(2); /*如果不能打开，则退出*/ out_fd = creat(argv[2], OUTPUT_MODE); /*创建目标文件*/ if (out_fd < 0) exit(3); /*如果不能创建，则退出*/ /*复制循环*/ while (TRUE) { rd_count = read(in_fd, buffer, BUF_SIZE); /*读入一个数据块*/ if (rd_count <= 0) break; /*如果文件结束或者错误，退出循环*/ wt_count = write(out _fd, buffer, rd_count); /*写数据*/ if (wt_count <= 0) exit(4); /*wt_count <= 0为错误*/ } /*关闭文件*/ close(in_fd); close(out_fd); if (rd_count == 0) /*最后的读没有错误*/ exit(0); else exit(5); /*最后的读有错误*/ }

32 第5章 文件系统 5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述
5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述 5.7 MINIX 3文件系统的实现

33 5.2 目录 在多数系统中，目录也是一种文件 文件控制块（FCB）：文件控制块是操作系统为管理文件 而设置的数据结构，存放了为管理文件所需的所有有关 信息，文件控制块是文件存在的标志。 文件控制块的内容： 文件名，文件号，用户名，文件地址，文件长度，文 件类型，文件属性，共享计数，文件的建立日期，保 存期限，最后修改日期，最后访问日期，口令，文件 逻辑结构，文件物理结构

34 5.2.1 简单的目录文件 为了记录文件信息，文件系统通常有目录(directories)或者文件夹(folders)。
在许多系统中，目录本身就是文件。 目录包括其组织(organization)、属性(properties)以及作用于其上的操作(operations)。 (a) 含有文件名、属性和文件数据在磁盘上的存储地址等信息 (b)含有文件名和指向另一个数据结构的指针，文件的属性和磁盘地址等信息存放于这个数据结构中

35 一级目录系统 目录系统的最简单形式是使用一个目录包含所有的文件。
有时候，称之为根目录(root directory)，由于只有一 个目录，名字无关紧要。 在早期的个人计算机上，这种系统非常普遍，部分原 因是只有一个用户。 非常有趣的是，世界上最大的超级计算机CDC 6600， 对于所有文件也只有一个目录，尽管它同时有多个用 户使用。 这个决断无疑是想保持软件设计的简单。

36 一级目录系统 单层目录系统 单层目录系统包含的4个文件，分别属于3个不同的人A、B和C。

37 一级目录系统 多用户环境下使用这种单一目录系统，会出现重名的问 题-即不同的用户给他们的文件起了相同的名字 例如：
A用户创建了mailbox的文件，B用户也创建了一个 mailbox的文件。这样，B的文件会把A的文件给覆盖， 所以这种方案不能再用于多用户的系统中，但可以用 在一些小型的嵌入式系统中，如手持式个人数字助理 或手机等

38 二级目录系统 为了避免不同用户为其自己拥有的文件取相同的文件名 所导致的冲突，下一步就是给每个用户一个私有目录。
一个用户选择的名字不会干扰另一个用户的选择，而且 在两个或多个目录中的相同名字不会发生问题。 例如，这种设计可以用于多用户计算机或者通过局 域网共享公用文件服务器的个人计算机的简单网络 上。

39 二级目录系统 图中字母表示目录和文件的所有者

40 层次目录系统 二级目录系统消除了不同用户之间的文件名冲 突，但仍然难以使有很多文件的用户感到满意。 用户常常需要把文件按某种逻辑方式组织起来。 最终我们需要的是一般的层次(即目录树)。采 用层次结构，每个用户可以拥有多个所需的目 录，自然地组织他们的文件。

41 层次目录系统 目录树

42 5.2.3 路径名 用目录树组织文件系统时，要某种方法指明文件名。 常用的方法有两种：
绝对路径名(absolute path name)：绝对路径名是从 根目录开始到文件的路径，且是唯一的。 相对路径名(relative path name)：它常和工作目录， 也称作当前目录一起采用。是从当前目录到文件的 路径。

43 5.2.3 路径名 绝对路径: 从根目录开始一直到改文件的路径组成，最 常见且是最直接的方式，来指明文件的具体位置;
路径：/usr/ast/mailbox表示在根目录下有一个子目录usr/, 他又 包含子目录/ast, 而文件mailbox存放在ast/下 绝对目录是从根目录开始，并且是唯一 \ DOS中的分隔符 / UNIX中的分隔 \usr\ast\mailbox 等效于 /usr/ast/mailbox 无论那种分割方式，只要路径名的第一个字符是分割符，那么 这个路径名就是绝对路径名

44 5.2.3 路径名 相对路径名：和工作目录一起使用，相对于工作目录的 路径；用户可以指定一个目录作为工作目录。这时所有 的路径不是从根目录开始，而是从这个工作目录开始的 使用相对路径更加简洁 如工作目录为： /usr/ast cp /usr/ast/mailbox /usr/ast/mailbox.bak 等效于 cp mailbox mailbox.bak 有些程序需要访问特定的文件，而不管当前的工作目录，这种 情况下应使用绝对路径名 无论那种情况下都能使用绝对路径

45 5.2.3 路径名 当绝对路径(/usr/lib)有很多文件，可以通过一个系统调用，把当前工作目录切换到/usr/lib，然后直接使用dictionary最为open的第一个参数，通过这种方式改变工作目录，程序可以知道他在目录树中的具体位置 系统中的每个进程都有自己的工作目录，当一个进程改变改变了工作目录后，其他进程不受影响，对于进程来说，工作目录的切换是安全的。 但是库函数中的工作目录改变了，其他函数可能无法运行，因为假定的工作目录已经无效了。 尽量不要修改库函数的工作目录如果非修改不可，则在返回之前改回到原来的工作目录。

46 5.2.3 路径名 特殊目录：在创建目录的时候，默认会出现的目录 .(一个点)：表示当前的目录 ..(两个点)：表示父目录
工作目录为： /usr/ast cd ..表示退回到父目录/usr cd ../lib/dict 表示到了 /usr/lib/dict/ cp /usr/lib/dict . 将/usr/lib/dict 下所有文件拷贝 到/usr/ast/下，文件名不变化

47 5.2.3 路径名 UNIX目录树

48 5.2.4 目录的操作 Create Delete Opendir Closedir Readdir Rename Link Unlink
创建一个目录，除了. 和.. 该目录没有包含任何内容 删除一个目录，只有空目录可以被删除，一个只含有. 和.. 的目录被认为是空目录 目录的内容可被读取，与文件的打开和读取的操作一样，在读一个目录之前必须打开它 当一个目录读完以后，应该关闭，以释放相应的内部表格空间 返回一个目录中的下一个目录项 重命名目录，和文件类似 链接技术允许一个文件同时出现在多个目录中，硬链接：这种类型的链接，是把文件的索引节点中的计数值加1 删除一个目录项，如果被解链的文件只出现在一个目录中，那么该文件会被删除，如果出现在多个目录中，则指删除指定的路径名，

49 5.2.4 目录的操作 目录操作 与文件非常类似：rename、create、delete…. 差别：访问操作、管理操作

50 本章小结 文件 目录 文件的命名 文件的结构 文件的类型 文件的访问 文件的属性 文件的操作 简单的目录系统 层状的目录系统 路径名
目录的操作

51 第5章 文件系统 5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述
5.1 文件 5.2 目录 5.3 文件系统的实现 5.6 MINIX 3文件系统概述 5.7 MINIX 3文件系统的实现

52 5.3 文件系统的实现 两方面看待文件系统： 用户的观点：对于用户来说，关心文件系统所提供的对外接口(包括文件命名、如何保护、如何访问)
操作系统的观点：对于操作系统的设计者来说，关心如何实现与文件有关的各个功能的模块(包括空闲存储空间的管理、文件系统的布局、逻辑块的大小等)

53 5.3 文件系统的实现 以上从用户角度考察文件和目录 以下从实现者角度来考察文件系统。
用户关心的是文件是怎样命名的、可以进行哪些操作、目录树是什么样的以及类似的界面问题。 以下从实现者角度来考察文件系统。 实现者感兴趣的是文件和目录是怎样存储的、磁盘空间是怎样管理的以及怎样使系统有效而可靠地工作等等。

54 5.3 文件系统的实现 文件系统布局 文件的实现 目录的实现 共享文件 日志结构文件系统 日志文件系统 虚拟文件系统

55 5.3.1 文件系统的布局 文件系统通常保存在磁盘上 磁盘由几个分区构成，每个分区的文件系统的是相互独立的
磁盘的扇区0称为主引导记录(Master Boot Record, MBR)用来启动计算机 MBR末尾的分区表，记录了每个分区的起始地址和结束地址。 每个分区都是都是以一个引导块开头，即使该分区中并没有包括可引导的操作系统 启动BIOS读入并执行MBR代码读取操作系统 MBR所做的第一件事就是确定活动分区，并读入它的第一个磁盘块称为引导块，

56 5.3.1 文件系统的布局 文件系统通常保存在磁盘上 磁盘由几个分区构成，每个分区的文件系统的是相互独立的
磁盘的扇区0称为主引导记录(Master Boot Record, MBR)用来启动计算机 MBR末尾的分区表，记录了每个分区的起始地址和结束地址。 每个分区都是都是以一个引导块开头，即使该分区中并没有包括可引导的操作系统 启动BIOS读入并执行MBR代码读取操作系统 引导块中的代码会把保存在该分区中的操作系统读取出来，装入内存运行

57 5.3.1 文件系统的布局 不同的操作系统中，使用的名称不太相同
主引导记录(MBR)也叫初始化程序装载器(Initial program Loader,IPL)、卷引入代码(Volume Boot Code)或简称为主引导(masterboot) BIOS装入MBR或引导扇区，随后可能不止使用一个块来存放引导代码。系统的实现者也可以提供一个自定义的MBR，必须和标准分区兼容

58 5.3.1 文件系统的布局 主要分区的个数不能超过4个，因为在主引导记录和第一个512字节的扇尾之间，仅能容纳4个数组元素，存放分区的描述符。 解决方法：分区表分某一项作为扩展分区指向一个逻辑分区链表，BIOS不能从逻辑分区来启动一个操作系统，最初的启动必须是从主分区开始，由它装入代码，管理各个逻辑分区。 MNIX3允许在一个分区中包含子分区表：可以使得管理子分区表的代码管理子区分表。

59 5.3.1 文件系统的布局 不是所有的磁盘需要分区，软盘的引导块通常从第一个扇区开始。
BIOS读入磁盘的第一个扇区然后查找一个魔数(标明这是有效的可执行代码)，这样可以避免执行一个未格式化或已损坏的磁盘。 主引导记录和引导块使用的是相同的魔数，因而可执行的代码可能是两者之一。

60 5.3.1 文件系统的布局 不同的系统文件磁盘分区的布局差别很大。 类UNIX的文件系统的内容项：
第一项超级块(superblock)：包含了文件系统的所有关键参数 第二项空闲空间管理：关于文件系统中的空闲物理块的管理信息 第三项索引节点：是一组数据结构，一个文件对应一个，描述了文件的所有属性信息和它在磁盘上的存储位置 第四项根目录：文件系统的根节点 最后剩余的磁盘空间存放其他目录和文件

61 5.3.1 文件系统的布局 不同的文件系统磁盘布局不相同

62 5.3.2 文件的实现 实现文件的存储时，关键问题在于记录文件的存储的 位置和存储的方法 常用的方法： 连续分配方式
将文件存储在连续的磁盘块中 链表分配 为文件建立块链接表 带有文件分配表的链表结构 对块链接表建立索引，保存在内存中 索引节点方式 为每个文件建立I-Node表，类似页表

63 （1）连续分配 最简单的分配方案是把每个文件作为连续数据块存储 在磁盘上。所以，在块大小为1K的磁盘上，50K的文 件要分配50个连续的块。
该分配方案有两大优势 简单、容易实现，记录每个文件用到的磁盘块简化为只需记 住一个数字即可，也就是第一块的磁盘地址。 性能较好，在一次操作中，就可以从磁盘上读出整个文件。 缺点：不能预知文件的长度，会造成磁盘碎片。 适用于CD-ROM，文件长度已知且在使用中不会改变。

64 （1）连续分配 (a) 分配给7个文件的连续磁盘空间 (b) 文件D、F被删除后的磁盘状态

65 （2）链表分配 链表分配：为文件构造磁盘块链表，每个块的第一个字用做指针，指向下一个块，块的其余部分用来存放数据。
优点：每一个磁盘都能用上不会出现外碎片的问题；在目录项中，只要存放第一个块的磁盘地址，其余的可以通过链表来访问。 缺点： 顺序访问方便，随机访问速度慢；当访问第n个文件块，需要把前面n-1块全部读进来。 指针也会占据字节数，使得存储数据的字节数不是2的整数次幂，降低了系统的运行效率。

66 （2）链表分配 文件A访问4,7,2,10,12 文件B访问6,3,11,14 存放不再连续，而是通过链接表来将各个分散的块链接起来，每块的第一个字用来指向下一个指针，其余部分存放数据

67 （3）带有文件分配表的链表结构 对链表结构的改进，把每一个磁盘块中的链表指针抽取出来，单独组成一个表格，放在内存中。
A访问4,7,2,10,12 B访问6,3,11,14 从第4个块开始，顺着链表往下走找到A的所有磁盘块--A 从第6个块开始，顺着链表往下走找到A的所有磁盘块--B 两条链表都以-1来表示结束 这种表格叫做文件分配表 File Allocation Table, FAT

68 （3）带有文件分配表的链表结构 优点： 整个块都可以存放数据，也利于文件的随机访问虽然仍要对链表遍历搜索，找到文件块所在的磁盘地址，但是由于整条链表都存放在内存中，因此速度快。 与链表分配方案一样，不管文件多大，系统只要在目录项中存放一个整数(起始块号)，就能找到文件的所有块。

69 （3）带有文件分配表的链表结构 缺点：整个FAT表都必须位于内存之中
20GB的磁盘，块的大小为1KB，FAT表需要2000万个表项来描述相应的2000万个磁盘块。每个表项最少需要3个字节，为了提高查找速度，最好设为4个字节，这样整个表格就需要占用60或80MB的内存。 解决方案：放在虚拟页式存储器，但是仍然要占用大量的虚拟内存和磁盘空间，还会增加页面置换次数。 MS-DOS 和 Windows98都是使用FAT文件系统，Windows的后续版本也都支持这种文件系统。

70 （4）索引节点 索引节点(index node)/i节点：给每个文件赋予一个数据结构,包含了文件的属性和各个数据块的磁盘地址。

71 （4）索引节点 优点： 充分吸收了连续分配和链表分配的优点，支持顺序存取和随机存取。 可以方便的实现文件的空间动态增长，插入删除的要求。
充分利用了外存空间，管理过程有很高的效率，同时，系统中同时打开的I-Node数目和大小都不会很大，比FAT节省空间。

72 （4）索引节点 缺点： 当文件的物理空间分布过于分散时，文件读取消耗 较长的时间。
当文件的物理空间分布过于分散时，文件读取消耗 较长的时间。 索引表方式占用了较多的系统资源，包括磁盘和内 存，同时对操作系统的设计要求也很高。

73 （4）索引节点 文件太大的解决方案：最后一个磁盘地址不描述一个数据块而 是指向一个间接块。
一级间接块包含着附加的磁盘地址，二级间接块包含很多一次 间接块的地址，同样，三级间接块包含很多二级间接块的地址。

74 （4）索引节点 例题： UNIX文件系统，采用1KB的磁盘块大小和4B的磁盘地址。若I-节点包括10个直接块，一次、二次、三次间接块各一个，则此文件系统允许文件最大长度是？ 解：1KB的磁盘块，存放4B的地址号，每块可放1K/4=256个块号 最大文件长度： (10*1K+1*256*1K+1*2562*1K+1*2563*1K)B

75 文件物理空间分配方式的总结 连续分配 链表方式 索引方式 存储介质 磁带 支持 不支持 磁盘 存取方式 顺序＋随机存取 顺序 空间利用效率
较低，会产生外零头 指针占用磁盘空间引起管理问题 利用磁盘和内存，但效率很高 应用环境分析 最简单、最原始 中间过渡阶段 广泛应用

76 5.3.3 目录的实现 目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。
目录项：构成文件目录的项目 查找目录项首先定位根目录：可能位于磁盘分区的某个固定位置或者其实信息由其他决定 UNIX系统中在超级块中包含文件系统各个数据结构的大小，从中找到i节点所在的位置。第一个i节点指向的是根目录。 Windows XP中根据应到扇区的信息可以找到主文件表(Master File Table, MFT )然后定位其他部分。

77 5.3.3 目录的实现 打开文件时，操作系统利用用户给出的路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。
目录项的功能就是将用户提供ASII文件名映射成为查找文件数据所需要的信息。 目录项的设计 文件名 磁盘地址 文件属性

78 固定长度的目录项 (a)文件+固定长度的目录项 (b)文件属性放在节点中

79 长度不固定的目录项 在目录中处理长文件名的两种方法 (a) 行方式 (b) 堆方式

80 共享文件 链接：使得同一个项目组的各个成员能够共享文件
硬链接：UNIX中，i节点存放文件属性，i节点中有一个字段，每当有一个新的链接加进来，其值加1；删除一个链接，其值减1。当计数为0，文件的数据和节点才会被删除。 局限： 目录和i节点是一个文件分区的数据结构，在一个文件系统中的目录不能指向另一个文件系统中的i节点 一个文件只能有一个权限,当一个用户删除了共享用户目录项，对于其他用户他的目录下由于权限不够无法删除这个共享文件

81 共享文件 符号链接：路径名包含在网络地址中，这种链接能访问不同计算机上的文件，可以把属性存放在目录项中的系统。
缺点：如果在多个目录项都存在文件属性信息，那么将会难以同步因为任何修改都会影响目录项。 不同系统说法不同 类UNIX系统符号链接(symbolic link) Windows系统快捷方式(shortcut) Macos系统别名(alias)

82 Windows 98中的目录 CP/M中的目录:该系统的目录结构最为简单，系统中只有一个目录，文件系统只需查找这个唯一的目录，当找到对应的目录项的时候，也就知道了文件的磁盘号。 当文件过大，目录项中容不下过多的磁盘号的时候，就为这个文件分配额外的目录项。 用户码 1 8 3 2 块数 文件类型（扩展名） 范围 磁盘块号（16）

83 Windows 98中的目录 Windows95和MS-DOS文件系统相同。Windows98开始增加了对长文件名和大文件的支持，Windows98包含两种目录项：基本目录项和长文件目录项 基本目录项：在Windows早期版本信息的基础上升级，从NT字段开始的10个字节是新加的内容，并且把起始数据的地址从16位增加到32位，系统访问的数据块从216增加到了232 Windows 98中使用的扩展的MS-DOS目录项

84 Windows 98中长文件名(的一部分)的项
保持老系统兼容的情况下支持长文件名 长文件目录项：能达到13个字符的长文件名，对于使用长文件名 的文件来说系统会自动生成一个缩短的文件名放在基本目录项(上 图)的文件名和扩展名字段中。 文件名的长度超过13个字符可以增加更多目录项（下图） 这些目录项放在基本目录项的前面，按反向序列排序。在每个文 件名目录项的属性字段包含特殊值0x0F，老的系统访问忽略这些 目录项。 Windows 98中长文件名(的一部分)的项

85 UNIX中的目录 UNIX目录结构十分见简单，每个目录项只包含一个文件名及相应的i节点号。
总的结构：ASCII字符串和i节点号 UNIX V7的目录项

86 UNIX中的目录 文件系统根据用户给定的文件名，找到对应的磁盘块

87 UNIX中的目录 相对路径名和绝对路径处理方式相似。 起始位置不同：相对路径名是当前工作目录；绝对路径 是根目录。
. 和 .. 分别表示当前工作i节点和父目录的i节点，是由系 统创建。 ../dick/prog.c 首先当前工作目录下查找 .. ,找到父目录 的i节点，然后在该目录下搜索dick文件

88 NTFS中的目录 NTFS: New Technology File System是Microsoft公司开发 的专用文件系统，从Windows NT 3.1开始成为Windows NT家族的标准文件系统。 NTFS取代FAT（文件分配表）和HPFS（高性能文件系统） 并进行一系列改进，例如增强对元数据的支持，使用更 高级的数据结构以提升性能、可靠性和磁盘空间利用率， 并附带一系列增强功能，如访问控制列表（ACL）和文 件系统日志。

89 NTFS中的目录 NTFS对长文件的命名 NTFS支持长文件名(最多255)和路径名(32767)。
Windows老版本不能访问NTFS系统。 NTFS为文件提供了8+3类型的名字，老的系统可以通 过网络访问NTFS文件。 NTFS使用Unicode编码：NTFS支持不同的数据集 Unicode用16位表示一个字符并且支持多种语言的混合 NTFS解决不同语言出现在同一个目录下大小写的问题 的方法为每个文件设定属性，以便定义在该语言中 文件名的大小写规范。

90 NTFS中的目录 NTFS文件是一组属性集合，不同于UNIX的字节序列： 所以增加属性是NTFS解决问题的方法，每个属性是一个 字节流
基本的NTFS数据结构为主文件表(MFT): 提供了16个 属性，每种属相可达1KB。 当不足时，可以让属性指向另一个文件来存放额外的 属性值。称这种属性为非常驻属性。 MFT也是一个文件，由于为每个文件和目录设置了一 个目录项，这样它可能会增长得非常大。NTFS会在磁 盘分区预留12.5%的存储空间，留给MFT。

91 NTFS中的目录 NTFS中的数据处理: NTFS文件有多个数据流 好处：
最初是为了使Windows服务器能够服务于苹果的 Macintosh客户。在最初的Macintosh(Mac OS 9), 所有 的文件都有两个数据流—资源流和数据流。 高效的处理大/小数据： 在一个很大的数据文件中。可以用一个数据流来存放一幅 比较小的缩略图 如果文件非常小只有几百个字节，NTFS可以直接存放在属 性中，称为立即文件.

92 5.3.4 磁盘空间管理 管理内容 关键设计问题 为文件提供磁盘空间资源，实现文件逻辑结构与物理结构的对应
为目录建立磁盘空间结构，实现层次化目录(目录块） 对磁盘空间进行有效的分配、释放和维护 关键设计问题 磁盘空间的管理策略：如何分配磁盘？如何维护磁盘？ 文件与目录的实现机制：如何更好的支持上层应用？ 文件系统的可靠性和安全性：如何防止访问错误和数据丢失？

93 块尺寸(Block Size) 空间单位划分 关键设计问题 字节序列：对磁盘空间不进行划分，管理效率低下 块定义：类似于内存管理中的分页模式
由于连续字节存储时文件扩大空闲不够时，需要移动到另一个位置，基于这个原因大多数选着块存储 关键设计问题 块大小的设计：空间利用效率与访问速度的权衡 重点——影响磁盘访问速度的因素 磁道容量、旋转时间、平均寻道时间 空间利用效率与访问速度的关系

94 块尺寸(Block Size) 实线：磁盘数据库 虚线：磁盘空间效率 所有文件均为2KB 在一个磁盘上，每条磁通道有131072个字节，旋转时间为8.33ms，平均磁头定位时间为10ms。那么访问一个长度为k个字节的数据块所需要的时间=磁头定位时间+旋转延迟时间 (k/131072) x 8.33

95 块尺寸(Block Size) 对曲线的理解
数据块的访问时间由磁头定位时间和旋转延迟时间来 决定。数据块包含的数据越多，性能越好数据率随着 块的大小的增加而增大 数据块小，性能差，磁盘空间利用率高；数据块大， 性能好，磁盘空间利用率低性能和空间利用效率本质 上是相背的 故需要些折中的办法，把块分为512、1K或2K字节， 如果在扇区大小为512自己的磁盘选择1K大小的磁盘块时， 系统常连续需要连续读取两个扇区，并把他们认为是一 个单元。

96 空闲块的管理 一旦选定了块大小，下一个问题就是如何记录空闲块。 广泛采用的是两种方法：
第一种方法使用一个条链表，每个链表节点是一个磁盘块，里面存放了尽可能多的空闲磁盘块号。 另一种空闲磁盘空间管理的方法是采用位图。n个块的磁盘需要n位位映像。在位映像中，空闲块用0表示，分配块用1表示(或者反之)。

97 空闲块的管理 链表法(a):使用链表，每个链表节点是一个磁盘块
假设块的大小是1KB，磁盘块号用32位来表示，每个链表最多能存放255个空闲块号。这种方式下一个256GB的磁盘最多需要 个块的空闲链表来存放所有的228个磁盘块的块号

98 空闲块的管理 位图法：用一串二进制位反映磁盘空间中分配使用情况, 每个物理块对应一位, 分配物理块为1，否则为0。申请物理块时，可以在位示图中查找为0的位，返回对应物理块号；归还时；将对应位转置0 描述能力强，适合各种物理结构 一个256GB的磁盘有228个1KB的块，需要一张228个数据位的位图，该位图需要占用32768个磁盘块。占用的磁盘空间少于链表法

99 空闲块的管理 设磁盘块大小为1KB，16bits磁盘地址，若磁盘容量为20MB，则共有20M/1K= 20480个块，存放所有块号所需空间：
用链表记录空闲块 一个磁盘块可以存放1KB/16-1=511个块号 全部磁盘块共需 20480/511=40个块的空闲链表来存放 位映像 20480个块需要20480bit的位图，则位图占用20480/1KB=20个块

100 本章小结 文件系统的实现 文件系统的布局 文件的实现 目录的实现 磁盘空间管理 文件系统的可靠性 文件系统的性能 日志结构的文件系统