操作系统进阶

1. 进程调度

1.1 调度算法

1.2 周转时间计算

$\text{周转时间}=\text{完成时间}-\text{到达时间}$

$\text{带权周转时间}=\frac{\text{周转时间}}{\text{服务时间}}$

$\text{平均周转时间}=\frac{1}{n}{\sum }_{i=1}^n{T}_i$

1.3 多级反馈队列（MLFQ）

基本规则：

1. 优先级高的队列先执行
2. 同一队列内按 RR 执行
3. 新进程进入最高优先级队列
4. 用完时间片后降级
5. I/O 阻塞返回后升级（可选）

优化：

• 定期提升所有进程优先级（避免饥饿）
• 使用不同时间片：高优先级短时间片，低优先级长时间片

1.4 实时调度

硬实时：必须在截止时间内完成。

软实时：尽量在截止时间内完成。

EDF（最早截止时间优先）：

• 动态优先级调度
• 截止时间越近优先级越高
• CPU 利用率 $\le 1$ 时可调度

RMS（速率单调调度）：

• 静态优先级调度
• 周期越短优先级越高
• 可调度条件：${\sum }_{i=1}^n\frac{C_i}{T_i}\le n(2^{1/n}-1)$

2. 死锁

2.1 死锁必要条件

1. 互斥：资源不能共享
2. 持有并等待：持有资源同时等待其他资源
3. 不可抢占：已获得的资源不能被强制剥夺
4. 循环等待：存在进程的循环等待链

2.2 死锁预防

破坏必要条件：

2.3 死锁避免

银行家算法：

$\text{安全状态}⟺\exists \text{安全序列}$

安全序列判断：

1. Work = Available, Finish[i] = false
2. 找到 Finish[i]=false 且 Need[i] ≤ Work 的进程
3. Work = Work + Allocation[i], Finish[i] = true
4. 重复2-3直到所有 Finish[i] = true

资源分配图算法：每类资源只有一个实例时，检测图中是否存在环。

2.4 死锁检测

定期运行检测算法，发现死锁后：

• 终止进程
• 资源抢占回滚

3. 内存管理

3.1 分区分配

3.2 伙伴系统

内存按 $2^k$ 大小分配：

• 请求大小 $n$，分配 $2^{\lceil {\log }_{2}n\rceil }$ 的块
• 块可以分裂为两个大小相等的伙伴
• 伙伴可以合并为更大的块

$\text{内部碎片}\le \text{分配大小}/2$

3.3 页面置换算法

OPT（最优）：置换未来最久不被访问的页。

FIFO：置换最早进入的页。存在 Belady 异常（更多物理页导致更多缺页）。

LRU：置换最近最久未访问的页。无 Belady 异常。

Clock：LRU 的近似，使用引用位和循环指针。

LFU：置换访问频率最低的页。

栈算法性质：LRU 和 OPT 是栈算法，$M\subset M^{\prime }$（更多物理页的内存包含更少的子集）。

3.4 抖动

当分配的物理页数小于工作集时，频繁缺页：

$\text{缺页率}\uparrow ⟹\text{有效访问时间}\uparrow ⟹\text{CPU 利用率}\downarrow$

$\text{有效访问时间}=(1-p)\times t_{mem}+p\times t_{fault}$

4. 文件系统

4.1 文件分配方式

4.2 索引节点

Unix inode 结构：

┌──────────────────┐
│ 直接块指针 × 12   │  ← 小文件
│ 一级间接块指针     │  ← 中等文件
│ 二级间接块指针     │  ← 大文件
│ 三级间接块指针     │  ← 超大文件
└──────────────────┘

最大文件大小计算（4KB 块，4B 指针）：

• 直接：$12\times 4\text{KB}=48\text{KB}$
• 一级间接：$1024\times 4\text{KB}=4\text{MB}$
• 二级间接：$1024^2\times 4\text{KB}=4\text{GB}$
• 三级间接：$1024^3\times 4\text{KB}=4\text{TB}$

4.3 空闲空间管理

4.4 日志结构文件系统（LFS）

• 所有写入追加到日志末尾
• 段（Segment）为单位写入
• 后台清理线程合并段

优势：写入性能高（顺序写），崩溃恢复快。

劣势：读取可能需要间接寻址，清理开销。

4.5 写时复制（COW）

用于 ZFS、Btrfs 等文件系统：

1. 修改数据时，写入新位置
2. 更新指针指向新位置
3. 旧数据保留用于快照

5. I/O 子系统

5.1 I/O 软件层次

用户层 I/O 软件
    ↓
设备无关软件（缓冲、缓存、设备命名）
    ↓
设备驱动程序
    ↓
中断处理程序
    ↓
硬件

5.2 缓冲技术

单缓冲：

$T=\max (T_{input},T_{process})+T_{copy}$

双缓冲：

$T=\max (T_{input},T_{process})$

循环缓冲：多个缓冲区组成环形队列。

5.3 磁盘调度

寻道时间是磁盘访问的主要开销。

5.4 磁盘性能计算

$\text{访问时间}=\text{寻道时间}+\text{旋转延迟}+\text{传输时间}$

$\text{平均旋转延迟}=\frac{1}{2\times \text{RPM}}\times 60$

7200 RPM 磁盘的平均旋转延迟：

$\frac{1}{2\times 7200}\times 60=4.17\text{ms}$