操作系统）"/>

“锁”（操作系统）

目录

前言

资源问题

1、可重用性资源和消耗性资源

1）可重用性资源

2）可消耗性资源

2、可抢占性资源和不可抢占性资源

1）可抢占性资源

2）不可抢占性资源

计算机系统的死锁

1、竞争不可抢占性资源引起死锁

2、竞争可消耗资源引起死锁

3、进程的推进顺序不当引起的死锁

1）进程推进顺序合法

2）进程推进顺序不合法

死锁的定义、必要条件和处理方法

1、死锁的定义

2、产生死锁的必要条件

（1）互斥条件

（2）请求和保持条件

（3）不可抢占条件

（4）循环等待条件

3、处理死锁的方法

(1)预防死锁。

(2)避免死锁。

(3)检测死锁。

(4)解除死锁。

预防死锁

1、破坏请求和保持条件

（1）第一种协议

（2）第二种协议

2、破坏“不可抢占”条件

3、破坏“循环等待”条件

避免死锁

1、系统安全状态

（1）安全状态

（2）安全状态之例

2、利用银行家算法避免死锁

---

前言

系统中只有一台扫描仪R1和一台刻录机R2。有两个进程P1和P2,它们都准备将扫描的文档刻录到CD光盘上,进程P先请求扫描仪R1并获得成功，进程P2先请求CD刻录机R2也获得成功。后来P又请求CD刻录机，因它已被分配给了P2 而阻塞。P2 又请求扫描仪，也因被分配给了P2 而阻塞，此时两个进程都被阻塞，双方都希望对方能释放出自己所需要的资源，但它们谁都因不能获得自己所需的资源去继续运行，从而无法释放出自己占有的资源，并且一直处于这样的僵持状态而形成死锁。又如，哲学家进餐问题中，如果每一个哲学家因饥饿都拿起了他们左边的筷子，当每一个哲学家又试图去拿起他们右边的筷子时，将会因无筷子可拿而无限期地等待，从而产生死锁问题。

本文将对死锁发生的原因、如何预防和避免死锁等问题作较详细的介绍。

资源问题

在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被抢占的资源，系统中这类资源有很多，如打印机、数据文件、队列、信号量等。

1、可重用性资源和消耗性资源

1）可重用性资源

可重用性资源是一种可供用户重复使用多次的资源，它具有如下性质:
(1)、每一个可重用性资源中的单元只能分配给一个进程使用， 不允许多个进程共享。
(2)、进程在使用可重用性资源时，须按照这样的顺序:①请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。②使用资源。进程对资源进行操作，如用打印机进行打印;③释放资源。当进程使用完后自己释放资源。
(3) 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。对资源的请求和释放通常都是利用系统调用来实现的，例如对于设备，一般用request/release;对于文件，可用open/close.对于需要互斥访问的资源，进程可以用信号量的wait/signal操作来完成。进程在每次提出资源请求后，系统在执行时都需要做一系列的工作。计算机系统中大多数资源都属于可重用性资源。

2）可消耗性资源

可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质:①每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0;②进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。③进程在运行过程中，可以请求若千个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中，可消耗资源通常是由生产者进程创建，由消费者进程消耗。最典型的可消耗性资源就是进程间通信的消息等；

2、可抢占性资源和不可抢占性资源

1）可抢占性资源

指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。例如优先级高的进程可以抢占优先级低的进程的处理机。又如可把一个进程从一个存储区转移到另一个存储区，在内存紧张时，还可将一个进程从内存调出到外存上，即抢占该进程在内存的空间。可见，CPU和主存均属于可抢占性资源。对于这类资源是不会引起死锁的。

2）不可抢占性资源

系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。例如，当一个进程已开始刻录光盘时，如果突然将刻录机分配给另一个进程，其结果必然会损坏正在刻录的光盘，因此只能等刻好光盘后由进程自己释放刻录机。另外磁带机、打印机等也都属于不可抢占性资源。

计算机系统的死锁

死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。

1、竞争不可抢占性资源引起死锁

通常系统中的不可抢占资源的数量并不能满足多个进程运行的需要。使得进程在运行过程中，因争夺资源而陷入僵局。

例如：

进程p1和进程p2，都准备写两个文件F1和F2，而这两者都属于不可重用不可抢占性资源。进程p1先打开F1再打开F2，进程p2先打开文件F2再打开F1；

代码：

 会产生这几种情况；

（1）进程P1打开F1和F2，然后P2去打开F1或F2时，会发生阻塞；等P1运行完释放后；P2会进入就绪状态；被调度后重新打开F1或F2；这种情况下会正常运行；

（2）进程P1打开F1的同时，P2打开F2，都占有一个文件，都等待另一个文件，因此两个进程都会被阻塞；形成死锁；

我们用方格表示资源（文件），用圆圈代表进程；该死锁可以画出如图所表示的：

 形成一个环路，说明已经进入死锁状态；

2、竞争可消耗资源引起死锁

   在利用消息通信机制进行通信时所形成的死锁情况。图中，m1、m2和m3是可消耗资源。进程P1一方面产生消息m1，利用send(p2, m)原语将它发送给P2;另一方面，它又要求从P3接收消息m3。而进程P2一方面产生消息m2,利用send(p3, m2)原语将它发送给P3;另一方面，它又需要接收进程P1所产生的消息m1。类似地，进程P3也产生消息m3,利用send(p1, m3)原语将它发送给P,而它又要求从进程P2 接收其所产生的消息m2。如果三个进程间的消息通信，则按下述顺序进行:

 这三个进程都可以将消息发给下一个进程，相应的也能从上一个进程接收消息，因此说可以顺利运行下去，不会发生死锁；但是看下面的例子：

 可以看出他们都阻塞在receive操作上；永远等待一条不会发出的消息；就会发生死锁；

3、进程的推进顺序不当引起的死锁

 除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。例如，系统中只有一台打印机R1和一台磁带机R2,可供进程P1和P2共享，由于进程在运行中具有异步性特征，这就可能使PI和P2两个进程按下述两种顺序向前推进。

1）进程推进顺序合法

在进程PI和P2并发执行时，如果按图3-14中的曲线①所示的顺序推进: P1: Request(R1)→P1: Request(R2)-P1: Releast(R1)→P1: Release(R2)→P2: Request(R2)→P2: Request(R1)→P2: Release(R2)→P2: Release(R1), 两个进程可顺利完成。类似地，若按图中曲线②和③所示的顺序推进，两进程也可以顺利完成。我们称这种不会引起进程死锁的推进顺序是合法的。

2）进程推进顺序不合法

若并发进程PI和P2按图中曲线④所示的顺序推进，它们将进入不安全区D内。此时P保持了资源R1，P2保持了资源R2，系统处于不安全状态。此刻，如果两个进程继续向前推进，就可能发生死锁。例如，当P运行到P: Request(R2)时， 将因R2已被P2占用而阻塞:当P2运行到P2：Request(R)时， 也将因R1已被P1占用而阻塞，于是发生了进程死锁，这样的进程推进顺序就是非法的。

死锁的定义、必要条件和处理方法

1、死锁的定义

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

2、产生死锁的必要条件

产生死锁必须同时具备下列四个条件，其中任意一个条件不成立。死锁就不发生；

（1）互斥条件

含义：进程对所分配的资源进行排它性使用，也就是说：某资源在一段时间只能被一个进程占用。其他进程请求该资源，只能等待，直到占有该资源的进程用完释放。

（2）请求和保持条件

进程已经保持了至少一个资源，但是又提出新的资源请求，但是该资源已经被其他进程占有，此时请求进程被阻塞，但对自己的获得的资源保持不放。

（3）不可抢占条件

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

（4）循环等待条件

在发生死锁时，必然会存在一个进程——资源的循环链，即进程集合{P0,P1,P2,P3,P4,P5}中的P0正在等待一个P1占用的资源，P1正在等待P2占用的资源，..........，Pn正在等待已被P0占用的资源。

3、处理死锁的方法

         目前处理死锁的方法可归结为四种:

(1)预防死锁。

这是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。

(2)避免死锁。

同样是属于事先预防策略，但它并不是事先采取各种限制措施，去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。

(3)检测死锁。

这种方法无须事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可通过检测机构及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。

(4)解除死锁。

当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤消一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行。

上述的四种方法，从(1)到(4)对死锁的防范程度逐渐减弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降(即并发程面提高)。

预防死锁

1、破坏请求和保持条件

（1）第一种协议

      该议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。此时若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给它。这样，该进程在整个运行期间，便不会再提出资源要求，从而破坏了“请求”条件。

      系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件。

优点：简单、易行且安全。

缺点：资源严重浪费，严重的恶化资源的利用率；

           使进程经常发生饥饿现象。（所需资源被其他进程占有，迟迟不能运行）；

（2）第二种协议

    一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且己用毕的全部资源，然后再请求新的所需资源。通过一个具体例子来说明，第二种协议比第一种协议要好。

例如：
有一个进程，它所要完成的任务是，先将数据从磁带上复制到磁盘文件上，然后对磁盘文件进行排序，最后把结果打印出来。在采用第一种协议时， 进程必须在开始时就请求磁带机、磁盘文件和打印机。然而打印机仅在最后才会用到，既影响到其利用率，还会影响到其它进程的运行。此外，又如磁带机和磁盘文件虽然空闲，但因打印机已分配给其它进程，因而进程还需要等待。在采用第二种协议时，进程在开始时只需请求磁带机、磁盘文件，然后就可运行。等到全部磁带上的数据已复制到磁盘文件中并已排序好后,便可将磁带机和磁盘文件释放掉，再去请求磁盘文件和打印机。这不仅能使进程更快地完成任务，提高设备的利用率，还可减少进程发生饥饿的机率。

2、破坏“不可抢占”条件

为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。该方法实现起来比较复杂，且需付出很大的代价。因为一个不可抢占的资源如打印机、CD刻录机等在使用一段时间后被抢占,可能会造成进程前一阶段工作的失效，即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续。这种策略还可能因为反复地申请和释放资源致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。

3、破坏“循环等待”条件

一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。设R =(R1, R2, R3........ Rm)为资源类型的集合，为每个资源类型赋予唯一的序号。如果系统中有磁带驱动器、硬盘驱动器、打印机，则函数F可按如下形式来定义:
              F(tape drive)= 1;  F(disk drive)= 5;  F(printer)= 12;
例如，当某进程需要同时使用打印机和磁带机时，由于磁带机序号低，而打印机序号高，故必须先请求磁带机，再请求打印机。假如某进程已请求到一些序号较高的资源，后来它又想请求一个序 号低的资源时，它必须先释放所有具有相同和更高序号的资源后，才能申请序号低的资源。在采用这种策略后所形成的资源分配图中，不可能再出现环路，因而破坏了“循环等待”条件。事实上，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。
        在采用这种策略时，应如何来规定每种资源的序号是十分重要的。通常应根据大多数进程需要资源的先后顺序来确定。一般情况下，进程总是先输入程序和数据，继而进行运算，最后将计算结果输出。故可以为输入设备规定较低的序号，如前面是将磁带机定为1; 为输出设备规定较高的序号，如把打印机定为12。
        这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善。但也存在下述问题:

       首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加；其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况；作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而这种按规定次序申请资源的方法必然会限制用户简单、自主地编程。

避免死锁

      避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。.

1、系统安全状态

在避免死锁方法中，把系统的状态分为安全状态和不安全状态；也就是说处于安全状态，可以避免死锁。反之，则可能进入死锁状态。

（1）安全状态

系统在进行分配资源之前，应先计算此次资源分配的安全性，若不会导致系统进入不安全状态，才进行资源的分配，否则，令进程等待。

安全状态是指：系统能按某种进程推进顺序(P1, P2, ....., Pn)为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称(P1, P2, ... Pn)为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态；

虽然并非所有不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态。反之，只要系统处于安全状态，系统便不会进入死锁状态。因此，避免死锁的实质在于，系统在进行资源分配时，应使系统不进入不安全状态。

（2）安全状态之例

假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机。尚有三台空闲未分配。如下表所示：

 可以看出，在T0时刻系统是安全的，因为这时存在一个安全序列(P2，P1，P3), 即只要系统按此进程序列分配资源，就能使每个进程都顺利完成。例如将剩余的磁带机取2台分配给P2，使之继续运行，待P2完成便可释放出4台磁带机，于是可用资源增至5台；以后再将这些全部分配给进程P1，使之运行，待P1完成后，将释放出10台磁带机, P3便能获得足够的资源，从而使P1、P2、P3 每个进程都能顺利完成。

2、利用银行家算法避免死锁

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

具体可以看 操作系统 银行家算法 c/c++实现_小小圆脸的博客-CSDN博客。