面试题：并发与同步之哲学家问题：死锁预防策略

Question

请阐述至少两种解决哲学家就餐问题中死锁的策略，并详细说明每种策略是如何从根本上预防死锁发生的，同时分析这些策略在实际应用场景中的优缺点。

Answer 1

策略一：资源分配图算法（如银行家算法）

1. 预防死锁原理：
   • 系统对进程发出的每一个资源请求进行动态检查，并根据检查结果决定是否分配资源。银行家算法中，系统将资源分配给进程后，会判断剩余资源是否能满足所有进程的最大需求，若能则分配，否则不分配。这样可以确保系统始终处于安全状态，避免进入死锁状态。因为死锁的发生需要同时满足四个条件（互斥、占有并等待、不可剥夺、循环等待），该算法通过动态分配资源避免了占有并等待和循环等待条件的发生。
2. 优点：
   • 理论上可以有效预防死锁，只要系统按照算法进行资源分配，就能保证系统不会进入死锁状态。
   • 可以实现资源的较合理分配，因为它考虑了进程的最大需求和当前资源状态，能在满足安全性的前提下尽量满足进程对资源的需求。
3. 缺点：
   • 实现复杂度高，需要记录每个进程的最大需求、已分配资源和可用资源等信息，并进行复杂的安全性检查计算。
   • 每次资源请求都要进行检查，增加了系统开销，影响系统性能。
   • 假设进程预先声明最大资源需求，在实际应用中，有些进程可能无法准确预知自己的最大需求，导致算法的应用受限。

策略二：破坏循环等待条件

1. 预防死锁原理：
   • 给所有资源类型分配一个唯一的编号，要求每个进程按照编号递增的顺序申请资源。这样就打破了循环等待的条件，因为在这种规则下，进程申请资源时不会形成循环等待的环。例如，有筷子1、筷子2、筷子3（编号依次递增），哲学家们必须先申请编号小的筷子，再申请编号大的筷子，从而避免了循环等待。
2. 优点：
   • 实现相对简单，不需要像银行家算法那样进行复杂的计算和记录。
   • 对系统性能影响较小，只需要在申请资源时按照编号顺序进行，额外开销相对较小。
3. 缺点：
   • 资源分配不够灵活，可能导致资源浪费。例如，编号大的资源可能长时间闲置，而进程因为编号顺序限制无法先获取该资源。
   • 可能不符合实际应用场景，实际场景中资源的编号顺序可能与进程对资源的需求顺序不匹配，导致进程无法按照理想方式申请资源。