6．磁盘与文件系统

磁盘的结构和基本概念

磁道：磁盘上的同心圆
盘面：磁盘的某一面
扇区（盘块）：磁道划分为扇区，每个扇区固定大小
柱面：所有盘面上相对位置相同的磁道组成柱面
磁头
磁头臂
磁盘地址组成：柱面号·盘面号·扇区号

（其他基本概念详见教材）

磁盘的调度（★★★★★）

存取时间的计算

寻找时间 $T_s$ ：磁头移动到指定磁道的时间（下式中，m 是和磁盘驱动器速度相关的常数，移动跨越 n 条磁道，s 为磁臂启动时间）

\[ T_s=m\times n + s \]

延迟时间 $T_r$ ：磁头定位到某一磁道的扇区所需要的时间（下式中 r 为磁盘转速）

\[ T_r=\frac{1}{2r} \]

传输时间 $T_t$ ：磁盘读出或写入数据经历的时间（下式中 b 为每次读/写的字节数， N 为一个磁道上的字节数）

\[ T_{t}=\frac{b}{rN} \]

总平均存取时间为

\[ T_a=T_s+\frac{1}{2r}+\frac{b}{rN} \]

调度算法（★★★★★）

算法名称	调度标准	优点	缺点
先来先服务（FCFS）	先来先服务	公平、简单	平均寻道距离大
最短寻找时间优先（SSTF）	选择距离当前磁头位置最短的请求	性能比FCFS好	不能保证平均寻道时间最短，可能出现“饥饿”
扫描算法（SCAN，电梯调度）	选择当前磁头运动方向上且距离当前磁头位置最短的请求	寻道性能好，可避免“饥饿”	不利于远离磁头一端的请求
循环扫描算法（C-SCAN）	类似 SCAN 算法，但是当一个方向上处理完成后回返时，直接移动到起始端，不响应途中的任何请求。到达起始端后，才继续响应	消除了对两端磁道请求的不公平性	--------

磁盘的性能改善和容错

（见教材 8.4 8.5节）

外存分配方法与物理文件组织

连续分配

每个文件在磁盘上占有一组连续的块

链接分配

每个文件散落在磁盘的各个碎片区域，每一块都存有指向下一块的指针

索引分配

单独使用一块来存储文件各块存储位置，构成索引块

文件存储空间的管理

空闲表法

类似内存中的动态分配（回看内存管理）

空闲链表法

空闲盘块链
空闲盘区链

位示图法（★）

用二进制的一位来表示某一盘块的使用情况： 1 表示已分配， 0 表示未分配（空闲）
盘块的分配算法（行列号从 1 开始）
1. 找到合适的 “0” 的二进制位
2. 计算盘块号 b ：$b = (i-1)n+j$ （其中 i 代表行数，j 代表列数，n 代表每行位数）
3. 修改位示图矩阵：$map[i,j] = 1$
盘块的回收算法
1. 块号 b 转换为行 i 列 j 号$i = (b-1)\ DIV\ n + 1,j=(b-1)\ MOD\ n + 1$
2. 修改位示图矩阵：$map[i,j] = 0$

成组链接法

（详见教材）

逻辑文件组织

无结构文件（流式文件）

以字节为单位，如源代码文件等

有结构文件（记录式文件）

由一条条记录组成，每条记录中包含若干数据项。

顺序文件

按某种顺序排列形成的文件
排列方式分为串结构和顺序结构
- 串结构：通常按存入时间先后顺序排序
- 顺序结构：用户指定关键字，按关键字排序

索引文件

建立索引表，为每个记录设置一个表项，从而加快检索记录的速度
可按关键字建立索引，一个索引文件可能被多个索引表索引（如图书信息可按图书编号、图书名、作者等进行索引查找）

索引顺序文件

为每个文件建立索引表，将记录分组，只为每组的第一条记录建立索引表项
可以有一级、二级、多级索引顺序文件
查找效率比较（假设文件所含有的记录数为 N ，为检索到指定含有关键字的记录）
- 顺序文件：平均需要查找 $\frac{N}{2}$
- 索引顺序文件：平均需要查找 $\sqrt{N}$

直接文件（散列文件）

通过哈希函数，完成从关键字到物理地址的直接转换。

文件的基本操作

基本操作

创建
删除
读
写
设置读/写位置

“打开”和“”关闭“”（★★★★）

打开：系统将指名文件的属性（包括该文件在外存上的物理位置），从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引号）返回给用户，即建立了用户和指定文件之间的连接。
关闭：断开上述连接
“打开”并非真正打开，而是读取文件相关属性；“关闭”并非真正关闭，而是断开连接。

文件目录及其管理

目录管理的要求
- 实现“按名存取”
- 提高目录检索速度
- 文件共享
- 允许文件重名

文件控制块（FCB）

作用类似进程管理中的 PCB ，用来存放控制文件需要的各种信息，包括：
- 基本信息：文件名、物理位置、逻辑结构、物理结构等
- 存取控制信息：存取权限
- 使用信息：创建时间、修改时间
从而实现了“按名存取”
FCB 的有序集合成为文件目录，一个 FCB 就是一个文件目录表项
创建新文件时，也会创建一个对应的 FCB

索引结点

为加快按文件名检索目录文件而引入。（无索引时，需依次检索 FCB，但是 FCB 中很多信息对于检索目录是多余的，因此把需要的信息抽出，形成索引【通常包括 文件名 、索引结点编号 】，从而可以加快检索速度）
根据索引结点所处位置不同，分为
- 磁盘索引结点
- 内存索引结点

目录结构

单级目录结构

目录表类似一维数组，存储目录表项
评价
- 简单，实现了“按名存取”
- 查找速度慢
- 不允许重名
- 不便于共享
- 只适用于单用户

两级目录结构

顶级目录表类似二维数组，第一维为用户名、第二维存储指向用户目录表的指针
二级目录表存储对应用户的目录表项
评价
- 能满足目录管理的四个要求

树形（多级）目录结构（★★★）

对二级的推广，现代 OS 常用
包括以下目录操作
- 创建目录
- 删除目录
- 改变目录
- 移动目录
- 链接操作
- 查找

目录查询技术

线性检索法（★★★）

单级目录情况
- 类似顺序查找算法流程
树形目录情况
- 读入第一个文件分量（文件分量即文件路径中被 “/” 分隔的字符串），在第一级目录表中，顺序查找，找到匹配，得到下一级目录表的块号
- 读入下一个文件分量，在对应级目录表中，顺序查找，找到匹配，得到下一级目录表的块号
- 以此类推，直至目录中所有文件分量都已处理完毕或者是未找到退出

Hash 方法

利用 Hash 函数完成从文件名到索引值的映射，之后再用得到的索引值找到目录

文件共享和保护

文件共享

基于有向无循环图

（详见教材）

利用索引结点（硬链接）（★★★）

在用户目录表中，其表项只包括文件名和指向索引结点的指针，其他的相关信息放在索引结点中

不同用户对共享文件创建、删除操作中的链接计数

利用符号链接（软链接）（★★★）

共享时，会新建一个 LINK 文件，这个 LINK 文件中只含有被链接文件的路径

硬链接查找较快

文件保护

有口令保护、加密保护、访问控制等方法
访问控制
- 类型
  - 读
  - 写
  - 执行
  - 添加
  - 删除
  - 列表清单
- 根据用户身份进行控制，为文件和目录添加一个访问控制表，规定每个用户名及其所允许访问的类型

解题技巧及重要结论

软链接、硬链接中的引用计数问题
- 建立
  - 软链接（符号链接）：引用计数直接复制
  - 硬链接：引用计数加一
- 删除
  - 软链接：删除操作，对软链接不可见（注意软链接只保存了文件的路径）。当之后依据软链接访问文件，发现不存在时，此时可以删除符号链接
  - 硬链接：删除文件，引用计数减一；若引用计数不为零，则不能删除所共享的文件
- 例题（2009·408统考）
  - F1 引用计数为 1 ，建立符号链接（软链接）F2 ，再建立硬链接 F3 ，删除 F1 ，则此时 F2 、F3 引用计数为
  - 解答：建立 F2 ，由于是软链接，引用计数直接复制，为 1 ；再建立 F3 ，F1 和 F3 的引用计数都加一，为 2；删除 F1，不影响 F2 但影响 F3 ，故 F2 仍为 1 ，F3 要减掉一为 1
混合索引中的计算
- 相关概念
  - 文件索引结点：存储索引地址。索引地址类型又分为
    - 直接地址：此地址直接指向磁盘数据块。
      - 所以$磁盘数据块的块数 = 文件索引结点中含有直接地址项的项数$
    - 一级间接地址索引：顶级索引节点（在这里便是文件索引结点）存放索引，通过这个索引找第二张表，才能找到指向磁盘数据块的地址
      - 因此$磁盘数据块的块数 = 磁盘索引块地址项的项数=\frac{磁盘索引块大小}{地址项大小}$
    - 二级间接地址索引：顶级索引节点存放一级索引，通过这个索引找第二张表；找到二级索引，通过这个索引查第三张表才能找到指向磁盘数据块的地址
      - 故$磁盘数据块的块数 = 磁盘索引块地址项的项数^2=(\frac{磁盘索引块大小}{地址项大小})^2$
    - n 级间接地址索引，以此类推有$磁盘数据块的块数 = 磁盘索引块地址项的项数^n=(\frac{磁盘索引块大小}{地址项大小})^n$
- 典型例题
  - （2010·408）文件索引结点 7 个地址项，其中 4 个直接地址、2个一级间接地址索引、 1 个 2 级间接地址索引，每个地址项大小为 4 B，磁盘索引块和磁盘数据块大小均为 256 B，则可表示的单个文件最大长度是
    - 分析：
      - 4 个直接地址：4 × 256 B
      - 2 个一级间接：2 × (256/4) × 256 B
      - 1 个二级间接：1 × (256/4) × (256/4) × 256 B
      - 总计：上述三项之和
  - 文件系统二级索引分配，磁盘块大小 1KB，每个盘块号占 4B，单个文件最大长度为
    - 分析：
      - 依题意知，共有 1KB / 4B = 256 个索引项
      - 由于是二级索引，故最大文件长度为 256 × 256 × 1KB = 64 MB
    - 总结
      - （公式补充）
        
        $索引项个数 =\frac{磁盘块大小}{盘块号大小}$
        
        $文件长度= 索引项个数^{索引级数}\times 磁盘块大小$
  - 文件系统中， FCB 占 64 B，一个盘块大小为 1 KB，一级目录，设文件目录中有 3200 个目录项，则查找一个文件平均需要访问几次磁盘
    - 分析
      - 依题意知，共有 3200 × 64 B / 1 KB = 200 个盘块
      - 一级目录，平均访问磁盘为 200 / 2 = 100 次
    - 总结：
      - （公式补充）
        
        $目录项盘块数 = \frac{目录项项数\times FCB大小}$
        
        一级目录：$平均访问磁盘次数=\frac{目录项盘块数}{2}$（类似文件的顺序查找）
  - （2015·408）文件索引结点中，10 个直接、1个一级、1个二级，磁盘块大小 1 KB，索引指针大小 4 B 。若文件索引结点已经读入内存，则把该文件偏移量（按字节编址）为 1234 和 307400 处所在的磁盘块读入内存，需访问的盘块数分别是
    - 分析
      - 10 个直接地址：10 × 1 KB = 10 KB
      - 1 个一级间接：1 × ( 1 KB / 4 B ) × 1 KB = 256 KB
      - 1 个二级间接：1 × ( 1 KB / 4 B ) × ( 1 KB / 4 B ) × 1 KB = 64 KB
      - 1234 B < 10 KB，地址可以直接得到，只需再访问 1 次磁盘，获取该地址的数据即可
      - 10 KB + 256 KB < 1234 B < 64 MB，可知该文件内容在二级索引指针所指向的某个磁盘块中。访问 2 次磁盘，获得地址；再依此地址访问 1 次磁盘，获得数据。共需要 3 次
    - 总结
      - 磁盘访问次数 = 索引级数（为了找到地址。P.S.直接地址当作 0 级）+ 1（为了找到数据：依地址，取数据）
  - 设有一记录文件，采用链接分配方式，逻辑记录的固定长度为 100 B，在磁盘上存储时采用记录成组分解技术，盘块长度为 512 B。若该文件的目录项已经读入内存，则对 22 个逻辑记录完成修改后，共启动磁盘多少次
    - 分析
      - 第 22 条记录的地址为 22 × 100 B = 2200 B
      - 2200 B / 512 B = 4 还有剩余，故在第 5 个盘快上。
      - 链接分配，要找到第五个盘块的地址，需要从第一个开始，依次寻找，需要 5 次此盘启动，才能拿到第 22 个逻辑记录的物理地址。之后依据这个物理地址，访存修改，还需要启动 1 次磁盘。所以共需 6 次
位示图相关
- （2015·408）文件系统中用位示图，位图位于 32 ~ 127 号块中，每个盘块占 1024 B，盘块和块内字节均从 0 号开始编号。假设要释放盘块号为 409612 ，则位图中要修改的位所在的盘块号和块内字节序号分别是
  - 分析：
    - $盘块号=起始块号+\lfloor\frac{盘块号}{盘块大小\times 8}\rfloor$
    - $块内字节号 =盘块号 mod (盘块大小)/8$
    - 数据带入公式，即可

参考资料

计算机操作系统.汤小丹等
2020年操作系统考研复习指导.王道论坛