操作系统论文死锁问题

1、操作系统论文学 号：2135123姓 名：张冰专 业：物联网工程东北大学秦皇岛分校操作系统中的死锁问题摘要：进程死锁问题是操作系统的主要问题之一，很多学者专家一直在研究怎样解决这个问题。本文针对操作系统中经常出现的死锁问题进行了讨论，阐述了死锁出现的原因、必要条件，以及死锁的处理方法，最后谈论了一个避免死锁的经典算法银行家算法。关键词：死锁；死锁的原因；死锁的必要条件；银行家算法一、死锁的概述死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出的。所谓死锁，是指多个进程因为竞争资源而造成的一种僵局。死锁其实在信号量时已经提到过，当一个进程想要申请资源A，拥有资源B，而

2、另一个进程想申请资源B，但是拥有资源A，那么就会产生死锁。信号量本身就是个资源，有一定数量。资源分为很多很多，如内存空间，CPU周期，I/O设备等，每个资源有一定数量的资源实例。资源和信号量一样，有等待队列，当一个进程想要申请资源，但需要其他进程释放此资源，则进入该资源的等待队列。二、死锁的原因（一）并发进程对临界资源的竞争。在进程并发环境下，进程需要独占某个系统资源，而这些资源又被进程所共享，因此，必然引起进程之间对资源的竞争。（二）并发进程推进顺序不当。以哲学家进餐问题为例，有5个哲学家同时围坐在圆桌上进餐，每个哲学家右手边放一把叉子，完成就餐需要用两把叉子。如果5个哲学家同时去拿叉子，则

3、每个哲学家只能拿到一把，然而所有哲学家都在等待另一把得不到的叉子，因此无法完成就餐。这就发生了死锁现象。三、死锁的必要条件1.互斥。即资源不能被多个进程所占有。这点其实除了只读文件，其他基本都满足。2.占有并等待：A进程占有一些资源，还需要的一些资源被其他进程占有，所以处在等待状态。3.非抢占：资源不能被中途抢占。4.循环等待：P0，P1,P2.进程队列，P0等待P1占用的资源，类似。只要4个条件满足，则说明必定死锁。四、死锁的处理死锁现象会导致计算机系统无法正常运行，我们必须对死锁进行处理以排除死锁带来的不便。处理死锁归结起来有四种方法：（一）预防死锁。通过设置某些限制条件，去破坏产生死锁的

4、4个必要条件中的一个或几个条件，来防止发生死锁。（二）避免死锁。是指在资源的动态分配过程中，用某种方法防止系统进入不安全状态从而避免死锁的发生。（三）检测死锁。这种方法允许系统在运行过程中发生死锁，但可通过系统设置的检测机构，及时地检测出死锁的发生，并采取适当措施，从系统中将已发生的死锁清除掉。（四）解除死锁。这是检测死锁的最终目的。在已检测到死锁的基础上，采取某种针对死锁的措施，将死锁从系统中排除掉。五、银行家算法（一）银行家算法简述首先介绍一下系统的安全状态。所谓系统的安全状态是指系统能够将并发进程 按照某种顺序为每个进程分配其需要的资源，直到满足最大需求为止，每个进程都可以顺利完成。如果

5、系统存在这样的序列，则称系统处于安全状态；否则，称系统处于不安全状态。在银行家算法的实现中，需要知道所有进程对资源的最大需求、系统所拥有的资源数、当前进程已经分配到的资源数，从而可以得到系统剩下的资源数和进程当前对资源的需求数。因此，我们引入如下五个矩阵：1.系统可提供的资源矩阵 ；2.进程的最大需求矩阵 ；3.进程已经分配的资源矩阵 ；4.系统分配后的剩余矩阵 ；5.进程当前的需求矩阵 。（二）银行家算法的描述 根据已知的系统可提供的资源 和进程已经分配的资源 ，确定当前资源的剩余 ；根据进程最大需求 和进程已经分配的资源 ，确定进程当前的需求 ；将当前剩余资源和进程当前的需求进行对比，检查

6、是否有进程的当前需求能够从 中得到满足。若有，则执行 ，若没有，则执行 ；若进程 的当前需求能够从 中得到满足，则将资源分配给 ，使进程 完成并释放所有分配的资源，这时 的值应为 所分配的所有资源加上系统分配给进程 后剩余的资源；检查是否还有没有完成的进程，若有，执行 ，若没有，执行；出现系统资源不能满足进程需求的现象，则此时的分配状态为不安全状态，算法结束；所有进程都能够完成并释放了系统资源，则此时的分配状态为安全状态，算法结束。（三）代码 银行有一些资源，一个客户一会要一点资源，一会要一点资源，银行耐着性子分配。 预先知道Max，Allocation，Available在新进程进入时，必须

7、说明需要资源类型的种类和数量，但是不能超过系统总资源。n为进程个数，m为资源类型种类，available为长度为m的向量，表示每种资源拥有多少的资源。Max是n*m的矩阵，Maxi表示特定进程需要的每个资源的最大需求。Allocation是n*m的矩阵，Allocationi表示特定进程已经分配的每个资源的数量。Need是n*m的矩阵，Needi是特定进程需要的剩余资源。两个向量比较，只有每个分量都大，才大。安全性算法：设work是长度m的向量，finish是长度n的向量，work=available;for(int i=0;in;i+)finishi=false;for(int i=0;in

8、;i+)O(n)if(finishi=false&Neediwork) O(m) /如果进程i的最大剩余需求小于系统剩余的资源量work=work+allocationi; O(m) /执行完后释放，则系统剩余资源变多finishi=true; /进程i执行结束else break;for(int i=0;in;i+)if(finishi=false) return false;return true;资源请求算法：Requesti是进程i的请求向量。if RequestiNeedi 说明能申请if RequestiAvailable 说明能分配if能分配Available-=Requesti

9、; /系统剩余减少Allocationi+=Requesti; /已分配增多Needi-=Requesti; /剩余需求减少分配完执行安全性算法，即看看是不是安全。系统不采用预防或避免提前去除死锁时，可以1.有一个算法可以检索死锁的发生。2.有一个算法可以让死锁恢复。当资源类型只有一个资源实例时，可以用等待图（只有进程）解决。当有环时，则死锁。当资源类型可以有多个实例时，则可以用银行家算法解决。有一个好办法解决死锁，就是当CPU使用率低于多少多少时，才调用死锁检测，再去除死锁。六、恢复死锁1.随便终止一个进程打破循环等待。当选择进程的终止时，需要考虑很多方面，就像CPU调度里的优先队列法，可以以不同方面考虑优先。可以以进程执行时间、进程还需资源多少、进程是交互的还是批处理的。2.抢占死锁进程资源。抢占要抢占谁的又是个问题。自己选呗而被抢占资源的进程必须回滚到不会发生死锁的时刻。而且不能一直欺负一个进程，这样该进程会发生饥饿。七、总结 合理的分配计算机资源是操作系统主要工作之一，有效的处理死锁是其重要的组成部分。然而由于计算机系统的复杂性，死锁问题至今仍然难以完全解决，现有的各种解决方法都是以不同程度在牺牲系统效率为代价的。总之，在这里讨论死锁问题，希望本文的