并发 – Notes

并发

并发进程的特点
- 分类
  - 互斥关系：对资源共享引起，是间接制约关系。
  - 同步关系：协作完成同一个任务、需要互相等待同步引起，是直接制约关系。
  - 前序关系：由互斥、同步关系引起，决定各个进程的创建和终止时间。
- 顺序
  - 间接制约关系的进程可以并发，但是可能会互斥执行。
  - 直接制约关系的进程要顺序执行。
互斥
- 临界区
  - 临界资源：一次只允许一个进程访问的共享资源。
  - 临界区：访问临界资源的必须互斥执行的程序。
- 进入临界区的准则
  - 互斥使用：不能有两个或以上的进程在临界区执行。
  - 让权等待：等待进入的进程，要释放 CPU 并阻塞等待。
  - 有空让进：在临界区外的进程不可以阻止其他进程进入临界区。
  - 有限等待：等待过程不可以无限长。
- 软件实现
  - 实现复杂，不够灵活。
- 硬件实现
  - 关中断：简单、限制了并发能力、使进程权限过高、对多 CPU 无效。
  - 硬件指令：原子变量 CAS，实现自旋锁，会浪费 CPU 时间。
- 信号量
  - 信号量可以完成互斥功能，并且可以使进程阻塞等待，不会浪费 CPU。
信号量
- 定义
  - 信号量包含 value 和一个进程队列（指针）processes。
  - value 大于等于 $0$ 时表示可以资源数量，小于 $0$ 时表示等待进程数量。
- 操作
  - 信号量包含 P 操作（acquire）和 V 操作（release）。
  - P：表示获取资源。递减 value，如果递减后小于 $0$ ，则把当前进程加入队列。
  - V：表示释放资源。递增 value，如果队列中有进程，取出一个并唤醒。
  - P/V 操作是原语，不可中断。
- 实现互斥锁
  - 对于一个需要互斥保护的资源，定义一个信号量 mutex，初值为 $1$ 。
  - 访问资源时，使用 P(mutex)，不需要访问时，使用 V(mutex)。
  - mutex.value 的取值为 $(-\infty, 1]$ 。
- 实现通道/同步队列/MPMC
  - 对于一个长度为 $n$ $n$ 的通道，有三种资源：
    - 空位置：用 empty 表示，初值为 $n$ （通道初始为空）。
    - 已写位置：用 full 表示，初值为 $0$ 。
    - 通道修改权限：用 mutex 表示，初值为 $1$ 。
  - Send/Produce：按顺序执行 P(empty)、P(mutex)、插入、V(full)、V(mutex)。
  - Receive/Consume：按顺序执行 P(full)、P(mutex)、删除、V(empty)、V(mutex)。
  - mutex 的使用：
    - 对于 $n > 1$ ，可能存在多个进程可以同时修改通道，需要用互斥锁。
    - 对于 $n = 1$ ，可以不需要 mutex，empty 和 full 之间的关系保证不会有竞争。
  - P(empty)/P(full) 和 P(mutex) 不可以交换，否则可能造成死锁。
- 实现读写锁
  - 使用以下数据：
    - 写权限：wmutex 信号量，初值为 $1$ 。
    - 修改读进程数权限：rmutex 信号量，初值为 $1$ 。
    - 读进程数：count，初值为 $0$ 。
  - 读：按顺序执行：
    - P(rmutex)。
    - 如果 count 等于 $0$ ，则 P(wmutex)，因为接下来开始有读操作，不可以写。
    - 递增 count。
    - V(rmutex)。
    - 读操作。
    - P(rmutex)
    - 递减 count。
    - 如果 count 等于 $0$ ，则 V(wmutex)，因为最后一个读操作已完成，接下来可以写。
    - V(rmutex)。
  - 写：按顺序执行：
    - P(wmutex)。
    - 写操作。
    - V(wmutex)。
高级通信
- 方式
  - 消息缓冲：从发送进程复制消息体到系统缓冲区，再把缓冲区添加到接收进程 PCB（无复制）。
  - 信箱
  - 管道：是文件，但在硬盘上无内容。连接写进程和读进程。
  - 共享内存：最快捷。
死锁
- 必要条件
  - 互斥条件：需要访问临界资源。
  - 保持和等待条件：进程请求其他资源而阻塞时，不释放已获得资源。
  - 不剥夺条件：已经分配给进程的资源只能由进程释放。
  - 循环等待：每个进程等待另外一个进程的资源，最终依赖于自身。
- 解决方法
  - 鸵鸟算法：忽略死锁。
  - 预防死锁：破坏死锁的必要条件，使死锁不可能发生。
    - 避免互斥条件：用 spooling 技术把单个设备改造为多个设备，但不适用于所有设备，也可能失败。
    - 避免保持和等待条件：提取获取所有需要的资源，但难以预测需要的资源有哪些。
    - 避免不剥夺条件：允许资源被其他进程释放，但代价高、破坏正确性。
    - 避免循环等待：为资源编号，所有进程按顺序获取，但难以找到符合条件的编号。
  - 避免死锁：分配资源过程中检查分配，防止系统进入不安全状态。
    - 银行家算法。
  - 检测死锁并恢复。
- 银行家算法
  - 设有 $m$ 个进程和 $n$ 种资源，每种资源可以有不同的数量。
  - 符号定义：
    - 已分配资源矩阵：每一行对应进程，每一列对应资源，矩阵元素表示进程已获得的这种资源数量。
    - 剩余请求资源矩阵 $R$ ：每一行对应进程，每一列对应资源，矩阵元素表示进程未来还需要的这种资源数量。
    - 剩余资源向量 $A$ ： $1 \times n$ 行向量，每一列对应资源的剩余数量。
  - 判断状态是否安全：
    - 若 $R$ 存在一行 $R_i$ ，使得 $R_i \le A$ ，则当前状态不会死锁，否则当前状态不安全。
    - 若找到 $R_i$ ，则假设进程 $i$ 接下来可以获得资源并运行结束，标记为终止，收回 $R_i$ 并加到 $A$ 上。
    - 重复，直到所有进程都标记为终止，则此状态安全，否则不安全。
- 死锁检测和恢复
  - 检测方法：
    - 把进程和资源都抽象为有向图节点。
    - 如果进程 $P$ 已获得资源 $R$ ，则连边 $R \to P$ ；如果 $P$ 请求 $R$ ，则连边 $R \to P$ 。
    - 检查有向图是否存在回路，如果存在则有死锁。
  - 恢复方法：
    - 终止进程：
      - 终止所有进程
      - 一次终止一个死锁进程，直到死锁接触。
    - 资源剥夺：
      - 直接取走资源给另外一个进程使用。
      - 回滚进程到获取资源前的检查点。

线程