死锁

死锁概念

死锁可以定义为一组相互竞争资源或进行通信的进程间的“永久”阻塞。

死锁的产生

• 竞争不可抢占性资源引起死锁
  假设有两个进程A、B
  A和B都需要对文件f1、f2进行写操作。
  一个进程都必须独占f1、f2文件才能进行。
  
  A、B并发执行，A得到了f1、B得到了f2，A需要f2但在B手里、B需要f1但在A手里，他们将无法继续进行下去，从而形成死锁。

• 竞争可消耗资源所引起的死锁

A需要的资源在C手中、C所要资源在B手中、B所要资源在A手中。
类似于三角债。

• 进程推进顺序不当引起死锁
  

如果A进行到Req(R1)时，B进行到Req（R2）时 就会发生死锁。
但是如果A先执行完，再执行B就不会发生死锁。

产生死锁的必要条件

1. 互斥条件

进程对于分配到的资源进行排他性使用，即在一段时间内
某个资源只能被一个进程占用

2. 请求和保持条件

进程已经保持了至少一个资源，但是又提出了新的资源需求，而这个新资源又被别的进程占有
此时请求进程被阻塞，但对自己拥有的资源不释放。

3. 不可抢占条件

进程已经获得的资源在未使用完前不可被抢占，只能由进程使用完自己释放。

4. 循环等待条件

在发生死锁时，必然存在进程等待资源的循环链。

处理死锁的方法

• 预防死锁
  预防死锁的方法是通过破坏产生死锁的四个必要条件的一个或几个，以避免发生死锁。互斥条件是非共享设备所必须的，不仅不可以改变，还需要来保证。只能破坏剩下的三个条件。

  • 破坏“请求和保持条件”
    1、第一种协议
    一次性将进程所需要的资源全部分配，只要有一个没有就不给分配。
    这样就破坏了“请求条件”。
    缺点 ：

    (1)资源被严重浪费，影响资源利用率 进程有可能一开始并不使用获取到的资源
    (2)使进程时常发生饥饿现象

    2、第二种协议
    该协议为第一种协议的改进，它允许进程得到初期运行的所需的资源（可不用全要，只要进程可以向前推进）。进程运行过程中逐步释放占有资源。

  • 破坏“不可抢占”条件
    当一个已经保持了某些不可被抢占资源的进程，提出新的资源请而不能得到满足时，它必须释放已经保持的所有资源，待以后使用时再重新申请。

  • 破坏“循环等待”条件
    一个能保持“循环等待”条件不成立的方法是：对系统所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按照序号递增的顺序请求资源。一个进程在开始时，可以请求某类资源Ri的单元。以后，当且仅当F(Rj) > F(Ri)时，进程才可以请求资源Rj的单元。如果需要多个同类资源单元，则必须一起请求。
    例如：当某进程需要打印机和磁带机时，（假设磁带机序号低，打印机磁带序号高），故必先请求磁带机，再请求打印机。如果进程拥有较高序号的资源，现在请求较低资源序号的资源，它必须释放所具有相同和更高序号的资源，才能申请低序号的资源。

• 避免死锁
  这种方法相对预防死锁限制条件较弱。

  • 系统安全状态
    在死锁避免方法中，把系统的状态分为安全状态和不安全状态，在系统在安全状态时，可避免死锁。
    安全状态
    在该方法中，允许进程动态地申请资源，但是在系统分配资源之前，会计算此次资源分配的安全性。若此次分配资源不会使系统进入不安全状态，则系统才将资源分配出去。反之，进程等待
    安全状态例子
    假定系统有12台磁带机，3个进程。分配情况如图

  进程	最大需求	已分配	可分配
  p1	10	5	3
  p2	4	2
  p3	9	2

  这时，存在一个安全序列（p2， p3， p1）。
  如果不按照安全序列分配，系统便进入不安全状态。就会导致死锁。

  • 利用银行家算法避免死锁
    为实现银行家算法，每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程申请一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统进入不安全状态。如果不会，才将资源分配给它。否则让进程等待。