|
|
|
在计算机系统中有许多互斥资源（如磁带机、打印机和绘图仪等）或软件资源（如进程表、临界区等），若两个进程同时使用打印机，或同时进入临界区必然会出现问题。所谓死锁，是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。
|
|
|
|
|
|
根据例4.4~例4.6的情况分析不难看出，产生死锁的原因为竞争资源及进程推进顺序非法。当系统中有多个进程所共享的资源不足以同时满足它们的需求时，将引起它们对资源的竞争导致死锁。其中，进程推进顺序非法，是指进程在运行的过程中请求和释放资源的顺序不当，导致进程死锁。
|
|
|
|
|
|
进程资源有向图由方框、圆圈和有向边三部分组成。其中方框表示资源，圆圈表示进程。请求资源：〇→□，箭头由进程指向资源；分配资源：〇←□，箭头由资源指向进程。
|
|
|
|
例如，系统中有进程P1、P2和P3，资源R1、R2和R3。假设系统中R1、R2和R3的资源数分别为1、1和2，其中P1占用了1台R1，又申请1台R3；P2占用了1台R2，又申请1台R1；P3占用了2台R3，又申请1台R2。对于这种情况可用进程资源图来描述，如下图所示。
|
|
|
|
|
|
|
|
|
|
产生死锁的4个必要条件是互斥条件、请求保持条件、不可剥夺条件和环路条件。当发生死锁时，在进程资源有向图中必构成环路，其中每个进程占有了下一个进程申请的一个或多个资源，导致进程申请的资源无法满足而产生死锁。
|
|
|
|
|
|
死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。
|
|
|
|
|
|
死锁预防是采用某种策略限制并发进程对资源的请求，破坏死锁产生的4个必要条件之一，使系统在任何时刻都不满足死锁的必要条件。预防死锁的两种策略如下：
|
|
|
|
（1）预先静态分配法。破坏了“不可剥夺条件”，预先分配所需资源，保证不等待资源。该方法的问题是降低了对资源的利用率，降低进程的并发程度；有时可能无法预先知道所需资源。
|
|
|
|
（2）资源有序分配法。破坏了“环路条件”，把资源分类按顺序排列，保证不形成环路。该方法存在的问题是限制进程对资源的请求；由于资源的排序占用系统开销。
|
|
|
|
|
|
死锁预防是设法破坏产生死锁的4个必要条件之一，严格防止死锁的产生。死锁避免则不那么严格地限制产生死锁的必要条件。最著名的死锁避免算法是Dijkstra提出的银行家算法，死锁避免算法需要很大的系统开销。
|
|
|
|
银行家算法对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后系统进入不安全状态，则不予分配；若分配资源后系统仍处于安全状态，则实施分配。与死锁预防策略相比，它提高了资源的利用率，但检测分配资源后系统是否安全增加了系统开销。
|
|
|
|
所谓安全状态，是指系统能按某种顺序如<P1，P2，…，Pn>来为每个进程分配其所需资源，直到最大需求，使每个进程都可顺序完成。通常称<P1，P2，…，Pn>序列为安全序列。若系统不存在这样一个安全序列，则称系统处于不安全状态。
|
|
|
|
|
|
解决死锁的另一条途径是使用死锁检测方法，这种方法对资源的分配不加限制，即允许死锁产生。但系统定时地运行一个死锁检测程序，判断系统是否发生死锁，若检测到有死锁，则设法加以解除。
|
|
|
|
|
|
死锁解除通常采用资源剥夺法和撤销进程法。资源剥夺法从一些进程那里强行剥夺足够数量的资源分配给死锁进程；撤销进程法根据某种策略逐个地撤销死锁进程，直到解除死锁为止。
|
|
|
