文件的概念
文件的定义
一组有意义的信息的集合
文件的属性
文件名：由创建文件的用户决定，同一目录下不允许存在相同的文件名
标识符：系统内各文件的唯一标签，对于用户而言不可见
类型：文件的类型
位置：文件存放的路径（对用户而言）、在外存中的地址信息（对操作系统而言）
保护信息：对文件进行访问控制用的信息
创建时间、修改时间等。
操作系统提供的相关功能
- 创建文件（create系统调用）
- 删除文件（delete系统调用）
- 读文件（read系统调用）
- 写文件（write系统调用）
- 打开文件（open系统调用）
- 关闭文件（close系统调用）
打开文件表：存储文件的读写信息
每一位用户有一个自己的打开文件表
| 编号 | 文件名 | 读写指针 | 访问权限 | 系统表索引号 |
|---|---|---|---|---|
| …… | …… | 读/写进程对该 文件的读/写操作 进行到的位置 | 只读/读写/.. | 文件在系统的打开 文件表中的编号 |
此外，整个系统拥有一张系统打开文件表
| 编号 | 文件名 | …… | 外存地址 | 打开计数器 |
|---|---|---|---|---|
| …… | …… | …… | …… | 当前有多少进程 打开了此文件 |
每个文件在系统打开表中仅有一个表项
每个文件在用户打开表中的表项不一定相同
文件的逻辑结构
逻辑结构：在用户看来，文件内部的数据应该是如何组织起来的
物理结构：在操作系统看来，文件 的数据是如何存放在外存中的
无结构文件
文件内部的数据就是一系列二进制流或字符流组成。又称流式文件，如：Windows操作系统中的.txt文件、mp3文件等。
有结构文件
由一组相似的记录组成，又称记录式文件。每条记录又若干个数据项组成。如：数据库表文件，CSV文件等。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。
根据每条记录的长度是否相等，可以分为定长记录和可变长记录两种。
有结构文件的逻辑结构可以分为以下三种：
顺序文件
文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。
顺序文件可以有以下存储方式：
- 链式存储：（逻辑上相邻、物理上不相邻）无论是定长/可变长记录，都只能依次查找，无法实现随机存取
- 顺序存储：（逻辑上相邻、物理上也相邻）
- 可变长记录：无法实现随机存储
- 定长记录：可以实现随机存储。记录长度为L，则第i个记录的相对位置就是 i
* L
- 若采用串结构；（记录之间的顺序与关键字无关，一般按照记录时间排序）无法快速找到对应关键字的记录
- 若采用顺序结构：（记录之间按照关键字排列）可以迅速查找到相应关键字对应的记录
考试中一般提到顺序文件默认为顺序存储的顺序文件
顺序文件实现增删改查较为困难
索引文件
索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。
可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。
每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
同时，可以对不同的数据项建立多个索引表，方便查找。
缺点：当记录数量增大时，索引表的大小也会变大，甚至可能出现索引表比文件本身还大的情况
索引文件是顺序存储的，可以使用折半查找。
索引顺序文件
索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
即，将文件分为若干组顺序文件，查找时先通过索引表找到所在的顺序文件，再通过顺序检索找到相应的记录。
若有n个记录，则索引顺序文件最好的分组为：
- 分成\(\sqrt{n}\)组
- 每组\(\sqrt{n}\)条记录
索引顺序文件的索引表不是顺序存储的，只能使用顺序查找。
小结：文件物理结构和逻辑·结构区别
总结：逻辑结构是用户设置的，物理结构是操作系统设置的
每个字符1B。在用户看来，整个文件占用一片连续的逻辑地址空间，用fseek找到逻辑上第十六个字符
在操作系统角度，就是一堆二进制数据，随便拆，将（逻辑块号，块内偏移量）转换为（物理块号，块内偏移量）
创建顺序文件
逻辑上
物理上
连续分配
链接分配
索引分配
顺序文件采用顺序存储/链式存储（用户设计）
顺序文件：各个记录可以顺序存储或链式存储
顺序存储
链式存储
链式存储的顺序文件采用连续分配
其中链式存储是用户逻辑上设置的存储方式，连续分配则是操作系统的物理存储形式
链式存储的顺序文件采用链接分配
逻辑结构：索引文件
用户自己建立的，映射：关键字à记录存放的逻辑地址
索引文件采用索引分配
操作系统建立的，映射：逻辑块号à物理块号
目录结构
文件控制块
文件控制块（FCB）：FCB的有序集合称为文件目录，一个FCB就是一个文件目录项
FCB中包含了文件的：
- 基本信息（文件名、物理地址、逻辑结构、物理结构等）
- 存取控制信息（是否可读/可写、禁止访问的用户名单等）
- 使用信息（如文件的建立时间、修改时间等）。
目录结构
用户需要对目录进行的操作：
- 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
- 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
- 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
- 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
目录有以下几种结构：
单级目录结构
整个系统中只建立一张目录表，每个文件占一个目录项。
- 优点
- 实现了按名存取
- 缺点
- 不允许文件重名
- 不适用于多用户操作系统
两级目录结构
早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。
主目录记录用户名和其用户文件目录存储的位置，用户目录记录用户文件的FCB信息。
- 优点
- 允许不同用户的文件重名
- 对多用户文件的访问限制
- 缺点
- 缺乏灵活性，用户不能对文件进行分类
多级目录结构
又称树形目录结构。用户要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。
当目录层数较多时，每次都从根目录查找是很费时的，因此一般会设置当前目录。
当用户已经打开了某个目录，即这张目录表已调入内存，那么可以把它设置为当前目录。当用户想要访问某个文件时，可以使用从当前目录出发的相对路径。
- 优点
- 便于对文件进行分类
- 层次结构清晰
- 缺点
- 不便于实现文件的共享
无环图目录结构
在树形目录结构的基础上，增加些指向同一节点的有向边，使整个目录成为一个有向无环图。可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
可以更方便地实现多个用户间的文件共享。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除节点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。当共享计数器的值为0时，才会删除该结点。
索引节点
由于在查找文件时只需要使用到文件名这一信息，因此可以将其他的文件信息放进索引节点中。这样目录中只需要存储文件名和指向索引节点的指针即可。
存放在外存中的索引结点称为磁盘索引结点，当索引结点放入内存后称为内存索引结点。 相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。
目录的实现
- 线性表
- 查找方式：顺序查找
- 优点：实现简单
- 缺点：查找比较费时
- 哈希表
- 查找方式：散列查找
- 优点：查找迅速
- 缺点：需要一些措施来避免冲突
实际使用中顺序查找比较多
查找得到的是文件的逻辑地址
文件共享
基于索引节点的共享方式（硬链接）
在索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。
当某个用户删除自己的该文件时，只是删除该用户目录项中指向索引节点的条目，并将索引节点中count减一。
基于符号链的共享方式（软链接）
系统创建一个LINK类型的文件，记录了它所指向的文件的路径，当操作系统访问时，通过该路径按级查找目录，得到该文件。
软链接直接复制计数变量，删除文件不影响符号链接。
软连接的方式由于需要逐级访问目录，因此会比硬链接要慢。
文件保护
口令保护
为文件设置一个口令，用户请求访问该文件时必须提供口令。
口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输 入口令，操作系统会将用户提供 的口令与FCB中存储的口令进行对比， 如果正确，则允许该用户访问文件。
- 优点
- 保存口令的开销不多
- 验证口令的开销也很小
- 缺点
- 口令存放在系统内部，不够安全
加密保护
使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密。
例如，使用异或运算，密码为01001，则对于文件的原始二进制位每5个一组依次与密码进行异或运算，得到密文，解码时，同样将密文依次异或运算，得到明文。
- 优点
- 保密性强
- 缺点
- 加密/解密需要一定的时间
访问控制
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List，ACL），该表中记录了各个用户可以对该文件执行哪些操作。
精简的访问列表：以组为单位，标记各用户组可以对文件执行哪些操作。解决了当系统用户过多时访问控制表过大的问题。
- 优点
- 实现灵活，可以实现复杂的文件保护方式