文件管理

这是一个文件管理知识点的思维导图，包括初始文件管理、有结构文件、文件目录、文件的物理结构、文件存储空间管理、文件的基本操作、文件共享、文件保护、文件系统的层次结构、磁盘的结构、磁盘调度算法这几个方面的知识点，并对其作了详细的介绍。

文件管理

• 1. 初始文件管理
  • 文件的定义：一组有意义的信息的集合
  • 文件的属性
    • 文件名、标识符、类型、位置、大小、保护信息
  • 文件内部应该如何被组织起来（文件的逻辑结构）
  • 文件之间应该如何被组织起来（目录结构）
  • 操作系统应该向上提供哪些功能（create、delete、open、close、read、write系统调用
  • 文件应如何存放在外存中（文件的物理结构）
  • 操作系统如何管理外存中的空闲块（存储空间的管理）
  • 操作系统需要提供的其他文件管理功能
    • 文件共享
    • 文件保护
• 2. 有结构文件
  • 顺序文件
    • 串结构
      • 记录顺序与关键字无关
    • 顺序结构
      • 记录按关键字顺序排列
    • 可变长记录的顺序文件无法实现随机存取，定长记录可以
    • 定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）
    • 最大缺点：不方便增加/删除 记录
  • 索引文件
    • 建立一张索引表，每个记录对应一个表项，各记录不用保持顺序，方便增加/删除记录
    • 索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
    • 若索引表按关键字顺序排列，则可支持快速检索
    • 解决了顺序文件不方便增加/删除记录的问题，同时让不定长记录的文件实现了随机存取，但索引表可能占用很多空间
  • 索引顺序文件
    • 将记录分组，每组对应一个索引表项
    • 检索记录时先顺序查索引表，找到分组，再顺序查找分组
    • 当记录过多时，可建立多级索引表
• 3. 文件目录
  • 文件目录的实现
    • 一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
    • 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
  • 目录结构
    • 单级目录结构
      • 一个系统只有一张目录表，不允许文件重名
    • 两级目录结构
      • 不同用户的文件可以重名，但不能对文件进行分类
    • 多级（树形）目录结构
      • 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
      • 系统根据文件路径找到目录文件
      • 从根目录出发的路径是绝对路径
      • 从当前目录出发的路径是相对路径
    • 无环图目录结构
      • 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
      • 为共享节点设置一个共享计数器，技术为0时才真正删除该节点
  • 索引节点
    • 除了文件名之外的所有信息都放在索引节点中，每个文件对应一个索引节点
    • 目录项中只包含文件名，索引节点指针，因此每个目录项的长度大幅减小
    • 由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/O的次数就减少了很多
• 4. 文件的物理结构（文件分配方式）
  • 对非空闲磁盘块的管理
  • 连续分配
    • 为文件分配的必须是连续的磁盘块
    • 目录项内容：起始块号、文件长度
    • 顺序存取速度快，支持随机访问
    • 会产生碎片，不利于文件拓展
  • 链接分配
    • 隐式分配
      • 除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针
      • 目录项内容：起始块号、结束块号
      • 可解决碎片问题，外存利用率高，文件拓展实现方便
      • 只能顺序访问，不能随机访问
    • 显式分配
      • 建立一张文件分配表FAT，显式记录盘块的先后关系（开机后FAT常驻内存）
      • 目录项内容：起始块号
      • 除了拥有隐式链接的优点之外，还可通过查询内存中的FAT实现随机访问
      • FAT需要占用一定的存储空间
  • 索引分配
    • 为文件数据块建立索引表，若文件太大，可采用链接方案、多层索引、混合索引
    • 链接方案记录的是第一个索引快的块号，多层/混合索引记录的是顶级索引快的块号
    • 支持随机访问，易于实现文件的拓展
    • 索引表需要占用一定的存储空间，访问数据块前需要先读入索引快。若采用链接方案，查找索引快时可能需要很多次读磁盘操作
• 5. 文件存储空间管理
  • 对空闲磁盘块的管理
  • 存储空间的划分与初始化
    • 文件卷（逻辑卷），目录区、文件区的概念
    • 目录区包含文件目录、空闲表、位示图、超级快等用于文件管理的数据
  • 空闲表法
    • 空闲表中记录每个连续空闲区的起始块号、盘块数
    • 分配时可采用首次适应、最佳适应等策略；回收时注意表项的合并问题
  • 空闲链表法
    • 空闲盘块链
      • 以盘块为单位组成一条空闲链
      • 分配时从链头依次取出空闲块，回收时将空闲块插到链尾
    • 空闲盘区链
      • 以盘区为单位组成一条空闲链
      • 分配时可采用首次适应、最佳适应等策略；回收时注意相邻空闲盘区合并的问题
  • 位示图法
    • 二进制位对应一个盘块。（字号，位号）或（行号，列号）与盘块号一一对应
    • 重要考点：要能够自己退出盘块号到（字号，位号）的相互转换公式
    • 需要注意的题目条件
      • 二进制0/1到底哪个代表空闲，哪个代表不空闲
      • 字号，位号，盘块号到底是从0开始还是从1开始
  • 成组链接法
    • UNIX采用的策略，适应大型文件系统，理解即可，不方便文字描述的知识点也很难作为考题
• 6. 文件的基本操作
  • 创建文件
    • 分配外存空间，创建目录项
  • 删除文件
    • 回收外存空间，删除目录项
  • 打开文件
    • 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号返回给用户
      • 打开文件时并不会把文件数据直接读入内存。索引号也称文件描述符
    • 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
    • 每个进程由自己的打开文件表，系统中也有一张总的打开文件表
    • 进程打开文件表中特有的属性：读写指针、访问权限（只读？只写？）
    • 系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）
  • 关闭文件
    • 将进程打开文件表中的相应表项删除
    • 系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表中的表项
  • 读文件
    • 根据读指针、读入数据量、内存位置将文件数据从外存读入内存
  • 写文件
    • 根据写指针、写出数据量、内存位置 将文件数据从内存写出外存
• 7. 文件共享
  • 硬链接
    • 各个用户的目录项指向同一个索引节点
    • 索引节点中需要有链接计数count
    • 某用户想删除文件时，只是删除用户的目录项，且count--
    • 只有count==0时才能真正删除文件数据和索引节点，否则会导致指针悬空
  • 软链接（符号链接）
    • 在一个Link型的文件中记录共享文件的存放路径（Windows 快捷方式）
    • 操作系统根据路径一层层查找目录，最终找到共享文件
    • 即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败（找不到对应目录项）
    • 由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问的速度要比硬链接慢
• 8. 文件保护
  • 口令保护
    • 为文件设置一个口令，用户想要访问文件时需要提供口令，由系统验证口令是否正确
    • 实现开销小，但口令一般存放在FCB或索引节点（也就是存放在系统中）因此不太安全
  • 加密保护
    • 用一个密码对文件加密，用户想要访问文件时，需要提供相同的密码才能正确的解密
    • 安全性高，但加密/解密需要耗费一定的时间（eg:异或加密）
  • 访问控制
    • 用一个访问控制表ACL 记录各个用户（或各组用户）对文件的访问权限
    • 对文件的访问类型可以分为：读/写/执行/删除 等
    • 实现灵活，可以实现复杂的文件保护功能
    • 如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制
• 9. 文件系统的层次结构
  • 用户应用程序
  • 用户接口
    • 处理用户发出的系统调用请求
  • 文件目录系统
    • 所有和目录、目录项相关的管理工作都在本层完成
  • 存取控制模块
    • 主要完成文件保护的相关功能
  • 逻辑文件系统与文件信息缓冲区
    • 用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址
  • 物理文件系统
    • 把上一层提供的文件逻辑地址转换为实际的物理地址
  • • 辅助分配模块
      • 负责文件存储空间的管理，即负责分配和回收存储空间
    • 设备管理模块
      • 设备
      • 直接与硬件交互，负责和硬件直接相关的一些管理工作
• 10. 磁盘的结构
  • 磁盘、磁道、扇区的概念
    • 磁盘由表面涂有磁性物质的圆形盘片组成
    • 每个盘片被划分为一各个磁道，每个磁道又划分为一个个扇区
  • 如何在磁盘中读/写数据
    • 磁头移动到目标位置，盘片旋转，对应扇区划过磁道次啊能完成读/写
  • 盘面、柱面的概念
    • 磁盘中有多个盘片摞起来，每个盘片有两个盘面
    • 所有盘面中相对位置相同的磁道组成柱面
  • 磁盘的物理地址
    • 柱面号、盘面号、扇区号
  • 磁盘的分类
    • 根据磁头是否可移动
      • 固定头磁盘
      • 移动头磁盘
    • 根据盘片是否可更换
      • 固定盘磁盘
      • 可换盘磁盘
• 11. 磁盘调度算法
  • 一次磁盘读写操作需要的时间
    • 寻找（寻道）时间：启动磁臂 移动磁头花的时间
    • 延迟时间：将目标扇区转到磁头下面所花的时间
    • 传输时间：读写数据所花的时间
  • 磁盘调度算法
    • 先来先服务FCFS
      • 按访问请求到达的先后顺序进行处理
    • 最短寻找时间优先SSTF
      • 每个都优先相应距离磁头最近的磁盘访问请求
      • 贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短
      • 缺点：可能导致饥饿
    • 扫描算法（电梯算法）SCAN
      • 只有磁头移动到最边缘的磁道时才可以改变磁头移动方向
      • 缺点：对各个位置磁道的响应频率不平均
    • 循环扫描算法（C-SCAN算法）
      • 只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求
    • 低频考点
      • LOOK算法
        • SCAN算法的改进，只要磁头移动方向上不在有请求，就立即改变磁头方向
      • C-LOOK算法
        • C-SCAN算法改进，只要磁头移动方向上不再有请求，就立即让磁头返回
• 12. 减少延迟时间的方法
  • 交替编号
    • 具体做法：让编号相邻的扇区在物理上不相邻
    • 原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区
  • 错位命名
    • 具体做法：让相邻盘面的扇区编号错位
    • 原理：与交替编号的原理相同，错位命名法可降低延迟时间
  • 磁盘地址结构的设计
    • 理解为什么要用（柱面号，盘面号，扇区号）的结构
    • 理解为什么不用（盘面号，柱面号，扇区号）的结构
    • 原因：在读取地址连续的磁盘块时，前者不需要移动磁头
• 13. 磁盘的管理
  • 磁盘初始化
    • 低级格式化/物理格式化：划分扇区
    • 磁盘分区（C盘、D盘、E盘）
    • 逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空间管理的数据结构）
  • 引导块
    • 计算机启动时需要运行初始化程序（自举程序）来完成初始化
    • ROM中存放很小的自举装入程序
    • 完整的自举程序存放在初始块（引导块）中
  • 坏块的管理
    • 简单的磁盘：逻辑格式化时将坏块标记出来
    • 复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区