
图中每个进程先持有一台、还需要一台,剩余资源能否让至少一个进程完成是关键。
五台相同打印机,每个进程最多需要两台,而且一次只申请一台。最多允许几个进程竞争,才能在题设条件下保证不出现资源死锁?答案不能只靠“五除以二”。这道题考的是最坏分配状态下,是否总有一个进程能够继续完成。
把资源模型先说完整
这里假设打印机不可共享、申请后可以持有等待、系统不抢占;进程最多同时需要两台,拿齐后能够完成并释放资源,不依赖其他未描述的资源或事件。讨论的是这类打印机竞争造成的死锁,不保证进程不会自己出错或一直不被调度。
如果改成一次性申请两台、申请失败不持有任何资源,或者允许强制回收,状态就变了。若进程拿齐资源后还等待别的锁,下面的保证也不再覆盖整个程序。所有结论都应跟资源模型一起给出。
最危险的是大家都差一点
当五个进程各持有一台打印机时,五台全部用完,每个进程都再等一台。没有谁拿齐两台并释放,其他人也就无法继续。这是一个可能出现的死锁状态,所以允许五个进程不能给出最坏情况下的无死锁保证。
注意“可能死锁”不等于“五个进程一运行就必定死锁”。如果调度让某个进程先拿到两台并完成,程序可能顺利结束。题目问的是保证,因此只要存在一种合法分配使所有人互等,就已经足以否定这个并发上限。

四个进程为什么可以保证推进
若只有四个进程,每个都还没拿齐两台,那么各自最多持有一台,最多占用四台,至少剩一台。这一台足以让某个已持有一台的进程拿齐并完成,随后释放它的两台,其他进程便有更多资源可用。
如果有人已经持有两台,在题设“拿齐即可完成”的前提下,它本来就是能够推进的进程。若某些进程一台也没拿到,也不会让前面的最坏占用更多。关键不是指定谁先完成,而是证明不存在所有未完成者都无法获得剩余需求的资源僵局。
这个论证还依赖系统最终允许可运行进程执行并释放资源。调度永远不给某个进程机会,属于饥饿或公平性问题,不能用资源数量公式解决。不要把无资源死锁写成每个请求都有严格完成时限。
一般公式从“最多差一台”推出来
若有 m 台同类资源、n 个进程、每个最多需要 r 台,在上述逐个申请和完成释放模型里,一个充分的最坏情况保证是 m 至少为 n×(r-1)+1。证明时,取尚未完成进程中的最大持有量 h。若已有进程拿齐,它可以完成;否则 h≤r-1,所有进程合计最多持有 n×h 台。空闲量至少为 n×(r-1-h)+1,这不小于该进程还需的 r-h 台,因此它能拿齐并释放资源。重复这个过程即可推进。
更一般地,可以用安全序列检查当前分配:寻找剩余需求不超过空闲资源的进程,假设它完成后归还已持有资源,再继续寻找。公式提供统一的资源上限保证,具体状态则可能在更少资源下仍然安全。
这里各进程最大需求一致,讨论的也是同一种可互换资源。不同进程需求不同、多类资源相互依赖时,需要重新建模,不能把打印机公式直接套成所有系统的死锁判定器。
无保证、不安全与已经死锁要分开
资源总量不满足统一保证,不代表当前状态就已经死锁。可能大家还没拿资源,也可能某个进程能马上完成。要判断某个实际局面,应查看当前持有、剩余需求和可用资源,而不是只看最大并发人数。
同样,有些安全性分析按最大需求判断没有安全序列,但实际进程之后未必真的请求到最大值。若题目把需求明确为必须拿齐两台,才能按这里的完成条件分析;换了需求语义,结论也要随之调整。
面试回答可以先给“五个各拿一台”的反例,再给“四个最多占四台”的保证证明。若有六台打印机、每个进程最多需要三台,你会怎样重新推导可保证的进程数,而不是只做六除以三?