一、文件管理
1、文件管理概述
文件的定义：一组有意义的信息的集合
文件的属性：文件名、标识符、类型、位置、大小、保护信息
2、文件的逻辑结构
逻辑结构：指在用户看来，文件内部的数据应该是如何组织起来的。
物理结构：指的是在操作系统看来，文件的数据是如何存放在外存中的。
无结构文件：文件内部的数据就是一系列二进制流或字符流组成。如txt
文件内部的数据其实就是一系列字符流，没有明显的结构特性
1）顺序文件
串结构：记录顺序与关键字无关
顺序结构：记录按关键字顺序排列
可变长记录的顺序文件无法实现随机存取，定长记录可以（可变长记录的顺序文件在每
次查询时只能从头依次查找）
定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）
缺点：不方便增加、删除记录
2）索引文件
建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录
索引表本身就是定长记录的质顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
若索引表按关键字顺序排列，则可支持快速检索
解决了顺序文件不方便增、删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间
3）索引顺序文件
将记录分组，每组对应一个索引表项
检索记录时先顺序查索引表，找到分组，再顺序查找分组
当记录过多时，可建立多级素引表
3、文件目录
1）文件目录的实现
一个文件对应一个FCB（目录项），多个FCB组成文件目录
图中的每一条数据即为一个FCB
2）目录结构
1. 单级目录结构
一个系统只有一张目录表，不允许文件重名
2. 两级目录结构
主文件目录（MFD）和用户文件目录（UFD）。不同用户有不同的目录表
不同用户的文件可以重名，但不能自己创建目录
3. 树形目录结构
不同文件下的目录可以重名，可以自己创建目录进行分类
系统根据文件路径找到目标文件
不方便文件共享
绝对路径：从根目录出发的路径
相对路径：从当前目录出发的路径
相对路径检索文件可以减少磁盘IO次数
4. 无环图目录结构
在树形目录结构的基础 上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
为共享结点设置一个共享计数器，计数器为0时才真正删除该结点
3）索引节点
除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引节点
目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减少
由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，提高了检索效率
4、文件保护
1）口令保护
为文件设置一个“口令"，用户想要访问文件时需要提供口令，由系统验证口令是否正确
实现开销小，但"口令"一般存放在FCB或索引结点中（存放在系统中），因此不太安全
2）加密保护
用一个"密码"对文件加密，用户想要访问文件时，需要提供相同的“密码〞才能正确的解密
安全性高，但加密/解密需要耗费一定的时间
3）访问控制
用一个访问控制表（ACL） 记录各个用户或各组用户对文件的访问权限
对文件的访问类型可以分为：读/写/执行/删除等
实现灵活，可以实现复杂的文件保护功能
5、文件共享
1）硬连接
硬连接：基于索引结点的共享
各个用户的目录项指向同一个索引结点
索引结点中需要有链接计数 count
某用户想删除文件时，只是删除该用户的目录项，且count--
只有count ==0时才能真正删除文件数据和索引结点，否则会导致指针悬空
2）软连接
软连接：基于符号链的共享
在一个 Link 型的文件中记录共享文件的存放路径（Windows 快捷方式）
操作系统根据路径一层层查找目录，最终找到共享文件
即使软链接指向的共享文件已被刷除，Link 型文件依然存在，只是通过 Link 型文件中的路径去查找共享文件会失败（找不到对应目录项）
由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘IO，因此用软链接访问共享文件的速度要比硬链接更慢
二、文件
1、文件实现
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。
磁盘块的大小与内存块、页面的大小相同
内存与磁盘之间的数据交换都是以“块”为单位进行的。即每次读入一块，或每次写出一块
2、文件分配方式
1）连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。
物理块号 = 起始块号 + 逻辑块号
连续分配支持顺序访问和直接访问（即随机访问）
2）隐式链接分配
缺点：只支持顺序访问，不支持随机访问，查找效率低。指向下一个盘块的指针也需要耗费少量的存储空间。
优点：不会有碎片问题，外存利用率高。方便文件拓展。
3）显式链接分配
把用于链接文件各物理块的指针显式地存放在一张表中。即 文件分配表（FAT）
一个磁盘仅设置一张FAT。 开机时，将FAT读入内存，并常驻内存。
优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间
4）索引分配
1. 链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
2. 多层索引
建立多层索引（原理类似于多级页表）
若采用多层索引，则各层索引表大小不能超过一个磁盘块
采用K层索引结构，且顶级页级索引表未调入内存，则访问一个数据块需要K+1次读磁盘操作
3. 混合索引
多种索引分配方式的结合
5）总结
| 分配方式 | How | 目录项内容 | 优点 | 缺点 |
|---|---|---|---|---|
| 顺序分配 | 为文件分配的必须是连续的磁盘块 | 起始块号、文件长度 | 顺序存取速度快，支持随机访问 | 会产生碎片，不利于文件拓展 |
| 隐式链接分配 | 除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针 | 起始块号、结束块号 | 可解决碎片问题，外存利用率高，文件拓展实现方便 | 只能顺序访问，不能随机访问 |
| 显式链接分配 | 建立一张文件分配表(FAT)， 显式记录盘块的先后关系 （开机后FAT常驻内存） | 起始块号 | 除了拥有隐式链接的优点之外，还可通过查询内存中的FAT实现随机访问 | FAT需要占用一定的存储空间 |
| 索引分配 | 为文件数据块建立索引表。若文件太大，可采用链接方案、多层索引、混合索引 | 链接方案记录的是第一个索引块的块号，多层/混合索引记录的是顶级索引块的块号 | 支持随机访问，易于实现文件的拓展 | 索引表需占用一定的存储空间。访问数据块前需要先读入索引块。若采用链接方案，查找索引块时可能需要很多次读磁盘操作。 |
3、逻辑结构和物理结构
1）逻辑结构
用户（文件创建者）的视角看到的样子
在用户看来，整个文件占用连续的逻辑地址空间
文件内部的信息组织完全由用户自己决定，操作系统井不关心
2）物理结构
由操作系统决定文件采用什么物理结构存储
操作系统负责将逻辑地址转变为（逻辑块号：块内偏移量）的形式，并负责实现逻辑块号到物理块号的映射
4、文件存储空间管理
1）存储空间的划分与初始化
存储空间的初始化：将各个文件卷划分为目录区、文件区
目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
文件区用于存放文件数据
2）空闲表法
为一个文件分配连续的存储空间。
可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
回收时注意表项的合并问题
3）空闲链表法
空闲盘块链：以盘块为单位组成一条空闲链。分配时从链头依次取出空闲块，回收时将空闲块查到链尾。
空闲盘区链：以盘区为单位组成一条空闲链。分配时可采用首次适应、最佳适应等策略，回收时注意相邻空闲盘区合并的问题。
4）位示图法
位示图：每个二进制位对应一个盘块。可以用（字号，位号）对应一个盘块号。
注意题目条件：盘块号、字号、位号到底是从0开始还是从1开始
(字号, 位号)=(i, j) 的二进制位对应的 盘块号 b = ni + j
b号盘块对应的字号 i = b/n，位号 j = b%n
5）成组链接法
UNIX 采用的策略，适合大型文件系统。
理解即可，不方便用文字描述的知识点也很难作为考题
咸鱼学长这里讲的比较一般，参考【天勤考研】成组链接法
分组：
1号块为超级块，超级块需要调入内存
1块的空间用完之后，将2块调入内存
5、文件基本操作
创建文件：分配外存空间，创建目录项
删除文件：回收外存空间，删除目录项
打开文件：
- 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号（文件描述符）返回给用户
- 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
- 每个进程有自己的打开文件表，系统中也有一张总的打开文件表
- 进程打开文件表中特有的属性：读写指针、访问权限（只读？读写？）
- 系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）
关闭文件：
- 将进程打开文件表中的相应表项删除
- 系统打开文件表的打开计数器减1，若打开计数器为0，则别除系统表的表项
读文件：根据读指针、读入数据量、内存位置将文件数据从外存读入内存
写文件：根据写指针、写出数据量、内存位置将文件数据从内存写出外存
6、文件系统的层次结构
用一个例子来辅助记忆文件系统的层次结构：
假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。
- 用户需要通过操作系统提供的接口发出上述请求——用户接口
- 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统
- 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层）
- 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
- 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
- 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
- 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块
三、磁盘
1、磁盘的结构
1）磁盘、磁道、扇区
磁盘由表面涂有磁性物质的圆形盘片组成
每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区
最内侧磁道上的扇区面积最小，因此数据密度最大
2）如何在磁盘中读/写数据
磁头移动到目标位置，磁片旋转，对应扇区划过磁道才能完成读写
3）盘面、柱面的概念
磁盘有多个盘片“摞”起来，每个盘片有两个盘面
所有盘面中相对位置相同的磁道组成柱面
4）磁盘的物理地址
（柱面号，盘面号，扇区号）
5）磁盘的分类
根据磁头是否可移动：固定头磁盘（每个磁道有一个磁头）、移动头磁盘（每个盘面只有一个磁头）
根据盘片是否可更换：固定盘磁盘、可换盘磁盘
2、磁盘调度算法
1）一次读写的时间
寻道时间：启动磁臂、移动磁头所花的时间
① 启动磁头臂是需要时间的。假设耗时为 s；
② 移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。
则寻道时间 TS = s + m * n
延迟时间：将目标扇区转到磁头下面所花的时间
设磁盘转速为 r （单位：转/秒，或 转/分）
则平均所需的延迟时间 TR = (1/2) * (1/r) = 1/(2r)
传输时间：读/写数据花费的时间
假设磁盘转速为 r，此次读/写的字节数为 b，每个磁道上的字节数为 N
传输时间Tt = (1/r) * (b/N) = b/(rN)
2）先来先服务（FCFS）
按访问请求到达的先后顺序进行处理
优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。
3）最短寻找时间优先 （SSTF）
按访问请求到达的先后顺序进行处理
贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短
优点：性能较好，平均寻道时间短
缺点：可能导致饥饿
4）扫描算法（电梯算法、SCAN）
只有磁头移动到最边缘的磁道时才可以改变磁头移动方向
缺点：对各个位置磁道的响应频率不平均
5）循环扫描算法（C-SCAN）
只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求
6）LOOK算法
SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向
7）C-LOOK 算法
C-SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回
3、减少延迟时间的优化
1）交替编号
磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”
具体做法：让编号相邻的扇区在物理上不相邻
原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区
2）错位命名
具体做法：让相邻盘面的扇区编号"错位"
原理：与"交替编号"的原理相同。"错位命名法”可降低延迟时间
3）磁盘地址结构的设计
磁盘的物理地址是（柱面号，盘面号，扇区号）
在读取地址连续的磁盘块时，不需要移动磁头
4、磁盘的管理
1）磁盘初始化
- 低级格式化/物理格式化：划分扇区
- 磁盘分区 （C盘、D盘、E盘）
- 逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空问管理的数据结构）
2）引导块
计算机启动时需要运行初始化程序（自举程序）来完成初始化
ROM中存放很小的自举装入程序
完整的自举程序存放在初始块（引导块）中
3）坏块的管理
简单的磁盘：逻辑格式化时将坏块标记出来（坏块对操作系统不透明）
复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区（坏块对操作系统透明）
