这样,每个人还能贷款至少 2 个单位的额度,如果其中有一个人发起最大额度的贷款请求,就会使系统处于一种死锁状态。
这里注意一点:不安全状态并不一定引起死锁,由于客户不一定需要其最大的贷款额度,但是银行家不敢抱着这种侥幸心理。
银行家算法就是对每个请求进行检查,检查是否请求会引起不安全状态,如果不会引起,那么就接受该请求;如果会引起,那么就推迟该请求。
类似的,还有多个资源的银行家算法,读者可以自行了解。
破坏死锁死锁本质上是无法避免的,因为它需要获得未知的资源和请求,但是死锁是满足四个条件后才出现的,它们分别是
互斥
保持和等待
不可抢占
循环等待
我们分别对这四个条件进行讨论,按理说破坏其中的任意一个条件就能够破坏死锁
破坏互斥条件我们首先考虑的就是破坏互斥使用条件。如果资源不被一个进程独占,那么死锁肯定不会产生。如果两个打印机同时使用一个资源会造成混乱,打印机的解决方式是使用 假脱机打印机(spooling printer) ,这项技术可以允许多个进程同时产生输出,在这种模型中,实际请求打印机的唯一进程是打印机守护进程,也称为后台进程。后台进程不会请求其他资源。我们可以消除打印机的死锁。
后台进程通常被编写为能够输出完整的文件后才能打印,假如两个进程都占用了假脱机空间的一半,而这两个进程都没有完成全部的输出,就会导致死锁。
因此,尽量做到尽可能少的进程可以请求资源。
破坏保持等待的条件第二种方式是如果我们能阻止持有资源的进程请求其他资源,我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。如果所需的资源可用,进程会完成资源的分配并运行到结束。如果有任何一个资源处于频繁分配的情况,那么没有分配到资源的进程就会等待。
很多进程无法在执行完成前就知道到底需要多少资源,如果知道的话,就可以使用银行家算法;还有一个问题是这样无法合理有效利用资源。
还有一种方式是进程在请求其他资源时,先释放所占用的资源,然后再尝试一次获取全部的资源。
破坏不可抢占条件破坏不可抢占条件也是可以的。可以通过虚拟化的方式来避免这种情况。
破坏循环等待条件现在就剩最后一个条件了,循环等待条件可以通过多种方法来破坏。一种方式是制定一个标准,一个进程在任何时候只能使用一种资源。如果需要另外一种资源,必须释放当前资源。对于需要将大文件从磁带复制到打印机的过程,此限制是不可接受的。
另一种方式是将所有的资源统一编号,如下图所示
进程可以在任何时间提出请求,但是所有的请求都必须按照资源的顺序提出。如果按照此分配规则的话,那么资源分配之间不会出现环。
尽管通过这种方式来消除死锁,但是编号的顺序不可能让每个进程都会接受。
其他问题下面我们来探讨一下其他问题,包括 通信死锁、活锁是什么、饥饿问题和两阶段加锁
两阶段加锁虽然很多情况下死锁的避免和预防都能处理,但是效果并不好。随着时间的推移,提出了很多优秀的算法用来处理死锁。例如在数据库系统中,一个经常发生的操作是请求锁住一些记录,然后更新所有锁定的记录。当同时有多个进程运行时,就会有死锁的风险。
一种解决方式是使用 两阶段提交(two-phase locking)。顾名思义分为两个阶段,一阶段是进程尝试一次锁定它需要的所有记录。如果成功后,才会开始第二阶段,第二阶段是执行更新并释放锁。第一阶段并不做真正有意义的工作。
如果在第一阶段某个进程所需要的记录已经被加锁,那么该进程会释放所有锁定的记录并重新开始第一阶段。从某种意义上来说,这种方法类似于预先请求所有必需的资源或者是在进行一些不可逆的操作之前请求所有的资源。
不过在一般的应用场景中,两阶段加锁的策略并不通用。如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受的。
通信死锁