分布式系统中的死锁

《分布式系统中的死锁》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章分布式系统中的死锁6.1死锁问题死锁发生的条件(1)互斥。正如我们第五章所讨论的，互斥是一种资源分配方式，保证同一个资源在同一时刻最多只能被一个进程占用，它用于防止多个进程同时共享访问不可同时共享访问的资源。(2)不可剥夺的资源分配。系统将一个资源的访问权分配给某一个进程后，系统不能强迫该进程放弃对该资源的控制权。(3)占有并等待。必然有一个进程占用了至少一个资源，同时在等待获取被其他进程占用的资源。(4)循环等待。在等待图中有一个循环路径。第六章分布式系统中的死锁6.1死锁问题死锁的图论模型可以用图模型来表示死锁，表示死锁

2、的图模型有两种，一种是等待图，另一种是资源分配图。在等待图中，节点代表进程，当且仅当进程Pi等待一个被进程Pj所占用的资源时，边(Pi,Pj)存在于等待图中，图中的边是有向的。资源分配图中的节点有两种：一种是进程节点，另一种是资源节点。每个边是一个有序对(Pi,Rj)或(Rj,Pi)，其中P代表进程，R代表一个资源类型。边(Pi,Rj)表示进程Pi请求类型为Rj的一个资源，并且正在等待这个资源，一个资源类型中可能有多个资源。边(Rj,Pi)表示类型为Rj的一个资源已经分配给进程Pi。由于等待图假定一个资源类型中只有一个资源，所以资

3、源分配图是一个比等待图更加有力的工具。第六章分布式系统中的死锁6.1死锁问题死锁的图论模型资源分配图实例：第六章分布式系统中的死锁6.1死锁问题死锁的图论模型资源分配图到等待图的转化：(1)在资源分配图中找到一个未被处理的资源R。如果所有的资源都已经处理，转向步骤3。(2)从这个资源R的每个输入进程节点到每个输出进程节点之间加一条有向边。一个资源的输入进程节点是等待这个资源的进程节点，一个资源的输出进程节点是占有这个资源的进程节点。转向步骤1。(3)删除所有的资源节点以及相应的边。第六章分布式系统中的死锁6.1死锁问题死锁的图论模

4、型资源分配图到等待图的转化实例：第六章分布式系统中的死锁6.1死锁问题处理死锁的策略死锁可以使用PAID来概括死锁处理的各种方法：预防(Prevent)、避免(Avoid)、忽略(Ignore)和检测(Detect)。预防死锁。通过限制请求，保证四个死锁条件中至少有一个不能发生，从而预防死锁。避免死锁。如果资源分配会导致一个安全的结果状态，就将资源动态地分配给进程。如果至少有一个执行序列使所有的进程都能完成运行，那么这个状态就是安全的。忽略死锁。忽略死锁是UNIX常采用的一种方法，这种方法只是简单地忽略死锁问题。检测死锁和从死锁中

5、恢复。允许死锁发生，然后发现并解除死锁。第六章分布式系统中的死锁6.1死锁问题死锁的AND条件和OR条件资源死锁和通信死锁：在通信死锁中，进程等待的资源就是报文。资源死锁和通信死锁的真正区别在于资源死锁通常使用AND条件，而通信死锁通常使用OR条件。所谓AND条件就是当进程取得所有所需资源时，它才能继续执行；所谓OR条件就是当进程得到至少一个所需资源，它就能继续执行。在使用AND条件的系统中，死锁条件是在等待图中存在回路。但是在使用OR条件的系统中，等待图中的回路未必会引发死锁。在使用OR条件的系统中，死锁条件是存在结(knot)

6、。一个结K是一个节点集合，对于K中的任何节点a，a能到达K中的所有节点，并且只能到达K中的节点。第六章分布式系统中的死锁6.1死锁问题死锁的AND条件和OR条件OR条件死锁图例：第六章分布式系统中的死锁6.2死锁的预防预防死锁的一般方法死锁预防算法是通过限制进程的资源请求来达到预防死锁的目的，都是通过打破四个死锁条件中的一个条件来实现的。进程在开始执行之前同时获得所有所需资源。这种方法打破了占有并等待的条件。所有的资源都要被赋予一个唯一的数字编号。一个进程可以请求一个有唯一编号i的资源，条件是该进程没有占用编号小于或等于i的资源。

7、这样，就打破了循环等待的条件。每个进程被赋予一个唯一的优先级标识。优先级标识决定了进程Pi是否应该等待进程Pj，从而打破了不可剥夺的条件。第六章分布式系统中的死锁6.2死锁的预防基于时间戳的预防死锁方法包括两种死锁预防方案。这两种方案相互补充，这种方法常用于分布式数据库系统中。等待—死亡方案(wait-diescheme)。该方案是基于非剥夺方法。当进程Pi请求的资源正被进程Pj占有时，只有当Pi的时间戳比进程Pj的时间戳小时，即Pi比Pj老时，Pi才能等待。否则Pi被卷回(roll-back)，即死亡。伤害—等待方案(wound

8、-waitscheme)。它是一种基于剥夺的方法。当进程Pi请求的资源正被进程Pj占有时，只有当进程Pi的时间戳比进程Pj的时间戳大时，即Pi比Pj年轻时，Pi才能等待。否则Pj被卷回(roll-back)，即死亡。第六章分布式系统中的死锁6.2死