深入解析Linux死锁：原理、原因及解决方案
个人主页：chian-ocean
文章专栏-Linux
深入解析Linux死锁：原理、原因及解决方案
- 个人主页：chian-ocean
- 文章专栏-Linux
- 前言：
- 死锁
- 资源
- 可抢占资源与不可抢占资源的对比
- 死锁
- 死锁的四个必要条件（Coffman等人提出）
- 死锁建模
- 四种处理死锁的策略
- 死锁预防
- 死锁避免(银行家算法)
- 死锁忽略
- 鸵鸟算法
- 死锁检测和死锁恢复
- **死锁检测方法**
- 关键恒等式：
- 死锁恢复
- 其他问题
- 两阶段加锁
- 例子：银行转账事务
- 事务1（T1）：
- 事务2（T2）：
- 两阶段加锁的过程
- 通信死锁
- 举例解释：生产者-消费者模型中的通信死锁
- 步骤1：正常通信
- 步骤2：发生通信死锁
- 步骤3：死锁的发生
- 死锁的原因
- 活锁（Livelock）
- 活锁的特点
- 饥饿（Starvation）
- 饥饿的特点
前言：
死锁（Deadlock）是指在多进程或多线程的系统中，多个进程或线程因争夺资源而互相等待，导致系统中所有相关进程都无法继续执行的状态。
死锁
资源
可抢占资源与不可抢占资源的对比
特性 可抢占资源 不可抢占资源 定义 资源可以被操作系统或其他线程/进程强制抢占 资源不能被操作系统或其他线程/进程抢占 例子 CPU时间、内存、网络带宽等 锁、文件描述符、硬件设备 控制机制 操作系统的调度器管理 需要显式的同步机制，如锁和信号量 死锁风险 较低，因资源可能随时被抢占 较高，特别是在锁竞争时容易死锁 死锁
死锁（Deadlock） 是一种多线程或多进程程序中的问题，指的是两个或多个线程或进程在执行过程中，由于争夺共享资源而导致的相互等待的状态，从而导致这些线程或进程永远无法继续执行。换句话说，死锁是指系统中各个资源的请求无法得到满足，导致进程停滞不前。
死锁的四个必要条件（Coffman等人提出）
- 互斥条件：每个资源要么分配给一个进程（线程），要么就是可用的。
- 占有和等待条件：已经得到某个资源的进程（线程）可以再次请求新的资源。
- 不可抢占条件：已经分配给一个进程（线程）的资源不能强制性地被抢占。
- 环路条件：死锁发生的时候一定由两个或两个以上的进程（线程）组成的一条环路，该环路中的每个进程（线程）都在等待着下一个进程（线程）所占有的资源。
死锁建模
死锁的具体表现：
- A请求R，B请求S，C请求T（图a），这是初始的资源请求阶段。
- 资源被分配给进程A、B、C（图b和图c），此时每个进程持有了一个资源。
- 进程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） 假设死锁不会发生，或者即使发生死锁也不去检测和处理。 - 简单实现，系统开销小。 - 死锁发生时可能导致系统停滞或无法继续工作。 - 不适用于高可靠性和高可用性要求的系统。 死锁预防
- 破坏互斥条件：
- 在某些情况下，资源可以共享（如读操作）。通过允许多个进程共享资源，可以避免互斥条件。例如，多进程同时读取一个文件，而不进行写操作。
- 破坏占有并等待条件：
- 要求进程一次性请求所有资源：进程在执行前，必须先一次性请求所有所需的资源。如果请求资源的数量大于当前可用资源，进程就会阻塞，直到所有资源都可用。这种方式确保了进程不会在占有资源时再请求新的资源，避免了占有并等待条件。
- 请求资源时不持有其他资源：进程请求一个资源时，必须先释放当前持有的所有资源，直到获得请求的资源。这意味着进程在请求资源时不能持有任何资源。
- 破坏非抢占条件：
- 允许资源抢占：当一个进程请求资源时，如果该资源已被其他进程占用，操作系统可以中断当前持有该资源的进程，强制将资源抢占并分配给请求进程。抢占的资源可以在适当的时机返回给原进程。
- 资源可以被强制回收：如果进程无法获得所需资源，系统可以强制回收当前占用的资源，并重新安排资源分配。
- 破坏循环等待条件：
- 资源请求顺序：规定资源的请求顺序，要求进程按固定顺序请求资源。例如，进程必须先请求资源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的总数加起来的再和所有可供使用的资源总数相加，结果就是该类资源总数。
死锁恢复
- 终止进程：强制终止一个或多个进程来释放资源，从而解除死锁。
- 资源回收：强制某些进程释放资源，其他进程可以使用这些资源来继续执行。
- 进程回滚：把某些进程的状态恢复到之前的安全状态，让它们重新开始执行。
其他问题
两阶段加锁
两阶段加锁（Two-Phase Locking, 2PL） 是一种常见的数据库事务控制协议，它在保证事务隔离性的同时避免了死锁的发生。两阶段加锁的基本原理是：一个事务必须首先完成对所需资源的加锁，直到它释放资源前不可以请求更多的锁。两阶段加锁分为两个阶段：
- 扩展阶段（Growing Phase）：事务可以不断地请求和获取锁。
- 收缩阶段（Shrinking Phase）：一旦事务释放了一个锁，它就不能再申请任何新的锁。
例子：银行转账事务
假设有两个进程（事务）在银行系统中执行转账操作，涉及两个账户的资源：账户A和账户B。
事务1（T1）：
T1的操作是从账户A转账到账户B，具体过程是：
- 请求锁定账户A，进行扣款。
- 请求锁定账户B，进行存款。
- 提交事务，释放锁。
事务2（T2）：
T2的操作是从账户B转账到账户A，具体过程是：
- 请求锁定账户B，进行扣款。
- 请求锁定账户A，进行存款。
- 提交事务，释放锁。
两阶段加锁的过程
- 事务T1：
- 扩展阶段：T1首先请求锁定账户A，成功获取锁。
- T1继续请求锁定账户B，也成功获得锁。
- T1没有再申请其他锁，进入收缩阶段，开始释放锁。
- 事务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 #include #include #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 pthread_mutex_unlock(&lock); // 解锁，允许其他线程访问临界区 break; // 如果票数小于或等于0，退出循环，结束线程执行 } pthread_mutex_unlock(&lock); // 解锁，允许其他线程访问临界区 } } return nullptr; // 线程结束 } int main() { // 创建NUM个线程 for(int i = 0; i
- 破坏互斥条件：
