3 同步、通信与死锁

第三章同步、通信与死锁

1、并发进程

顺序程序设计特点：

执行的顺序性
环境的封闭性
执行结果的确定性
计算过程的可再现性

并发的实质：处理器在几个程序之间的多路复用，是对有限的物理资源强制行使多用户共享，以提高系统的资源利用率

进程的无关性是进程执行与时间无关的一个充分条件，又称为Bernstein条件

R(pi)={a1,a2,…an}，程序pi在执行期间引用的变量集
W(pi)={b1,b2,…bm}，程序pi在执行期间改变的变量集
若两个程序的变量集交集之和为空集： R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={ }
则并发进程的执行与时间无关

并发程序设计的优点：

对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力
简化程序设计任务
对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度

采用并发程序设计的目的：

充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计
并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中

与时间有关的错误：一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现

结果不唯一
永远等待

进程的交往：竞争与协作

竞争：
- 资源竞争的两个问题：死锁和饥饿
- 进程互斥：指若干进程因相互争夺独占型资源而产生的竞争制约关系
协作关系：
- 某些进程为完成同一任务需要分工协作
- 进程同步：为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系
- 进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调

2、临界区管理

临界区：并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”

共享变量的并发进程应遵守临界区资源调度的三个原则：

一次至多一个进程能够进入临界区内执行
如果已有进程在临界区，其他视图进入的进程应等待
进入临界区内的进程应在有限时间内退出以便让等待进程的一个进入
即：
1. 互斥使用、有空让进
2. 忙则等待、有限等待
3. 择一而入、算法可行

实现临界区的软件算法：

Peterson算法

实现临界区管理的硬件设施：

关中断
- 进程上下文切换由中断事件引起，这样进程的执行再也不会被打断
- 实现互斥的最简单的方法
- 影响系统的性能和效率，一个处理器上的关中断，并不能防止其他处理器上执行相同的临界区代码
测试并设置指令TS
- 原语
对换指令

上述方法的缺点：

对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间
将测试能否进入临界区的责任推给各个竞争进程会削弱系统的可靠性，加重用户编程的负担

3、信号量与PV操作

生产者--消费者问题：生产者和消费者进程交替运行会导致进程永远等待

信号量：一种软件资源

一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)
操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量
实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针
按用途分为：
- 公用信号量
- 私有信号量
按取值：
- 二元信号量
- 一般信号量
一般信号量：
- 设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue, P和V操作原语定义：
  - P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。
  - V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程
- 推论：
  - •推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数
  - •推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数
  - •推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作
二元信号量：
- •设s为一个记录型数据结构,一个分量为value,它仅能取值0和1,另一个分量为信号量队列queue, 把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：
信号量实现互斥：
PV操作只对信号测试一次，TS指令必须反复测试，造成忙式等待

原语：内核中执行时不可被中断的进程

p操作原语和V操作原语

4、管程

引入管程：

把分散在各进程中的临界区集中起来进行管理
防止进程有意或无意的违法同步操作
便于用高级语言来书写程序，也便于程序正确性验证

管程：管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块

属性：共享性、安全性、互斥性
一般形式：
结构：
条件变量-是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它
wait( )-挂起调用进程并释放管程，直到另一个进程在该条件变量上执行signal( )
signal( )-如果存在其他进程由于对条件变量执行wait( )而被挂起，便释放之；如果没有进程在等待，那么，信号不被保存
- 使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：
- 执行signal的进程等待，直到被释放进程退出管程或等待另一个条件 ·
- 被释放进程等待，直到执行signal的进程退出管程或等待另一个条件

管程与进程比较：

管程定义的是公用数据结构，而进程定义的是私有数据结构
管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中
管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的
管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性
管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡

5、进程通信

并发进程之间的交互必须满足两个基本要求：同步和通信

进程之间互相交换信息的工作称为进程通信IPC（InterProcess Communication）

进程需要通信的情况：

共享资源
协调工作
并发控制
通知进程
传递数据

通信方式：

信号通信机制
- 软中断：中断与异常要通过硬件设施来产生中断请求，称为硬中断。不必由硬件产生中断源而引发的中断称为软中断。软中断是利用硬中断的概念，采用软件方法对中断机制进行模拟，实现宏观上的异步执行。“信号”是一种软中断机制
- 用法：
  - “中断”（硬中断）用于外部设备对CPU的中断，中断正在运行的任何程序，转向中断处理程序执行
  - “异常”（硬中断）因指令执行不正常而中断CPU，中断正在执行这条指令的程序，转向异常处理程序执行
  - “信号”(软中断)，用于内核或进程对某个进程发出中断，向进程通知某个特定事件发生或迫使进程执行信号处理程序
- 与信号机制类比：
  - 概念上是一致的，都是异步的，均采用向量表实现，均有屏蔽设施
  - 前者由硬件和软件实现，后者完全由软件实现
  - 中断向量表和中断处理程序均位于系统空间，而信号处理程序由应用程序提供，并在用户空间执行
- 信号机制又称软中断，一种简单的通信机制，通过发送一个指定信号通知进程某个异常事件发生
- 进程处理信号的三类：忽略信号、捕获信号、执行缺省操作
- 实现：
管道通信机制
- 管道(pipeline)是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据,也能使进程同步执行操作
- 发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信
- 管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写
消息传递通信机制
信号量通信机制
共享内存通信机制

7、死锁

死锁：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁

形成死锁的四个必要条件：

互斥条件：进程互斥使用资源
占有和等待条件：请求资源得不到满足时，不释放已占有资源
不剥夺条件：一个进程不能抢夺其他进程占有1资源
循环等待条件

死锁防止：破坏三个条件之一，第四个条件采用层次分配

死锁避免：

银行家算法：
应满足当前系统中所有进程对资源Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数
系统安全性定义：在时刻T0系统是安全的,仅当存在一个进程序列P1,..,Pn,对进程Pk满足公式：

Need[k,i] ≤Available [i]+ ∑Allocation[j,i]

k=1,…,n;i=1,…,m;
基本思想：
- 系统中的所有进程进入进程集合, •在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。
- 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。
- 把这个进程从集合中去掉, 系统的剩余资源更多了,反复执行上述步骤。
- 最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可实施本次分配;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待
分配步骤：
1. 如果 Request［i, *］≦Need[i,*]，转步骤（２）；否则，进程申请量超过最大需求量，出错处理
2. w*］≦Available [*]，转步骤（3）；否则，申请量超过当前系统拥有的可分配量，进程P i 等待
3. 系统对 P i进程请求资源进行试探性分配，执行：
  
           Allocation［i ，* ］＝ Allocation［i ，* ］＋ Request［i . * ］
  
           Available［* ］＝ Available［* ］－ Request［i , * ］
  
           Need［i , * ］＝Need［i , * ］- Request［i , * ］
4. 转向（5）执行安全性测试算法，如果返回安全状态则承认试分配，否则，抛弃试分配，进程 P i等待，并执行；
  
          Allocation［i ，* ］＝ Allocation［i ，* ］ - request［i , * ］
  
          Available［ * ］＝ Available［ * ］ + Request［i, * ］
  
          Need［i , * ］＝Need［i, * ］+ Request［i , * ］
5. 安全性测试算法
  1. 定义工作向量 Work[i ]、布尔型标志 possible 和进程集合 rest
  2. 执行初始化操作：让全部进程进入 rest 集合，并让：
    Work［*］＝Available［*］，possible ＝true
  3. 保持 possible ＝true，从进程集合 rest 中找出满足下列条件的进程 P k ：
    
    Need［k，*］≤ Work［*］
  4. 如果不存在，则转向⑤；如果找到，则释放进程 P k 所占用的资源，并执行以下操作：
    
    Work［*］＝ Work［*］＋ Allocation［k，*］
    把 P k 从进程集合中去掉，即 rest ＝ rest －｛Pk｝，再转向③
  5. 置 possible ＝false，停止执行本算法
  6. 最后，查看进程集合 rest，若其为空集则返回安全标记；否则，返回不安全标记
每个进程目前还需资源为Need[k,i]
可以断言目前系统处于安全状态,因为,T0时刻序列{P1,P3,P4,P2,P0}能满足安全性条件

死锁检测和解除：

资源分配图：
- 约定Pi→Rj为请求边，表示进程Pi申请资源类Rj中的一个资源得不到满足而处于等待Rj类资源的状态，该有向边从进程开始指到方框的边缘，表示进程Pi申请Rj类中的一个资源
- Rj→Pi为分配边，表示Rj类中的一个资源已被进程Pi占用，由于已把一个具体的资源分给了进程Pi，故该有向边从方框内的某个黑圆点出发指向进程
检测：
- 如果进程-资源分配图中无环路，则此时系统没有发生死锁
- 如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程
- 如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件
如果能在进程-资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的
死锁定理：系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理

死锁的解除：

结束所有进程的执行，重新启动操作系统。方法简单，但以前工作全部作废，损失很大。
撤销陷于死锁的所有进程，解除死锁继续运行。
逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除
剥夺陷于死锁的进程占用的资源，但并不撤销它，直至死锁解除。可仿照撤销陷于死锁进程的条件来选择剥夺资源的进程
根据系统保存的检查点，让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制
当检测到死锁时，如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，有可能释放足够的资源来解除死锁