qileilove

blog已经转移至github,大家请访问 http://qaseven.github.io/

操作系统之死锁

 死锁其实在信号量时已经提到过,当一个进程想要申请资源A,拥有资源B,而另一个进程想申请资源B,但是拥有资源A,那么就会产生死锁。

  信号量本身就是个资源,有一定数量。资源分为很多很多,如内存空间,CPU周期,I/O设备等,每个资源有一定数量的资源实例。

  资源和信号量一样,有等待队列,当一个进程想要申请资源,但需要其他进程释放此资源,则进入该资源的等待队列。

  死锁的必要条件:

  1、互斥。即资源不能被多个进程所占有。这点其实除了只读文件,其他基本都满足。

  2、占有并等待:A进程占有一些资源,还需要的一些资源被其他进程占有,所以处在等待状态。

  3、非抢占:资源不能被中途抢占。

  4、循环等待:{P0,P1,P2....}进程队列,P0等待P1占用的资源,类似。

  只要4个条件满足,则说明必定死锁。

  资源分配图:为了清晰的看是否有死锁。P->R实线 申请;R->P实线 分配;P->R虚线 需求。

  当每个资源类型只有一个实例,则有环等价于死锁。

  当存在资源类型有多个实例,则死锁必有环,有环不一定死锁。

  死锁处理:

  1.1 死锁预防。通过不满足四个必要条件之一。

  (1)互斥:很难不满足。

  (2)占有并等待:第一,可要求进程创建就要申请好全部的资源;或第二,进程申请资源时要释放占有的资源。

  但是第一种情况会发生饥饿。因为如果一个进程需要很多很多进程,这些资源几乎不会同时有,则这个进程永远不会执行。

  (3)非抢占:如果A进程想要申请资源a,但是a被B进程占有,且B进程在等待资源b,则A进程可以抢占B进程的资源a执行。等到B进程得到原本

  拥有的资源a和申请的b,则执行。 抢占和被抢占

  (4)循环等待:规定资源被申请的顺序,每个进程申请资源的顺序被规定了。如果需要Rj(j<i)则需要先释放Ri。

  1.2 死锁避免。前面讨论的预防死锁的解决方案中包括限制资源的申请,但是这对资源的利用率来说下降太多了。

  所以引出了死锁避免:要求事先得到进程申请资源和拥有的资源的信息 来判定是否值得等待。(想起了管程的条件变量选择重启进程的解决方

  法就是得知进程的最大需求)

  最简单的方法是事先告诉每个进程对于每个资源类型的最大需求。从而使得循环等待不成立。

  (1)安全状态:能确定一个进程序列<p1,p2...>,按照这种顺序执行进程就不会死锁(一个结束一个开始)。使得当Pi申请资源时,申请的资

  源一定要小于剩余可用资源+pi队列前面的进程所占有的资源,则称为安全的。因为你想,Pi最多就等的长一点时间,但是最终还是能行的。

  安全则不会死锁。不安全不一定会死锁。

  只有资源分配后能安全状态,才允许申请。

  (2)资源分配图算法:适用于每个资源类型只有一个实例。

  分配边释放就变成需求边。

 2、允许进入死锁,但可以检测并恢复。

  3、忽略死锁。

  银行家算法: 银行有一些资源,一个客户一会要一点资源,一会要一点资源,银行耐着性子分配。 预先知道Max,Allocation,Available

  在新进程进入时,必须说明需要资源类型的种类和数量,但是不能超过系统总资源。

  n为进程个数,m为资源类型种类,available为长度为m的向量,表示每种资源拥有多少的资源。

  Max是n*m的矩阵,Max[i]表示特定进程需要的每个资源的最大需求。

  Allocation是n*m的矩阵,Allocation[i]表示特定进程已经分配的每个资源的数量。

  Need是n*m的矩阵,Need[i]是特定进程需要的剩余资源。

  两个向量比较,只有每个分量都大,才大。

  安全性算法:

  设work是长度m的向量,finish是长度n的向量

work=available;
for(int i=0;i<n;i++)
 finish[i]=false;
for(int i=0;i<n;i++) O(n)
{
 if(finish[i]==false&&Need[i]<work)  O(m)   //如果进程i的最大剩余需求小于系统剩余的资源量
 {
  work=work+allocation[i];  O(m)   //执行完后释放,则系统剩余资源变多
  finish[i]=true;                  //进程i执行结束
 }
 else break;
}
for(int i=0;i<n;i++)
{
 if(finish[i]==false) return false;
}
return true;

  资源请求算法:

  Request[i]是进程i的请求向量。

  if Request[i]<Need[i] 说明能申请
  if Request[i]<Available 说明能分配
  if能分配
  {
  Available-=Request[i]; //系统剩余减少
  Allocation[i]+=Request[i];  //已分配增多
  Need[i]-=Request[i];  //剩余需求减少
  }

  分配完执行安全性算法,即看看是不是安全。

  系统不采用预防或避免提前去除死锁时,可以

  1、有一个算法可以检索死锁的发生。

  2、有一个算法可以让死锁恢复。

  当资源类型只有一个资源实例时,可以用等待图(只有进程)解决。当有环时,则死锁。

  当资源类型可以有多个实例时,则可以用银行家算法解决。

  有一个好办法解决死锁,就是当CPU使用率低于多少多少时,才调用死锁检测,再去除死锁。

  恢复死锁可以:

  1、随便终止一个进程打破循环等待。

  当选择进程的终止时,需要考虑很多方面,就像CPU调度里的优先队列法,可以以不同方面考虑优先。可以以进程执行时间、进程还需资源多少、进程是交互的还是批处理的。

  2、抢占死锁进程资源。

  抢占要抢占谁的又是个问题。自己选呗~而被抢占资源的进程必须回滚到不会发生死锁的时刻。而且不能一直欺负一个进程,这样该进程会发生饥饿。

posted on 2011-11-21 10:27 顺其自然EVO 阅读(169) 评论(0)  编辑  收藏 所属分类: 数据库


只有注册用户登录后才能发表评论。


网站导航:
 
<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(54)

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜