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

type

status

date

slug

summary

概述

💡

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

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

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

线程定义

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

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

💡

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

进程切换开销大

进程通信开销大

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

不适合并行计算的要求

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

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

💡

为什么要这样设计?

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

资源不需要频繁切换, 进程之间互相隔离, 维持资源分配的独立性, 是系统资源分配和保护的独立单位;

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

线程调度

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

💡

调度实例

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

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

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

…(任意顺序均有可能)

临界区

💡

无关的并发线程: 一组并发线程分别运行在不同的变量集合上, 一个线程的执行与其他并发线程的进展无关 → 进程的执行与时间无关(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和队列操作的原子性. 它只涉及同时申请锁时的并发控制, 不涉及用户定义的临界区代码, 故自旋等待时间一般不会很久, 开销可以接受.

实现八: 混合方案

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

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

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

条件变量

概述

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

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

💡

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

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

使用条件变量

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

💡

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

两个疑问:

💡

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

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

void thread_exit() { done = 1; pthread_cond_signal(&c); }

void thread_join() { while (done == 0) // 若在此处被打断, 会发生什么? pthread_cond_wait(&c, &m); }

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

💡

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

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

void thread_exit() { pthread_mutex_lock(&m); pthread_cond_signal(&c); pthread_mutex_unlock(&m); } void thread_join() { pthread_mutex_lock(&m); // 子线程是否已经完成了? pthread_cond_wait(&c, &m); pthread_mutex_unlock(&m); }

如果在父线程调用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()来唤醒. 所以正信号量代表当前可并发执行的线程数, 负信号量代表等待的线程数.

信号量用作条件变量

💡

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

将信号量初始值设为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指向相同的数据项, 则并发访问很可能就会出现问题.

读者-写者锁

💡

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

核心思想: 写只能串行(写时阻止任何读者或其他写者访问), 读可以并发(只要没有写者在写就可以允许任意个数的读者并发读取).

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

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

哲学家就餐问题

💡

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

概述

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

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

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

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

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

打破循环, 避免死锁.

还有其他方案:

至多允许四个哲学家同时取叉子(C.A.R. Hoare方案);

奇数号先取左手边的叉子, 偶数号先取右手边的叉子;

每个哲学家取到手边的两把叉子才吃, 否则一把叉子也不取.

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

睡眠的理发师问题

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

农夫猎人问题

有一个铁笼子, 每次只能放入一个动物. 猎手向笼中放入老虎, 农夫向笼中放入羊; 动物园等待取笼中的老虎, 饭店等待取笼中的羊.

银行业务问题

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

售票问题

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

吸烟者问题

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

信号量的实现

💡

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

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

常见的并发缺陷

非死锁缺陷

违反原子性缺陷

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

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

错误顺序缺陷

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

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

死锁缺陷

概述

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

死锁产生的条件

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

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

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

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

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

静态预防手段

消除循环等待: 为申请资源的行为提供一个全序(难以构造全序时偏序也可), 各个申请资源时遵循固定的顺序, 就不存在循环等待问题(不可能在等待前一个资源的情况下持有下一个资源);

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

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

消除互斥: 干脆避免使用互斥的资源, 如使用原子的硬件指令.

动态避免手段

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

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

💡

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

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

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

诊断方式:

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

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

💡

事务等待图是一个有向图 .

为结点的集合, 每个结点表示正运行的事务;

为边的集合, 每条边表示事务等待的情况.

若T1等待T2, 则在T1与T2之间划一条从T1指向T2的有向边.

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