深入解析Linux死锁：原理、原因及解决方案

个人主页：chian-ocean

文章专栏-Linux

前言：

死锁（Deadlock）是指在多进程或多线程的系统中，多个进程或线程因争夺资源而互相等待，导致系统中所有相关进程都无法继续执行的状态。

死锁

资源

可抢占资源与不可抢占资源的对比

死锁

死锁（Deadlock） 是一种多线程或多进程程序中的问题，指的是两个或多个线程或进程在执行过程中，由于争夺共享资源而导致的相互等待的状态，从而导致这些线程或进程永远无法继续执行。换句话说，死锁是指系统中各个资源的请求无法得到满足，导致进程停滞不前。

死锁的四个必要条件（Coffman等人提出）

1. 互斥条件：每个资源要么分配给一个进程（线程），要么就是可用的。
2. 占有和等待条件：已经得到某个资源的进程（线程）可以再次请求新的资源。
3. 不可抢占条件：已经分配给一个进程（线程）的资源不能强制性地被抢占。
4. 环路条件：死锁发生的时候一定由两个或两个以上的进程（线程）组成的一条环路，该环路中的每个进程（线程）都在等待着下一个进程（线程）所占有的资源。

死锁建模

死锁的具体表现：

1. A请求R，B请求S，C请求T（图a），这是初始的资源请求阶段。
2. 资源被分配给进程A、B、C（图b和图c），此时每个进程持有了一个资源。
3. 进程A请求S，进程B请求T（图d和图e）。此时，进程A已持有资源R，正在请求资源S；进程B已持有资源S，正在请求资源T；进程C已持有资源T，正在请求资源R。此时发生死锁，因为A、B、C各自等待其他进程释放资源，形成循环等待（图g）

四种处理死锁的策略

• 以下是关于四种处理死锁策略的表格形式：

  策略	描述	优点	缺点
  死锁预防（Deadlock Prevention）	通过破坏死锁的四个条件之一来避免死锁，例如避免占有并等待、循环等待等条件。	- 可以完全避免死锁的发生。 - 系统始终保持安全状态。	- 可能导致系统效率下降，资源利用率低。 - 限制并发性。
  死锁避免（Deadlock Avoidance）	通过算法（如银行家算法）动态地判断资源请求是否会导致死锁，只有在安全情况下才会分配资源。	- 比死锁预防更加灵活。 - 可以允许更多的并发。	- 实现复杂，系统开销大，尤其在有大量资源和进程时。
  死锁检测与恢复（Deadlock Detection and Recovery）	系统允许死锁发生，但会定期检查是否有死锁并采取恢复措施（如回滚进程或终止进程）。	- 实现简单，不需要在资源分配时额外考虑死锁问题。	- 死锁检测和恢复会带来额外的开销。 - 恢复过程中可能需要终止进程，影响系统性能。
  死锁忽略（Deadlock Ignorance）	假设死锁不会发生，或者即使发生死锁也不去检测和处理。	- 简单实现，系统开销小。	- 死锁发生时可能导致系统停滞或无法继续工作。 - 不适用于高可靠性和高可用性要求的系统。

死锁预防

1. 破坏互斥条件：
   • 在某些情况下，资源可以共享（如读操作）。通过允许多个进程共享资源，可以避免互斥条件。例如，多进程同时读取一个文件，而不进行写操作。
2. 破坏占有并等待条件：
   • 要求进程一次性请求所有资源：进程在执行前，必须先一次性请求所有所需的资源。如果请求资源的数量大于当前可用资源，进程就会阻塞，直到所有资源都可用。这种方式确保了进程不会在占有资源时再请求新的资源，避免了占有并等待条件。
   • 请求资源时不持有其他资源：进程请求一个资源时，必须先释放当前持有的所有资源，直到获得请求的资源。这意味着进程在请求资源时不能持有任何资源。
3. 破坏非抢占条件：
   • 允许资源抢占：当一个进程请求资源时，如果该资源已被其他进程占用，操作系统可以中断当前持有该资源的进程，强制将资源抢占并分配给请求进程。抢占的资源可以在适当的时机返回给原进程。
   • 资源可以被强制回收：如果进程无法获得所需资源，系统可以强制回收当前占用的资源，并重新安排资源分配。
4. 破坏循环等待条件：
   • 资源请求顺序：规定资源的请求顺序，要求进程按固定顺序请求资源。例如，进程必须先请求资源R，然后请求资源S，依此类推。这样，可以确保不存在形成环路的等待关系，从而避免循环等待条件的发生。
   • 每个进程在获取资源时按一个固定的顺序请求资源，这样即使多个进程请求不同的资源，也不会形成等待环路

死锁避免(银行家算法)

Dijkstra（1965年）提出了一种能够修复死锁的调度算法，称为银行家算法（Banker’s Algorithm）。

• 该模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度。
• 算法要做的是判断对请求的满足是否会导致进人不安全状态。如果是，就拒绝请求;如果满足请求后系统仍然是安全的，就予以分配。
• 在图中我们看到4个客户A、B、C、D，每个客户都被授予一定数量的贷款单位(比如1单位是1千美元)，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留10个单位而不是22个单位的资金来为客户服务。
• 这里将客户比作进程，贷款单位比作资源，银行家比作操作系统。
• 客户们各自做自己的生意，在某些时刻需要贷款(相当于请求资源)。在某一时刻，具体情况如图b所示。这个状态是安全的，由于保留着2个单位，银行家能够拖延除了c以外的其他请求。
• 因而可以让C先完成，然后释放c所占的4个单位资源。有了这4个单位资源，银行家就可以给D或B分配所需的贷款单位，以此类推。

​ 考虑假如向B提供了另一个他所请求的贷款单位，如图b所示，那么我们就有如图c所示的状态，该状态是不安全的。如果忽然所有的客户都请求最大的限额，而银行家无法满足其中任何一个的要求，那么就会产生死锁。不安全状态并不一定引起死锁，由于客户不一定需要其最大贷款额度，但银行家不敢抱这种侥幸心理。
​ 银行家算法就是对每一个请求进行检查，检查如果满足这一请求是否会达到安全状态。若是，那么就满足该请求;否则，就推迟对这一请求的满足。为了检查状态是否安全，银行家需要考虑他是否有足够的资源满足某一个客户。如果可以，那么这笔贷款就是能够收回的，并且接着检查最接近最大限额的一个客户，以此类推。如果所有投资最终都能被收回，那么该状态是安全的，最初的请求可以批准。

死锁忽略

死锁忽略（Deadlock Ignorance）是一种处理死锁问题的策略，在这种策略下，系统选择完全不考虑死锁的发生。换句话说，系统不采取任何措施来检测或预防死锁，而是依赖于系统自然的恢复机制或用户干预来解决死锁。

鸵鸟算法

鸵鸟算法的核心概念：

• 算法的名字来源于“鸵鸟把头埋进沙子里”这一比喻，意味着系统在遇到问题时选择忽略它，而不是进行积极的处理。
• 该算法的基本思想是每个人在面对问题时都有自己的解决方式，有些人可能选择回避，认为这些问题会自动解决或不值得关注。

优缺点：

死锁检测和死锁恢复

死锁检测方法

• 该方法利用资源的当前分配情况进行死锁检测。
• 资源的分配情况通过矩阵来表示，其中：
  • C表示已分配矩阵（Allocation Matrix）：表示每个进程已分配的资源数。
  • B表示请求矩阵（Request Matrix）：表示每个进程还需要的资源数。
  • A可用资源向量（Available Resource Vector）：表示系统中未被分配的资源数。
  • E表示现有资源向量（Existing resource vector）：代表每种已经存在的资源总数。

关键恒等式：

公式表达为：

这条公式的含义是：

• Cij：表示第i个进程对资源类型j的请求数量。
• Aj：表示资源类型j已分配给所有进程的数量。
• Ej：表示资源类型j在系统中的总数。

总的来说就是已经分配的资源j的总数加起来的再和所有可供使用的资源总数相加，结果就是该类资源总数。

死锁恢复

1. 终止进程：强制终止一个或多个进程来释放资源，从而解除死锁。
2. 资源回收：强制某些进程释放资源，其他进程可以使用这些资源来继续执行。
3. 进程回滚：把某些进程的状态恢复到之前的安全状态，让它们重新开始执行。

其他问题

两阶段加锁

两阶段加锁（Two-Phase Locking, 2PL） 是一种常见的数据库事务控制协议，它在保证事务隔离性的同时避免了死锁的发生。两阶段加锁的基本原理是：一个事务必须首先完成对所需资源的加锁，直到它释放资源前不可以请求更多的锁。两阶段加锁分为两个阶段：

1. 扩展阶段（Growing Phase）：事务可以不断地请求和获取锁。
2. 收缩阶段（Shrinking Phase）：一旦事务释放了一个锁，它就不能再申请任何新的锁。

例子：银行转账事务

假设有两个进程（事务）在银行系统中执行转账操作，涉及两个账户的资源：账户A和账户B。

事务1（T1）：

T1的操作是从账户A转账到账户B，具体过程是：

1. 请求锁定账户A，进行扣款。
2. 请求锁定账户B，进行存款。
3. 提交事务，释放锁。

事务2（T2）：

T2的操作是从账户B转账到账户A，具体过程是：

1. 请求锁定账户B，进行扣款。
2. 请求锁定账户A，进行存款。
3. 提交事务，释放锁。

两阶段加锁的过程

1. 事务T1：
   • 扩展阶段：T1首先请求锁定账户A，成功获取锁。
   • T1继续请求锁定账户B，也成功获得锁。
   • T1没有再申请其他锁，进入收缩阶段，开始释放锁。
2. 事务T2：
   • 扩展阶段：T2首先请求锁定账户B，成功获取锁。
   • 然后，T2尝试请求账户A的锁，但由于T1已经锁定了账户A，T2会被阻塞，等待T1释放锁。
   • T2无法再请求任何新的锁（因为进入了收缩阶段），并且等待T1释放账户A的锁。

通信死锁

通信死锁（Communication Deadlock） 是指在分布式系统或多进程/多线程系统中，由于进程之间的通信（如消息传递、信号量等）引发的死锁问题。具体来说，当多个进程或线程相互依赖对方的消息或响应，而这些消息或响应无法被发送或接收时，系统可能进入死锁状态。

举例解释：生产者-消费者模型中的通信死锁

假设我们有一个简单的生产者-消费者问题，其中有两个进程：生产者和消费者。生产者将商品生产到缓冲区中，而消费者从缓冲区中取走商品。生产者和消费者通过共享一个缓冲区进行通信。如果在某些情况下，生产者和消费者由于等待彼此的消息而导致死锁，就会发生通信死锁。

步骤1：正常通信

• 生产者（P）生产一个商品，并将其放入缓冲区。
• 消费者（C）从缓冲区中取走一个商品。
• P 和 C 通过缓冲区的状态来进行通信，P 等待缓冲区有空位置，C 等待缓冲区中有商品。

步骤2：发生通信死锁

假设存在如下场景：

• 生产者 P 正在等待消费者 C 取走一个商品，以便腾出空间存放新商品（即 P 等待 C 消费）。
• 消费者 C 正在等待生产者 P 放入商品，以便它能够消费（即 C 等待 P 生产）。

这种情况下，生产者和消费者彼此等待对方的动作，形成了相互依赖的通信链条，导致死锁发生。

步骤3：死锁的发生

• 生产者 P 和消费者 C 永远互相等待对方的动作。
• 生产者没有商品可生产，因为缓冲区已满，消费者无法取走商品。
• 消费者没有商品可消费，因为生产者没有生产新商品。
• 结果，系统进入死锁状态，生产者和消费者都无法继续执行。

死锁的原因

• 消息依赖性：生产者和消费者相互依赖对方的消息才能继续执行。例如，生产者必须等待消费者消费商品才能继续生产，而消费者必须等待生产者生产商品才能继续消费。
• 资源共享：当多个进程或线程共享资源（如缓冲区、队列等），并且相互依赖对方的动作时，容易发生死锁。

活锁（Livelock）

活锁（Livelock） 是一种并发编程中的问题，类似于死锁，但有所不同。与死锁不同，活锁中的进程或线程并没有完全停顿，它们仍然在不断地改变自己的状态，但始终无法达到预期的目标或完成任务。换句话说，活锁是一种进程不停地做出反应，但没有实质性进展的状态。

活锁的特点

• 进程不断改变状态：尽管进程没有被完全阻塞，它仍然在进行某些操作（如尝试重新获取资源），但这些操作并没有实质性进展。
• 没有前进：进程虽然不停地变化和响应，但始终没有最终完成任务或获得所需资源。

饥饿（Starvation）

饥饿（Starvation） 是指在并发系统中，某些进程因为系统资源的分配不公或调度策略不合理，长时间得不到执行，导致它们无法完成任务。饥饿问题通常发生在多个进程争用资源时，其中某些进程总是得不到必要的资源，而一直处于等待状态。

饥饿的特点

• 长期等待：某些进程长时间无法获得执行机会，甚至无法获得资源来继续执行。
• 不公平资源分配：由于资源分配策略的不公，某些进程被反复忽略，导致它们得不到满足。
• 进程被“饿死”：虽然进程并没有完全被阻塞或终止，它们的执行被永久推迟，无法正常执行下去。

#include<iostream>
#include<unistd.h>
#include<pthread.h>
#include"lock.hpp"  // 这里的lock.hpp是自定义的头文件，假设它包含一些锁的相关定义
using namespace std;

// 初始化互斥锁
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

#define NUM  10  // 定义线程数量
int ticket = 1000;  // 初始票数

// 线程执行的函数
void* mythread(void* args)
{
    pthread_detach(pthread_self());  // 将当前线程设置为分离线程，线程结束后自动释放资源

    uint64_t number = (uint64_t)args;  // 获取传递给线程的参数，转化为线程编号

    // 无限循环，直到票数耗尽
    while(true)
    {
        {
            pthread_mutex_lock(&lock);  // 上锁，确保只有一个线程在修改票数时能访问临界区
            
            if(ticket > 0)  // 如果票数大于0，则继续执行
            {
                usleep(1000);  // 模拟处理过程，暂停1毫秒
                cout <<"thread: " << number << " ticket: " << ticket << endl;  // 打印当前线程号和票数
                ticket--;  // 减少票数
            }
            else 
            {
                pthread_mutex_unlock(&lock);  // 解锁，允许其他线程访问临界区
                break;  // 如果票数小于或等于0，退出循环，结束线程执行
            }
            
            pthread_mutex_unlock(&lock);  // 解锁，允许其他线程访问临界区

        }
    }

    return nullptr;  // 线程结束
}

int main()
{
    // 创建NUM个线程
    for(int i = 0; i < NUM; i++)
    {
        pthread_t tid;
        pthread_create(&tid, nullptr, mythread, (void*)i);  // 创建线程并传递线程编号
    }

    sleep(5);  // 主线程休眠5秒钟，等待子线程执行完成
    cout <<"process quit ..." <<endl;  // 主线程结束时输出消息
    
    return 0;
}

• 都是9号线程抢占资源。产生了竞争的关系。其他线程解饿。（需要同步解决）

NUM; i++)
{
pthread_t tid;
pthread_create(&tid, nullptr, mythread, (void*)i); // 创建线程并传递线程编号
}

sleep(5);  // 主线程休眠5秒钟，等待子线程执行完成
cout <<"process quit ..." <<endl;  // 主线程结束时输出消息

return 0;

}

* 都是9号线程抢占资源。产生了竞争的关系。其他线程解饿。（需要同步解决）

![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/0af7248320c44b54861466b7eb7ea758.png)