征服OS的第二座大山-并发

type

status

date

slug

summary

概述

💡

并发行为: 单处理器上交叉运行(交叉并发)/多处理器上同时运行(同时并发).

微观上, 任何时刻在一个处理器上只能运行一个线程(物理上只有一个PC).

并发程序设计: 将一个程序分成若干可同时执行的模块.

顺序设计(串行)的程序执行上具有顺序性(严格按序), 计算环境具有封闭性(独占资源), 计算结果具有确定性(与执行的速度和时间无关), 计算过程具有可再现性(程序运行轨迹确定).

然而以上这些在并发程序设计中都是行不通的...

线程定义

传统观念: 一个程序只有一个执行点(即PC), 程序执行严格按序, 独占资源, 执行结果确定且稳定可复现.

然而, 多线程程序会有多个执行点(即多个PC). 每个线程以类似于相互独立的过程的进程在运行, 但与进程不同的是它们之间共享同一个进程的地址空间, 能够访问相同的数据(而不考虑地址空间入侵的一般情况下, 进程之间的数据是互相隔离的).

💡

为什么需要多线程(为什么单线程组成一个进程不能满足需要)?

进程切换开销大

进程通信开销大

限制了并发粒度(进程中有可以并发的成分但没有被分拆出来, 不能单独并发运行)

不适合并行计算的要求

OS和并发编程要做的就是保证按照顺序程序设计方法编制的程序在并发执行时不受影响.

单个线程的状态与进程状态类似.

线程具有: 执行状态, 受保护的线程上下文, 独立的PC, 堆栈, 寄存器组.

💡

为什么要这样设计?

本质上是分离了进程”独立分配资源”和”调度分派执行”的两个主要职责.

资源不需要频繁切换, 进程之间互相隔离(独立虚拟地址空间), 维持资源分配的独立性;

线程作为系统调度和分派的基本单位, 能够轻装运行, 会被频繁调度和切换.

进程是操作系统中进行保护和资源分配的独立单位,

现成是进程的一条执行路径, 是调度的基本单位, 处理器调度最终落在线程一级.

线程调度

线程的状态: 运行/就绪/睡眠.

改变状态的操作: 孵化(创建), 封锁(睡眠), 活化(唤醒), 剥夺(取消调度), 指派(调度), 结束(销毁).

💡

线程与资源管理(由进程负责)无关, 故没有”线程挂起状态”一说.

处理器可以选择感知线程(直接调度线程, 考虑到此时调度的基本单位已经不是进程, 所以进程的三状态已经转移到线程, 只剩下一个挂起状态)或不感知线程(处理器调度进程, 用户调度程序调度进程内的线程)

线程创建后, 可能立即运行, 也可能在就绪状态下等待执行. 没理由认为先创建的线程先运行, 一切取决于调度程序的安排. 线程不像函数调用, 它独立在调用者线程的控制流之外, 可能在从创建者返回之前或之后的任意时刻完成.

💡

调度实例

case 1: 创建1 → 创建2 → 运行1 → 运行2

case 2: 创建1 → 运行1 → 创建2 → 运行2

case 3: 创建1 → 创建2 → 运行2 → 运行1

…(任意顺序均有可能)

💡

*补充: 处理器实现多线程的不同策略(初学者可以跳过)

用户级线程(User-Level Thread, ULT)

用户级线程是完全在用户空间管理的线程, 内核对此一无所知.

线程的创建、同步、调度都由用户态的线程库(如 pthread 用户实现版、Java 线程库)完成.

优点:

创建/销毁/切换速度快, 因为不需要陷入内核.
跨平台, 移植性好.

缺点:

因为内核不知道线程的存在, 阻塞调用(如I/O)会阻塞整个进程.

解读: 用户线程库只能运行在用户态下, 而阻塞调用会导致陷入内核态, 此时用户线程库无法运行, 内核调度又不知道用户线程的存在, 只能让整个进程等待I/O返回 → 解决方案: 混合方案, 将阻塞调用映射为内核线程, 让内核能够调度它.

不能利用多核 CPU(单核运行), 除非配合多个进程.

内核级线程(Kernel-Level Thread, KLT)

内核直接支持线程, 线程是内核调度的基本单位.

线程管理(创建、同步、调度)由操作系统内核完成(如 Linux pthread、Windows 线程).

优点:

内核调度线程, 能充分利用多核 CPU.
单个线程阻塞不会影响整个进程.

缺点:

线程切换开销大, 涉及内核态与用户态切换.
线程创建和销毁开销也比用户级线程大.

Jacketing 技术

Jacketing 是一种将用户级线程接口封装成内核级线程接口的技术(或反过来).

典型用途是在用户级线程实现中处理系统调用或阻塞操作:

系统调用通过 “jacket” 包裹, 改为非阻塞调用, 或者转交给内核线程池处理.
这样可以避免用户线程因阻塞操作而导致整个进程停顿.

过程:

在需要调用阻塞操作前, jacket 机制将用户线程挂起或映射到内核线程, 由内核线程执行阻塞操作.
完成后再恢复用户线程.

常用于混合线程库中, 增强用户级线程的 I/O 表现能力.

多线程实现的混合策略

混合策略是结合用户级线程与内核级线程优点的多线程实现方法, 典型模式为 M:N 模型:

M 个用户线程映射到 N 个内核线程(M ≥ N).

具体做法:

用户态线程库管理 M 个用户线程.
内核中注册 N 个内核线程作为调度与执行单位.
用户线程通过线程调度器在内核线程之间动态绑定与切换.

优点:

保持用户级线程的轻量和灵活.
同时能够利用多核 CPU, 避免阻塞问题.

缺点:

实现复杂, 需要在用户态与内核态之间维护映射关系.

代表技术:

早期 Solaris 线程库.
Go 语言的调度器(Goroutine 映射到工作线程).
Java 虚拟线程(Project Loom).

临界区

💡

无关的并发线程: 一组并发线程分别运行在不同的变量集合上, 一个线程的执行与其他并发线程的进展无关(Bernstein条件) → 整体进程的执行与时间无关;

交往的并发线程: 一组并发线程共享某些变量(不满足Bernstein条件), 则一个线程的执行可能影响其他并发线程的结果.

Bernstein条件: 允许同时读, 不允许一读一写或同时写.

交往的并发线程执行的相对速度(即执行顺序和进展速度)无法相互控制, 可能导致程序结果错误或永远等待.

线程之间可能存在竞争(竞争同一资源)或协作(遵循一定顺序和依赖).

线程之间共享同一个进程的地址空间, 所以有可能会尝试更新同一个全局变量. 此时数据一致性就成为问题.

💡

实例: 全局变量count = 0, 线程A和线程B并发增加count10000次, 最终count不一定为20000, 因为前一次增加在写回存储之前可能被下一次增加打断(如时钟中断触发调度), 这样下一次增加取到的还是前一次增加之前的值(旧版本), 这样就浪费了一次增加机会.

这种多个执行线程大致同时试图更新相同的共享的数据结构的情况叫做"竞态条件(race condition)".

可能导致竞争状态的代码称为临界区(critical section), 即访问重叠资源/共享资源的代码片段, 一定不能由多个线程同时执行.

我们想要做到的是:

"互斥(mutual exclusion, mutex)", 即当有一个线程在预先定义的互斥区内运行时, 就阻止其他线程进入互斥区.

"原子性(atomic)": 即单步完成要做的事, 要么根本没有运行, 要么已经运行完毕, 不存在中间状态, 不可被打断.

实现方式: 专门的原子的硬件指令支持/使用特殊指令构造同步原语(锁)来控制对临界区的访问

线程之间还需要交互机制, 例如睡眠/唤醒 → 同步原语支持(条件变量).

另外, 对临界区的管理目标: 首先保证一次至多允许一个线程停留在相关的的临界区内, 还要做到让一个线程不能无限驻留在临界区(恶意强占), 也不能无限等待临界区(饥饿现象).

💡

临界区的代码需要短小精悍, 这样才能增加并发, 保证系统效率.

POSIX的线程API

💡

什么是POSIX？

POSIX 是"可移植操作系统接口"(Portable Operating System Interface)的缩写, 是由 IEEE 制定的一系列标准, 旨在保证 UNIX 操作系统之间接口的一致性, 使程序在不同系统之间具有更好的可移植性.

从具体行为的角度解释 POSIX:

以下是一些具体行为, 说明操作系统如何遵循 POSIX 标准:

1. 文件系统行为

一切皆文件: 包括常规文件、目录、设备文件、套接字等都可以通过文件接口访问.

统一的文件操作接口: 提供标准的系统调用, 如:

open(): 打开文件
read() / write(): 读写文件
close(): 关闭文件
unlink(): 删除文件

2. 进程管理行为

创建进程: 使用 fork() 创建子进程.

执行程序替换: 使用 exec() 系列函数替换当前进程镜像.

进程同步: 父进程可以通过 wait() 或 waitpid() 等函数等待子进程结束.

信号处理: 支持异步事件处理, 如 SIGINT、SIGKILL, 通过 signal() 或 sigaction() 注册处理器.

3. 线程支持行为(POSIX Threads / pthreads)

提供标准的线程操作接口:

pthread_create(): 创建线程
pthread_join(): 等待线程结束
pthread_mutex_lock() / pthread_mutex_unlock(): 互斥锁
pthread_cond_wait(): 条件变量等待

4. 输入输出行为

基于文件描述符: 标准输入(0)、标准输出(1)、标准错误(2).

统一的 I/O 接口: 包括低级(如 read()/write())和高级(如 fopen()/fprintf())接口.

5. 错误处理行为

统一的错误码表示: 系统调用失败时设置全局变量 errno.

标准错误码: 如 EACCES(权限不足)、ENOENT(文件不存在)、EBADF(错误的文件描述符)等.

6. 时间处理行为

提供时间相关的系统调用和库函数:

time(): 获取当前时间
gettimeofday(): 获取精确时间
clock_gettime(): 获取高精度系统时钟

总结

POSIX 从接口函数、行为规范和常量定义等方面规范了操作系统的基本功能, 使得应用程序可以在符合 POSIX 的不同系统之间轻松移植, 而不需要修改代码逻辑. 这是操作系统设计中的重要标准之一, 广泛应用于各种类 UNIX 系统(如 Linux、macOS、FreeBSD 等).

💡

原则:

保持简洁

尽量减少线程间交互

初始化锁和条件变量

检查返回值

记住线程的栈是私有的

线程之间总是通过条件变量发送信号来交互, 切忌使用全局变量交互

线程创建

线程完成(等待同步机制)

小心, 不要返回野指针.

锁

💡

锁是提供临界区互斥的机制.

锁和互斥用于解决线程之间的竞争关系(并发访问同一资源).

示范调用例程:

对于pthread_mutex_lock(&lock)调用: 若调用时临界区内没有其他线程, 则获取锁并从该调用处返回, 继续执行后续代码; 若调用时临界区内有其他线程则该调用阻塞, 直到临界区内的线程释放锁并使得锁可用. 再获取锁并返回.

lock()和unlock()需要传入参数指定要上锁/解锁的对象, 从而可以用不同的锁保护不同的临界区, 使用更细粒度的并发控制, 允许更多的并发, 提升性能.

其他特殊版本的API(只在特殊情况下使用, 如防止死锁):

条件变量

💡

条件变量就是线程之间的信号.

条件变量用于协调线程之间的合作问题, 等待他人进展时阻塞自己, 由合作者唤醒.

互斥实际上也是特殊的协调关系(逐次使用资源), 于是锁和条件变量都能用信号量统一实现也就不足为奇了.

主要的API:

示范调用例程:

不要妄想用一个全局变量ready来简单控制线程间的等待和唤醒(出错概率极高)!

编译说明

引入pthread.h头文件, 并在编译时连接pthread库即可.

锁

概述

锁为实现临界区运行的原子性而创造.

原子性的敌人: 单处理器上的中断(如时钟中断), 多处理器上的并发.

锁的实体:(引用)锁(的)变量pthread_mutex_t lock.

💡

锁变量(结构)类型中保存的信息: 持有锁的线程, 等待并请求获取锁的线程队列等, 封装起来不向用户暴露.

锁的状态: available(没有线程持有该锁)/acquired(已有一个线程持有该锁). 锁只有处于available状态下才能被获取, 否则获取行为会导致阻塞, 无法进入锁把守的临界区.

锁是OS为程序员提供的最细粒度的调度控制. 线程一般来说由操作系统全权调度, 而锁让程序员获得一些控制权, 使操作系统调度由混乱变得部分可控.

POSIX将锁称为互斥量mutex, 因为它用来提供线程之间的互斥.

锁的实现

需要操作系统提供一定的硬件原语.

评价实现优劣的标准: 互斥性(最基本要求), 公平性(竞争锁的机会平等), 性能(使用/争抢锁的开销)

实现一: 在临界区关中断

进入临界区时禁用中断, 离开时重新启用.

优点: 简单

缺点: 简单的补集

需要授予所有线程开关中断的权限, 容易被恶意利用(强制占有全部的CPU时间, 隔绝OS控制);

不支持多处理器, 即使在自身运行的处理器上关中断也可能在其他处理器上形成竞争访问;

所有临界区处理期间收到的中断都得不到处理;

开关中断开销大, 效率较低.

实现二: 硬件指令支持(TestAndSet, 测试并设置)

创建锁/释放锁的操作自身就必须是原子的, 否则在一个线程获取锁的半路打断 → 切换到另一个线程 → 另一个线程获取锁 → 切换到原线程, 即可构造出两个线程同时持有锁的情况, 而这显然不满足互斥要求(至多只有一个线程同时持有同一个锁).

测试并设置指令(test-and-set): 写入新值, 返回旧值

这一指令可以用于实现一个简单的自旋锁(等待时以死循环形式阻塞)

解读: 到达11行时, 若flag为1(锁被占用)则testAndSet返回1并重复设置flag为1, 始终在while语句中自旋等待. 若flag为0(锁空闲)则testAndSet返回0并设置flag为1, 退出while循环, 抢占锁并从lock调用中返回, 进入互斥区.

一切的保障: testAndSet行为是原子的.

评价自旋锁:

自旋锁正确提供互斥性;

自旋锁不保证任何公平性(取决于调度, 听天由命), 自旋等待的线程可能饿死;

自旋锁在单处理器机器上需要抢占式调度, 因为自旋行为不会让出控制权, 需要中断并抢占自旋线程来让其他线程获得进展, 从而早日解放自旋线程, 所以在单处理器的情况下自旋锁开销很大(所有等待的线程都需要中断并空转一个时间片).

多处理器机器上, 在线程数不远多于CPU数的情况下自旋锁性能不错, 某一个线程在一个处理器上自旋时其余工作(不需要切换就)可以在其他处理器上取得进展. 由于临界区一般很短, 所以其他处理器上的线程一般很快就能释放锁并解放自旋等待的线程, 并没有浪费很多CPU周期.

实现三: 硬件指令支持(CompareAndSwap, 比较并交换)

比较并交换指令: 若考察变量的实际值等于预期值, 就写入更新值. 最终返回实际值.

这个指令也可以用于实现自旋锁:

解读: 解读: 到达11行时, 若flag为1(锁被占用)则compareAndSwap返回1且不修改flag的值, 始终在while语句中自旋等待. 若flag为0(锁空闲)则compareAndSwap返回0并设置flag为1, 抢占锁并退出while循环, 从lock调用中返回, 进入互斥区.

一切的保障: compareAndSwap行为是原子的.

仅仅对于自旋锁来说, 这两个指令在效果上等价. 其余某些情况下compareAndSwap会更强大.

实现四: 硬件指令支持(链接的加载LL+条件式存储SC)

链接的加载(Load-Linked, LL)与条件式存储(Store-Conditional, SC)是一对成对使用的硬件原语, 主要见于MIPS和ARM等架构.

LL: 从内存中加载某个地址的值, 并记录该地址为"监控地址".

SC: 尝试将值写回"监控地址"; 若期间该地址未被其他处理器修改, 则写入成功并返回1, 否则失败返回0.

可用于实现自旋锁:

storeConditional返回0(失败)的情况解读:

flag原为0, 假设现有线程1过了while(loadLinked(&lock->flag) == 1) ; // spin这一关, 正要通过进行storeConditional的条件判断来更新flag.

然而此时被中断(没有来得及完成对flag的更新), 切换到线程2.

线程2一路完成了storeConditional, 设置flag为1并持有锁.

此时再切换回线程1, 则线程1的storeConditional会失败, 无法与线程2同时持有锁, 满足互斥性.

优缺点分析:

原子性由LL/SC保证, 正确性高;

相比testAndSet减少了缓存一致性开销(因为SC失败时不修改内存);

可能出现"活锁": 多个线程反复尝试SC失败;

硬件依赖性强, 仅部分平台支持.

实现五: 硬件指令支持(FetchAndAdd, 获取并增加)

fetchAndAdd将变量值加上一个数, 并返回增加之前的旧值. 该指令常用于实现"票号锁"等公平锁.

用于实现票号锁(Ticket Lock):

优缺点分析:

满足互斥性;

保证公平性: 按照顺位叫号, 先来的线程先获得锁(先进先出), 所有的线程都能拿到锁;

忙等自旋, 单处理器上仍然低效;

如果轮数差距大,则等待时间长, 适用于竞争较激烈但临界区短的情况.

实现六: 要自旋时放弃CPU

💡

让要自旋的线程主动放弃调度自身, 交出CPU控制权用于运行其他线程.

核心调用: yield() → 取消调度自身, 从运行态回到就绪态.

虽然省出了自旋的时间片, 但是自旋线程还是会导致可观的上下文切换开销, 而且仍然可能出现饿死的线程(一直让出, 得不到调度).

实现七: 使用休眠队列替代自旋

维护一个队列来保存等待锁的线程, 显式施加控制, 决定锁释放时谁能够抢到锁.

使用Solaris提供的原语支持: park()和unpark(threadID). park()让调用者线程休眠(进入等待态), unpark(threadID)则唤醒指定的线程(进入就绪态).

guard起自旋锁的作用, 保证flag和队列操作的原子性. 它只涉及同时申请锁时的并发控制, 不涉及用户定义的临界区代码, 故自旋等待时间一般不会很久, 开销可以接受.

实现八: 混合方案

对于锁很快就能释放的场景, 自旋锁的效率较高. 自旋越久性能浪费越多.

对于锁需要等待很久才能释放的场景, 使用休眠队列效率较高. 休眠-唤醒越频繁性能浪费越多.

混合方案: 两阶段, 先自旋固定的时间/次数, 如果锁没有被释放再让申请者休眠等待锁释放.

*实现九: Peterson算法(补充, 纯软件)

Peterson算法是一种经典的并发编程算法, 用于解决临界区问题, 确保互斥访问.

Peterson算法使用两个共享变量来实现互斥:

flag[2](布尔数组):

flag[i]为true表示线程i想要进入临界区.

flag[i]为false表示线程i不想进入临界区.

turn(整型): 表示当前允许进入临界区的线程的ID. 如果turn = i, 则表示轮到线程i进入.

Peterson算法通过结合这两个变量, 巧妙地解决了互斥、进步和有限等待这三个临界区问题的基本要求.

伪代码(针对两个线程P0和P1)

解释:

当线程P0想要进入临界区时, 它会执行以下步骤:

将flag[0]设置为true, 表示自己想要进入.

将turn设置为1, 表示它将优先权交给P1. 这是关键的“礼让”行为.

进入while循环(忙等):

如果flag[1]为true(P1 也想进入)并且turn == 1(轮到 P1), 那么 P0 会一直等待.

只有当 flag[1] 为 false(P1 不想进入)或者 turn == 0(轮到 P0 了), P0 才能退出循环并进入临界区.

线程P1的逻辑与P0对称.

互斥的保证:

假设P0和P1都想进入临界区, 并几乎同时执行它们各自的进入区代码.

P0设置flag[0] = true, 然后turn = 1.

P1设置flag[1] = true, 然后turn = 0.

turn变量最终的值将取决于哪个线程最后执行了turn = X这一行.

情况一: P0 先执行turn = 1, 然后 P1 执行turn = 0.

此时turn最终为0.
P0的while循环条件是(flag[1] && turn == 1). 由于turn为0, P0可以进入临界区.
P1 的while循环条件是(flag[0] && turn == 0). 由于flag[0]为true且turn为0, P1会等待.
结果: P0进入临界区, P1等待, 实现了互斥.

情况二: P1 先执行 turn = 0, 然后 P0 执行 turn = 1.

此时turn最终为1.
P0 的while循环条件是(flag[1] && turn == 1). 由于flag[1]为true且turn为1, P0会等待.
P1 的while循环条件是(flag[0] && turn == 0). 由于turn为1, P1可以进入临界区.
结果: P1进入临界区, P0等待, 实现了互斥.

无论哪种情况, 只有一个线程能进入临界区. turn变量解决了两个线程都想进入时的冲突, 通过“礼让”机制确保了公平性.

优点:

满足临界区问题的三个要求:

互斥: 任何时候只有一个线程在临界区.
进步: 如果没有任何线程在临界区, 并且有线程想进入, 那么只有那些想进入的线程可以参与决定哪个线程可以进入, 并且这个决定不能被无限期推迟.
有限等待: 如果一个线程想进入临界区, 那么它在有限的时间内一定能进入, 不会无限期等待.

纯软件实现: 不依赖于任何特殊的硬件指令(如原子操作).

简单易懂: 算法逻辑相对直观.

缺点:

忙等: 当一个线程在等待进入临界区时, 它会不断地检查条件, 这会浪费 CPU 周期. 在多任务操作系统中, 更好的做法是让等待的线程阻塞, 释放 CPU 给其他线程.

仅限于两个线程: Peterson 算法原始版本只适用于两个线程. 虽然有推广到N个线程的版本(如 Bakery 算法), 但会变得更加复杂.

现代 CPU 架构问题: 在现代处理器上, 由于指令重排和缓存一致性的复杂性, Peterson 算法可能无法正常工作, 除非使用内存屏障来强制内存操作的顺序. 因此, 在实际的生产系统中, 很少直接使用Peterson算法, 而是使用操作系统提供的更底层、更健壮的同步原语(如互斥锁、信号量等).

条件变量

概述

为了实现等待和同步, 我们可以选择设置一个受子线程控制的全局变量flag, 让父线程自旋等待直到子线程返回并设置flag, 但是这样让父线程空转效率太低.

因此锁不是支持并发所需的唯一原语, 我们还需要线程之间交互的机制, 用于实现等待和同步(如父线程等待子线程join/执行完毕), 以及规定强制顺序.

💡

线程互斥关系也是一种特殊的线程同步关系, 即逐次使用互斥共享资源, 是对线程使用资源次序上的一种协调.

线程可以使用条件变量来等待条件变为真. 条件变量是一个显式队列, 当某些条件不满足时, 线程可以将自己加入队列等待该条件(进入等待态). 当另一个线程改变该条件时就可以通过在该条件上发信号来唤醒一个或多个等待该条件的线程, 让它们继续执行(进入就绪态).

使用条件变量

条件变量的两种相关操作: wait(用于睡眠)和signal(用于唤醒).

💡

使用signal发出的信号最多只能被1个线程捕获(还可能未被捕获而流失).

两个疑问:

💡

Q1: 使用条件变量时能不能不加锁?

A1: 不能. 假设实现如下:

如果在指定位置被打断, 切换到子线程, 子线程完成执行, 设置done为1并调用signal发出信号, 再返回到此处, 则父线程睡眠之后无人唤醒, 会一直睡下去.

💡

Q2: done这一变量是否可以删除?

A2: 不能. 假设实现如下:

如果在父线程调用thread_join之前子线程就已经调用了thread_exit完成执行, 则子线程发出的信号父线程又没有收到, 继续调用wait就会睡死.

如果有done变量, 父线程就可以知道子线程已经完成了exit调用, 选择不休眠.

生产者/消费者(有界缓冲区)问题

概述

生产者线程生成数据项, 放入缓冲区; 消费者线程从缓冲区取走并使用数据项.

在使用管道连接不同程序的输出和输入时, 也会使用有界缓冲区.

示例中ls是生产者, wc是消费者.

有界缓冲区是共享资源, 需要通过同步和锁来访问, 以免产生并发访问问题(竞态条件).

第一版程序: 骨架(无并发控制)

使用单独一个整型变量作为缓冲区, 一存一取.

如果并发访问缓冲区触发断言就会导致程序abort.

第二版程序: 加上锁和条件变量(有问题)

只有一个生产者和一个消费者线程时, 以上程序可以正确运行. 问题出现在有多个消费者或多个生产者的情况.

以一个生产者两个消费者为例, 问题流程如下:

消费者1获得锁, 调用get, 检查到缓冲区为空, 休眠等待信号并释放锁;

生产者获得锁, 调用put, 将数据放入缓冲区, 发出信号唤醒消费者1并释放锁, 进入下一个循环, 获取锁后发现缓冲区满, 睡眠并释放锁;

消费者1被唤醒进入就绪态, 但是被消费者2抢占调度;

消费者2获得锁, 消费完了缓冲区的值, 释放锁进入下一轮循环, 发现缓冲区空, 睡眠并释放锁;

消费者1重新获得调度, 它认为被唤醒就说明缓冲区满(但实际为空), 调用get触发断言, 程序abort.

启示: 信号只能暗示休眠中的线程等待的条件发生了变化, 但是不能保证这一变化能够维持到线程重新被调度.

信号的这种语义被称为Mesa语义.

第三版程序: 使用while替代if(仍有问题)

使用while替代if, 使得线程在被重新调度时再次检查缓冲区是不是真的有数据, 避免"假唤醒"问题.

💡

多线程程序检查条件时用while(而不是if)总是对的.

应对Mesa语义问题的方法: 使用while代替if, 多次检查获得保障.

仍以一个生产者两个消费者为例, 问题流程如下:

消费者1和消费者2先后因缓冲区空而睡眠;

生产者运行, 放入数据并发出信号唤醒消费者1, 自己循环一轮后休眠等待缓冲区空;

消费者1完成消费发出信号(这个信号唤醒了谁?), 自己循环一轮后休眠等待缓冲区满;

上述信号理应唤醒生产者, 但如果唤醒的是消费者2则消费者2也因等待缓冲区满而重新休眠;

三个线程同时处于休眠状态, 无人唤醒, 全部睡死.

启示: 信号需要具有指向性, 消费者只应该唤醒生产者, 生产者只应该唤醒消费者.

第四版程序: 正确方案

生产者线程等待条件变量empty, 发信号给变量fill; 相应地, 消费者线程等待fill, 发信号给empty. 这样设计不会出现错误唤醒问题.

第五版程序: 扩大缓冲区, 增加并发

扩大缓冲区, 增加一次生产/消费的数据项个数, 摊销上下文切换成本.

修改了缓冲区结构, put/get方法, 生产者和消费者线程的检查条件和等待信号逻辑.

第六版程序: 将锁, 条件变量和共享资源封装为管程(monitor)

一个管程封装并管理对共享资源的访问, 使得多个线程可以安全、有序地访问这些资源. 管程封装的是共享资源和安全访问机制, 并不直接拥有线程实体.

其他问题: 该唤醒谁?

多个线程等待时, 决定唤醒哪个线程也是一个问题(因为signal发出的信号只能被一个线程接收).

一种解决方案: 使用覆盖条件pthread_cond_broadcast(&cond)代替signal, 向该条件上的所有线程广播, 从而确保所有应该被唤醒的线程都被唤醒. 当然不该被唤醒的也被唤醒了, 要重新进入睡眠, 可能带来额外开销.

大部分情况下不需要使用覆盖条件. 如果当下不得不使用则可能是因为程序设计不当.

信号量

概述

信号的数量❌ (用作)信号(的变)量✅

信号量与锁和条件变量处于同一层次, 可以互相实现. 信号量更泛用, 锁和条件变量更专门化.

信号量(semaphore)的实体是具有一个整数值的对象. 使用sem_wait()和sem_post()接口进行操作(也叫PV操作, 即荷兰语Proberen和Verhogen).

推论1: 若信号量s为正值, 则该值等于在封锁线程之前对信号量s可施行的wait()/P()操作次数, 亦等于s所代表的实际还可以使用的物理资源数

推论2: 若信号量s为负值, 则其绝对值等于登记排列在该信号量的等待队列之中等待的线程个数, 亦即恰好等于对信号量s实施wait()/P()操作而被封锁起来并进入该信号量的等待队列的线程数

推论3: 通常, wait()/P()操作意味着请求一个资源, V()操作意味着释放一个资源. 在一定条件下, wait()/P()操作代表阻塞线程操作, 而post()/V()操作代表唤醒被阻塞线程的操作

请求不同资源的线程进入不同信号量的等待队列进行管理.

多个线程完全有可能并发调用sem_wait()和sem_post(), 所以这些临界区显然需要管理, sem_wait()和sem_post()的实现都需要是原子的, 由操作系统提供原子性保障(硬件/关中断).

💡

必须通过sem_wait()/P()和sem_post()/V()原子更新信号量, 而不能直接读写信号量.

二值信号量 → 锁

💡

信号量可以用于实现锁.

因为锁只有持有和未持有两种状态, 所以这种用法叫做二值信号量(binary semaphore).

将信号量初始值设为1, 则sem_wait()相当于pthread_mutex_lock(), sem_post()相当于pthread_mutex_unlock().

直接用一对sem_wait()和sem_post()环绕临界区即可.

如果信号量为0或负数时有另一线程试图访问同一临界区, 则信号量-1再令该线程挂起等待, 直到持有锁的线程调用sem_post()来唤醒. 所以正信号量代表当前可并发执行的线程数, 负信号量代表等待的线程数.

信号量用作条件变量

💡

信号量还可以用于实现条件变量.

注意: 条件变量必须在临界区内使用, 是因为它接收的是瞬时触发信息, 错过了(即signal操作在wait操作之前调度发生)则等待者就可能会睡死; 而信号量用作条件变量则没有这个顾虑, 因为信号量本身就有持久存储的值, 即使V操作比P操作先发生, 也可以通过信号量值来感知发生了什么事.

将信号量初始值设为0, 则sem_wait()相当于pthread_cond_wait(), sem_post()相当于pthread_cond_signal().

若main调用sem_wait()时child未返回, 则信号量由0减为-1, 挂起等待, 直到child执行完毕并调用sem_post()唤醒main;

若main调用sem_wait()时child已经返回, 则信号量由1减为0, main不挂起, 继续执行.

解决生产者/消费者(有界缓冲区)问题

第一版程序: 有问题的实现(竞态条件)

对于BUFFER_SIZE == 1的情况, 可以正确运行. 然而对于BUFFER_SIZE > 1的情况, 可能存在并发写入导致向buffer写入的数据项互相覆盖, 导致损失.

第二版程序: 产生了新问题的解决方案(死锁)

可以使用锁来解决并发访问临界区的控制问题:

问题: put和get都需要先获得锁, 而消费者/生产者线程挂起时均不会释放锁. 故当消费者阻塞等待生产者放入数据时生产者无法放入数据(消费者等待full, 生产者等待mutex), 生产者阻塞等待消费者取出数据时消费者无法取出数据(生产者等待empty, 消费者等待mutex), 导致死锁.

第三版程序: 收缩锁的作用域, 避免死锁

这样在等待full或empty时, 锁就是可用的.

💡

Q: 能不能令生产者和消费者使用不同的锁来避免死锁, 同时增加并发?

A: 能, 但没那么简单. 例如若fill和use指向相同的数据项, 则并发访问很可能就会出现问题.

读者-写者锁问题

💡

在不妨碍读操作的前提下尽可能提高并发性.

核心思想: 写只能串行(写时阻止任何读者或其他写者访问, 写之前应该把所有正在读或写的线程全部赶出去), 读可以并发(只要没有写者在写就可以允许任意个数的读者并发读取).

generalLock(泛用锁)在读写锁代码中扮演着关键的保护角色.

它本质上是一个互斥锁, 主要作用是:

保护readersCnt变量: readersCnt记录着当前正在读取共享资源的读者数量. 当多个读者同时尝试增加或减少这个计数时, 如果没有generalLock的保护, 就会出现竞态条件, 导致 readersCnt 的值不准确. 同样, 在rwLock_readLock_unlock()函数中, generalLock也以相同的方式保护着 rwLock->readersCnt--.

确保读者进入/退出逻辑的原子性: 除了保护readersCnt, generalLock还确保了读者进入或退出临界区的整个逻辑操作是原子性的.

当读者进入时(rwLock_readLock_lock): 当第一个读者进入(即rwLock->readersCnt 从0变为1)时, 它需要获取writeLock来阻止写者. 这个条件检查(if(rwLock->readers == 1))和随后的sem_wait(&rwLock->writeLock)必须作为一个不可中断的整体操作执行. generalLock确保了在这个关键阶段, 没有其他读者或写者逻辑可以干扰.
当读者退出时(rwLock_readLock_unlock): 当最后一个读者退出(即rwLock->readersCnt从1变为0)时, 它需要释放writeLock以允许写者继续. 这个检查 (if(rwLock->readers == 0))和随后的sem_post(&rwLock->writeLock)也需要是独占的. generalLock保证了这一点.

如果没有 generalLock, 这个读写锁的实现将会因为对共享状态(readersCnt)的并发访问以及管理写者访问的关键操作而容易出现不正确的行为.

缺陷: 读者很多时容易出现一直等待读者退出, 写者饿死的问题; 和简单快速的锁相比开销较大.

解决方向: 写者优先/先进先出.

💡

*例: 额外加一把锁, 使得写者发出请求时不允许新的读者进入.

解析(From Gemini):

信号量S的作用:

S被初始化为1, 并且在所有读者和写者尝试进入临界区之前都必须对其执行 P(S)操作.

在完成读或写操作后, 读者和写者都会执行V(S)操作.

写者优先权的提升:

在标准读者-写者问题(读者优先)的解决方案中, 如果一直有读者活跃, 写者可能会无限期地等待(写者饥饿). 这是因为只要有一个读者存在, 写者就无法获取 writeLock.

引入S信号量后, 无论是读者还是写者, 都必须先竞争S. 这意味着:

当写者到达时, 它会尝试P(S). 如果此时有读者正在读, 并且S已经被某个读者持有, 那么写者会阻塞在P(S)处.
当没有读者在读, 或者当前读者释放了S之后, 写者就有机会获得S. 一旦写者获得了S, 它就可以尝试获取writeLock并执行写入操作.
关键点在于, 当写者成功获取S之后, 它会立即尝试获取writeLock. 而此时如果有新的读者尝试进入, 它们也会被P(S)阻塞. 这就确保了在写者等待期间, 不会有新的读者持续涌入, 从而让写者获得进入临界区的机会.

防止写者饥饿:

假设有很多读者不断地进入和退出. 在没有S的情况下, 写者可能永远也得不到writeLock.

有了S之后, 每次只有一个进程(无论是读者还是写者)能够通过P(S)并进入到下一步的竞争中.

如果一个写者在P(S)处等待, 并且之前持有S的进程释放了S, 那么操作系统调度器有机会选择这个等待的写者来获得S. 一旦写者获得了S, 它就能阻止后续的读者获取S, 从而为自己获取writeLock创造条件.

总结来说, 这个方案促进读者-写者公平(尤其是防止写者饥饿)的主要机制是:

引入S作为一种“入口门卫”: 所有的进程(读者和写者)在进入真正的读写逻辑之前, 都必须先通过这个门卫.

限制并发性: S限制了在任何给定时刻, 可以有多少个进程(无论是新的读者还是写者)进入到竞争读写锁的下一阶段.

优先级切换: 当一个写者在P(S)处等待时, 它会阻止后续的读者也通过P(S). 这有效地给了写者一个更高的优先级, 因为当它获得S后, 它能够独占地尝试获取writeLock, 而无需担心大量新读者涌入.

哲学家就餐问题

💡

有趣但实用性不强的问题.

概述

哲学家绕着圆桌就座, 每两位哲学家之间有一把餐叉, 哲学家有时要思考(不需要餐叉→挂起), 有时要就餐(需要左右手同时持有餐叉→运行).

目标: 保证没有死锁, 没有饥饿现象(每个哲学家都能吃到东西), 并且并发度更高(尽可能让更多哲学家同时吃东西).

方案一: 问题实现(统一先拿/放左手叉, 再拿/放右手叉)

问题在于死锁: 所有人都拿了左手叉, 都在等待右手叉, 陷入死锁.

解决方案: 修改某些哲学家取餐叉的顺序

打破循环, 避免死锁.

还有其他方案:

至多允许四个哲学家同时取叉子(C.A.R. Hoare方案, 对应规避循环等待);

奇数号先取左手边的叉子, 偶数号先取右手边的叉子(对应修改顺序规避循环等待);

每个哲学家取到手边的两把叉子才吃, 否则一把叉子也不取(对应静态申请资源).

与后文中死锁预防部分方案有共同之处.

其他练习题

苹果-橘子问题

桌上有一只盘子, 每次只能放入一个水果. 爸爸专向盘子里放苹果, 妈妈专向盘子里放橘子, 儿子专门等着吃盘子里的橘子, 女儿专门等着吃盘子里的苹果.

睡眠的理发师问题

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子. 如果没有顾客, 理发师便在理发椅上睡觉. 首个顾客到来时, 它必须叫醒理发师. 如果理发师正在理发时又有顾客来到, 则如果有空椅子可坐, 就坐下来等待, 否则就离开.

银行业务问题

某大型银行办理人民币储蓄业务, 由n个储蓄员负责. 每个顾客进入银行后先至取号机取一个号, 并且在等待区找到空沙发坐下等着叫号. 取号机给出的号码依次递增, 并假定有足够多的空沙发容纳顾客. 当一个储蓄员空闲下来, 就叫下一个号.

售票问题

汽车司机与售票员之间必须协同工作, 一方面, 只有售票员把车门关好了司机才能开车, 因此售票员关好门应通知司机开车, 然后售票员进行售票. 另一方面, 只有当汽车已经停下, 售票员才能开门上下客, 故司机停车后应该通知售票员. 假定某辆公共汽车上有一名司机与两名售票员, 汽车当前正在始发站停车上客.

吸烟者问题

一个经典同步问题: 吸烟者问题(patil, 1971). 三个吸烟者在一个房间内, 还有一个香烟供应者. 为了制造并抽掉香烟, 每个吸烟者需要三样东西: 烟草, 纸和火柴. 供应者有丰富货物提供. 三个吸烟者中, 第一个有自己的烟草, 第二个有自己的纸, 第三个有自己的火柴. 供应者随机地将两样东西放在桌子上, 允许一个吸烟者进行对健康不利的吸烟. 当吸烟者完成吸烟后唤醒供应者, 供应者再把两样东西放在桌子上, 唤醒另一个吸烟者.

信号量的实现

💡

可以使用锁和条件变量来实现信号量. 这个视角下, 信号量是锁和条件变量的泛化, 更加通用(但是是否有泛化的价值还值得商榷).

这种实现不满足负信号量代表等待线程数的特性, 因为value恒≥0.

Hoare’s Monitor 霍尔管程

可以这样理解:

Hoare管程就是一种将 👉锁(互斥机制) 👉条件变量(同步机制) 👉共享资源(关键数据) 集成封装在一个结构化对象中的并发控制机制.

💡

From Gemini:

管程是存在于进程中的实体. 管程是编程语言提供的一种高级同步原语(或构造), 它存在于进程的地址空间内. 它不是独立的进程或线程, 而是进程内的一个逻辑模块或数据结构, 包含了一组共享数据和访问这些数据的过程(方法).

用于集中管理各线程的并发(如互斥和同步)问题, 是管程设计的主要目标和优势. Hoare管程通过以下机制实现这一点:

互斥: 管程内的数据和过程是受保护的. 在任何时刻, 只有一个线程可以执行管程内的任何过程. 当一个线程进入管程时, 其他尝试进入的线程将被阻塞, 直到当前线程退出管程. 这种互斥性是由管程的入口锁(隐式或显式)保证的.

同步: 除了互斥, 管程还提供了条件变量机制来实现线程间的同步. 线程可以在管程内等待某个条件(例如, 缓冲区为空), 当条件不满足时, 它会释放管程的锁并进入等待队列. 当其他线程使条件满足时, 会通过 signal 或 broadcast 操作唤醒等待的线程.

Hoare管程的特殊之处在于它的 signal 语义: 当一个线程发出 signal 后, 它会立即将管程的控制权交给被唤醒的线程, 自己暂停执行(通常会进入一个优先级队列), 直到被唤醒的线程完成其操作或再次等待, 它才能恢复执行. 这种“立即切换”的语义是为了避免死锁和简化证明, 但实现起来比较复杂.

更正式的理解方式

管程(Monitor)是:

一种高级并发抽象结构, 将对共享资源的互斥访问与线程间的同步统一封装.

而 Hoare管程 是其中一种经典实现方式, 具有:

互斥访问: 内部操作隐含互斥(不需要用户显式加锁)

同步等待: 条件变量管理线程等待/唤醒

严格信号语义: signal() 会立即让出执行权给被唤醒线程(Hoare语义)

Hoare管程集成组件拆解

组成元素	说明
锁	实现管程入口方法的互斥访问
条件变量(及其等待队列)	表达线程间的等待-唤醒关系
wait/signal	线程阻塞和唤醒的原语, 带有立即交接执行权的语义(Hoare语义)
共享数据	被封装的数据结构, 仅可通过 monitor 方法访问

其中next queue是条件变量信号发送方线程的等待队列, condition cn是条件变量的等待队列.

Hoare管程控制原语实现

控制原语: enter ←→ leave, wait ←→ signal.

为了保证管程中只有一个线程在运行, 需要对条件变量的唤醒(signal)机制做出特殊处理: 立即唤醒信号接收方线程, 让信号发送方线程进入睡眠(在next queue中等待), 直到被唤醒的线程完成执行并退出管程才唤醒发送方.

线程进入等待态时也需要检查释放在next上等待的线程, 若没有等待线程则释放锁以便其他新线程进入管程.

管程解决并发问题实例

Hoare管程解决读者写者问题

Hoare管程解决哲学家就餐问题

Hoare管程解决生产者-消费者问题

对比传统低层工具(信号量等)

特性	Hoare管程	手动使用信号量 / 条件变量
资源封装	✅ 结构清晰, 封装在对象中	❌ 程序员需显式管理
互斥管理	自动实现	需自行加锁/解锁
同步语义	条件变量 + 严格唤醒顺序(Hoare语义)	弱语义(如Mesa: notify不保证立即)
出错可能性	少, 结构化强	多, 极易出现死锁、竞争等问题

总结

💡

Hoare管程可以理解为把锁、信号量、条件变量等并发控制原语统一封装成一个安全的并发对象, 通过结构化的方式让程序员在使用时只关注逻辑条件而非底层控制细节, 并通过严格的唤醒语义保证线程在条件满足时立即执行.

线程之间的通信

💡

相关的线程之间通过信号量实现互斥和同步 → 低级通信方式, 只能传送一个信号, 有时还要传送更多信息(如传送数据), 需要更高级的线程间通信机制.

原语: send(), receive().

通信种类:

线程直接通信: 没有中间商

对称直接寻址 → 发送方指定接收方, 接收方也指定发送方(双向指定);

非对称直接寻址 → 发送方指定接收方, 接收方不明确指定发送方.

线程间接通信: 消息先发送到一个共享的消息队列(信箱)中临时保存, 一个线程给合适的信箱发送消息, 另一个线程从约定的信箱中取.

信箱的数据结构:

信箱头: 指出信箱容量, 信件格式, 存放信件位置的指针等;

信箱体: 分成若干个区, 每个区存放一封信件.

send() → 发送者等待信箱未满 → 将信件送入信箱并释放等待信件的接收者;

receive() → 接收者等待信箱中有自己的信 → 取出信件.

基于流的线程通信(管道): 多个线程使用共享的消息缓冲区, 一些线程向缓冲区写入字符流, 一些从缓冲区读出字符流. 信息交换单位基于字符流, 长度不受限制.

常见的并发缺陷

非死锁缺陷

违反原子性缺陷

定义: 违反多次内存访问中预期的串行性(即代码段预期是原子的, 但是没有实现原子性).

一般修复方法: 找到共享变量和互斥区, 加锁即可.

错误顺序缺陷

定义: 几次内存访问之间有固定的顺序要求, 但是实际运行时可能被线程调度打乱.

一般修复方法: 使用条件变量提供的同步机制来定义强制顺序.

死锁缺陷

概述

定义: 线程之间互相等待资源, 但是都不释放资源的现象.

💡

*所谓的”严格定义”: 一个线程集合中的每一个线程都等待只能由该集合中的另一个线程才能引发的事件, 则称这组线程或系统此时发生死锁.

死锁产生的条件

四个条件需要同时满足才能产生死锁:

互斥条件: 多个线程需要对共享的资源进行互斥的访问(等待的根源);

持有并等待条件: 线程持有了部分所需资源, 同时又在等待其他资源;

非抢占条件: 线程已经获得的资源不能被抢占或交出;

循环等待条件: 多个线程之间存在一个环路, 环路上每个线程都持有下一个线程正在等待的资源.

静态预防手段

消除循环等待: 为申请资源的行为提供一个全序(难以构造全序时偏序也可) 各个申请资源时遵循固定的顺序, 就不存在循环等待问题(不可能在等待前一个资源的情况下持有下一个资源). 等价于层次分配战略, 得到某一层的一个资源之后只能再申请更高层次的资源, 释放某一层次的资源时必须先释放更高层次的资源, 必须释放本层中已经占有的资源才能申请本层的另一个资源(实际上就是拓扑序).

消除持有并等待: 静态分配, 原子地抢占资源, 要么所有资源一次性全部拿到, 要么什么都不拿. 要在开始时而非使用时抢到所有资源, 可能会降低并发, 降低资源利用率.

消除非抢占: 碰壁时让出已占有的资源并重试.

消除互斥: 干脆避免使用互斥的资源, 使用原子的硬件指令. 但是有些资源具有天生的互斥性(如磁盘), 不能同时访问, 所以这种做法很多场合行不通.

银行家算法

以银行借贷系统的分配策略为基础, 判断并保证系统在资源分配时的安全运行, 从而避免死锁的发生.

理念: 在分配资源之前, 系统先检查: 假设这次分配完成, 系统是否仍然处于安全状态. 如果分配后系统处于不安全状态, 则拒绝这次分配, 让线程等待.

它把操作系统比作“银行家”, 把系统中的资源比作“资金”, 把线程比作“客户”. 银行家在客户申请贷款时, 会根据自身拥有的资金和客户的借款历史(最大需求量、已分配量)来判断是否可以满足这次贷款请求, 并且保证所有客户最终都能完成他们的项目并归还贷款.

关键数据结构:

Available[](可用资源): 一个数组, 表示每种类型当前可用的资源数量.

比如: Available[j] = k表示当前有k个类型为j的资源可用.

Max[][] (最大需求): 一个n×m矩阵, 表示每个线程最大需要的每种类型资源的数量. n是线程数, m是资源类型数(行代表线程, 列代表资源).

比如: Max[i][j] = k表示线程i最多需要k个类型为j的资源.

Allocation[][](已分配资源): 一个n×m矩阵, 表示每个线程当前已经分配到的每种类型资源的数量.

比如: Allocation[i][j] = k表示线程i当前已分配到k个类型为j的资源.

Need[][](尚需资源): 一个n×m矩阵, 表示每个线程还需要的每种类型资源的数量.

计算公式: Need[i][j] = Max[i][j] - Allocation[i][j]

工作流程:

银行家算法主要包含两个核心部分: 安全性算法和资源请求算法.

1. 安全性算法

用于检查当前系统是否处于安全状态. 如果存在一个安全序列(即一个线程的执行顺序, 使得每个线程在其执行完毕后都能获得其所需的所有资源并最终释放, 系统可以避免死锁), 则系统是安全的.

💡

算法思想: 不断找一个当前资源可以满足的线程, 假装完成运行它并释放资源, 判断最后能不能让所有线程全部运行完毕.

算法步骤:

初始化两个工作向量:

Available[][](表示当前可用的资源)

Finish[i] = false对所有线程i(表示线程i是否能完成)

寻找一个满足以下条件的线程i:

Finish[i] == false(线程i尚未完成)

Need[i] <= Work (线程i所需的资源数量小于等于当前可用的资源数量)

如果找到了这样的线程i:

for all j: Available[j] += Allocation[i][j](假设线程i执行完毕并释放其所有资源)

Finish[i] = true

返回步骤2迭代处理.

如果找不到这样的线程i:

检查所有Finish[i]是否都为true. 如果所有线程都已完成, 则系统处于安全状态, 存在一个安全序列. 否则, 系统处于不安全状态.

2. 资源请求算法

当一个线程P_i请求资源Request_i时, 系统会执行以下步骤:

检查请求是否合法:

如果Request_i <= Need[i](请求的资源不超过其声明的最大需求), 则进入下一步. 否则, 请求出错(线程请求的资源超过其声明的最大值).

检查可用资源是否满足请求:

如果Request_i <= Available(请求的资源小于等于当前可用资源), 则进入下一步. 否则, 线程P_i必须等待, 因为当前资源不足.

尝试分配资源(假设性分配):

暂时修改资源分配状态:

Available = Available - Request_i
Allocation[i] = Allocation[i] + Request_i
Need[i] = Need[i] - Request_i

运行安全性算法:

调用安全性算法检查新的系统状态是否安全.

如果新状态是安全的, 则实际分配资源给线程P_i, 并完成请求.

如果新状态是不安全的, 则撤销假设性分配(恢复到步骤3之前的状态), 并拒绝线程 P_i的请求, 让线程P_i等待.

优点:

避免死锁: 银行家算法能够有效地避免死锁的发生, 因为它总是在分配资源前检查系统的安全性.

资源利用率较高: 相对于死锁预防(预先阻止死锁发生的条件), 银行家算法允许更高的资源利用率, 因为它只在必要时才拒绝资源分配.

缺点:

需要预知最大需求: 每个线程在开始执行前必须声明其可能需要的每种资源的最大数量. 这在实际应用中往往很难做到.

线程数量和资源类型的固定性: 算法假设线程数量和资源类型在运行过程中是固定的, 如果动态添加或删除线程/资源, 算法需要重新计算.

计算开销大: 每次进行资源分配时都需要运行安全性算法来检查系统状态, 对于大型系统来说, 这会带来显著的计算开销.

资源必须是可重用的: 算法假设资源是可重用的(如CPU、内存、文件), 而不是消耗性的(如打印机的打印次数).

可能导致饥饿 (Starvation): 如果一个线程总是被拒绝资源请求, 它可能会永远等待下去, 导致饥饿.

一种理论上非常优雅的死锁避免策略, 通过对资源分配进行细致的控制, 确保系统始终处于安全状态.

由于其苛刻的先决条件(如需要预知最大需求)和较高的计算开销, 在实际操作系统中的应用有限.

动态避免手段

可能产生死锁的线程尽量不并发调度.

甚至当死锁不常见时, 就干脆允许死锁偶尔发生, 通过重启解决.

💡

为了尽可能避免死锁, 应该遵循非必要不使用锁的原则.

操作系统普遍采用预防死锁的方式.

数据库系统更多采用诊断并解除死锁的方式, 而非预防(因为代价太大).

诊断方式:

超时法: 如果一个事务的等待时间超过了规定的时限, 就认为发生了死锁. 优点: 实现简单; 缺点: 若时限设置过短则可能误判死锁, 若过长则不能及时处理;

等待图法: 并发控制子系统周期性地(比如每隔数秒)生成事务等待图, 检测事务. 如果发现图中存在回路, 则表示系统中出现了死锁(互相等待).

💡

*补充: 死锁定理

如果能在线程-资源分配图中消去一个线程的所有请求边和分配边, 就能让它成为孤立结点. 如果经一系列简化能使所有线程成为孤立结点, 则该图是可完全简化的, 否则则称该图是不可完全简化的. 系统为死锁状态的充分条件是该状态的线程-资源分配图是不可完全简化的. 该充分条件称为死锁定理.

解读:

进程-资源分配图是一种图形表示, 其中节点代表线程和资源, 有向边表示线程请求资源或资源被进程占用.

请求边: 从进程指向资源, 表示进程请求该资源.

分配边: 从资源指向进程, 表示该资源已被分配给该进程.

“消去此进程的所有请求边和分配边”: 这意味着假设一个进程能够完成其任务并释放其所占有的所有资源. 当一个进程完成后, 它不再需要任何资源, 也不再占用任何资源.

“成为孤立结点”: 当一个进程的所有请求边和分配边都被移除后, 它就与图中的其他节点断开了连接, 成为了一个孤立的节点.

“经一系列简化, 使所有进程成为孤立结点, 则该图是可完全简化的；否则则称该图是不可完全简化的. ”

一系列简化: 这是一个迭代过程. 我们首先找到一个可以完成的进程(即它的请求可以被满足的进程), 然后假设它完成并释放资源, 更新可用的资源, 然后寻找下一个可以完成的进程, 如此循环.
“可完全简化”: 如果通过这种迭代过程, 最终所有的进程节点都变成了孤立节点, 意味着所有的进程都可以顺利执行完毕而不会发生死锁. 在这种情况下, 图是可完全简化的.
“不可完全简化”: 如果在某个阶段, 我们找不到任何一个可以完成的进程(即所有剩余进程的请求都无法被满足), 那么简化过程就停止了. 在这种情况下, 图是不可完全简化的, 这通常意味着系统中存在死锁.

这条定理为我们提供了一种判断死锁的数学方法: 通过尝试简化资源分配图, 如果无法完全简化, 则表明有死锁发生.

孤立结点含义: 在进程节点的上下文中, 一个孤立的进程节点意味着这个进程已经完成了它的执行, 并且已经释放了它所占用的所有资源. 它不再有任何请求边, 也没有任何分配边指向它. 它的存在不再对资源的分配和死锁的检测产生影响. 通过将所有进程都变为孤立节点, 我们证明了所有进程都可以顺利完成, 系统是无死锁的.

可以借助银行家算法的思路, 根据线程当前申请资源量来判断系统是否进入了不安全状态.

解决方式:

重启整个系统(损失大)

撤销陷入死锁的全部线程, 继续运行

逐个撤销陷入死锁的线程, 回收资源, 直到死锁接触

剥夺死锁线程的资源, 但并不撤销, 直到死锁解除

所有进程回退到系统保存的上一个检查点

先等待未陷入死锁的线程执行完毕释放资源, 没准就可以拥有足够的资源解除死锁了

选择一个处理死锁代价最小的事务, 将其撤消, 释放此事务持有的所有的锁, 打破依赖环路, 使其它事务能继续运行下去.