01.初始文件管理

• 文件的定义

  • 一组有意义的信息的集合。

• 文件的属性

  • 文件名、标识符、类型、位置、大小、保护信息等。

• 文件内部应该如何被组织起来（文件的逻辑结构）

• 文件之间应该如何被组织起来（目录结构）

• 操作系统应该向上提供哪些功能（create、delete、open、close、read、write系统调用）
• 文件应如何放在外存中（文件的物理结构）
• 操作系统如何管理外存中的空闲块（存储空间的管理）

• 操作系统需要提供的其他文件管理功能

  • 文件共享
  • 文件保护

02.文件的逻辑结构

2.1无结构文件

• 无结构文件

  • 文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。

2.2有结构文件

• 有结构文件

  • 由一组相似的记录组成，又称“记录式文件”。
  • 每条记录有若干个数据项组成。
  • 如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。
  • 根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

2.3有结构文件的逻辑结构

• 顺序文件

  • 文件中记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。

  • 各个记录在物理上可以顺序存储或链式存储。

    • 链式存储：无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找。

    • 顺序存储：

      • 可变长记录：无法实现随机存取。每次只能从第一个记录开始依次往后查找。
      • 定长记录：可实现随机存取。记录长度为L，则第i个记录存放的相对位置是i*L。若采用串结构，无法快速找到某关键字对应的记录。
      • 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）

• 索引文件

  • 建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录。
  • 索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取。
  • 若索引表按关键字顺序排列，则可支持快速检索。
  • 解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多的空间。

• 索引顺序文件

  • 将记录分组，每组对应一个索引表项。
  • 检索记录时先顺序查索引表，找到分组，再顺序查找分组。
  • 当记录过多时，可建立多级索引表。

03.文件目录

3.1文件控制块（实现文件目录的关键数据结构）

• 一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录。
• 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件。

3.2目录结构

• 单级目录结构

  • 一个系统只有一张目录表，不允许文件重名。

• 两级目录结构

  • 不同用户的文件可以重名，但不能对文件进行分类。

• 多级（树形）目录结构

  • 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享。
  • 系统根据“文件路径”找到目标文件。
  • 从根目录出发的路径是“绝对路径”
  • 从“当前目录”出发的路径是“相对路径”

• 无环图目录结构

  • 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。
  • 为共享结点设置一个共享计数器，计数器为0时才真正删除该结点。

3.3索引结点（对文件控制块的优化）

• 除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点。
• 目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小。
• 由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/O的次数就少了很多。

04.文件的物理结构

4.1文件块、磁盘块

4.2文件分配方式

• 连续分配

  • 连续分配方式要求每个文件在磁盘上占有一组连续的块。
  • 读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
  • 连续分配的文件在顺序读/写时速度最快。
  • 物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片。
  • 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快。
  • 缺点：不方便文件拓展；存储空间利用率低，会产生持磁盘碎片。

• 链接分配

  • 隐式链接

    • 除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
    • 优点：很方便文件拓展，不会有碎片问题，外存利用率高。
    • 缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

• 显式连接

  • 把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
  • 优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
  • 缺点：文件分配表的需要占用一定的存储空间。

• 索引分配

  • 索引分配允许文件离散地分配在各个磁盘中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。（索引表的功能类似于内存管理中的页表--建立逻辑页面到物理页面之间的映射关系）。
  • 索引表存放的磁盘块称为索引块。
  • 文件数据存放的磁盘块称为数据块。

• 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

• 多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

• 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。

05.文件存储空间管理

• 存储空间的划分与初始化

  • 文件卷（逻辑卷），目录区、文件区的概念。
  • 目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据。

• 空闲表法

  • 空闲表中记录每个连续空闲区的起始盘块号、盘块数。
  • 分配时可采用首次适应、最佳适应等策略；回收时注意表项的合并问题。

• 空闲链表法

  • 空闲盘块链

    • 以盘块为单位组成一条空闲链。
    • 分配时从链头依次取出空闲块，回收时将空闲块查到链尾。

  • 空闲盘区链

    • 以盘区为单位组成一条空闲链。
    • 分配时可采用首次适应、最佳适应等策略；回收时注意相邻空闲盘区合并问题。

• 位示图法

  • 一个二进制位对应一个盘块。（字号，位号）或（行号，列号）与盘块号一一对应。
  • 重要考点：要能够自己退出盘块号->（字号，位号）之间的相互转换公式。

  • 需要注意的题目条件

    • 二进制位0/1到底哪个代表空闲，哪个代表不空闲。
    • 字号、位号、盘块号到底是从0开始还是从1开始。

• 成组链接法

  • UNIX采用的策略，适合大型文件系统。

06.文件的基本操作

• 创建文件

  • 分配外存空间，创建目录项。

• 删除文件

  • 回收外存空间，删除目录项。

• 打开文件

  • 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号返回给用户。
  • 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作。
  • 每个进程有自己的打开文件表，系统中也有一张总的打开文件表。
  • 进程打开文件表中特有的属性：读写指针、访问权限（只读？只写？）
  • 系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）

• 关闭文件

  • 将进程打开文件表中的相应表项删除。
  • 系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项。

• 读文件

  • 根据读指针、读入数据量、内存位置将文件数据从外存读入内存。

• 写文件

  • 根据写指针、写出数据量、内存位置将文件数据从内存写出外存。

07.文件共享

• 硬链接

  • 各个用户的目录项指向同一个索引结点。
  • 索引结点中需要有链接计数count
  • 某用户想删除文件时，只是删除该用户的目录项，且count--。
  • 只有count==0时才能真正删除文件数据和索引结点，否则会导致指针悬空。

• 软链接（符号链接）

  • 在一个Link型的文件中记录共享文件的存放路径（Windows快捷方式）。
  • 操作系统根据路径一层一层查找目录，最终找到共享文件。
  • 即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败（找不到对应目录项）。
  • 由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问。

08.文件保护

8.1口令保护

• 为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。

  • 口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件。
• 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
• 缺点：正确的“口令”存放在系统内部，不够安全。

8.2加密保护

• 使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。

• 优点：保密性强，不需要在系统中存储“密码”。
• 缺点：编码/译码，或者说加密/解密要花费一定时间。

8.3访问控制

• 在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List，ACL），该表中记录了各个用户可以对该文件执行哪些操作。

09.文件系统的层次结构

• 用一个例子来辅助记忆文件系统的层次结构：

• 假设某用户请求删除文件“D：/工作目录/学生信息.xlsx”的最后100条记录。

  • 用户需要通过操作系统提供的接口发出上述请求——用户接口。
  • 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统。
  • 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层）。
  • 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区。
  • 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统。
  • 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块。
  • 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块。

10.磁盘的结构

• 磁盘、磁道、扇区的概念

  • 磁盘由表面涂有磁性物质的圆形盘片组成。
  • 每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区。

• 如何在磁盘中读/写数据

  • 磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写。

• 盘面、柱面的概念

  • 磁盘有多个盘片“摞”起来，每个盘片有两个盘面。
  • 所有盘面中相对位置相同的磁道组成柱面。

• 磁盘的物理地址

  • 柱面号、盘面号、扇区号。

• 磁盘的分类

  • 根据磁头是否可移动

    • 固定头磁盘（每个磁道有一个磁头）。
    • 移动头磁盘（每个盘面只有一个磁头）。

  • 根据盘片是否可更换

    • 固定盘磁盘。
    • 可换盘磁盘。

11.磁盘调度算法

11.1一次磁盘读/写操作需要的时间

• 寻找时间（寻道时间）：启动磁臂、移动磁头所花的时间。
• 延迟时间：将目标扇区转到磁头下面所花的时间。
• 传输时间：读/写数据花费的时间。

11.2先来先服务（FCFS）

• 按访问请求到达的先后顺序进行处理。

• 优点：公平
• 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS性能很差，寻道时间长。

11.3最短寻找时间优先（SSTF）

• 每次都优先响应距离磁头最近的磁道访问请求。
• 贪心算法思想，能保证眼前最优，但无法保证总的寻道时间最短。
• 缺点：可能导致饥饿。

11.4扫描算法（电梯算法、SCAN）

• 只有磁头移动到最边缘的磁道时才可以改变磁头移动方向。
• 缺点：对各个位置磁道的响应频率不平均。

11.5循环扫描算法（C-SCAN）

• 只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求。

11.6LOOK算法

• SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向。

11.7C-LOOK算法

• C-SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回。

12.减少延迟时间的方法

• 交替编号

  • 具体做法：让编号相邻的扇区在物理上不相邻。
  • 原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区。

• 错位命名

  • 具体做法：让相邻盘面的扇区编号“错位”。
  • 原理：与“交替编号”的原理相同。“错位命名法”可降低延迟时间。

• 磁盘地址结构的设计

  • 为什么要用（柱面号，盘面号，扇区号）的结构。不用（盘面号，柱面号，扇区号）的结构。
  • 原因：在读取地址连续的磁盘块时，前者更不需要移动磁头。

13.磁盘的管理

• 磁盘的初始化

  • 低级格式化/物理格式化：划分扇区。
  • 磁盘分区（C盘、D盘、E盘）。
  • 逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空间管理的数据结构）。

• 引导块

  • 计算机启动时需要运行初始化程序（自举程序）来完成初始化。
  • ROM中存放很小的自举装入程序。
  • 完整的自举程序存放在初始块（引导块）中。

• 坏块的管理

  • 简单的磁盘：逻辑格式化时将坏块标记出来。
  • 复杂的磁盘：磁盘控制器维护一个坏块链，并管理设备用扇区。