第二种方式是如果我们能阻止持有资源的进程请求其他资源,我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。如果所需的资源可用,进程会完成资源的分配并运行到结束。如果有任何一个资源处于频繁分配的情况,那么没有分配到资源的进程就会等待。
很多进程无法在执行完成前就知道到底需要多少资源,如果知道的话,就可以使用银行家算法;还有一个问题是这样无法合理有效利用资源。
还有一种方式是进程在请求其他资源时,先释放所占用的资源,然后再尝试一次获取全部的资源。
破坏不可抢占条件破坏不可抢占条件也是可以的。可以通过虚拟化的方式来避免这种情况。
破坏循环等待条件现在就剩最后一个条件了,循环等待条件可以通过多种方法来破坏。一种方式是制定一个标准,一个进程在任何时候只能使用一种资源。如果需要另外一种资源,必须释放当前资源。对于需要将大文件从磁带复制到打印机的过程,此限制是不可接受的。
另一种方式是将所有的资源统一编号,如下图所示
进程可以在任何时间提出请求,但是所有的请求都必须按照资源的顺序提出。如果按照此分配规则的话,那么资源分配之间不会出现环。
尽管通过这种方式来消除死锁,但是编号的顺序不可能让每个进程都会接受。
其他问题下面我们来探讨一下其他问题,包括 通信死锁、活锁是什么、饥饿问题和两阶段加锁
两阶段加锁虽然很多情况下死锁的避免和预防都能处理,但是效果并不好。随着时间的推移,提出了很多优秀的算法用来处理死锁。例如在数据库系统中,一个经常发生的操作是请求锁住一些记录,然后更新所有锁定的记录。当同时有多个进程运行时,就会有死锁的风险。
一种解决方式是使用 两阶段提交(two-phase locking)。顾名思义分为两个阶段,一阶段是进程尝试一次锁定它需要的所有记录。如果成功后,才会开始第二阶段,第二阶段是执行更新并释放锁。第一阶段并不做真正有意义的工作。
如果在第一阶段某个进程所需要的记录已经被加锁,那么该进程会释放所有锁定的记录并重新开始第一阶段。从某种意义上来说,这种方法类似于预先请求所有必需的资源或者是在进行一些不可逆的操作之前请求所有的资源。
不过在一般的应用场景中,两阶段加锁的策略并不通用。如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受的。
通信死锁我们上面一直讨论的是资源死锁,资源死锁是一种死锁类型,但并不是唯一类型,还有通信死锁,也就是两个或多个进程在发送消息时出现的死锁。进程 A 给进程 B 发了一条消息,然后进程 A 阻塞直到进程 B 返回响应。假设请求消息丢失了,那么进程 A 在一直等着回复,进程 B 也会阻塞等待请求消息到来,这时候就产生死锁。
尽管会产生死锁,但是这并不是一个资源死锁,因为 A 并没有占据 B 的资源。事实上,通信死锁并没有完全可见的资源。根据死锁的定义来说:每个进程因为等待其他进程引起的事件而产生阻塞,这就是一种死锁。相较于最常见的通信死锁,我们把上面这种情况称为通信死锁(communication deadlock)。
通信死锁不能通过调度的方式来避免,但是可以使用通信中一个非常重要的概念来避免:超时(timeout)。在通信过程中,只要一个信息被发出后,发送者就会启动一个定时器,定时器会记录消息的超时时间,如果超时时间到了但是消息还没有返回,就会认为消息已经丢失并重新发送,通过这种方式,可以避免通信死锁。
但是并非所有网络通信发生的死锁都是通信死锁,也存在资源死锁,下面就是一个典型的资源死锁。
当一个数据包从主机进入路由器时,会被放入一个缓冲区,然后再传输到另外一个路由器,再到另一个,以此类推直到目的地。缓冲区都是资源并且数量有限。如下图所示,每个路由器都有 10 个缓冲区(实际上有很多)。