第三章 进程同步与通信

3.1 进程同步的基本概念

3.1.1 并发进程的关系

• 多个并发执行的进程的两种关系
  • 无关——可以保证程序的可再现性
  • 相关（存在以下两种相互制约关系）——不可保证程序的可再现性
    • 间接制约关系（资源共享）——进程互斥
    • 直接制约关系（进程间协作）——进程同步

3.1.2 进程互斥与同步

• 进程同步：进程之间相互合作等待对方消息的协调关系
• 进程互斥：某一资源同一时间只允许一个进程对其进行访问，这种访问具有排他性和唯一性
  • 饥饿：一个进程所申请的资源总是被优先于自己的其他进程所占有，而长时间处于不能被调度执行的状态（长时间处于就绪或阻塞状态）
  • 死锁：一个进程集合中已经占有部分资源的两个或两个以上进程，还需要获得被其他进程占有的资源才能继续运行，有可能出现某些进程相互之间都在等待对方占有的资源二无法运行的局面

3.1.3 临界资源与临界区

• 临界资源：一段时间内只允许一个进程使用的资源
• 临界区：进程中访问临界资源的代码段
• 同步机制的四条准则
  • 空闲让进
  • 忙则等待
  • 有限等待
  • 让权等待

3.2进程互斥方法

3.2.1 实现进程互斥的硬件方法

1. 开关中断指令
   • 缺点：如果关中断时间过长，回使系统效率下降、若关中断不当，有可能导致系统无法正常调度进程的运行
2. 测试与设置指令（Test and Set,TS）——没有遵循让权等待原则
   • 采用TS方法要为每个临界资源设置一个整型变量s
3. 交换指令(Swap)——没有遵循让权等待原则
   • 要为每个临界区设置一个整型全局变量，还要为每个进程设置一个整型局部变量key

3.2.2 实现进程互斥的软件方法（代表性）

1. 两标志进程互斥算法
   • 两标志算法不能很好解决两个进程同时到达的情况
2. 三标志进程互斥算法（Peterson算法）

3.3 信号量机制

3.3.1 信号量

信号量除初始化外，在其他情况下其值只能由P和V两个原语操作才能改变

1. 整型信号量——没有遵循“让权等待”原则
2. 结构体型信号量
   • 资源信号量：用于系统互斥资源信号的互斥管理，它涉及系统互斥资源的分配与回收
   • 控制信号量：用于除系统互斥资源之外的进程同步与互斥控制，不涉及系统互斥资源的分配与回收

3.3.2 使用信号量实现进程互斥

3.3.3 使用信号量实现进程同步

3.4 经典互斥同步问题

3.4.1 生产者-消费者问题

3.4.2 哲学家进餐问题

3.4.3 读者写者问题

3.4.4 睡眠理发师问题

3.5经典互斥同步问题的应用

3.5.1 缓冲区数据传送问题

3.5.2 吃水果问题

3.5.3 汽车过桥问题

3.6 管程机制

为了解决信号量带来的不便而引入了管程同步机制

3.6.1 条件变量与管程结构

1. 条件变量
2. 管程结构
   • 一个管程定义了一个数据结构和在该数据结构上执行的一组过程（函数），这组过程（函数）能够同步和改变管程中的局部数据
   • 管程的五个性质
   • 管程主要由三部分组成
     • 局部于管程内的数据结构
     • 管程内共享数据的初始化语句
     • 一组对管程内数据结构进行访问的调用过程（函数）
   • 使用管程实现进程同步的三个特点
     • 管程内的数据结构只能由管程定义的过程（函数）访问，任何外部过程（函数）都不能访问他们
     • 任何时刻只能有一个进程在管程中执行，其他申请进入管程的进程必须阻塞等待
     • 一个外部过程（函数）只有通过调用管程内的一个过程（函数）才能进入管程

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

3.6.3 哲学家进餐问题的管程解决

3.6.4 读者-写者问题的管程解决

3.6.5 睡眠理发师问题的管程解决

3.6.6 吃水果问题的管程解决

3.7 进程通信

3.7.1 进程通信的概念

• 根据交换信息量的大小分
  • 低级通信
  • 高级通信
    • 共享内存通信方式
    • 消息传递通信方式（可分为直接通信/消息缓冲通信和间接通信/信箱通信）
    • 共享文件通信方式（又称管道通信）

3.7.2 共享内存通信方式

3.7.3 消息缓冲通信方式

3.7.4 信箱通信方式

3.7.5 管道通信方式

3.8 死锁

3.8.1 产生死锁的原因和必要条件

• 系统资源
  • 可抢占资源（一般不会因为课抢占资源进入死锁状态）
  • 不可抢占资源（讨论死锁所指的资源都是不可抢占资源）-必然是互斥资源
• 死锁：多个进程在并发执行过程中因争夺不可抢占资源而造成的一种僵局
• 死锁（资源死锁）与程序设计中的死循环不同
  • 从产生来看。死锁具有偶然性，二死循环则有必然性
  • 从进程状态来看。一组进程处于死锁则它们都处于阻塞状态，即它们都没有占用CPU运行，而死循环程序则始终占用CPU运行
  • 从产生的原因看。死锁是由于操作系统采用多道程序的并发执行与进程之间对不可抢占资源的共享引起的，即与操作系统的管理和控制有关;而死循环则是因程序员的程序设计不当或编写错误造成的
• 死锁与饥饿的本质不同
  • 饥饿状态的进程是长时间得不到所需资源或CPU (进程处于阻塞态或就绪态)，一旦得到所需资源及CPU后就可以立即运行;而处于死锁状态的这些进程之间都在相互等待对方占用的资源，而又不释放自己所占用的资源，即造成了彼此永远都无法得到所需资源的僵局出现，因此它们都处于永远的阻塞状态而无法运行
  • 处于死锁状态的各进程都相互等待被对方占用的资源，因此处于死锁状态的进程至少有两个;而处于饥饿状态的进程仅是因为没有调度它执行(进程处于就绪状态)，或者是暂时没有获得所需资源(进程处于阻塞状态)，故饥饿状态可能只有一个进程
• 产生死锁的原因
  • 系统资源不足
  • 进程推进顺序不当
• 产生死锁的四个条件
  • 互斥条件
  • 请求和保持条件
  • 不可抢占（不剥夺）资源
  • 循环等待条件

3.8.2 死锁的预防

通过破坏死锁的必要条件来控制死锁的策略称为死锁预防（只破坏条件：互斥条件是不行的）

• 破坏“请求和保持”条件
• 破坏“不可抢占”条件
• 破坏“循环等待”条件

3.8.3 死锁的避免

• 系统的安全状态和不安全状态
  • 资源角度
  • 死锁角度（此处涉及概念：安全状态、安全序列）

3.8.4 死锁的检测与解除

• 死锁检测：通过周期性执行一个检测算法来检测是否会产生“循环等待”的条件
  • 资源分配图
  • 资源分配图的化简
• 死锁定理：某一时刻系统状态S为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全化简的，此充分条件称为死锁定理
  • 如果资源分配图中不存在环路，该资源分配图对应的系统状态是安全的，不会发生死锁。
  • 如果资源分配图中存在环路，且每类资源节点中只有一个资源，则系统一定发生死锁，环路中的进程就是死锁进程。
  • 如果资源分配图中存在环路，但所关联的资源节点有多个同类资源，那么这时环路的存在只是死锁发生的必要条件而不是充分条件。也就是说系统发生死锁时，资源分配图必定出现环路，而系统资源图出现环路时，则不一定 发生死锁。
• 死锁检测算法
  • 系统可用资源向量Available
  • 分配矩阵Allocation
  • 请求矩阵Request
• 死锁解除方法
  • 撤销所有死锁进程
  • 让死锁进程回撤到正常执行状态的某个检查点，然后重新启动所有的进程
  • 按照某种顺序逐个撤销死锁进程，直到不再发生死锁为止
  • 采用抢占资源的策略直到不再发生死锁
• 死锁解除中代价最小原则
  • 到死锁发现时，消耗的CPU时间最少
  • 到死锁发现时，获得系统资源的总量最少
  • 到死锁发现时，产生的输出量最少
  • 优先级最低
  • 预计进程的剩余时间最长