操作系统基础：进程知识笔记（三）

1、死锁概念知识

计算机中存在许多互斥资源（打印机）、软件资源（进程表、临界区）如果两个进程同时调用打印机，或同时进入临界区必然会出现问题。

死锁：指两个以上的进程互相要求对方已经占有的资源导致无法继续进行下去的现象。

2、死锁案例

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

假设系统中有一台打印机A、一台扫描仪B，它们被进程P1、P2共享，两个进程并发执行，按照下面的顺序请求和释放资源

如果按照P1<a>P2<a>P1<b>P2<b>的顺序执行，会发生死锁。首先P1<a>打印机A未被占用，可以正常执行；P2<a>扫描仪没有被占用所以可以正常执行。

P1<b>时扫描仪被占用，所以需要等待。P1<b>时打印机被占用所以也需要等待。这样导致双方互相请求对方已经占用的资源，系统就会发生死锁。

2.2 同类资源分配不当引起死锁

如果系统中有m个资源被n个进程共享，当每个进程都需要k个资源，并且m<nk时，即资源数小于进程所要求的的总数时，可能会引起死锁。

2.3 PV操作使用不当引起死锁

P2进程从缓冲区取产品前，先执行P(S2),因为S2=-1，故P2等待；P1进程将产品送到缓冲区后。执行P(S1)，因为S1=-1，故P1等待。这样P1、P2都无法继续执行下午，导致系统死锁。

3、产生死锁的原因和条件

原因：竞争资源及进程推进顺序非

必要条件：互斥条件、请求保持条件、不可剥夺条件、环路条件。

进程资源有向图：由方框(资源)、圆圈(请求资源)、有向边组成。

4、死锁的处理

鸵鸟策略(不理睬策略)、预防策略、避免策略、检测与解除死锁。

4.1 死锁预防

采用某种策略显示并发进程对资源的请求，破坏死锁产生的某个必要条件，是系统在任何时刻都不能满足死锁的必要条件。预防死锁的两种策略如下：

1、预先静态分配法

破坏不可剥夺条件、预先分配所需资源，保证不出现资源等待的情况。缺点：会降低资源利用率、并发程度。

2、资源有序分配法

破坏环路条件。把资源分类按顺序排列，保证不形成环路。缺点：限制了进程对资源的请求、资源的排序会占用系统开销。

4.2 死锁避免

死锁预防是设法破坏产生死锁的必要条件之一，严格防止死锁产生。死锁避免并不是严格地限制死锁产生的必要条件。最经典的死锁避免算法是Dijkstra提出的银行家算法。缺点：死锁算法会占用系统的很大开销。

4.3 死锁检测

该方法对资源分配不加限制，即允许死锁产生，当系统要定时运行死锁检测程序，判断系统是否发生死锁，如果检测到则设法解除。

4.4 死锁解除

1、资源剥夺法：从一些进程那里强行剥夺足够数量的资源分配给死锁进程。

2、撤销进程法：按照某种策略撤销死锁进程，直到解除死锁。

​