操作系统
操作系统概论
操作系统的主要特征
并发性 (Concurrency)
🔍 核心定义
并发性是指两个或两个以上的事件或活动在同一时间间隔内发生。
- 关键点:“同一时间间隔” ≠ “同一时刻”。它强调的是“看起来同时”,而不是“真正同时”。
📌 操作系统中的体现
- 多个 I/O 设备同时工作:
- 你的键盘在输入,打印机在打印,网卡在收发数据。这些设备都在“同时”工作。
- I/O 和 CPU 计算同时进行:
- 当 CPU 在计算时,I/O 设备可能在后台传输数据。CPU 不需要等待 I/O 完成,可以去处理其他任务。
- 内存中多个程序交替执行:
- 这是最核心的体现。操作系统通过时间片轮转(Time-Slicing)等调度算法,让多个程序“轮流”使用 CPU,从而实现“宏观上的并发”。
🖼️ 并发 vs 并行
这是你 PPT 中提出的关键问题!
| 特性 | 并发 (Concurrency) | 并行 (Parallelism) |
|---|---|---|
| 定义 | 多个任务在同一时间间隔内交替执行。 | 多个任务在同一时刻真正同时执行。 |
| 物理基础 | 单 CPU 系统即可实现。 | 需要多核 CPU 或多处理器系统。 |
| 效果 | “看起来”同时进行。 | “真正”同时进行。 |
| 类比 | 一个人在厨房里,一会儿切菜,一会儿炒菜,一会儿洗碗。 | 三个人在厨房里,一个人切菜,一个人炒菜,一个人洗碗。 |
✅ 一句话总结:并行是并发的一种特例。并发是“逻辑上的同时”,并行是“物理上的同时”。
共享性 (Sharing)
🔍 核心定义
共享性指操作系统中的资源(包括硬件资源和软件资源)可被多个并发执行的进程共同使用,而不是被一个进程所独占。
- 关键点:共享不等于“无限制访问”,它必须在操作系统管理下进行,以保证安全和有序。
📌 资源共享的方式
1️⃣ 透明资源共享 / 同时共享方式
- 含义:允许多个进程在同一时间段内对资源进行访问,好像每个进程都独占资源一样。
- 特点:
- 访问的次序对结果无影响。
- 通常用于可重入或只读的资源。
- 例子:
- CPU:通过时间片轮转,让多个进程“同时”使用 CPU。
- 主存 (RAM):多个进程的代码和数据可以同时存在于内存中。
- 磁盘:多个进程可以同时读取磁盘上的不同文件。
- 打印机:虽然物理上一次只能打印一个任务,但操作系统可以通过“打印队列”实现逻辑上的“同时共享”。
2️⃣ 独占资源共享 / 互斥共享方式
- 含义:在同一时间段内只允许一个进程访问资源。
- 特点:
- 这类资源称为临界资源 (Critical Resource)。
- 必须通过互斥机制(如锁、信号量)来保护。
- 例子:
- 磁带机:一次只能由一个进程控制。
- 扫描仪:一次只能扫描一份文档。
- 数据库中的某一行记录:如果两个事务同时修改同一行,会导致数据不一致。
🛠️ 操作系统如何管理共享?
- 提供显式资源共享机制:如
fork(),semaphore,mutex,lock等系统调用。 - 将互斥访问下放给用户决策:程序员需要自己负责加锁和解锁,操作系统提供工具。
异步性 (Asynchrony)
🔍 核心定义
异步性指在多道程序环境中,由于资源有限而进程众多,多数情况下,进程的执行不是一气呵成,而是“走走停停”。
- 关键点:进程的执行是不可预测的,它的推进速度取决于系统调度、I/O 等待、中断等多种因素。
📌 异步性的表现
- 作业到达系统的时间和类型不确定:
- 用户随时可能启动一个新程序。
- 操作员发出命令或操作的时间和类型不确定:
- 用户可能随时按下键盘或点击鼠标。
- 程序运行发生错误或异常的类型和时刻不确定:
- 程序可能因为除零、内存溢出等原因崩溃。
- 中断事件发生的时刻不确定:
- 时钟中断、I/O 中断、硬件故障中断等都是随机发生的。
1 | graph TD |
多道程序设计
核心思想
多道程序设计是指允许多个程序同时驻留在内存中,并由操作系统统一管理和调度,使它们交替(并发)地使用 CPU 和其他系统资源。
- 核心目的:掩盖 I/O 等待时间,提高 CPU 和系统资源的利用率。
- 终极目标:让昂贵的 CPU 永远不要闲着!
1 | gantt |
对比:在多道程序中,当作业 A 在等待 I/O 时,CPU 立刻去执行作业 B 和 C。CPU 几乎没有空闲时间,利用率接近 100%!
cpu利用率
CPU利用率 = 1 - p^n
🔍 假设条件
- 系统中有
n个程序 同时在内存中。 - 每个程序平均有
p的概率在等待 I/O 操作。- 例如,
p = 0.8表示一个程序有 80% 的时间在等磁盘读写、键盘输入等,只有 20% 的时间在真正使用 CPU。
- 例如,
- 各个程序的等待操作是相互独立的。
- 这是一个关键假设,意味着一个程序是否在等 I/O,不影响其他程序。
💡 公式推导
- CPU 空闲的概率:当且仅当所有
n个程序都在等待 I/O 时,CPU 才会空闲。 - 因为每个程序等待 I/O 的概率是
p,且它们相互独立,所以所有n个程序都等待 I/O 的概率是p^n。 - 因此,CPU 空闲的概率 =
p^n。 - CPU 利用率 = 1 - CPU 空闲的概率 =
1 - p^n。
若进程平均花费 80% 的时间等待 I/O,则为了使得 CPU 利用率不低于 80%,应至少有多少道程序在主存中运行?
计算过程
根据公式:
CPU利用率 = 1 - p^n ≥ 0.8
移项得:
p^n ≤ 0.2
代入 p = 0.8:
0.8^n ≤ 0.2
两边取对数(以 10 为底或自然对数均可):
n * log(0.8) ≤ log(0.2)
注意:log(0.8)
是负数,所以在除的时候要反转不等号方向:
n ≥ log(0.2) / log(0.8)
计算数值:
log(0.2) ≈ -0.69897log(0.8) ≈ -0.09691n ≥ (-0.69897) / (-0.09691) ≈ 7.21
因为 n 必须是整数,且要满足
n ≥ 7.21,所以:
n = 8
✅ 最终答案
为了使得 CPU 利用率不低于 80%,应至少有 8 道程序在主存中运行。
是不是同时运行的程序越多越好?
不是!同时运行的程序(道数)并不是越多越好。存在一个最优的“道数”,超过这个值,系统的整体效率反而会下降。
当道数 n
超过某个临界值后,系统性能会急剧下降。主要原因有:
1️⃣ 上下文切换开销 (Context Switching Overhead)
什么是上下文切换?
- 当操作系统从一个进程切换到另一个进程时,它需要保存当前进程的状态(寄存器、内存映射、程序计数器等),并加载下一个进程的状态。
2️⃣ 内存压力 (Memory Pressure)
- 每个进程都需要内存:代码段、数据段、堆、栈、页表等。
3️⃣ 资源竞争加剧 (Resource Contention)
- 锁竞争:多个进程同时访问共享资源(如数据库连接池、文件锁),需要排队等待,增加了延迟。
- 缓存失效:多个进程的指令和数据交替进入 CPU 缓存,导致缓存命中率降低,CPU 需要更频繁地从内存读取数据。
处理器状态
为什么需要两种处理器状态?
现代计算机是一个多用户、多任务的环境。如果所有程序都能随意执行任何指令,那么一个不小心的 bug 或一个恶意程序就可能:
- 格式化硬盘。
- 修改系统时间。
- 访问其他用户的隐私数据。
- 导致系统崩溃。
为了避免这种情况,CPU 被设计成有两种工作模式:
- 用户态 (User Mode):普通程序运行的状态,只能执行“安全”的指令。
- 核心态 (Kernel Mode / Supervisor Mode):操作系统内核运行的状态,可以执行所有指令,包括“危险”的特权指令。
程序状态字 (PSW)
Program Status Word (PSW) 是一个非常重要的寄存器。
- 定义:PSW 是 CPU 内部的一个特殊寄存器,用于存储当前处理器的各种状态信息。
- 关键作用:PSW
中有一个标志位(通常是最高位或某一位),用来标识当前
CPU 处于用户态还是核心态。
PSW[bit] = 0→ 用户态PSW[bit] = 1→ 核心态
✅ 这就是 CPU 判断当前是否可以执行特权指令的依据!
当 CPU 执行一条指令时,它会检查 PSW 中的这个标志位:
- 如果是用户态,并且指令是特权指令,则触发一个异常 (Exception),操作系统会介入处理(通常是终止该程序)。
- 如果是核心态,则允许执行。
CPU 如何判断当前是否可以执行特权指令?
答案:CPU 通过检查 程序状态字 (PSW) 中的一个特定标志位来判断。
- 如果该标志位表示当前处于用户态,并且遇到的是特权指令,则 CPU 会触发一个异常(通常是“非法指令”或“特权指令违规”),并将控制权交给操作系统内核。
- 操作系统内核会根据情况决定是终止该程序,还是进行其他处理。
进程控制和管理
进程定义与属性
进程(Process)是程序在计算机上的一次执行实例,是操作系统进行资源分配、调度和保护的基本单位。
为什么要引入“进程”?
1️⃣ 刻画系统的动态性(Dynamic Nature)
- 问题:程序是静态的代码,无法描述“执行中”的状态。
- 解决方案:进程是一个动态实体,它有生命周期(创建 → 运行 → 阻塞 → 终止)。
- 意义:操作系统可以精确跟踪每个任务的当前状态,做出调度决策。
2️⃣ 发挥系统的并发性(Concurrency)
- 问题:CPU 和 I/O 设备速度不匹配。程序在等待 I/O(如读文件、网络请求)时,CPU 就空闲了。
- 解决方案:通过进程切换,让 CPU 在等待期间去执行其他任务。
- 意义:提高了 CPU 利用率和系统吞吐量。
3️⃣ 解决资源共享与隔离的矛盾
- 问题:多个程序可能需要共享资源(如文件、打印机),但又不能互相干扰。
- 解决方案:
- 共享性:进程可以通过合法机制(如共享内存、消息队列)共享资源。
- 独立性/保护性:每个进程拥有独立的地址空间,操作系统通过内存管理单元(MMU)确保 A 进程不能访问 B 进程的内存。
- 意义:既实现了协作,又保证了安全和稳定。
进程的五大核心属性
| 属性 | 含义 | 举例说明 |
|---|---|---|
| 1. 动态性 | 进程是动态的,有生命周期(创建 → 运行 → 阻塞 → 终止)。 | uvicorn 启动时创建进程,Ctrl+C
终止时销毁进程。 |
| 2. 并发性 | 多个进程可以“同时”运行(宏观并发,微观交替)。 | 一台服务器同时处理成百上千个用户的 HTTP 请求。 |
| 3. 独立性 | 每个进程有独立的地址空间和资源,互不干扰。 | 一个 Python 进程崩溃,不会导致另一个 Python 进程退出。 |
| 4. 制约性 | 进程间可能存在同步或互斥关系(如竞争资源、等待结果)。 | 多个进程写同一个日志文件,需要用文件锁避免内容错乱。 |
| 5. 共享性 | 进程可以通过操作系统提供的机制共享资源(如内存、文件)。 | 多个 FastAPI worker 进程共享一个 Redis 缓存连接池。 |
进程状态转换
五态模型
七态模型
七态模型在五态模型的基础上,显式增加了“挂起(Suspend)”的概念
挂起 = 进程被换出到外存(Swap)
- 目的:当系统内存紧张时,操作系统会将一些暂时不活跃的进程(比如长时间阻塞的进程)从内存移到硬盘上的“交换区(Swap Space)”,以腾出内存给更紧急的任务。
挂起就绪态 (Ready/Suspend)
定义:
进程具备运行条件(即它已经准备好执行),但目前在外存中。只有当它被换入内存后,才能被调度器选中运行。
挂起等待态 (Blocked/Suspend)
定义:
进程正在等待某一个事件发生(如 I/O 完成、用户输入、网络响应),并且目前在外存中。
进程描述和组成
进程映像
进程映像(Process Image)是指进程在内存中的完整内容,包括代码、数据、堆、栈以及内核数据结构(如 PCB)等所有组成部分的集合。
进程上下文
寄存器上下文 (Register Context)存储在 PCB 中 包含:通用寄存器、程序计数器、栈指针、程序状态字
这是进程“灵魂”的一部分——CPU 执行时最直接依赖的状态。
PCB(Process Control Block,进程控制块)
PCB 是操作系统为每个进程创建的一个数据结构,用来记录和刻画该进程的所有状态和相关信息。
1️⃣ 进程标识信息 (Identification Information)
| 字段 | 说明 |
|---|---|
| PID (Process ID) | 进程的唯一数字标识,如 12345。 |
| PPID (Parent PID) | 父进程的 PID,用于构建进程树。 |
| UID/GID (User/Group ID) | 进程所属用户的 ID 和组 ID,用于权限控制。 |
🌰 你的例子:
这些值就是从 PCB 中读取的!
1
2
3 import os
print(f"当前进程 PID: {os.getpid()}")
print(f"父进程 PID: {os.getppid()}")
2️⃣ 处理器状态信息 (Processor State Information) —— 这就是“寄存器上下文”
这是 PCB 最关键的部分,用于上下文切换。
| 字段 | 说明 |
|---|---|
| 程序计数器 (PC) | 下一条要执行的指令地址。 |
| 通用寄存器 (AX, BX, CX…) | 存放临时计算结果、变量地址等。 |
| 程序状态字 (PSW) | 包含标志位(零标志 Z、进位标志 C、溢出标志 O 等)、中断允许位、特权级别。 |
| 栈指针 (SP) | 指向当前函数调用栈的顶部。 |
⚡ 关键点:每次进程切换时,操作系统都会将当前 CPU 寄存器的值“倾倒”进 PCB,再从新进程的 PCB “倒回”寄存器。这就是“上下文切换”的核心开销。
3️⃣ 进程调度信息 (Scheduling Information)
| 字段 | 说明 |
|---|---|
| 进程状态 | 就绪、运行、阻塞、挂起等。 |
| 进程优先级 | 决定调度顺序。 |
| 时间片剩余量 | 用于时间片轮转调度。 |
| 等待事件 | 如等待键盘输入、网络数据包到达等。 |
🌰 你的例子: 在 FastAPI 中,当一个请求在
await httpx.get(...)时,其对应协程/线程的状态会被标记为“阻塞”,并被放入等待队列。这就是 PCB 中“进程状态”字段的作用。
4️⃣ 内存管理信息 (Memory Management Information)
| 字段 | 说明 |
|---|---|
| 页表基址 / 段表指针 | 用于虚拟内存到物理内存的地址转换。 |
| 内存分配情况 | 代码段、数据段、堆、栈的起始地址和大小。 |
💡 关键点:确保进程访问的是自己的内存空间,实现“内存保护”。
5️⃣ I/O 状态信息 (I/O Status Information)
| 字段 | 说明 |
|---|---|
| 打开的文件列表 | 文件描述符(fd)、文件指针、访问模式等。 |
| 分配的 I/O 设备 | 如打印机、网卡等。 |
🌰 你的例子: 当你在 Python 中
f = open("log.txt", "a")时,操作系统会在 PCB 的“打开文件列表”中添加一条记录,记录这个文件句柄f对应的 fd。
6️⃣ 记账信息 (Accounting Information)
| 字段 | 说明 |
|---|---|
| CPU 使用时间 | 进程已使用的 CPU 时间总和。 |
| 累计运行时间 | 从创建到现在的总时间。 |
| 最大内存使用量 | 历史峰值。 |
📊 用途:用于性能监控、计费、调试等。
进程队列
链接方式
索引方式
进程切换和处理器状态转换
模式切换 vs. 进程切换
- 模式切换 (Mode Switch)
定义:CPU 在“用户态(User Mode)”和“核心态(Kernel Mode)”之间的切换。 触发方式:由中断(Interrupt)或系统调用(System Call) 引起。 目的:让操作系统获得控制权,执行特权指令(如访问硬件、修改内存映射)。
- 进程切换 (Process Switch / Context Switch)
定义:操作系统暂停当前正在运行的进程,保存其状态,并加载另一个进程的状态,使其开始运行。 触发方式:通常发生在核心态下,由中断或系统调用引发。 目的:实现多任务并发,公平分配 CPU 时间。
当进程开始运行时,操作系统如何重新获得控制?
果进程一直在运行,操作系统就永远没机会调度其他进程了,系统就会卡死。
答案:中断 (Interrupt) 是关键!
- 什么是中断?
中断就像一个“紧急电话”,它能打断 CPU
当前正在执行的程序,强制 CPU
去处理一个更高优先级的事情——通常是操作系统内核。
- 硬件中断:由外部设备触发,比如键盘敲击、鼠标移动、网络数据包到达、定时器到期。
- 软件中断/异常:由程序自身触发,比如除零错误、访问非法内存地址、或者程序主动发起的系统调用(如
open(),read())。
进程需要保存哪些状态?
当操作系统获得控制权后,它必须把当前正在运行的进程(比如进程0)的“工作状态”完整地记录下来,以便将来能恢复执行。这个过程叫做“保存现场 (Save Context)”。
需要保存哪些状态?
这些状态主要存储在一个叫做 PCB (Process Control Block, 进程控制块) 的数据结构里。PCB 就像是进程的“身份证 + 工作日志 + 资源清单”。
如何选择下一个待执行的进程/线程?
当操作系统保存完当前进程的状态后,它需要决定“接下来该让谁干活”。这个决策过程叫做“进程调度 (Process Scheduling)”。
如何选择?
这取决于操作系统的调度算法 (Scheduling Algorithm)。
线程
为什么需要线程?—— 引入线程的动机
❓ 问题:进程模型有什么不足?
- 切换开销大:进程切换需要保存/恢复整个内存空间(代码、数据、堆、栈)和 PCB,开销大。
- 通信困难:进程间通信(IPC)需要管道、消息队列、共享内存等复杂机制,效率低。
- 不适合细粒度并发:比如一个 Web 服务器,每个请求都创建一个进程,成本太高。
✅ 解决方案:引入线程!
线程是进程内的一个执行单元,是 CPU 调度和分派的基本单位。
- 同一个进程内的所有线程:
- 共享:代码段、数据段、堆、打开的文件等进程资源。
- 私有:各自的栈和寄存器上下文。
💡 核心价值:实现进程内部的并发,降低切换和通信开销。
什么是线程?—— 核心定义
线程(Thread)是进程中一个可并发执行的控制流,它拥有自己独立的栈和寄存器状态,但与其他线程共享进程的地址空间和资源。
线程如何工作?—— 线程的生命周期与切换
- 线程的生命周期状态
和进程类似,线程也有状态:新建 → 就绪 → 运行 → 阻塞 → 终止。
- 线程切换(Thread Switching)
- 开销远小于进程切换!因为不需要切换地址空间(页表),只需要保存/恢复寄存器上下文和栈指针。
- 切换由线程调度器(在 OS 内核或用户态库中)管理。
- 线程的实现方式
| 类型 | 说明 | 例子 |
|---|---|---|
| 用户级线程 (User-Level Threads) | 由用户态线程库(如 Java Green Threads)管理,内核 unaware | Python 的 greenlet(非标准) |
| 内核级线程 (Kernel-Level Threads) | 由操作系统内核直接管理,每个线程对应一个内核调度实体 | Python 的 threading 模块 |
| 混合模式 | 用户级线程映射到少量内核线程 | Go 的 Goroutine |
💡 Python 的
threading是内核级线程,但受 GIL 限制,无法真正并行执行 Python 字节码。
处理器调度
调度层次
1️⃣ 高级调度(High-Level Scheduling)—— 作业调度 / 长程调度
目标:决定哪些“作业”被允许进入系统参与 CPU 竞争。 对象:作业(Job)→ 通常是一个完整的程序或任务(如编译一个文件、运行一个脚本)。 发生频率:低(几分钟到几小时一次)。 执行者:操作系统内核。
🔍 核心功能:
- 选作业进内存:从后备队列中选择作业,将其加载到内存,创建进程。
- 控制多道程序的道数:决定同时在内存中运行多少个作业(即并发度)。太多会耗尽内存,太少会浪费 CPU。
2️⃣ 中级调度(Medium-Level Scheduling)—— 平衡调度 / 内存调度
目标:根据内存状态,决定哪些进程可以在内存中运行,哪些需要换出到外存。 对象:进程(Process)。 发生频率:中等(几秒到几分钟一次)。 执行者:操作系统内核。
🔍 核心功能:
- 选进程进出内存:当内存紧张时,将一些不活跃的进程(如长时间阻塞的进程)换出到 Swap 分区;当内存空闲时,再换回。
- 平衡系统负载:防止内存溢出,提高系统吞吐量。
3️⃣ 低级调度(Low-Level Scheduling)—— 进程调度 / CPU 调度
目标:决定哪个就绪队列中的进程/线程获得 CPU 执行权。 对象:进程或线程(内核级线程)。 发生频率:高(毫秒级,每几十到几百毫秒一次)。 执行者:操作系统内核 → 这是操作系统最核心的部分!
🔍 核心功能:
- 选进程分配 CPU:从就绪队列中选出下一个要运行的进程/线程。
- 执行上下文切换:保存当前进程上下文,恢复新进程上下文。
- 实现公平与效率:通过调度算法(如 RR、优先级、MLFQ)保证所有进程都能得到 CPU 时间。
1 | graph LR |
调度算法评价指标
七种调度策略
先来先服务 (First Come First Serverd, FCFS)
短作业优先 (Shortest Job First, SJF)
最短剩余时间优先 (Shortest Remaining Time First, SRTF)
最高响应比优先 (Highest Response Ratio First, HRRF)
优先级调度 (Priority Scheduling)
轮转调度 (Round Robin Scheduling, RR)
多级反馈队列调度 (Multi-Level Feedback Queue, MLFQ)
并发:互斥与同步
进程交互
为什么需要“进程交互”?
在单进程时代,程序是“独占”的——它不需要考虑别人。但在现代操作系统中:
- 多个进程/线程同时运行。
- 它们可能共享资源(如内存、文件、数据库连接)。
- 它们可能需要协同完成一个复杂任务(如一个 Web 请求涉及多个微服务)。
这就产生了两个根本性问题:
- 竞争(Competition):多个进程争抢同一个资源,导致结果不可预测。
- 协作(Cooperation):多个进程需要按特定顺序执行,才能完成共同目标。
✅ 进程交互就是解决这两个问题的机制。
竞争关系(进程互斥)
✅ 核心定义:
进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系。
📌 关键词解析:
- “相互争夺”:多个进程都想使用同一个资源。
- “独占型资源”:一次只能被一个进程使用的资源,如打印机、临界区代码、全局变量、数据库连接等。
- “竞争制约关系”:一个进程的执行会制约另一个进程的执行。
🧱 两个核心控制问题:
- 死锁问题(Deadlock)
- 定义:多个进程互相等待对方释放资源,导致所有进程都无法继续执行。
- 经典例子:“哲学家就餐问题”——五个哲学家围坐圆桌,每人左右各有一根筷子。他们必须拿到两根筷子才能吃饭。如果每个人都拿起左边的筷子,然后等待右边的筷子,就会陷入死锁。
- 四个必要条件:
- 互斥条件
- 请求与保持条件
- 不剥夺条件
- 环路等待条件
- 饥饿问题(Starvation)
- 定义:某个进程因为优先级低或资源分配策略不当,长时间得不到所需资源,导致无法执行。
- 例子:在一个高优先级任务永远不结束的系统中,低优先级任务可能永远得不到 CPU。
协作关系(进程同步)
✅ 核心定义:
进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动,因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。
📌 关键词解析:
- “完成共同任务”:多个进程/线程需要合作才能达成目标。
- “协调活动”:它们需要按特定顺序执行。
- “排定执行先后次序”:比如 A 必须在 B 之前执行。
- “等待、传递信号或消息”:通过同步机制(如信号量、条件变量、管道)实现通信和协调。
🧱 核心思想:
- “生产者-消费者”模型:生产者生成数据,消费者消费数据,它们必须同步。
- “读者-写者”模型:读者可以同时读,但写者必须独占。
- “屏障(Barrier)”:所有进程到达某个点后才能继续执行。
临界区管理
什么是“临界区”?
✅ 核心定义:
并发进程中,与共享变量有关的程序段叫做“临界区”(Critical Section)。
📌 关键词解析:
- “并发进程”:多个进程/线程同时运行。
- “共享变量”:多个进程都能访问和修改的变量(如全局变量、数据库连接、文件句柄)。
- “程序段”:一段代码,比如
counter += 1这样的操作。
💡 简单说:临界区 = 操作共享资源的那一小段代码。
🎯 为什么重要?
因为这段代码如果被多个进程同时执行,会导致竞态条件(Race Condition),产生不可预测的结果。
如何避免错误?—— 互斥访问临界区
如果保证进程在临界区执行时,不让另一个进程进入临界区,即各进程对共享变量的访问是互斥的,就不会造成与时间有关的错误。
这就是“进程互斥”的核心思想。
临界区调度的三个原则(经典!)
这是解决临界区问题的黄金法则,任何同步机制都必须满足这三个条件:
✅ 原则 1:一次至多一个进程能够进入临界区内执行
互斥性(Mutual Exclusion)
- 这是最基本的要求。任何时候,最多只能有一个进程在临界区内。
- 如果 A 在临界区,B 就不能进入,必须等待。
✅ 原则 2:如果已有进程在临界区,其他试图进入的进程应等待
忙则等待(Progress)
- 如果临界区空闲,想进入的进程可以立即进入。
- 如果临界区被占用,其他进程必须等待,不能“自旋”浪费 CPU(虽然有些实现会自旋,但理想情况下应该阻塞等待)。
✅ 原则 3:进入临界区内的进程应在有限时间内退出,以便让等待进程中的一个进入
有限等待(Bounded Waiting)
- 防止“饥饿”。不能让某个进程永远等下去。
- 例如,使用队列来管理等待的进程,确保每个进程最终都能获得进入临界区的机会。
实现临界区管理的软件方法一Peterson方法
1 | int turn; // turn 表示轮到谁进入 |
✅ 1. 互斥性 (Mutual Exclusion)
定义:一次至多一个进程能进入临界区。
📌 证明思路:
- 假设 P0 和 P1 同时进入临界区。
- 那么
flag[0] = true且flag[1] = true。 - 根据算法,P0 在进入前设置了
turn = 1,P1 设置了turn = 0。 - 由于
turn只能取值 0 或 1,不可能同时为 0 和 1。 - 所以,当 P0 检查
while (flag[1] && turn == 1)时,如果turn == 0,它就会阻塞。 - 同理,P1 也会被阻塞。
- 结论:不可能同时进入。
✅ 2. 空闲让进 (Progress)
定义:如果临界区空闲,且有进程想进入,则该进程应该能进入。
📌 证明思路:
- 如果 P1 不想进入临界区,则
flag[1] = false。 - 此时,无论
turn是多少,P0 的while (flag[1] && turn == 1)条件都会失败(因为flag[1]是false),所以 P0 可以立即进入临界区。
✅ 3. 有限等待 (Bounded Waiting)
定义:一个进程最多等待另一个进程执行完临界区一次,就能获得进入的机会。
📌 证明思路:
- 假设 P0 被阻塞,说明
turn = 1且flag[1] = true,即 P1 在临界区。 - 当 P1 执行完临界区后,它会设置
flag[1] = false。 - 此时,如果 P0 还想进入,它的
while条件会失败,从而进入临界区。 - 如果 P1 在
flag[1] = false后又想进入,则它会设置flag[1] = true和turn = 0。 - 此时,P0 会被阻塞,但 P1 执行完后,P0 就能进入。
- 结论:P0 最多等待 P1 执行一次临界区,就能进入。
信号量与PV操作
信号量(Semaphore)
✅ 核心定义:
信号量是一种软件资源,用于表示物理资源的实体,是一个与队列有关的整型变量。
📌 关键词解析:
- “表示物理资源”:比如打印机、数据库连接池、线程池中的可用线程数。
- “整型变量”:信号量的值代表当前可用资源的数量。
- “与队列有关”:当资源不足时,等待的进程会被放入一个等待队列。
P/V 操作:信号量的“原子操作”
✅ 定义:
P (Proberen, 尝试) 和 V (Verhogen, 增加) 是对信号量进行操作的原语。
- P 操作:尝试获取资源。如果资源可用(信号量 > 0),则减 1;否则,进程进入等待队列。
- V 操作:释放资源。增加信号量值,并唤醒一个等待的进程。
1 | // P 操作 (Wait) |
⚠️ 关键点:P/V 操作必须是原子操作(Atomic Operation),即在执行过程中不能被中断。否则会导致竞态条件。
哲学家进餐问题
哲学家进餐问题:核心描述
✅ 问题设定:
- 有 5 位哲学家 围坐在一张圆桌旁。
- 每位哲学家面前有一盘意大利面。
- 桌子上有 5 把叉子,每两位哲学家之间放一把。
- 哲学家的生活只有两件事:
- 思考(Think):什么都不做。
- 吃饭(Eat):必须同时拿到左右两边的叉子才能吃。
- 吃完后,会放下叉子,继续思考。
💡 目标:设计一个算法,让所有哲学家都能吃饱,且不会发生死锁或饥饿。
为什么会出现死锁?
📌 死锁的四个必要条件:
- 互斥条件:叉子一次只能被一个人使用。
- 请求与保持条件:哲学家拿起一把叉子后,会继续等待另一把。
- 不剥夺条件:不能强行从哲学家手中拿走叉子。
- 环路等待条件:每位哲学家都在等右边的人放下叉子,形成一个循环等待链。
解决方案:打破死锁的四个条件之一
要避免死锁,只需破坏其中一个必要条件即可。以下是几种经典的解决方案:
✅ 解决方案 1:限制同时就餐的哲学家数量(破坏“环路等待”)
最多允许 4 位哲学家同时吃面。
📌 原理:
- 如果只有 4 个人尝试拿叉子,那么至少有一把叉子是空闲的。
- 这样,总会有一个人能拿到两把叉子并吃完,从而释放资源。
1 | import threading |
✅ 解决方案 2:奇偶号哲学家取叉子顺序不同(破坏“环路等待”)
奇数号哲学家先取左边叉子,再取右边;偶数号哲学家先取右边叉子,再取左边。
📌 原理:
- 这样就不会形成环路等待。
- 例如,哲学家 0(偶数)先拿右边叉子(叉子 1),哲学家 1(奇数)先拿左边叉子(叉子 1)→ 他们争抢同一把叉子,但最终只会有一个成功,另一个等待,从而打破环路。
1 | def philosopher(i): |
✅ 解决方案 3:拿起两把叉子才开始吃(破坏“请求与保持”)
每位哲学家必须同时拿到两把叉子才能开始吃,否则一把也不拿。
1️⃣ 全局变量定义
1 |
|
s[i]初始值为 0,因为一开始没有人需要等待。state[i]初始化为THINKING。
2️⃣ take_fork(int i) 函数
1 | void take_fork(int i) { |
📌 关键点:
state[i] = HUNGRY: 告诉“管家”,我饿了。test(i): “管家”检查我是否能吃。- 如果能吃,
test(i)会执行V(s[i]),唤醒我。 - 如果不能吃,
test(i)不做任何事。
- 如果能吃,
P(s[i]): 如果我没被唤醒,我就在这里阻塞,等待邻居放叉子。
✅ 这个函数是“非阻塞”的:它只负责声明“我饿了”,然后立即返回。真正的等待发生在
P(s[i])。
3️⃣ put_fork(int i) 函数
1 | void put_fork(int i) { |
📌 关键点:
state[i] = THINKING: 我吃饱了,不再占用叉子。test((i+1)%5)和test((i+4)%5): 告诉“管家”,我的邻居们可能现在可以吃饭了。- 例如,哲学家 0 放下叉子后,哲学家 1 和 4 可能现在能拿到两把叉子了。
- “管家”会检查他们是否处于
HUNGRY状态,并且邻居都不在吃,如果是,就唤醒他们。
4️⃣ test(int i) 函数 —— 核心逻辑!
1 | void test(int i) { |
📌 关键点:
- 检查三个条件:
state[i] == HUNGRY: 我确实想吃饭。state[(i+1)%5] != EATING: 我右边的邻居没在吃。state[(i+4)%5] != EATING: 我左边的邻居没在吃。
- 如果都满足:说明我现在可以拿到两把叉子!
- 设置
state[i] = EATING。 - 执行
V(s[i]),唤醒我自己(因为我在take_fork中P(s[i])阻塞了)。
- 设置
✅ 这个函数是“原子”的:因为它在
mutex保护下执行,不会被其他哲学家打断。
生产者消费者问题
mutex 的作用就是:
保护对共享变量(或临界区)的访问, 只在真正操作这些共享资源的前后“加锁”和“解锁”。
(防死锁铁律):
永远不要在持有互斥锁(mutex)的情况下,调用可能阻塞的操作(如 P(empty)、P(full)、sleep、wait 等)。
什么是生产者-消费者问题?
这是一个经典的多线程同步问题,用于模拟现实中的“生产”与“消费”场景:
- 生产者 (Producer):负责制造数据或产品。
- 消费者 (Consumer):负责处理或消费这些数据/产品。
- 缓冲区 (Buffer):一个有限大小的共享空间,用来暂存生产者的产品,供消费者取用。
📌 核心挑战
- 互斥 (Mutual Exclusion):多个生产者/消费者不能同时操作缓冲区的同一个位置,否则数据会错乱。
- 同步 (Synchronization):
- 生产者不能在缓冲区满时继续生产(要等待)。
- 消费者不能在缓冲区空时继续消费(要等待)。
代码
1 | item B[n]; |
问题:如果将P操作的顺序交换,会出现什么情况?
生产者霸占着 mutex 锁,等待
empty,消费者等待 mutex
锁,导致死锁。
1 | sequenceDiagram |
问题:当前生产者消费者共用一个互斥锁会造成竞争
1 | Semaphore pmutex, cmutex; // 两个独立的互斥锁 |
优势:
- 生产者之间:仍然需要
pmutex来互斥,因为多个生产者可能同时想写入in指针指向的位置。 - 消费者之间:仍然需要
cmutex来互斥,因为多个消费者可能同时想读取out指针指向的位置。 - 生产者 vs 消费者:它们可以并行! 只要生产者在写一个位置,消费者在读另一个位置,两者互不干扰,完全可以同时进行。
死锁
死锁产生
什么是死锁
在多进程/多线程系统中,死锁是指两个或多个进程因竞争资源而造成的一种互相等待的现象,若无外力作用,它们都将无法向前推进。
简单说:A 等 B,B 等 C,C 又等 A,大家谁也不让步,结果全都卡住。
死锁的4个必要条件
只要系统发生死锁,以下4个条件必然同时成立。缺一不可!
1️⃣ 互斥访问 (Mutual Exclusion)
- 定义:系统中存在临界资源,进程应互斥地使用这些资源。
- 通俗解释:资源一次只能被一个进程使用。比如,打印机、文件、数据库连接、内存中的某个变量等。
- 为什么是必要条件?如果资源可以被多个进程同时共享(如只读文件),那就不存在竞争,也就不会死锁。
2️⃣ 占有和等待 (Hold and Wait)
- 定义:进程在请求资源得不到满足而等待时,不释放已占有的资源。
- 通俗解释:一个进程已经拿着一些资源,但它还需要其他资源才能完成工作,于是它一边等着新资源,一边还紧紧攥着自己手里的旧资源,不肯放手。
- 为什么是必要条件?如果一个进程在等待新资源时能主动释放旧资源,那么它就不会阻塞别人,死锁也就不会形成。
3️⃣ 不剥夺 (No Preemption)
- 定义:已被占用的资源只能由属主进程自愿释放,而不允许被其他进程剥夺。
- 通俗解释:资源一旦被某个进程拿走,除非它自己愿意还回来,否则谁也不能强行抢走。这保证了进程的“自主性”,但也为死锁埋下了隐患。
- 为什么是必要条件?如果系统能强行剥夺资源(比如操作系统强制回收),那么就可以打破死锁链。
4️⃣ 循环等待 (Circular Wait)
- 定义:存在循环等待链,每个进程在链中等待下一个进程所持有的资源,造成这组进程处于永远等待状态。
- 通俗解释:这是一个闭环。A 等 B 的资源,B 等 C 的资源,C 又等 A 的资源,形成了一个“等待环”。
- 为什么是必要条件?如果没有循环,等待链最终会指向一个“不等待”的进程,这个进程完成后会释放资源,从而解开整个等待链。
死锁防止
死锁避免
银行家算法
死锁检测和解除
资源分配图
- 阻塞节点 (Blocked Node):一个进程,它正在请求一个或多个资源,但这些资源当前都被其他进程占用,且没有空闲实例可用。它必须等待。
- 非阻塞节点 (Non-blocked Node):一个进程,它要么没有请求任何资源,要么它请求的资源当前有空闲实例可以立即满足。它可以继续执行。
如何通过资源分配图判断死锁?
✅ 死锁的充分条件(当资源类型只有一个实例时)
如果资源分配图中存在一个环,则系统一定发生死锁。
- 原因:在一个环中,每个进程都在等待下一个进程所持有的资源,而下一个进程又在等待再下一个……形成一个无限等待的闭环。
⚠️ 当资源类型有多个实例时
环的存在是死锁的必要条件,但不是充分条件。
- 原因:即使图中有环,但如果环中的某个资源类型有多个实例,那么可能还有空闲实例可以满足某个进程的需求,从而打破死锁。
资源分配图的简化
死锁检测算法
与银行家算法的安全性检测类似