搜索
操作系统论文学号：2135123姓名：张冰专业：物联网工程东北大学秦皇岛分校操作系统中的死锁问题摘要：进程死锁问题是操作系统的主要问题之一，很多学者专家一直在研究怎样解决这个问题。本文针对操作系统中经常出现的死锁问题进行了讨论，阐述了死锁出现的原因、必要条件，以及死锁的处理方法，最后谈论了一个避免死锁的经典算法——银行家算法。关键词：死锁；死锁的原因；死锁的必要条件；银行家算法一、死锁的概述死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出的。所谓死锁，是指多个进程因为竞争资源而造成的一种僵局。死锁其实在信号量时已经提到过，当一个进程想要申请资源A，拥有资源B，而另一个进程想申请资源B，但是拥有资源A，那么就会产生死锁。信号量本身就是个资源，有一定数量。资源分为很多很多，如内存空间，CPU周期，I/O设备等，每个资源有一定数量的资源实例。资源和信号量一样，有等待队列，当一个进程想要申请资源，但需要其他进程释放此资源，则进入该资源的等待队列。二、死锁的原因（一）并发进程对临界资源的竞争。在进程并发环境下，进程需要独占某个系统资源，而这些资源又被进程所共享，因此，必然引起进程之间对资源的竞争。（二）并发进程推进顺序不当。以哲学家进餐问题为例，有5个哲学家同时围坐在圆桌上进餐，每个哲学家右手边放一把叉子，完成就餐需要用两把叉子。如果5个哲学家同时去拿叉子，则每个哲学家只能拿到一把，然而所有哲学家都在等待另一把得不到的叉子，因此无法完成就餐。这就发生了死锁现象。三、死锁的必要条件1.互斥。即资源不能被多个进程所占有。这点其实除了只读文件，其他基本都满足。2.占有并等待：A进程占有一些资源，还需要的一些资源被其他进程占有，所以处在等待状态。3.非抢占：资源不能被中途抢占。4.循环等待：｛P0，P1,P2....｝进程队列，P0等待P1占用的资源，类似。只要4个条件满足，则说明必定死锁。四、死锁的处理死锁现象会导致计算机系统无法正常运行，我们必须对死锁进行处理以排除死锁带来的不便。处理死锁归结起来有四种方法：（一）预防死锁。通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个条件，来防止发生死锁。（二）避免死锁。是指在资源的动态分配过程中，用某种方法防止系统进入不安全状态从而避免死锁的发生。（三）检测死锁。这种方法允许系统在运行过程中发生死锁，但可通过系统设置的检测机构，及时地检测出死锁的发生，并采取适当措施，从系统中将已发生的死锁清除掉。（四）解除死锁。这是检测死锁的最终目的。在已检测到死锁的基础上，采取某种针对死锁的措施，将死锁从系统中排除掉。五、银行家算法（一）银行家算法简述首先介绍一下系统的安全状态。所谓系统的安全状态是指系统能够将并发进程按照某种顺序为每个进程分配其需要的资源，直到满足最大需求为止，每个进程都可以顺利完成。如果系统存在这样的序列，则称系统处于安全状态；否则，称系统处于不安全状态。在银行家算法的实现中，需要知道所有进程对资源的最大需求、系统所拥有的资源数、当前进程已经分配到的资源数，从而可以得到系统剩下的资源数和进程当前对资源的需求数。因此，我们引入如下五个矩阵：1.系统可提供的资源矩阵；2.进程的最大需求矩阵；3.进程已经分配的资源矩阵；4.系统分配后的剩余矩阵；5.进程当前的需求矩阵。（二）银行家算法的描述根据已知的系统可提供的资源和进程已经分配的资源，确定当前资源的剩余；根据进程最大需求和进程已经分配的资源，确定进程当前的需求；将当前剩余资源和进程当前的需求进行对比，检查是否有进程的当前需求能够从中得到满足。若有，则执行，若没有，则执行；若进程的当前需求能够从中得到满足，则将资源分配给，使进程完成并释放所有分配的资源，这时的值应为所分配的所有资源加上系统分配给进程后剩余的资源；检查是否还有没有完成的进程，若有，执行，若没有，执行；出现系统资源不能满足进程需求的现象，则此时的分配状态为不安全状态，算法结束；所有进程都能够完成并释放了系统资源，则此时的分配状态为安全状态，算法结束。（三）代码银行有一些资源，一个客户一会要一点资源，一会要一点资源，银行耐着性子分配。预先知道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(inti=0;in;i++)finish[i]=false;for(inti=0;in;i++)O(n){if(finish[i]==false&&Need[i]work)O(m)//如果进程i的最大剩余需求小于系统剩余的资源量{work=work+allocation[i];O(m)//执行完后释放，则系统剩余资源变多finish[i]=true;//进程i执行结束}elsebreak;}for(inti=0;in;i++){if(finish[i]==false)returnfalse;}returntrue;资源请求算法：Request[i]是进程i的请求向量。ifRequest[i]Need[i]说明能申请ifRequest[i]Available说明能分配if能分配｛Available-=Request[i];//系统剩余减少Allocation[i]+=Request[i];//已分配增多Need[i]-=Request[i];//剩余需求减少｝分配完执行安全性算法，即看看是不是安全。系统不采用预防或避免提前去除死锁时，可以1.有一个算法可以检索死锁的发生。2.有一个算法可以让死锁恢复。当资源类型只有一个资源实例时，可以用等待图（只有进程）解决。当有环时，则死锁。当资源类型可以有多个实例时，则可以用银行家算法解决。有一个好办法解决死锁，就是当CPU使用率低于多少多少时，才调用死锁检测，再去除死锁。六、恢复死锁1.随便终止一个进程打破循环等待。当选择进程的终止时，需要考虑很多方面，就像CPU调度里的优先队列法，可以以不同方面考虑优先。可以以进程执行时间、进程还需资源多少、进程是交互的还是批处理的。2.抢占死锁进程资源。抢占要抢占谁的又是个问题。自己选呗~而被抢占资源的进程必须回滚到不会发生死锁的时刻。而且不能一直欺负一个进程，这样该进程会发生饥饿。七、总结合理的分配计算机资源是操作系统主要工作之一，有效的处理死锁是其重要的组成部分。然而由于计算机系统的复杂性，死锁问题至今仍然难以完全解决，现有的各种解决方法都是以不同程度在牺牲系统效率为代价的。总之，在这里讨论死锁问题，希望本文的讨论有利于读者对死锁问题的深刻理解，并深入研究解决死锁问题的方法。参考文献：[1]汤子赢.计算机操作系统[M].西安:西安电子科技大学出版社,1999[2]张尧学,史美林.计算机操作系统教程[M].北京:清华大学出版社,2000[3]甄志龙,于远诚.OS中死锁问题的状态模型探讨[J].通化师范学院学报,2005,26:23-25