《计算机操作系统》学习笔记（四）---文件管理

1、三级数据组成：数据项，在文件中最低级的数据组织形式；记录，是一组相关数据项的集合；文件，可分为有结构文件和无结构文件，有结构文件由若干个记录组成，无结构文件可看成一个字符流，文件在文件系统中是一个最大的数据单位。
2、文件系统：文件系统包括三方面

（1）对象及其属性，如文件、目录、磁盘存储空间；
（2）对对象操纵和管理的软件集合，这是文件管理系统的核心部分，包括对文件存储空间的管理、对文件目录的管理、逻辑地址转物理地址、文件读写管理、文件共享保护等；
（3）文件系统接口。

（1）顺序文件

顺序文件分为串结构（关键字无序）和顺序结构（关键字有序）。它们只是一个记录接着一个记录存放着，对串结构的顺序文件只能关键字一个一个地对比，直至找到，对顺序结构的顺序文件可使用折半查找、插值查找等有效算法快速检索

（2）索引文件

分索引区和数据区。索引区包括关键字（n），纪录长度（m）和记录的首地址（ptr）。数据区是由一个接着一个的不定长记录组成的。检索时，通过关键字在索引区找到相应的目录项，从而得到m和ptr之后，再从ptr指向的地址（在数据区）开始，读或写m长度的数据。

（3）索引顺序文件

与索引文件类似，只是其数据区是有一组一组定长记录组成的，而索引文件的数据区是由一个一个不定长记录组成。索引顺序文件的索引区包括关键字与逻辑地址，检索时，通过关键字在索引区找到相对应的目录项，从而得到逻辑地址后，再从该逻辑地址处（在数据区）开始，顺序对比n个记录的的关键字直至找到该记录为止。

图片：32_3710_69fcc99afcecccc.gif

（4）直接文件和哈希文件

此类文件的检索是通过哈希函数与关键字计算出逻辑地址，再从该逻辑地址处读取数据。

（1）连续分配

为一个文件分配的盘块是相邻的，一般位于一条磁道，进行读/写时一般不必移动磁头，这样形成的物理文件称为顺序文件。在文件目录的目录项中只需给出首盘块号与盘块数，即可顺序读取数据。

图片：32_3710_1846ec0a4c46429.gif

（2）链接分配

链接分配的盘块之间不是连续的，而是多个离散的盘块依靠指针前后链接着，读取数据可以顺着指针一个一个盘块地读取。

隐式链接：在文件目录的目录项中，只需给出首盘块号与末盘块号，而中间的盘块则依靠指针链接在一起。

图片：32_3710_351ca356f8fc3d1.gif

显式链接：该种方式是把所有的盘块的链接关系制作成一张表（FAT），该表放在内存中，每次找下一个盘块时，只需从这张表上找即可，找到后再到相应的盘块中读取数据。文件目录的目录项只需给出首盘块号即可。

图片：32_3710_0ce39043436ae3e.gif

（3）索引分配

索引分配是把该文件用到的盘块号制作成表，该表不在内存中，而是在外存中。文件目录的目录项只需给出该表所在的盘块号，从该盘块将表读到内存后，再根据该表给的所有盘块号读取数据。

图片：32_3710_b2d1b9a9a5e342f.gif

（1）文件控制块

在Linux中，文件名是与索引节点分开。文件名放在内存中目录的目录项里面供检索用，待找到与该文件名相对应的目录项之后，再根据该目录项提供的指针从外存中读入索引节点。

图片：32_3710_314f6edd965fb34.gif

（2）目录结构

单级目录结构
两级目录结构
多级目录结构（树型目录结构）

（1）空闲表法（用顺序表记录着空闲盘块号）和空闲链表法（用指针将所有空闲盘块链接成一个链表）

图片：32_3710_f633caa1048e93b.gif

（2）位示图法（一个存放存放0或1的二维数组，1表示已分配，0表示空闲）

图片：32_3710_2658e055408be83.gif

（3）成组链接法（索引法）

图片：32_3710_8c9f9c6797c37e8.gif

（1）基于索引节点的共享方式

图片：32_3710_e464a7f37bcbd8b.gif

（2）利用符号链实现文件共享

图片：32_3710_1ada611742c9ebb.gif