mutex: mutual exclusion
只有可能互斥的对象之间才需要有mutex
1. 并发进程
1.1. 顺序程序设计
1.2. 进程的并发性
并发进程分类：
- 无关的
- 交互的
$\text{Bernstein}$ 条件: 并发进程的无关性是进程的执行与时间无关的一个充分条件
程序 $p_i$ 在执行期间改变的变量集 为 $W(p_i) = \{b_1, b_2, ...b_m\}$
两个进程的程序 $p_i$ 和 $p_j$ 满足$\text{Bernstein}$ 条件 $\iff$
- $R(p_i) \cap W(p_j) = \phi$
- $R(p_j) \cap W(p_i) = \phi$
- $W(p_i) \cap W(p_j) = \phi$
在这样的条件下, 并发进程的执行与时间无关
两个问题
- 机票问题
- 主存管理问题
1.3. 进程的交互：竞争和协作
竞争与协作是进程之间的两种基本的关系
竞争关系带来两种问题:
- 死锁
- 饥饿
这里参考了这篇文章
为了解决进程间竞争关系（间接制约关系）而引入进程互斥；
为了解决进程间松散的协作关系( 直接制约关系)而引入进程同步；
为了解决进程间紧密的协作关系而引入进程通信。
2. 临界区管理
2.1. 互斥与临界区
并发进程中涉及到共享变量的程序段叫 “临界区” (critical section), 共享变量代表的资源叫“临界资源”.
2.2. 临界区管理的尝试
直接尝试: 有bug
临界区管理的软件方法: Peterson算法 (设计比较巧妙, 能够实现良好的临界区管理)
临界区管理的硬件方法:
- 关中断
- 测试并建立指令
- 对换指令
硬件这一部分跳过了, 不知道重不重要
2.3. 实现临界区管理的硬件设施
3. 信号量与PV操作
“忙式等待”方法解决临界区调度问题的缺点
上面的Peterson算法属于忙式等待的方法: 也就是一种轮询, 要一直查看是否互斥对象忙. 显然对象很多时, Peterson算法需要for嵌套while, 时间复杂度很高, 而且一直占用CPU, 设计不是很合理. 同时从软件工程的角度来讲, 将测试能否进入临界区的职责 (responsibility) 推给各个竞争的进程会削弱系统的可靠性, 加重用户编程负担
我们在这里提出阻塞式等待的方法: 也就是所谓的PV操作, 我们这里不需要进程来查看共享资源是否被占用, 相反地, 当资源的占有情况发生改变的时候, 我们会主动通知进程
哲学家就餐问题的一些解决方案
- 至多允许四个哲学家同时取叉子(C. A. R. Hoare方案)
- 奇数号先取左手边的叉子，偶数号先取右手边的叉子
- 每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取 (第五版教材, Page 188, AND型信号量)
4. 管程
4.1. 管程和条件变量
管程的定义: 管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块
管程的概念是由Brinch Hansen提出的, 但是由Hoare改进
4.2. 管程的实现
4.3. 管程求解进程的同步与互斥问题
5. 进程通信
直观上感觉挺 trivial, 但是仔细一想感觉蛮神奇.
但是第五节并不考, 所以没空看了