（十）操作系统-文件系统
什么是文件系统
- 文件是用来保存数据的，而文件系统可让用户组织、操纵和存取文件；
- 文件——具有符号名的数据项的集合；
- 普遍将文件看成是命名的相关记录的集合（数据项——记录——文件）
- 文件系统是操作系统中负责存取和管理辅助存储器上文件信息的模块，它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操作方法。
文件的类型
文件的类型涉及对文件的操作功能、访问方法和访问权利。
按用途分
- 系统文件——与操作系统本身有关的信息（程序或数据）组成的文件；
- 库文件——由系统提供给用户调用的各种标准过程、函数和应用程序等；
- 用户文件——由用户的信息（程序或数据）所组成的文件。
按文件中数据分
- 源文件——指源程序和数据，以及作为处理结果的输出数据的文件；
- 相对地址形式文件——由各种语言编译程序所输出的相对地址形式的程序文件；
- 可执行的目标文件——由连接装配程序连接后所生成的可执行的目标程序文件。
按操作保护分
- 只读文件——仅允许对其进行读操作的文件；
- 读写文件——有控制地允许不同用户对其进行读或写操作的文件；
- 不保护文件——没有任何访问限制。
文件目录
文件目录中存放着每个文件的有关信息，即每个文件在文件目录中都应该有一个表目；
- 把目录作为一个特殊的文件（目录文件）来处理，有关文件系统的所有操作也同样适用于目录文件；
- 目录的设计包括目录内容和目录结构两方面。
目录结构
使用整体目录结构还是分体式目录结构？
- 整体式目录结构——目录中的每个文件都有一个表目，包含该文件目录的全部内容；
- 分体式目录结构——文件目录只包括文件名和一个指向另一个数据块的指针，该数据块中包含了文件目录内容中除文件名以外的全部内容（如UNIX系统中的索引节点i节点）。
采用分体式目录结构的好处
-
每个物理块中能存放更多目录表目，查询目录时命中率高，查询效率高；
-
便于文件的共享连接。
是否使用层次的树形目录结构？
一级目录结构
把系统中的所有文件都建立在一张目录表中，整个目录组织是一个线性表，结构简单，建立或删除文件时，只需在目录表中增加或删除一个表目；
缺点：
- 文件多，文件目录表很大，查找扫描时间长，不方便用户查询；
- 不方便用户对文件的管理，要求系统中不能有同名文件，无法解决多用户环境下命 名冲突的问题。
主要用在单用户的操作系统中。
二级目录结构
-
由一个根目录文件和它所管辖的若干个用户子目录组成；
-
二级目录中每个节点在主目录中都有一个表目来指出二级目录文件的位置；
-
该树状结构的叶就是具体的数据文件；
-
主目录中，每个用户都有一个表目，指出各次级目录（也即各用户自己的文件目录）所在的位置；
-
各用户的目录（次级目录）指出其所属的各具体文件的位置和其他属性。
多级目录结构
-
可以使每个用户按其任务的不同层次、不同领域建立多层次的分目录，给大作业的用户带来更多的方便；
-
从树状结构的每一个节点（目录）出来的分支既可以是叶（数据文件），也可以是又一个节点（次级目录）；
-
图中圆代表数据文件，矩形代表目录文件，目录中的字母表示文件的符号名。
文件系统的实现
文件空间的分配和管理
静态分配、动态分配
- 静态分配是在文件建立时一次分给所需全部空间；
- 但对于动态增长的文件则需要采用动态分配方法；
分区大小
- 若分区太大，则未用部分空间浪费大；
- 若分区太小，则会增加文件分配表的表目空间；
文件空间管理
- 文件分配表FAT（File Allocation Table）
文件分配方法
- 连续分配
- 链接分配
- 索引分配
- i节点
连续分配
文件被存放在辅存的连续存储区中；
- 用户必须在分配前说明被建文件所需存储区的大小；
- 系统查找空闲区管理表格，看是否有足够大的空闲区可供使用，如果有，就分给其所需的存储区，如果没有，该文件就不能建立，用户进程必须等待。
优点
- 查找速度比其他方法快；
- 目录中关于文件物理存储区的信息简单，只需要起始块号和文件大小。
缺点
- 有碎片问题，需要定期进行存储空间的紧缩；
- 不适合文件随时间动态增长和收缩的情况，也不适合用户事先不知道文件大小的 应用情况。
链接分配
以扇区为单位的链接分配
-
按所建文件的动态要求，分给它若干个磁盘的扇区，这些扇区可能分布在整个磁盘上而不一定相邻；
-
属于同一个文件的各扇区按文件记录的逻辑次序用链接指针相链接；
-
优点——消除了碎片问题，不需要采取压缩技术；
-
缺点——检索逻辑上连续的记录时，查询时间较长；同时还存在链的维护开销和链指针占用存储空间开销的问题。
以区段（或簇）为单位的链接分配
- 是连续分配和非连续分配的结合，以区段（或称簇）为单位进行分配，而区段是由若干个连续扇区组成的；
- 文件所属的各区段可以用链指针、索引表等方法来管理；
- 当为文件动态分配一个新区段时，该区段应尽量接近文件的已有区段号，以减少查找时间；
- 优点——对辅存的管理效率较高，并减少了文件访问的执行时间。
索引分配
链接文件的缺点
- 当要求随机访问文件上一个记录时，需要按链指针进行查找，十分缓慢；
- 链指针要占用盘块空间的几个字节，使得盘块的可用空间大小已不再是2的幂。
索引分配方法克服了链接文件分配方法的缺点；
系统在文件分配表FAT中为每一个文件分配一个表目，指出该文件的索引表所在物理块；
还可以支持索引分配和变长连续分配的结合方法，可以节省索引表空间，提高效率。
i节点
i节点中包含文件属性和该文件的盘块分配信息。
UNIX系统的目录实现
如果要访问文件/A/Tools，文件系统实现步骤如下：
- 按文件的路径名首先查找UNIX的根目录，根目录放在磁盘的固定盘块中，找出文件/A的i节点号是8；
- 从i节点表中找出/A的i节点，知道该目录文件放在88块中；
- 读入88块找到文件/A/Tools的i节点号是21；
- 从i节点表中找出/A/Tools的i节点，它指出文件在168块中；
- 读入168块。
磁盘空间管理
位示图（位图）
- 以“位”的值为1或0来反映磁盘上的相应物理块是否已分配的情况；
- 用若干个连续的字节构成一张表，其中每一位对应于盘上的一个物理块，依次顺序为0，1，2…。如果某位的值为1，表示该对应的物理块已分配，值为0表示对应的物理块为空闲。
链接索引表方法（成组链接法）
使用若干个空闲物理块作为索引表块，来指出磁盘分区中所有的空闲物理块；
每个索引表块的第0个表目作为空闲物理块链的Next指针和链尾标志，Next指针指出下一个索引表块；
链表的头指针在超级块中；
文件释放空闲块时添加到链头指针指出的索引表块的尾，为文件分配空闲块时从链表头的索引块的尾开始分配。
例题
设某文件为链接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。若要存取文件的第1569逻辑字节处的信息，问要访问哪一个磁盘块？
解答：因为1569=512X3+33，所以要访问字节的逻辑记录号为3，对应的物理磁盘块号为80。故应访问第80号磁盘块。