面试题：并发与同步之高级难度：死锁与并发同步策略

Question

在一个多线程或多进程的系统中，死锁是并发同步中常见的问题。请阐述死锁产生的四个必要条件，并且说明如何通过资源分配图算法（如银行家算法）来预防死锁。同时，请举例说明一个可能出现死锁的场景，并提出相应的避免策略。

Answer 1

死锁产生的四个必要条件

1. 互斥条件：资源在某一时刻只能被一个进程或线程所占有。例如打印机在打印一份文件时，不能同时被另一个进程使用。
2. 占有并等待条件：进程已经占有了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。比如一个进程持有资源A，又请求资源B，而资源B被其他进程持有。
3. 不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，只能由获得该资源的进程自己释放。例如进程获取到了一个锁，其他进程不能强行夺取这个锁。
4. 循环等待条件：存在一个进程资源的循环链，链中每一个进程已获得的资源同时被下一个进程所请求。假设有进程P1、P2、P3，P1等待P2占用的资源，P2等待P3占用的资源，P3又等待P1占用的资源，形成循环等待。

通过资源分配图算法（银行家算法）预防死锁

1. 银行家算法原理：把系统的资源比作银行的资金，进程向系统请求资源相当于客户向银行贷款。系统在进行资源分配前，先计算此次分配后系统是否处于安全状态，如果处于安全状态则进行分配，否则拒绝分配。
2. 具体步骤：
   • 数据结构定义：
     • 可用资源向量Available：表示系统中各类资源的可用数量。
     • 最大需求矩阵Max：记录每个进程对各类资源的最大需求量。
     • 分配矩阵Allocation：记录每个进程当前已分配到的各类资源数量。
     • 需求矩阵Need：计算得出，Need[i, j] = Max[i, j] - Allocation[i, j]，表示每个进程还需要的各类资源数量。
   • 安全性检查：
     • 初始化一个工作向量Work = Available，表示当前可用资源。
     • 查找一个进程i，使得Need[i] <= Work，若找到则执行下一步，否则系统处于不安全状态。
     • 假设进程i获得所需资源并运行完毕，释放其占有的资源，即Work = Work + Allocation[i]，标记进程i为完成状态。
     • 重复上述查找和释放资源的步骤，直到所有进程都标记为完成状态，此时系统处于安全状态，否则处于不安全状态。只有在安全状态下才进行资源分配。

可能出现死锁的场景及避免策略

1. 场景举例：假设有两个进程P1和P2，系统中有两个资源R1和R2。P1先请求并获得R1，然后P2请求并获得R2，接着P1请求R2，P2请求R1，此时两个进程相互等待对方释放资源，形成死锁。
2. 避免策略：
   • 破坏占有并等待条件：进程在开始运行前一次性申请所需的全部资源，若不能满足则不运行。这样可以避免进程在占有部分资源的情况下等待其他资源。例如上述场景中，P1和P2开始运行前就申请R1和R2，若不能同时满足则等待，不会出现占有一个资源再等待另一个资源的情况。
   • 破坏循环等待条件：对资源进行排序，规定进程只能按照顺序申请资源。比如规定先申请R1再申请R2，那么P1申请R1后，只能继续申请R2，而P2若想申请资源，也必须先申请R1，这样就不会形成循环等待。