OS–学习笔记：磁盘与文件系统
六、磁盘与文件系统
1.磁盘的结构和基本概念
- 磁道：磁盘上的同心圆
- 盘面：磁盘的某一面
- 扇区（盘块）：磁道划分为扇区，每个扇区固定大小
- 柱面：所有盘面上相对位置相同的磁道组成柱面
- 磁头
- 磁头臂
- 磁盘地址组成：柱面号・盘面号・扇区号
磁盘设备包括多或一个个物理盘片，每个磁盘片分为一个或两个储存面。每个磁盘被组织成若干个同心环，称为磁道。每个磁道从逻辑上划分为多个扇区（通常为512B），一个扇区称为一个盘块（数据块），各个扇区之间保留一定的间隙。磁盘地址：柱面号-盘面号-扇区号磁盘访问时间包括三部分：寻道时间，旋转延迟时间，传输时间。
1.2存取时间：
- 寻找时间
T
s
Ts
Ts ：磁头移动到指定磁道的时间（下式中，m是和磁盘驱动器速度相关的常数，移动跨越n条磁道，s为磁臂启动时间）
T
s
=
m
×
n
+
s
Ts=m×n+s
Ts=m×n+s
- 延迟时间
T
r
Tr
Tr ：磁头定位到某一磁道的扇区所需要的时间（下式中r为磁盘转速）
T
r
=
1
2
r
Tr=frac{1}{2r}
Tr=2r1
- 传输时间
T
t
Tt
Tt ：磁盘读出或写入数据经历的时间（下式中b为每次读 / 写的字节数，N为一个磁道上的字节数）
T
t
=
b
r
N
Tt=frac{b}{rN}
Tt=rNb
- 总平均存取时间为：
2.磁盘的调度★★★★★
| 算法名称 | 调度标准 | 优点 | 缺点 |
|---|---|---|---|
| 先来先服务（FCFS） | 先来先服务 | 公平、简单 | 平均寻道距离大 |
| 最短寻找时间优先（SSTF） | 选择距离当前磁头位置最短的请求 | 性能比 FCFS 好 | 不能保证平均寻道时间最短，可能出现 “饥饿” |
| 扫描算法（SCAN，电梯调度） | 选择当前磁头运动方向上且距离当前磁头位置最短的请求 | 寻道性能好，可避免 “饥饿” | 不利于远离磁头一端的请求 |
| 循环扫描算法（C-SCAN） | 类似 SCAN 算法，但是当一个方向上处理完成后回返时，直接移动到起始端，不响应途中的任何请求。到达起始端后，才继续响应 | 消除了对两端磁道请求的不公平性 | -------- |
3.磁盘的性能改善和容错
提高磁盘IO速度：采用磁盘高速缓存，利用内存中的存储空间来暂存从磁盘读出一系列盘块中的信息。
数据交付方式有数据交付和指针交付。
置换算法：。。。。不少系统在设计其高速缓存的置换算法时，除了考虑最近最久未使用，还考
虑以下几点：1）访问频率；2）可预见性；3）数据一致性
提高IO速度的其他方法：1）提前读；2）延迟写；3）优化物理块分布；4）虚拟盘
容错技术：廉价磁盘冗余阵列 RAID（除了0级以外）。 RAID的优点： 1）可靠性高；2）磁盘IO速度高；3）性价比高；
4.外存分配方法与物理文件组织
4.2连续分配
-
每个文件在磁盘上占有一组连续的块
要求为每个文件分配一组相邻的盘块。一组盘块的地址定义了定义了磁盘上一段线性地址。这样形成的文件结构是顺序文件结构，此时的物理文件称为顺序文件。
优点：顺序访问容易、顺序访问速度快。缺点：要求有连续的存储空间、必须事先知道文件长度。
4.3链接分配
- 每个文件散落在磁盘的各个碎片区域，每一块都存有指向下一块的指针
通过每个盘快上的链接指针，将同属于一个文件的离散盘块链接成一个链表，这样形成的物理文件称为链接文件。
**优点：**消除了外部碎片，显著提高了外存利用率；当文件动态增长时，可动态的在为他分配盘块，故无需实现知道文件大小；此外，对文件的增删改也很方便。
有两种方式：
- 隐式链接
在文件目录的每个目录项中，都需要含有指向链接文件的第一个盘块和最后一个盘块，每个盘块中含有指向下一个盘块的指针
问题： 只适合于顺序访问，对于随机访问及其低效，其次只通过一大批指针把离散的盘块链接起来，可靠性差，只要任何一个盘块的指针出现问题，都将会导致整条链断裂。为了提高检索速度和减少指针所占用的存储空间，可以将几个盘块组成一个簇，在盘块分配时，以簇为单位。这样会成倍的减少超找指定块的时间。
- 显式链接
把用于链接文件各个物理块的指针，显式的存放在内存的一张链接表中。该表在整个磁盘仅设置一张。由于查找记录是在内存中进行的，不仅显著的提高了检索的速度，而且大大减少了访问磁盘的次数，该表也成为文件分配表（FAT）
[显示链接表]
4.4索引分配
-
单独使用一块来存储文件各块存储位置，构成索引块
缺点：
1）不支持高效的直接存取2）FAT占用较大的内存空间。索引分配（文件的物理组织结构是 索引式文件机构）为每个文件分配一个索引块（表）
优点：
支持直接访问，当要读第i个盘块时，可以直接从索引块中找到第i个盘块的盘块号。此外，索引分配不会产生外部碎片。文件较大时，索引优于链接。索引分配的主要问题：可能会花费较多的外存空间。
- 多级索引
- 混合索引
5.文件存储空间的管理
储存空间的基本分配单位是磁盘块而非字节。管理包括对空闲块的组织，分配和回收。
5.2空闲表法
属于连续分配方式，系统为外存上所有的空闲区建立一张空闲表。
类似于内存分配中的动态分配
文件较小时，采取空闲表法。
5.3空闲链表法
-
空闲盘块链：
以盘块为单位拉成一条链，优缺点：用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次；
-
空闲盘区链：将磁盘上所有的空闲盘区拉成一条链。分配盘区的算法通常采用首次适应算法，回收时也要考
虑合并，为提高对空闲盘区的检索速度，可以采用显示连接法，为内存中的空闲盘区建立一张链表。
5.4位示图★
-
用二进制的一位来表示某一盘块的使用情况： 1 表示已分配， 0 表示未分配（空闲）
-
盘块的分配算法（行列号从1开始）
- 找到合适的 “0” 的二进制位
- 计算盘块号 b ：$b=(i−1)n+j $（其中 i 代表行数，j 代表列数，n 代表每行位数）
- 修改位示图矩阵：
m
a
p
[
i
,
j
]
=
1
map[i,j]=1
map[i,j]=1
-
盘块的回收算法
- 块号 b 转换为行 i 列 j 号 i
=
(
b
−
1
)
D
I
V
n
+
1
,
j
=
(
b
−
1
)
M
O
D
n
+
1
=(b−1) DIV n+1,j=(b−1) MOD n+1
=(b−1)DIVn+1,j=(b−1)MODn+1 - 修改位示图矩阵：
m
a
p
[
i
,
j
]
=
0
map[i,j]=0
map[i,j]=0
- 块号 b 转换为行 i 列 j 号 i
5.5 成组链接法
空闲表法和空闲链表法不适合大型文件，会使链表和空闲表太长。将上述两种方法结合在一起，兼备了优点，而克服了表太长的缺点。
**大致思想：**把顺序的n个空闲扇区的地址保存在第一个空闲扇区内，其后一个空闲扇区则保存另一个顺序空闲扇区的地址，在直至所有空闲扇区均已连接。系统只需要保存一个指向第一个空闲扇区的指针。
6.逻辑文件组织
6.2无结构文件(流式文件)
- 以字节为单位，如源代码文件等
6.3有结构文件(记录型文件)
- 由一条条记录组成，每条记录中包含若干数据项。
6.3.1顺序文件
- 按某种顺序排列形成的文件
- 排列方式分为串结构和顺序结构
- 串结构：通常按存入时间先后顺序排序
- 顺序结构：用户指定关键字，按关键字排序
- 优点：只有顺序文件能储存在磁带上，当每次要读或写一大批文件时，顺序文件的存储效率
最高。 - 缺点：顺序文件对于查找、修改、增加、删除等操作比较困难。
6.3.2索引文件
对于定长记录可以方便的实现顺序存取，但对于变长记录难以实现直接存取。可以为变长文件记录建立一张索引表（本身是一个定长记录的顺序文件）。
- 建立索引表，为每个记录设置一个表项，从而加快检索记录的速度
- 可按关键字建立索引，一个索引文件可能被多个索引表索引（如图书信息可按图书编号、图书名、作者等进行索引查找）
6.3.3顺序索引文件
将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为魅族第一条记录建立一个索引项，其中含有该记录的关键字值，和指向该记录的指针。
- 为每个文件建立索引表，将记录分组，只为每组的第一条记录建立索引表项
- 可以有一级、二级、多级索引顺序文件
- 查找效率比较（假设文件所含有的记录数为 N，为检索到指定含有关键字的记录）
- 顺序文件：平均需要查找
N
2
frac{N}{2}
2N - 索引顺序文件：平均需要查找
N
sqrt{N}
N
- 顺序文件：平均需要查找
6.3.4直接文件(散列文件)
记录值本身就决定了自己的物理地址，
- 通过哈希函数，完成从关键字到物理地址的直接转换。
7.文件的基本操作
7.2基本操作
- 创建
- 删除
- 读
- 写
- 设置读 / 写位置
7.2.1打开&关闭(★★★★)
- 打开：系统将指名文件的属性（包括该文件在外存上的物理位置），从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引号）返回给用户，即建立了用户和指定文件之间的连接。
- 关闭：断开上述连接(即删除条目)
- “打开” 并非真正打开，而是读取文件相关属性；“关闭” 并非真正关闭，而是断开连接。
8.文件目录及其管理
8.2目录管理的要求
- 实现 “按名存取”
- 提高目录检索速度
- 文件共享
- 允许文件重名
8.3文件控制快(FCB)
- 作用类似进程管理中的 PCB ，用来存放控制文件需要的各种信息，包括：
- 基本信息：文件名、物理位置、逻辑结构、物理结构等
- 存取控制信息：存取权限
- 使用信息：创建时间、修改时间
- 从而实现了 “按名存取”
- FCB 的有序集合成为文件目录，一个 FCB 就是一个文件目录表项
- 创建新文件时，也会创建一个对应的 FCB
8.4索引结点
- 为加快按文件名检索目录文件而引入。（无索引时，需依次检索 FCB，但是 FCB 中很多信息对于检索目录是多余的，因此把需要的信息抽出，形成索引【通常包括 文件名 、索引结点编号 】，从而可以加快检索速度）
- 根据索引结点所处位置不同，分为
- 磁盘索引结点
- 内存索引结点
8.5目录结构
在文件目录中，每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。
8.5.1单极目录结构
只建立一张目录表，每个文件占有一个目录项。访问时，先按文件名在该目录中找到对应的FCB。
- 评价
- 简单，实现了 “按名存取”
- 查找速度慢
- 不允许重名
- 不便于共享
- 只适用于单用户
8.5.2两级目录结构
顶级目录表类似二维数组，第一维为用户名、第二维存储指向用户目录表的指针
- 二级目录表存储对应用户的目录表项
- 评价
- 能满足目录管理的四个要求
8.5.3多级(树形)目录结构
-
对二级的推广，现代 OS 常用
-
包括以下
目录操作
- 创建目录
- 删除目录
- 改变目录
- 移动目录
- 链接操作
- 查找
- 优点：可以很方便的对文件进行分类，层次结构清晰，能有效的进行文件的管理和保护。但是在树形文件中，查找一个文件时，需要按路径名逐级访问，增加了磁盘访问次数，影响查询速度。
8.6目录检索法
8.6.1线性检索法
- 单级目录情况
- 类似顺序查找算法流程
- 树形目录情况
- 读入第一个文件分量（文件分量即文件路径中被 “/” 分隔的字符串），在第一级目录表中，顺序查找，找到匹配，得到下一级目录表的块号
- 读入下一个文件分量，在对应级目录表中，顺序查找，找到匹配，得到下一级目录表的块号
- 以此类推，直至目录中所有文件分量都已处理完毕或者是未找到退出
8.6.2Hash 方法
- 利用 Hash 函数完成从文件名到索引值的映射，之后再用得到的索引值找到目录
9.文件共享和保护
9.2文件共享
9.2.1基于有向无环图
9.2.2利用索引结点（硬链接)★★★
- 在用户目录表中，其表项只包括文件名和指向索引结点的指针，其他的相关信息放在索引结点中
9.2.3不同用户对共享文件创建、删除操作中的链接计数
9.2.4利用符号链接（软链接）★★★
- 共享时，会新建一个 LINK 文件，这个 LINK 文件中只含有被链接文件的路径
硬链接查找较快
9.3 文件保护
- 有口令保护、加密保护、访问控制等方法
- 访问控制
- 类型
- 读
- 写
- 执行
- 添加
- 删除
- 列表清单
- 根据用户身份进行控制，为文件和目录添加一个访问控制表，规定每个用户名及其所允许访问的类型
- 类型
参考
七、操作系统接口
1.操作系统接口类型
1）用户接口2）程序接口，是程序能取得操作系统服务的唯一途径，大多数程序接口由一组系统调用组成。
2.系统调用概念
一方面由于系统提供保护机制，防止程序至直接调用操作系统得过程，从而避免不安全性，另一方面，应用程序必须取得操作系统提供的服务。为此，操作系统提供系统调用，使应用程序通过提供系统调用的方法，间接调用操作系统的相关过程。
3.系统调用的类型和实现方法
类型：进程控制类系统调用、文件操纵类系统调用、进程通信类系统调用。