---
title: 操作系统复习笔记
author: 萑澈
pubDatetime: 2026-01-12T00:00:00Z
featured: false
draft: false
printable: true
tags:
- 操作系统
- cs408
description: 操作系统复习笔记，涵盖进程管理（状态转换、PCB、线程）、处理机调度算法（FCFS、SJF、优先级、HRRN）、死锁（必要条件、银行家算法、资源分配图）、进程同步与互斥（信号量机制、PV 操作、生产者消费者、哲学家进餐）、存储器管理（连续分配、分页、分段、地址变换）、虚拟存储器（页面置换算法 OPT/FIFO/LRU）、磁盘调度算法（FCFS、SSTF、SCAN、C-SCAN）等核心知识点
---
# 操作系统复习笔记
---
# 第一部分：重点题型与解法
## 银行家算法
### 题目 1
#### 1. 基础数据准备
##### A. 计算 Need 矩阵 ($Need = Max - Allocation$)
- **P0:** $(4, 3, 7) - (3, 2, 1) = (1, 1, 6)$
- **P1:** $(3, 4, 4) - (2, 3, 1) = (1, 1, 3)$
- **P2:** $(5, 6, 3) - (1, 4, 3) = (4, 2, 0)$
- **P3:** $(7, 3, 4) - (4, 2, 2) = (3, 1, 2)$
- **P4:** $(6, 4, 3) - (3, 2, 1) = (3, 2, 2)$
##### B. 计算 Available 向量 ($Available = Total - \sum Allocation$)
1. **已分配总量：**
- $R1 = 3 + 2 + 1 + 4 + \mathbf{3} = 13$
- $R2 = 2 + 3 + 4 + 2 + \mathbf{2} = 13$
- $R3 = 1 + 1 + 3 + 2 + \mathbf{1} = 8$
2. **当前可用 (Available)：**
- $R1: 14 - 13 = \mathbf{1}$
- $R2: 15 - 13 = \mathbf{2}$
- $R3: 12 - 8 = \mathbf{4}$
- 即 **Available = (1, 2, 4)**
#### 2. 安全性检查（回答第 2 问）
我们要尝试找到一个安全序列。此时 **Available = (1, 2, 4)**。
|**步骤**|**进程**|**Work (可用)**|**Need (需求)**|**Allocation (已分配)**|**Work + Allocation**|**Finish**|
|---|---|---|---|---|---|---|
|1|**P1**|(1, 2, 4)|(1, 1, 3)|(2, 3, 1)|(3, 5, 5)|True|
|2|**P2**|(3, 5, 5)|(4, 2, 0)|(1, 4, 3)|资源不足，跳过|False|
|3|**P4**|(3, 5, 5)|(3, 2, 2)|(3, 2, 1)|(6, 7, 6)|True|
|4|**P2**|(6, 7, 6)|(4, 2, 0)|(1, 4, 3)|(7, 11, 9)|True|
|5|**P3**|(7, 11, 9)|(3, 1, 2)|(4, 2, 2)|(11, 13, 11)|True|
|6|**P0**|(11, 13, 11)|(1, 1, 6)|(3, 2, 1)|(14, 15, 12)|True|
结论：
存在安全序列（如 P1 -> P4 -> P2 -> P3 -> P0，序列不唯一）。
因此，系统处于安全状态。
#### 3. 资源请求分配（回答第 3 问）
**问题：** 若 P4 请求资源 $Request_4 = (1, 2, 0)$，且此时 $P4$ 的分配变为 $(4, 4, 1)$。
根据算法，当 P4 已经变为 $(4, 4, 1)$ 时，我们需要先判断这个状态是否合法，再看请求：
1. **检查请求是否超过需求：**
- 此时 $Need_4$（基于第二步计算）是 $(3, 2, 2)$。
- $Request_4 = (1, 2, 0) \le (3, 2, 2)$，**满足条件**。
2. **检查系统可用资源是否足够：**
- 此时由于 P4 已经是 $(4, 4, 1)$，我们需重新计算当前的 $Available$。
- $\sum Allocation = (3+2+1+4+\mathbf{4}, 2+3+4+2+\mathbf{4}, 1+1+3+2+\mathbf{1}) = (14, 15, 8)$
- $Available = (14-14, 15-15, 12-8) = \mathbf{(0, 0, 4)}$
3. **判定：**
- $Request_4 = (1, 2, 0)$
- $Available = (0, 0, 4)$
- 由于 $1 > 0$ 且 $2 > 0$，即 **$Request_4 \not\le Available$**。
结论：
不能实施资源分配。 因为系统当前剩余资源（特别是 R1 和 R2）不足以满足 P4 的请求，P4 必须等待。
## PV 操作
- P：申请
- V：释放
- semaphore：资源数
### 题目 1：吃水果
#### 题目描述：
桌子上有一个能盛下 10 个水果的空盘子。爸爸不停地向盘中放苹果和橘子，儿子不停地从盘中取出橘子吃，女儿不停地从盘中取出苹果吃。规定 3 人不能同时向（从）盘子中放（取）水果。试用信号量机制实现爸爸、儿子和女儿 3 个进程之间的同步。请将信号量值和伪代码补充完整。
#### 标准解法与分析
要解决这个问题，我们需要设置两类信号量：
1. **互斥信号量**：用于保证同一时刻只有一个进程访问盘子（临界资源）。
2. **同步信号量**：用于协调进程间的执行顺序（盘子空位、橘子数量、苹果数量）。
##### 1. 信号量定义
- `empty`：盘子里的空位数，初值为 **10**。
- `orange`：盘中橘子的数量，初值为 **0**。
- `apple`：盘中苹果的数量，初值为 **0**。
- `mutex`：互斥锁，保证对盘子的互斥访问，初值为 **1**。
##### 2. 伪代码补充（填空答案）
根据图片中的编号，完整填空如下：
- **(1) 信号量初值：** `empty = 10, orange = 0, apple = 0, mutex = 1`
- **(3)：** `V(mutex)`（放入水果后释放锁）
- **(4)：** `V(orange)`（如果是橘子，增加橘子计数）
- **(5)：** `V(apple)`（如果是苹果，增加苹果计数）
- **(6)：** `P(orange)`（儿子等待橘子）
- **(7)：** `P(mutex)`（儿子申请进入临界区）
- **(8)：** `V(mutex)`（儿子取完后释放锁）
- **(9)：** `V(empty)`（儿子吃完后，盘子空位加 1）
- **(10)：** `P(apple)`（女儿等待苹果）
- **(11)：** `P(mutex)`（女儿申请进入临界区）
- **(12)：** `V(mutex)`（女儿取完后释放锁）
- **(13)：** `V(empty)`（女儿吃完后，盘子空位加 1）
#### 完整逻辑代码展示
```
semaphore empty = 10; // 盘子剩余空间
semaphore orange = 0; // 橘子数量
semaphore apple = 0; // 苹果数量
semaphore mutex = 1; // 互斥访问盘子
Dad() {
while(1) {
prepare fruit;
P(empty); // 等待盘子有空位
P(mutex); // 锁定盘子
put fruit in plate;
V(mutex); // 释放盘子
if (fruit == orange)
V(orange); // 提醒儿子来吃橘子
else
V(apple); // 提醒女儿来吃苹果
}
}
Son() {
while(1) {
P(orange); // 等待橘子
P(mutex); // 锁定盘子
take orange;
V(mutex); // 释放盘子
V(empty); // 释放一个盘子空位
eat orange;
}
}
Daughter() {
while(1) {
P(apple); // 等待苹果
P(mutex); // 锁定盘子
take apple;
V(mutex); // 释放盘子
V(empty); // 释放一个盘子空位
eat apple;
}
}
```
> **重点提示：** 在进程同步中，**P(empty/orange/apple)** 必须在 **P(mutex)** 之前，否则可能会导致死锁（例如：爸爸拿到了互斥锁但盘子满了，他会阻塞，而儿女因为拿不到互斥锁无法取水果释放空间）。
### 题目 2：哲学家进餐
#### 题目描述
有 n(n>=3)名哲学家围坐在一张圆桌边，每名哲学家交替地就餐和思考。在圆桌中心有 m(m>=1)个碗，每两名哲学家之间有一根筷子。每名哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考，为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量 PV 操作描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
#### 1. 信号量定义及初值含义
为了解决此问题，我们需要设置以下信号量：
| **信号量** | **初值** | **含义** |
| ------------------ | ---------------- | ---------------------------------------------------- |
| **`bowl`** | $m$ | 资源信号量：表示圆桌中心可用碗的数量。 |
| **`chopstick[n]`** | `[1, 1, ..., 1]` | 互斥信号量数组：`chopstick[i]` 表示第 $i$ 根筷子是否可用。 |
| **`max_diners`** | $min(n-1, m)$ | 同步信号量：为了防止死锁，限制同时尝试去拿筷子的哲学家人数。必须小于总人数 $n$ 以打破循环等待条件。 |
#### 2. 算法设计思路
- **防止死锁**：如果所有哲学家同时拿起左手的筷子，就会发生死锁。通过 `max_diners` 信号量，限制最多只有 $n-1$ 个人同时进行“拿筷子”的操作，保证至少有一人能凑齐两根筷子。
- **碗的限制**：碗是共享资源，通过 `P(bowl)` 保证哲学家必须先拿到碗。
- **互斥访问**：每一根筷子同一时间只能被一人使用。
#### 3. PV 操作描述
设哲学家编号为 $i$（$0$ 到 $n-1$），其左侧筷子编号为 $i$，右侧筷子编号为 $(i+1) \bmod n$。
```
// 哲学家 i 的进程逻辑
Philosopher_i() {
while(true) {
think(); // 思考
P(max_diners); // 限制同时进餐的人数，防止死锁
P(bowl); // 取一个碗
// 拿起两侧筷子的顺序可以根据策略调整，此处采用限制人数法
P(chopstick[i]); // 拿起左侧筷子
P(chopstick[(i + 1) % n]); // 拿起右侧筷子
eat(); // 就餐
V(chopstick[i]); // 放下左侧筷子
V(chopstick[(i + 1) % n]); // 放下右侧筷子
V(bowl); // 将碗放回原位
V(max_diners); // 释放进餐名额
}
}
```
#### 4. 关键点说明
1. **为什么 `max_diners` 是 $min(n-1, m)$？**
- 为了防止死锁，同时去拿筷子的人数不能超过 $n-1$。
- 由于碗只有 $m$ 个，同时能吃饭的人数也不能超过 $m$。
- 结合两者，限制人数为这两者的最小值，既能保证资源最大化利用，又能绝对避免死锁。
2. **资源获取顺序**：在 P 操作中，先申请碗还是先申请筷子？通常建议先申请最稀缺或最容易导致死锁的资源。在本解法中，通过 `max_diners` 门限位，已经从逻辑上隔离了环路等待的风险。
### 题目 3 2022 统考真题
#### 题目描述
某进程有 A、B、C、D、E 和 F 共 6 个操作，分别由两个线程并发执行，其中 T1 执行 A、E 和 F，T2 执行 B、C 和 D。下图表示上述 6 个操作的执行顺序所必须满足的约束：C 在 A 和 B 完成后执行、D 和 E 在 C 完成后执行、F 在 E 完成后执行。请使用信号量机制描述 T1 和 T2 之间的同步关系，并说明所用信号量的作用及其初值。
这道题目考查的是操作系统中**进程（线程）同步**的经典问题。我们需要使用信号量（Semaphore）的 $P$、$V$ 操作来确保操作 A 到 F 按照给定的前驱图顺序执行。
#### 1. 信号量定义及初值
为了实现同步，我们需要为前驱图中每一条跨越线程的“箭头”设置信号量。在这个问题中，线程 T1 负责 {A, E, F}，线程 T2 负责 {B, C, D}。
跨线程的依赖关系如下：
1. **A → C**: C 需要等待 A 完成。设置信号量 $S_{ac}$，初值为 0。
2. **C → E**: E 需要等待 C 完成。设置信号量 $S_{ce}$，初值为 0。
> **注意**：同一线程内部的顺序（如 B→C, C→D, E→F）可以通过代码的先后顺序自然实现，不需要额外信号量。但在严格的标准解答中，通常为所有依赖关系设置信号量以保证逻辑严密。
|**信号量**|**含义**|**初值**|
|---|---|---|
|$S_{ac}$|表示 A 操作是否完成，用于 T1 通知 T2|0|
|$S_{bc}$|表示 B 操作是否完成（T2 内部同步，可选）|0|
|$S_{ce}$|表示 C 操作是否完成，用于 T2 通知 T1|0|
|$S_{cd}$|表示 C 操作是否完成（T2 内部同步，可选）|0|
|$S_{ef}$|表示 E 操作是否完成（T1 内部同步，可选）|0|
#### 2. 线程执行描述（伪代码）
##### 线程 T1 (执行 A, E, F)
```
T1() {
// 1. 执行 A
执行 A 操作;
V(Sac); // 信号 A 已完成，通知 C
// 2. 执行 E
P(Sce); // 等待 C 完成
执行 E 操作;
// 3. 执行 F
// (由于 E、F 在同线程且顺序执行，此处不需要额外的 P/V)
执行 F 操作;
}
```
##### 线程 T2 (执行 B, C, D)
```
T2() {
// 1. 执行 B
执行 B 操作;
// 2. 执行 C
P(Sac); // 等待 A 完成 (B 已在本线程前面完成)
执行 C 操作;
V(Sce); // 信号 C 已完成，通知 E
// 3. 执行 D
// (由于 C、D 在同线程且顺序执行，直接执行)
执行 D 操作;
}
```
#### 3. 核心逻辑总结
- **同步点 1 (C 的启动)**：C 的执行依赖于 A 和 B。由于 B 和 C 都在 T2 中，顺序执行即可保证 B 先于 C；但 A 在 T1 中，所以 C 必须通过 `P(Sac)` 等待 T1 发出的 `V(Sac)`。
- **同步点 2 (E 的启动)**：E 的执行依赖于 C。由于 E 在 T1，C 在 T2，E 必须通过 `P(Sce)` 等待 T2 发出的 `V(Sce)`。
- **内部顺序**：E 完后执行 F，C 完后执行 D，这两对关系在各自线程内通过语句的先后顺序自动满足。
### 题目 4 2020 年统考题
【一句话讲清楚 pv 操作，操作系统有救啦！】 https://www.bilibili.com/video/BV1fuUQYBEHL/ （讲的很通透）
## 内存分配与管理
- **动态分区分配算法：**
- **FF (First Fit):** 首次适应（找第一个能放下的）。
- **NF (Next Fit):** 循环首次适应（从上次结束位置找）。
- **BF (Best Fit):** 最佳适应（找最小能满足的，易产生外部碎片）。
- **WF (Worst Fit):** 最坏适应（找最大的空闲区）。
- **地址变换 (逻辑地址 -> 物理地址)：**
- **分页系统：** 给定逻辑地址和页面大小，计算页号 \$P\$ 和页内偏移 \$d\$，查页表找物理块号 \$f\$，物理地址 = \$f \times \text{块大小} + d\$。
- **分段系统：** 查段表，检查段内越界。
- **快表 (TLB)：** 理解 TLB 命中与未命中的时间差异。
### 逻辑地址 VS 物理地址
**逻辑地址**：是指程序在运行过程中使用的地址，也称为虚拟地址（VirtualAddress）。它是由 CPU 生成的，用于访问内存中的数据。逻辑地址的大小和位数取决于处理器的架构和操作系统的设计，通常是一个定长的二进制数值。在执行指令时，CPU 通过将逻辑地址转化为物理地址来获取数据。
**物理地址**：是指内存中实际的地址，也称为实地址（RealAddress）。物理地址表示内存模块中每个存储单元（通常是字节）的唯一标识符，因此具有唯一性，且直接与内存相关联。物理地址通常是一个以十六进制表示的数字，它确定了计算机中的实际内存位置。
### 地址转换
## 页面置换算法
1. **最佳置换算法（OPT）（看将来）**：置换那些不再使用或者长时内不再使用的页。
2. **先进先出置换算法（FIFO）**：置换先进入内存的页（淘汰在内存驻留时间最久的页
3. **最近最久未使用置换算法（LRU）**（从过去预测将来）置换过去最近，最长时间未使用的页
**缺页次数**：物理块空缺，发生置换
### 题目 1
【页面置换算法：先进先出置换算法，最佳置换算法，最近最久未使用置换算法#操作系统#期末周】 https://www.bilibili.com/video/BV1S43teEEfL/
## 磁盘与文件系统
磁盘调度算法，算法思想：
1. **先来先服务算法**：根据进程的请求顺序进行先后调度（就是题目中给的顺序）
2. **最短寻道时间优先算法**：选择最近的磁道进行访问。
3. **扫描算法（电梯算法 SCAN，先向外）**：既要考虑磁道与磁头的距离又要考虑方向。
4. **循环扫描算法**
解题步骤：
1. 明确算法思想
2. 根据算法思想写出访问顺序
3. 根据访问顺序计算移动距离
---
# 第二部分：系统知识梳理
---
## 第一章 引论
### 操作系统的主要功能
1. **处理机管理**
2. **存储器管理**
3. **设备管理**
4. **文件管理**
5. **接口管理**
### 操作系统的特征
1. **并发**：两个或多个事件在同一时间间隔内发生。
2. **共享**：系统中的资源可供内存中多个并发执行的进程共同使用。
3. **虚拟**：把一个物理上的实体变为若干个逻辑上的对应物。
4. **异步**：在多道程序环境下，运行走走停停，以不可知的速度向前推进。
* 操作系统在计算机系统中处于**计算机硬件和用户之间**的位置。
### 操作系统的基本类型
有实时操作系统、批处理操作系统及分时操作系统。
1. **实时操作系统**：优先处理紧急事务，实时性、可靠性。
2. **批处理操作系统**：多道批处理并发执行，提高资源利用率。
3. **分时操作系统**：允许用户直接与计算机进行交互。
---
## 第二章 进程的描述与控制
* **进程**：动态的，程序的一次执行过程。
* **进程的组成**：
* **PCB** (进程控制块)
* 进程标识符 PID
* 用户标识符 UID
* 控制信息
* **程序段**：程序的代码。
* **数据段**：运行时产生的数据。
* **进程的特征**：动态性、并发性、独立性、异步性、结构性。
### 进程的状态转换
graph LR
Create(创建态) --> Ready(就绪态)
Ready --> Running(运行态)
Running --> Terminate(终止态)
Running -->|时间片到, CPU 被优先级高的抢占| Ready
Running -->|等待系统资源分配, 等待事件发生| Blocked(阻塞态)
Blocked -->|事件发生| Ready
### 进程通信的 3 种方式
**共享存储器机制**：
```
[ ]
[进程P]
[共享区]
[进程Q]
[ ]
```
**消息传递机制**：
```
[消息头] --> 发送进程ID/接收进程ID
[消息体]
```
**管道通信**：
```
进程P --> [管道] --> 进程Q
```
### 线程
* 线程是一个基本的 **CPU 执行单元**，也是程序执行流的**最小单位**。
* 引入线程之后，进程之间可并发，进程内的各线程之间也可以并发。
* 进程是**资源分配**的基本单位，线程是**调度**的基本单位。
* 每个线程都有一个线程 ID，线程控制块 (TCB)。
* 线程也有就绪态、阻塞态、运行态三种基本状态。
**线程的实现方式：**
* **用户级线程** vs **内核级线程**
graph TD
subgraph 用户级线程
A[线程] --> B[线程库]
C[线程] --> B
D[线程] --> B
B --> E[进程]
end
subgraph 内核级线程
F[用户线程] --> G[内核线程]
H[用户线程] --> I[内核线程]
J[用户线程] --> K[内核线程]
G --> L[进程]
I --> L
K --> L
end
---
## 第三章 处理机调度与死锁
### 进程调度方式
1. **非抢占方式**：进程一直运行完，才执行下一个进程。
2. **抢占式**：有更重要的进程需要处理机时，将处理机分配给重要的进程。
### 调度算法的指标
* **周转时间** = 完成时间 - 到达时间
* 带权周转时间 = 周转时间 / 实际运行时间
* **等待时间** = 周转时间 - 实际运行时间
### 调度算法
#### 1. 先来先服务 (FCFS)
(非抢占)
| 进程 | 到达时间 | 运行时间 |
| --- | ---- | ---- |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
**调度顺序**：
`0 [P1] 7 [P2] 11 [P3] 12 [P4] 16`
**计算**：
* **周转时间**：
* P1 = 7-0 = 7
* P2 = 11-2 = 9
* P3 = 12-4 = 8
* P4 = 16-5 = 11
* **带权周转时间**：
* P1 = 7/7 = 1
* P2 = 9/4 = 2.25
* P3 = 8/1 = 8
* P4 = 11/4 = 2.75
* **等待时间**：
* P1 = 7-7 = 0
* P2 = 9-4 = 5
* P3 = 8-1 = 7
* P4 = 11-4 = 7
#### 2. 短作业优先 (SJF)
**2.1 非抢占式**
| 进程 | 到达时间 | 运行时间 |
| --- | ---- | ---- |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
**调度顺序**： `P1 -> P3 -> P2 -> P4`
`0 [P1] 7 [P3] 8 [P2] 12 [P4] 16`
* **周转时间**：
* P1 = 7-0 = 7
* P2 = 12-2 = 10
* P3 = 8-4 = 4
* P4 = 16-5 = 11
* **带权周转时间**：
* P1 = 1
* P2 = 10/4 = 2.5
* P3 = 4/1 = 4
* P4 = 11/4 = 2.75
* **等待时间**：
* P1 = 0
* P2 = 6
* P3 = 3
* P4 = 7
**2.2 抢占式 (SRTF - 最短剩余时间优先)**
| 进程 | 到达时间 | 运行时间 |
| --- | ---- | ---- |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
**执行过程**：
* 0 时刻: P1(7)
* 2 时刻: P1(5), P2(4) -> P2 更短，抢占
* 4 时刻: P1(5), P2(2), P3(1) -> P3 更短，抢占
* 5 时刻: P1(5), P2(2), P4(4) -> P3 运行完，P2(2)最短
* 7 时刻: P1(5), P4(4) -> P2 运行完，P4(4)最短
* 11 时刻: P1(5) -> P4 运行完，P1 运行
**调度顺序**：
`0 [P1] 2 [P2] 4 [P3] 5 [P2] 7 [P4] 11 [P1] 16`
* **周转时间**：
* P1: 16-0 = 16
* P2: 7-2 = 5
* P3: 5-4 = 1
* P4: 11-5 = 6
* **带权周转时间**：
* P1: 16/7 = 2.28
* P2: 5/4 = 1.25
* P3: 1/1 = 1
* P4: 6/4 = 1.5
* **等待时间**：
* P1: 16-7 = 9
* P2: 5-4 = 1
* P3: 0
* P4: 6-4 = 2
#### 3. 优先级调度
**3.1 非抢占式**
| 进程 | 到达时间 | 运行时间 | 优先级 |
| --- | ---- | ---- | --- |
| P1 | 0 | 7 | 1 |
| P2 | 2 | 4 | 2 |
| P3 | 4 | 1 | 3 |
| P4 | 5 | 4 | 2 |
必须先约定“数字越小优先级越高”还是“数字越大优先级越高，一般题目会给出
**情况 A：数字越小优先级越高（最常见约定）**
非抢占调度应为：
`0-7 P1, 7-11 P2, 11-15 P4, 15-16 P3`（与你时间轴一致）
对应指标应是（按这个时间轴算）：
- 周转时间：P1=7，P2=11-2=9，P4=15-5=10，P3=16-4=12
- 等待时间：P1=0，P2=9-4=5，P4=10-4=6，P3=12-1=11
- 带权周转：P1=1，P2=9/4=2.25，P4=10/4=2.5，P3=12/1=12
**情况 B：数字越大优先级越高**
则 7 时刻会先选 P3（优先级 3 最大），整体会变成
`P1 -> P3 -> P2 -> P4`，指标就会**刚好和 SJF(非抢占)那组一样**。
#### 4. 高响应比优先 (HRRN)
非抢占式，选响应比最高的进程上机。
| 进程 | 到达时间 | 运行时间 |
| --- | ---- | ---- |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
相应比 = （等待时间+需要服务时间）/ 需要服务时间 = 1 + （等待时间 / 需要服务时间）
0 时刻只有 P1 → 运行 0-7
7 时刻计算响应比（等待=7-到达）
- P2：W=5，S=4 → R=(5+4)/4=2.25
- P3：W=3，S=1 → R=(3+1)/1=4 ✅（最高，选 P3）
- P4：W=2，S=4 → R=(2+4)/4=1.5
8 时刻（P3 完）
- P2：W=6，S=4 → R=10/4=2.5 ✅（选 P2）
- P4：W=3，S=4 → R=7/4=1.75
12 时刻只剩 P4 → 运行
**调度顺序**： `P1 -> P3 -> P2 -> P4`
---
### 死锁
* **定义**：各进程互相等待对方手里的资源，导致进程被阻塞，无法向前推进的现象。
* **死锁产生的必要条件**：
1. **互斥条件**
2. **不剥夺条件**
3. **请求和保持条件**
4. **循环等待条件**
* **死锁的处理策略**：
1. **预防死锁**：破坏死锁产生四个必要条件中的一个。对资源采用按序分配策略。
2. **避免死锁**：用某种方式防止进入不安全状态。**银行家算法**。
3. **检测死锁**：允许死锁发生，检测出发生后的采取措施。**资源分配图**
* 找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。(从资源向进程的边减去，还回资源)。
* 上图未死锁，下图为死锁。
4. **解除死锁**。
### 银行家算法
**1. 数据结构**
* 可利用资源向量 `Available`
* 最大需求矩阵 `Max`
* 分配矩阵 `Allocation`
* 需求矩阵 `Need`
**2. 安全性算法**
(1) 若找到 `Finish[i] = FALSE` 且 `Need[i,j] <= Work[j]`
(2) `Work[j] = Work[j] + Allocation[i,j]`
`Finish[i] = TRUE`
(3) 所有进程满足 `Finish[i] = TRUE`，则为安全状态。
**示例**：
Available: 3 3 2
|**进程**|**Max (A B C)**|**Allocation (A B C)**|**Need (A B C)**|**Available (A B C)**|
|---|---|---|---|---|
|**P0**|7 5 3|0 1 0|7 4 3|3 3 2|
|**P1**|3 2 2|2 0 0|1 2 2||
|**P2**|9 0 2|3 0 2|6 0 0||
|**P3**|2 2 2|2 1 1|0 1 1||
|**P4**|4 3 3|0 0 2|4 3 1||
* P1: Available 5 3 2
* P1 -> P3: Available 7 4 3
* P1 -> P3 -> P4: Available 7 4 5
* P1 -> P3 -> P4 -> P0: Available 7 5 5
* P1 -> P3 -> P4 -> P0 -> P2: Available 10 5 7
(存在安全序列，系统安全)
**3. 银行家算法步骤**
(1) `Request[j] <= Need[i,j]`
(2) `Request[j] <= Available[j]`
(3) 试分配：
`Available[j] = Available[j] - Request[j]`
`Allocation[i,j] = Allocation[i,j] + Request[j]`
`Need[i,j] = Need[i,j] - Request[j]`
(4) 检查是否处于安全状态 (执行安全性算法)。
**Example**: P1 发出请求向量 Request(1, 0, 2)
(1) Request(1,0,2) <= Need(1,2,2)
(2) Request(1,0,2) <= Available(3,3,2)
(3) 更新 Available(2,3,0), Allocation(3,0,2), Need(0,2,0)
(4) 执行安全性算法 -> 处于安全状态，就一定不会发生死锁；不安全状态就可能发生死锁。
### 死锁的检测
找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。（从资源向进程的边减去，还有资源）。
上图未死锁，下图为死锁。
## 第四章 进程同步
### 进程同步与进程互斥
* **进程同步**：两个或多个进程在它们的工作次序产生制约关系。
* **进程互斥**：一个进程访问临界资源时，另一个想访问该资源的进程必须等待。
### 信号量机制
* `wait(S)` 原语：P 操作
* `signal(S)` 原语：V 操作
**记录型信号量**：
```c
/* 记录型信号量的定义 */
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} semaphore;
```
```c
void wait(semaphore S) {
S.value--;
if (S.value < 0) block(S.L);
} // 可能进入阻塞
void signal(semaphore S) {
S.value++;
if (S.value <= 0) wakeup(S.L);
} // 可能唤醒进程
```
* `S.value < 0`: 有进程等待该资源。
* `S.value > 0`: 已没有进程等待。
* `S.value` 初值为某资源的数目。
* `S.value = -2`: 有 2 个进程在等待。
### 用信号量实现进程互斥、同步
**1. 进程互斥**
(互斥信号量 `mutex`，初值为 1)
在进入区 `P(mutex)` —— 申请资源
在退出区 `V(mutex)` —— 释放资源
```c
semaphore mutex = 1;
P1() {
...
P(mutex);
代码段;
V(mutex);
...
}
```
**2. 进程同步**
(同步信号量 `S`，初值为 0)
在“前操作”之后执行 `V(S)`
在“后操作”之前执行 `P(S)`
设代码 1 在代码 4 之前执行：
```c
semaphore S = 0;
P1() { P2() {
代码1; 代码3;
代码2; P(S);
V(S); 代码4;
} }
```
### 3. 前趋关系
(图中有向无环图，S1 -> S2/S3, S2->S4/S5, S3->S6, S4->S6, S5->S6)
* 边上标注信号量 a, b, c, d, e, f, g 等。
```c
P1(){ ... S1; V(a); V(b); }
P2(){ P(a); S2; V(c); V(d); }
P3(){ P(b); S3; V(g); }
P4(){ P(c); S4; V(e); }
P5(){ P(d); S5; V(f); }
P6(){ P(e); P(f); P(g); S6; }
```
## 第五章 存储器管理
* **解决“程序大小超过物理内存总和”问题**：使用**覆盖技术**与**交换技术**。
### 连续分配存储管理方式
1. **单一连续分配**：
* 分为系统区与用户区。
* 系统区位于内存的低地址部分。
* 用户区存放用户进程的数据。
2. **固定分区分配**：
* 用户区划分为固定大小的分区，每份区只装一道作业。
3. **动态分区分配**：
- 空闲分区表
- 空闲分区链
* **动态分区分配算法**：
1. **首次适应算法**：找到第一个能满足大小的。
2. **最佳适应算法**：优先使用更小的空闲区。
3. **最坏适应算法**：优先使用更大的空闲区。
4. **邻近适应算法**：从上次查找结束位置开始查找第一个空闲分区。
### 分页存储管理
* **逻辑地址**：
| 页号 P | 页内地址 |
* **页表**：
| 页号 | 块号 |
| :---: | :---: |
| 0 | 3 |
| 1 | 6 |
| ... | ... |
**计算**：
* **页号** = 逻辑地址 / 页面长度
* **页内偏移量** = 逻辑地址 % 页面长度
* **物理地址** = 页面起始址 + 页内偏移量
**地址变换机构**：
* [逻辑地址] -> [页号|页内偏移] -> 查页表(含越界中断检查) -> 得到块号 -> 拼接 -> [物理地址]
**Eg**: 某作业的逻辑地址空间为 4 页(每页 2048 字节)。页面映像表如右图(0->2, 1->4, 2->6, 3->8)。求出逻辑地址 4865 对应的物理地址。
* 页号 = 4865 / 2048 = 2
* 页内偏移量 = 4865 % 2048 = 769
* 查表：页号 2 对应块号 6
* 物理地址 = 6 * 2048 + 769 = 13057
---
## 第六章 虚拟存储器 (图: image_695867.jpg, image_695886.jpg)
### 页面置换算法
#### 1. 最佳置换算法 (OPT)
* 淘汰页面将是以后最长时间内不再被访问的页面。
* **Eg**: 分配 3 个内存块。访问序列: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | ... |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 内存 1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | |
| 内存 2 | | 0 | 0 | 0 | 0 | 4 | 4 | 4 | |
| 内存 3 | | | 1 | 1 | 1 | 3 | 3 | 3 | |
| 是否缺页 | √ | √ | √ | √ | | √ | | √ | |
* 发生 9 次缺页，页面置换发生 6 次 (前 3 次是填满，不需置换)。
* 缺页率 = 9/20 = 45%
#### 2. 先进先出置换算法 (FIFO) (图: image_695886.jpg)
* 每次选择淘汰页面是最早进入内存的页面。
* **Eg**: 同样序列，分配 3 个块。
(表格显示置换过程)
* 缺页次数：10 次 (笔记中更正后的数字，原写 12 后改为 10)。
* 缺页率：10/12 = 83.3% (注：这里分母似乎写错了或者是不同的例子长度，按照 20 次访问应该是 50%)。
#### 3. 最近最久未使用置换算法 (LRU)
* 每次淘汰的页面是最近最久未使用的页面。
* (表格显示置换过程)
* 缺页率：6/20 = 30%
---
## 第七章 输入/输出系统 (图: image_695886.jpg)
### 磁盘调度算法
#### 1. 先来先服务算法 (FCFS)
**Eg**: 假设磁头的初始位置是 100 号磁道。有多个进程先后陆续地请求访问 55, 58, 39, 18, 90, 160, 150, 38, 184 磁道。
* 路线：100 -> 55 -> 58 -> 39 -> 18 -> 90 -> 160 -> 150 -> 38 -> 184
* **磁头总移动距离**：
45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498
* **平均移动**： 498 / 9 = 55.3 千磁道
#### 2. 最短寻找时间优先 (SSTF)
初始为 100。访问 55, 58, 39, 18, 90, 160, 150, 38, 184。
* 每次找离当前最近的。
* 路线：100 -> 90 -> 58 -> 55 -> 39 -> 38 -> 18 -> 150 -> 160 -> 184
* **共移动**： (100-18) + (184-18) = 248 个磁道
* **平均移动**： 248 / 9 = 27.5 个磁道
#### 3. 扫描算法 (SCAN)
只有磁头移动到最外/内侧磁道的时候才能往内/外移动，移动到最内侧磁道的时候才能往外移动。(也叫电梯算法)
假设磁道为 0\~200。访问同上。假设当前朝磁道号增加方向移动 (向外)。
* 路线：100 -> 150 -> 160 -> 184 -> **200** (边界) -> 90 -> 58 -> 55 -> 39 -> 38 -> 18
* **共移动**： (200-100) + (200-18) = 282
* **平均**： 282 / 9 = 31.3 个磁道
#### 4. 循环扫描算法 (C-SCAN)
规定只有磁头朝某个方向移动才能处理访问请求。
假设磁道为 0\~200。访问同上。
* 路线：100 -> 150 -> 160 -> 184 -> **200** -> **0** (直接回到底部不处理) -> 18 -> 38 -> 39 -> 55 -> 58 -> 90
* **共移动**： (200-100) + (200-0) + (90-0) = 390
* **平均**： 390 / 9 = 43.3 个磁道
---
# 第三部分：详细图解
---
