内容系听课复习所做笔记，图例多来自课程截图
序
图：操作系统的文件功能
文件系统就是管理外存用的（免去用户接触底层繁杂的细节）
- 方便了用户
- 保证了文件的安全性
- 有效提高了系统的资源利用率
需要考虑：
- 文件内部数据如何组织（无结构和有结构）
- 文件之间如何组织（树形，层级，目录）
- OS应提供哪些功能才能方便用户、应用程序使用文件（5种基本文件操作+打开关闭等）
- 文件该怎么存放在外存上
五种基本文件操作：
- 创建文件
- 删除文件
- 读文件
- 写文件
- 设置文件的读/写位置（改顺序存取为随机存取）
其他操作还有打开open关闭close、文件属性操作、目录操作
文件的逻辑结构：
- 按是否就结构分（有结构文件和无结构文件）
- 按组织方式分（顺序、索引、索引顺序）
文件的物理结构：
- 连续存放在磁盘
- 离散存储在磁盘（读取先后顺序）
- 空闲磁盘块的管理
基础概念
操作系统对于文件的管理分为两方面：
- 对非空闲磁盘块的管理（文件的物理结构/分配方式）
- 对空闲磁盘块的管理（文件存储空间管理）
磁盘读写的最小单位是扇区，一个扇区大小一般为512B，多个扇区组合为一个数据块（逻辑块）
块=磁盘块=物理块
文件系统的基本操作单位是数据块，内存块和磁盘块在IO时总是对应的
正是这种对应关系，用户可以采用(逻辑块号, 块内地址)的形式表示文件的逻辑地址，文件的逻辑地址到物理地址的映射由操作系统负责。
多数情况，磁盘块大小和内存块（或内存页面）大小相同
既然知道文件的的存储是靠一个一个的数据块，那么文件的物理结构的关键问题无非就是一个文件包含哪些数据块，以及数据块之间的先后关联。
文件的物理结构/分配方式有三种：
- 连续分配
- 链接分配（分为显式链接和隐式链接）
- 索引分配
从物理空间上看，则分为
- 连续空间分配（存放）方式
- 非连续空间分配（存放）方式
三大逻辑结构（文件组织方式）
顺序文件
只有定长的顺序结构可以随机存取，变长的顺序结构不行。串结构每次都得从头访
随机存取的关键就是能否直接根据iii推定第iii位的元素地址
顺序文件增删困难（串结构略简单点）
索引文件
由表+实际数据构成，数据可以离散存放，索引表本身则是定长记录的顺序文件
哪怕记录是变长的也不要紧，在索引表中的表项是定长的。查到第iii项就可以获取到记录的首地址和长度。这种方式查找速度快。
可以依据不同的关键字建立多个索引表
索引表项如果不显著小于记录项，存储空间利用率是不高的（存储开销大）
索引顺序文件
顺序文件和索引文件相结合的产物
索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项（通常每组中的第一个记录对应索引表项）
如果文件特别大，可以采用多级索引进一步优化查询效率
文件目录
文件使用FCB管理（类似进程使用PCB），文件与FCB一一对应
- FCB的有序集称为文件目录
- 一个FCB就是一个文件目录项
- 文件更改后也得更改对应的FCB
- 文件目录也被看作是一个文件（目录文件）
FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）
最重要，最基本的还是文件名、文件存放的物理地址。
目录操作：
- 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
- 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
- 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
- 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
- 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）
建立新文件之前要检查相应 的目录下有没有重名
有向无环图目录实际上是允许“一子多父”的树形目录
书P255页原话：“在用户要创建新文件时，只需查看在自己的UFD及其子目录中有无与新建文件相同的文件名，若无，便可在UFD或其某个子目录中增加一个新目录项”
但是上方导图说了，树形结构中，不同目录下的文件可以重名，我个人觉得是可以重名，只要不在同一层目录即可。
三大物理结构（文件分配方式 ）
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理
块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同
内存与磁盘之间的数据交换（即读/写操作、磁盘I/O）都是以“块”为单位进行的。即每次读入一块，或每次写出一块
操作系统为文件分配存储空间都是以块为单位的
用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射
支持随机访问意味着磁盘地址能算出来，而不是得去依次访问才知道
连续分配
文件存放在磁盘连续的物理空间中，需要记录起始块和长度
物理块号=起始块号+逻辑块号
需要验证逻辑块号合法性（是否超过文件长度）
好处：读写效率最高、支持顺序访问和直接访问（即随机访问）
缺点：产生磁盘空间碎片、文件长度拓展困难、紧凑工作开销大、存储空间利用率低
链接分配
分为隐式链接和显式链接，题目没明确指出就是默认隐式链接
FAT和NTFS技术
隐式链接
类似于链表。
特点：
- 只能顺序访问，不能随机访问
- 访问第iii个磁盘块需要i+1i+1i+1次磁盘I/O
优点：
- 无外部碎片
- 易于增删
- 无需提前知道文件大小，易于拓展长度
缺点：
- 有内部碎片（以簇为单位内部碎片更大）
- 不能随机访问（访问开销还是有些大的）
- 空间不全是存数据（也存了指向下一个数据块的指针）
显式链接
基于文件分配表（FAT，File Allocation Table）实现显式分配，该表开机后常驻内存（提高了效率）。由于表项长度固定且表是连续存储的，故第iii个磁盘块对应的表项是可以计算出来的。
特点：
- 一个磁盘对应一张FAT
- PCB记录占用的第一个磁盘块下标iii，读磁盘能获取它的数据，若要获取后续数据，则访问FAT的第iii项，它记录的就是下一个磁盘块的编号
优点：
- 很方便文件拓展
- 不会有碎片问题
- 外存利用率高
- 支持随机访问
- 相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高
缺点：
- FAT占用一定存储空间
实际发展：
- FAT12
- 基于簇的FAT12
- FAT16
- FAt32
索引分配
索引块+数据块
特点：
- 文件离散存放
- 每个文件对应一张索引表
- 存索引表的块叫做索引块（块是单个表的最大长度）
- 文件数据存放的磁盘块称为数据块
优点：
- 易于拓展
- 支持随机访问
缺点：
- 是索引表需要占用一定的存储空间
当一个索引块内每项都表示一个磁盘块，此时若还不够用，就得有改进方式
- 链接方案
- 多层索引
- 混合索引
链接方案就是把多个索引表连接起来，但是访问第2个表得先访问第一个表才能知道第二个表在哪（访问的表越靠后，效率越低）
多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作
逻辑结构和物理结构的对比
逻辑结构实际上就是用户视角，用户不关注怎么存储，只考虑怎么从一堆比特流里解读出信息。用户只知道需要用到这些比特流的信息时，磁盘（经由操作系统）能给用户呈现完整的比特流。
物理结构就是磁盘视角，它拿来表示一个文件的一堆比特流，只考虑怎么存，不考虑怎么解读。当需要这些比特流信息时，能给原封不动还原回去就行。磁盘只知道用户（经由操作系统）给它的是一串完整的比特流，并不知道这个比特流怎么解读。
两者的链接桥梁就是操作系统，操作系统拿着这一堆比特流，上要给用户处理（读取显示），下要告诉磁盘怎么存（管理磁盘）。此外，也要管理文件与文件之间的关系，即“文件目录”
无结构文件：
顺序文件：
