分布式系统中避免死锁的问题

死锁是分布式系统中的根本问题。所谓死锁，指的是在分布式系统中，一组进程被阻塞的情况——因为系统中的每个进程都占用了某些资源，而这些资源又被其他进程所需要。在这种情况下，各个进程会陷入死锁状态。

死锁的条件：在分布式系统中，某个进程会以以下方式使用不同的资源。
   

• 请求/要求
• 使用/运用
• 发布/发行

也就是说，一个进程会请求该资源，并在执行过程中使用该资源。在执行完成后，该进程就会释放该资源。

处理死锁的方法：

处理死锁的方法有四种：

• 避免僵局/防止停滞状态
• 避免死锁
• 死锁检测
• 死锁恢复

避免死锁：

在避免死锁的过程中，系统会检查其是否处于安全状态或不安全状态。当系统中不存在死锁现象时，系统就处于安全状态。如果发现了死锁现象，那么系统就处于不安全状态了。

为了避免死锁的情况发生，该进程需要向系统报告：为了执行其任务，该进程应该请求多少资源。为了实现这一点，我们使用算法来达成这一目标。

步骤1：请完成这两个大小为 m 和 n 的向量。将“工作量”初始化为可用的值，同时令 finish[i] 的值为 False。

对于 i=1 到 n，m≥#资源数量，且 n≥#处理数量。

步骤2：请找到一个这样的 i，使得：(i) finish[i] = false；(ii) need(i) <= work。如果不存在这样的 i，则转到步骤 4。

步骤3：工作 = 工作 + 分配

finish[i] = true

请进入第二步。

步骤4：如果对于所有的 i，finish[i] 都为真，那么系统就处于安全状态。

假设有 m = 4 种资源，分别是 A、B、C、D。同时，还有 n = 5 个进程，分别是 P0、P1、P2、P3、P4。请构造一个安全序列，以确保系统始终处于安全状态。

在这里，

n => #processes = 5 = <P0, P1, P2, P3, P4>m => #resources = 4 = (A, B, C, D)

可获取：它定义了针对特定资源，可以使用的实例数量。在上面的例子中，A-1、B-5、C-2、D-0这些资源都是可用的。

Size = Available [m] => 1 D array.

分配：它定义了为某个特定进程的所有资源所分配的资源数量。在上面的例子中，对于Process P0来说，被分配了A-0、B-0、C-1、D-2个资源。

 Size = Allocation [n x m] => 2 D array.

马克斯：它定义了某个特定进程的所有资源可使用的实例的最大数量。在上面的例子中，对于Process P0来说，可用的资源数量最多为A-0、B-0、C-1和D-2。

Size = Max [n x m] => 2 D array.

需要：它说明了，对于一个进程中的资源来说，还需要多少这样的实例。

Size = Need [n x m] => 2 D array.

为了检查是否有一个安全的序列，我们首先需要计算Need矩阵。

Need(i) = Max(i) - Allocation(i)

例如，如果我们选择P0的话，那么所需的资源就会是：

A = (0-0)B = (0-0)C = (1-1) D = (2-2)similarly for all processes.

在计算出需求矩阵之后，现在开始按照该算法进行后续操作。

步骤1：开始工作，然后完成它。

步骤2：现在，以P0流程为例。根据算法的第二步，我们需要找到这样一个i值，使得这两个条件都能得到满足。

(i) finish[i] = false(ii) need(i) <= work should be satisfied. we found for P0, finish[i] = false and need(i) <= work 

也就是说，当 0 <= 1 时，结果为真；当 0 <= 5 时，结果也为真；当 0 <= 2 时，结果同样为真；当 0 <= 0 时，结果也是真的。因此，所有条件都得到了满足。

现在，根据算法的第三步，执行“工作 = 工作 + 分配”这一步骤。之后，将 finish[i] 设置为 true，然后再次进入算法的第二步。

步骤3：现在来看 Process P1。我们发现 finish[i] 的值为 false。但是，在判断 need(i) <= work 这个条件时，该条件仍然为 false。

即：0 <= 1 时，结果为真；7 <= 5 时，结果为假；5 <= 3 时，结果仍为假；0 <= 2 时，结果为真。由于条件不满足，因此跳过过程P1，进入过程P2。

步骤4：对于流程P2来说，我们发现满足所有条件。因此，可以按照算法中的第三步进行计算。

步骤5：对于流程P3来说，我们发现所有条件都得到了满足。因此，可以按照算法中的第三步进行计算。

步骤6：对于流程P4，我们发现所有条件都得到满足。因此，按照算法中的第三步进行计算即可。

步骤7：现在，我们仍然处于“Process P1”阶段。因此，如果我们检查“Process P1”，会发现这两个条件都得到了满足。所以，按照算法的第三步来进行计算吧。

步骤8：因此，当我们再次进入算法的第二步时，我们无法找到满足两个条件的“i”值，因为所有流程都已经完成。所以现在我们需要进入算法的第四步。我们会发现所有的[i]都等于true。根据算法的规定，系统目前处于安全状态。

最后，上述示例中的安全序列为：<P0, P2, P3, P4, P1>

交叉核对：我们可以通过将每个资源的分配矩阵值与每个资源的可用矩阵值相加来确认解决方案的准确性。这样，就得到了每个资源的最终工作矩阵值。

在上述例子中，如果我们添加以下内容：

=> Allocation + Available for resource 'A' for all processes = 0 + 1 + 1 + 0 + 0 + 1 = 3.=> Allocation + Available for resource 'B' for all processes = 0 + 0 + 3 + 6 + 0 + 5 = 14.=> Allocation + Available for resource 'C' for all processes = 1 + 0 + 5 + 3 + 1 + 2 = 12.=> Allocation + Available for resource 'D' for all processes = 2 + 0 + 4 + 2 + 4 + 0 = 12.

在这里，我们可以清楚地看到，在将“分配”与“可用资源”矩阵中的数值相加之后，最终得到的数值与“工作”矩阵中的数值是相等的。因此，系统处于安全状态。

缺点：

• 在执行过程中，它拥有固定数量的进程和所需资源。
• 在出现死锁之前，其他任何进程都无法执行。同时，任何资源也不得被分配给其他进程。
• 为这些流程所获取的最大资源量应该被提前知晓并妥善分配。
• 在银行家算法中，所有资源都可以在一定的时间内被请求使用，不过这个时间限制为一年。
• 因此，那些正在获取资源的进程，在经过一定的时间后才会释放这些资源。在此之前，其他仍在等待资源的进程必须等待下去。这就是所谓的“饥饿问题”。