死锁(Deadlock)

发表于

deadlock

定义

一个进程在得不到资源之后进入等待状态，而这个状态永远不会改变，这种情况就叫做死锁。

死锁主要发生的情况就在于资源的请求与释放不合理，而这些资源包括了physical resource和logical resource（锁，信号量，文件等）

特点

发生死锁的必要不充分条件

不是独立的四个条件

  • mutual exclusion：在同一时间内只有一个进程能访问该资源
  • hold and wait：一个进程必须同时拥有一个资源，并且在请求另一份被别的进程拥有着的资源
  • no preemption：资源不能被抢占
  • circular wait：一系列的进程在循环等待，比如p1在等待p2的资源，p2在等待p3的资源，p3在等待p1的资源

利用资源分配图可以检测是否发生了死锁

在资源分配图中，顶点分为resource(R)和process(P)两种，由R指向P的称为分配边（即P已经获得R的资源），由P指向R的称为请求边（即P在请求R的资源），而边是可以动态变化的。一旦分配成功，即从请求边转化为分配边。

如下图：

img

那么如何检测死锁呢？

一旦成环并且环中的每种资源只有一个实例(即没有多余的资源可用时)，就会发生死锁。如下图有两个环，其中没有多余资源。

img

解决办法

目前有三种：

  • 采取办法去避免死锁，保证系统永远不会进入死锁状态；
  • 允许系统进入死锁状态，检测出来然后恢复；
  • 忽略死锁，然后假装死锁没有发生过；

大多数操作系统采用第三种。

deadlock prevention

使得前面提到的那四个死锁发生的必要不充分条件之一不成立，即可以避免死锁

  • mutual exclusion：某些资源可以允许多个进程访问，比如read-only file。但互斥锁不能允许多个进程访问，因此这个方法不能采用。
  • hold and wait：一个方法是实现一个协议使得进程应该一次性获得所有资源；另一种方法则是要求实现一个协议使得进程在释放所有资源之前，不能请求资源；但这两个方法有很多缺点：一是资源的调度效率很低，有些不用的资源却一直hold住。二是有可能发生饥饿，有可能想要的资源因为其它进程hold住而一直等待。
  • no preemption：实现抢占式。一般应用在那些保存方便，易于重新加载的资源（比如寄存器）。但不能用在互斥锁和信号量。
  • circular wait：举个例子，可以实现一个协议使得进程在请求资源时，按照资源id，从大到小去请求（也就是设置一个资源请求顺序）

deadlock avoidance

了解额外信息，决定资源如何分配

  • safe state：系统以某些分配顺序去分配资源，不会发生死锁。这个顺序也叫safe sequence
  • 算法一：resource-allocation-graph algorithm
    • 还是利用资源分配图表示，但此时由p指向r的虚线表示p请求资源；
    • 在多个进程请求资源资源时，系统会检测分配该资源给某个进程后，该图会否成环
  • 算法二：banker's algorithm
    • 算法一 只适合于某种资源只有一个实例的情况；
    • 数据结构：available(某种资源的可用数量)、max(nxm的矩阵，某个进程Pi需要Ri资源的最大数量)、allocation(nxm的矩阵，某个进程Pi已经得到Ri资源的数量)、need(还需要多少资源)；need = max - allocation
    • safety algorithm：
1
2
3
4
5
6
7
初始化Work=avaliable和finish=false；//数组
2：找一个索引i满足：finish[i]=false && need[i]<=work[i]
如果不存在这个i，就goto4
work = work+allocation
finish[i]=true
goto2
4：如果所有都完成了，那么系统是安全状态

​ resource-request algorithm：

1
2
3
4
5
//requesti[ij]=k意味着进程i需要j类资源k个
//如果发生了请求,模拟一下操作
1. if requesti<=needi；goto 2; else 出错
2. requesti<=available;goto 3；else waiting
3. available -= request; allocation += quest; need -= quest

deadlock detection

如果系统没有采用以上两种死锁避免方法，就必须要有算法检测系统是否发生了死锁，并且使得系统从死锁中恢复

  • 假如每种资源只有一个实例，可以采用wait-for 图来检测死锁是否发生（Pi指向Pj意味着Pi在等待Pj释放资源）。如果改图含有环，则意味着死锁发生了
  • 假如每种资源含有多个实例，那么可以采用以上的safety算法，只要在最后检查每个finish是否都是true即可

recovery from deadlock

当检测到死锁发生时，需要从死锁中恢复

  • 中断一个或多个进程的运行，打破成环
  • 抢占资源：关键是要选择抢占谁的资源；实现回滚；并且如何避免饥饿的发生