死锁 | 不如吃茶去

什么是死锁

各进程互相等待（循环等待）对方手中的资源，导致各进程都阻塞，无法向前推进的现象叫死锁。由“互相等待、循环等待”可以看出，发生死锁，至少是两个进程同时进入死锁，而且发生死锁的进程一定是处于阻塞态的。

进程无法推进的现象，除了可以是死锁导致，也有可能是由饥饿或死循环导致。饥饿是指进程长期得不到想要的资源而导致无法推进，可以是一个进程自己发生饥饿，发生饥饿的进程可能是阻塞态（如长期等待I/O），也可能是处于就绪态（长期得不到处理机）；死循环的进程甚至可以是处于运行态的，只是无法像期待的那样顺逆推进（故意设计的死循环除外）。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，是管理者的问题，而死循环一般是由代码的逻辑错误导致的，是被管理者的问题。

死锁产生的必要条件

产生死锁必须同时满足以下四个条件，任一条件不成立都不可能发生死锁。

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁，比如哲学家问题中的筷子，比如打印机等设备，而对于内存和扬声器这样的可以同时供多个进程使用的资源的争抢是不会导致死锁的。
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但是又提出了新的资源请求，而该资源被其他进程占有，此请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。需要注意：循环等待是死锁的必要不充分条件，如果同类资源数大于1，那么即使它处于循环等待之中，也未必发生死锁。当该资源仅1个时，循环等待是死锁的充要条件。

死锁的处理策略

策略一：预防死锁

预防死锁是指破坏死锁产生的四个必要条件中的一个或多个。

破坏互斥条件：将临界资源改造成可共享使用的资源（如SPOOLing技术）。这种方法可行性并不高，因为有些资源不可以改造成共享资源，很多时候无法破坏互斥条件，甚至为了系统安全要保护这种互斥性。
破坏不剥夺条件：下面提供两种破坏不剥夺条件的方案。一是，申请的资源得不到满足时，立即释放拥有的所有资源；二是，申请的资源被其它进程占用时，由操作系统协助剥夺（考虑优先级）。破坏不剥夺条件的方式实现复杂，剥夺资源可能导致部分工作失效，反复申请和释放也会导致系统开销大，这种方式也可能导致饥饿。
破坏请求和保持条件：运行前分配好所有需要的资源，之后一直保持（静态资源分配法）。缺点是资源利用率低，可能导致饥饿。
破坏循环等待条件：给资源编号，必须按照编号从小到大的顺序申请资源（顺序资源分配法），一个进程只有已占有小编号的资源时，才有资格去申请编号更大的资源，这样有大编号资源的进程不可能逆向回来申请小编号的资源，也就不会出现循环等待现象。这种方法的缺点是不方便增加新设备，因为可能需要重新编号，进程实际使用资源的顺序可能和编号递增顺序不一致而导致资源浪费，用户编程变得更麻烦。