[数据结构与算法]操作系统二轮复习（文件管理）

初识文件管理

1. 文件管理包含文件的内部组织和文件的内部组织
2. 内部组织：逻辑上的组织and物理上的组织
   2.1 文件的逻辑结构一般不考
3. 外部组织：文件之间通过目录组织起来
4. 目录由文件控制块FCB构建起来的

1. 一个文件控制块FCB对应一个文件目录项
2. 不同用户对文件的操作权限是不同的，所以文件控制块中包含存取控制信息

逻辑结构

根据有结构文件中的各条记录在逻辑上如何组织，可以分为三类

顺序文件

1. 定长记录的顺序文件，若物理上采用顺序存储，则无论是采用串结构or顺序结构都行实现随机存取。只不过串结构无法根据关键字快速检索
2. 顺序文件有两种结构：串结构（时间）and 顺序结构（关键字）
3. 串结构增删一条记录相对简单
4. 在对记录进行批量处理处理时，顺序文件的效率是所有逻辑文件中最高的。
5. 只有顺序文件才能存储在磁带上

索引文件

1. 解决顺序文件增删记录不方便的问题
2. 可以让不定长文件实现随机存取
3. 索引表用于记录每一个文件所对应的物理地址
4. 索引表是一个定长记录的顺序文件，可以实现随机存取
5. 如果为每一个文件都建立一个索引项，那么这个索引表可能非常大
6. 对于索引文件方式，如果要记录可变长文件的地址，除了要记录起始地址外，还需要记录这个文件的长度

索引顺序文件

1. 索引顺序文件就是将索引表中的记录分组， 将每个分组对应一个索引项。
2. 查找一条记录时，先通过索引表找到其所在的组，然后在改组中使用顺序查找，就能很快找到记录
3. 注意：索引顺序文件中的索引表只包含关键字和指针两个部分
   这个与索引文件中的索引表不同

注意k级索引，查找一个文件要查找k+1次

文件目录+文件控制块

1. 索引节点就是让目录表瘦身，目录表中只存放文件名和索引节点的地址。
2. 索引节点中保存目录表中的其他剩余信息
   查找过程中，如果命中了目录表中的目录项，就读取对应的索引节点
3. 引入索引节点可以提高查找文件的效率
4. 当不引入索引节点时
   每个磁盘可以存放16个FCB，也就是16个目录项，640个目录项就需要640/16=40块磁盘来存放，对于640条目录项，平均检索一条目录需要查询320个目录项，320个目录项需要320/16=20块磁盘，也就是说，需要启动磁盘20次
5. 当引人了索引节点
   假设一个目录项FCB只占16个字节，那么一个磁盘就可以存放1KB/16=64个目录项，那么在640条目录项中查找目标记录时，平均访问320次，320/64=5块磁盘，也就是说只需要启动5次磁盘。

1. 在 Linux 中，“.”表示当前目录
2. 在树形目录结构中，根据相对路径检索文件可以减少磁盘IO次数，因为每查询下一级目录的时候都要启动磁盘，然后把下一级文件目录从外存调入内存
   
3. 无环图目录结构
   

文件共享

硬链接可以联系无环图目录结构（找不到直接搜索关键字）

1. 软连接可以理解为：
   1.1 用户B要访问用户A的一个文件F，可以由系统创建一个LINK类型的新文件L，这个新文件L中只保存了文件F的路径地址。
   1.2用户B的目录文件中加入这个文件L
   1.3 用户要访问F，就找到这个文件L，读取了文件L中的保存的F的地址信息，然后再去找文件F

2. 只有文件F的拥有者用户A才拥有指向其索引节点的指针。

3. 注意：建立符号链接时，引用计数值直接复制
   

文件保护

文件实现-文件分配方式（非空闲）

1. OS对空闲磁盘块和非空闲磁盘块都要进行管理
2. 文件分配方式or文件的物理结构：是对非空闲磁盘块的探索
3. 文件存储空间管理：是对空闲磁盘块的探索

1. 连续分配

连续分配会产生外部碎片

2. 链接分配

2.1 隐式链接

隐式链接：访问一次磁盘，将磁盘中的一个物理块读入内存，读取这块文件后才能知道下一个物理块存放在磁盘的什么位置。

2. 2 显示链接

注意：

1. 显式链接支持随机访问！！！隐式链接不支持
2. 相比于隐式链接，地址转换时不需要访问磁盘
3. FAT是常驻内存的
   

3. 索引分配

注意索引分配中的索引表与显示链接中的FAT文件分配表区别

1. 索引表：一个文件对应一张表
2. FAT：一个磁盘对应一张

注意：FAT是常驻内存的，索引表保存在磁盘中

索引分配问题解决（索引表太大）

链接方案（将多个索引表链接）

多层索引（类似于多级页表）

混合索引（inode）

分配方式总结

文件实现-文件存储空间管理（空闲块）

注意FCB存储在磁盘的目录区

1. 空闲表法

2. 空闲链表法

连续的多个空闲盘块组成一个空闲盘区

空闲链表法：OS保存了链头and链尾指针，链头指针在分配空闲块的时候用，链尾指针在回收空闲块的时候用

3. 位示图法

4. 成组链接法（不常考，需要看视频理解）

总结

文件操作

1. 打开文件：
   在用户打开了一个文件之后，这个文件相关的那些信息就已经放入内存当中了， 之后如果用户想要操作这个文件，只需要根据打开文件表的编号就可以找到这个文件的所有信息，这样就不需要每次查文件的时候都重新访问目录了。因此，把目录项复制到打开文件表当中，是可以大幅度提升文件访问速度的。
2. 打开文件表分为两种

系统的打开文件表：

1. 这个打开文件表中会记录所有的正在被其他进程使用的文件的信息
2. 这个表中包含一个打开计数器的字段
3. 打开计数器：用于记录有多少个进程打开了该文件。
4. 整个系统只有一张

每个进程也有一张自己的打开文件表

1. 这个表用于记录这个进程此时打开的文件有哪些
2. 进程打开文件表中有一个系统表索引号字段
3. 系统表索引号：

磁盘结构（注意簇的概念）

1. 通俗的来讲，在Windows下如NTFS等文件系统中叫做簇；在Linux下如Ext4等文件系统中叫做块（block）。每个簇或者块可以包括2、4、8、16、32、64…2的n次方个扇区。
2. 簇也可以称作分配单元（allocation unit），它是操作系统磁盘文件存储管理的单位，可为一个或多个物理扇区组成，由格式化时选定的文件系统而定。簇是操作系统所使用的逻辑概念而非磁盘的物理特性。
3. 簇是系统在硬盘上读写文件时的单位，是一个数据块。而扇区是硬盘划分的最小单位值，就是簇（数据块）占用的地方。
4. 打个比方，你（系统）要在仓库（仓库可视为硬盘）里存放一些书（数据）。你先把书分门别类放到一些大纸箱（簇）里，然后放进仓库，纸箱的体积是根据你仓库大小来决定的，而仓库始终划分成单位为0.1m3的小格子（扇区），仓库大了，纸箱就大些，仓库小了，纸箱就小些。
5. 绝大多数操作系统以簇为单位进行空间分配

1. 先确定柱面号：磁头移动到指定磁道
2. 再确定盘面号：决定激活哪个盘面的磁头
3. 磁盘的物理地址编号是按照
   1、柱面号->盘面号->扇区号
   而不是
   2、盘面号->柱面号->扇区号
   原因是如果按照2来编号，存取数据的时候首先确定一个盘面，然后磁头需要在盘面的不同柱面间移动，耗费时间较多
   而采用1的方式由于顺序编号会按照柱面来编号，故在存取数据时只有当整个柱面的数据都被存取完才需要切换柱面进入下一个柱面，这才需要移动磁头，因此相比2大大减少了磁头移动的距离，缩短了寻道时间。
   注：采用1相同柱面不同磁道间存取数据时只需要激活相应盘面的磁头即可，不需要移动磁头。因为磁头由上到下在每个盘面上都有，且是在一条垂直直线上同时运动的。

总的平均存取时间 T a = T S + 1/2r + b/(rN)

磁盘调度算法

减少延迟时间的方法：（交替编号+错位命名）

磁盘的管理（初始化+引导块+坏块）

文件层次结构