image-20240420163459407

死锁

1. 死锁的概念

死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

2. 死锁的必要条件

  1. 互斥条件：一个资源每次只能被一个进程使用
  2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放
  3. 不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺
  4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系

3. 死锁的处理

  1. 预防死锁
    • 破坏互斥条件, 例如共享资源,spooling技术,可以将打印机作为共享资源
    • 破坏请求与保持条件, 一次性申请所有资源
    • 破坏不剥夺条件, 资源可以被剥夺，使用trylock，如果获取不到资源，就释放已经获取的资源
    • 破坏循环等待条件, 给资源编号, 按序申请
  2. 避免死锁
    • 银行家算法: 安全状态和不安全状态
      • 安全状态: 当前系统状态下, 存在一个安全序列, 使得每个进程都能顺利完成
      • 不安全状态: 不存在安全序列
      • 比如有5个进程, 3个资源, 进程1需要3个资源, 进程2需要2个资源, 进程3需要2个资源, 进程4需要1个资源, 进程5需要4个资源。如果进程1先执行, 进程2,3,4都无法执行, 进程5也无法执行, 这就是不安全状态。所以要避免这种情况
        表示资源分配状态
      • 系统资源向量Available
      • 进程最大需求矩阵Max
      • 进程已分配资源矩阵Allocation
      • 进程还需要资源矩阵Need
        例如: 
        Available = (3, 3, 2)
        Max = ((7, 5, 3), (3, 2, 2), (9, 0, 2), (2, 2, 2), (4, 3, 3))
        Allocation = ((0, 1, 0), (2, 0, 0), (3, 0, 2), (2, 1, 1), (0, 0, 2))
        Need = ((7, 4, 3), (1, 2, 2), (6, 0, 0), (0, 1, 1), (4, 3, 1))
    • 资源分配图
      • 有向图, 顶点表示进程或资源, 边表示请求或分配
      • 有向边表示请求, 无向边表示分配
  3. 检测死锁

    • 资源分配图

    • 死锁检测算法

  4. 解除死锁
    • 终止所有死锁进程
    • 逐个终止进程, 直到死锁解除
    • 选择一个进程, 终止, 释放资源, 重启进程

4. 死锁的工业界应用

4.1 Redis 的分布式锁

  1. 所谓分布式锁，就是在分布式环境下，对资源进行加锁，保证在同一时刻只有一个客户端能够访问资源。Redis 的分布式锁是通过 setnx 命令实现的，setnx 是 set if not exists 的缩写，即如果 key 不存在，则设置 key 的值为 value，返回 1；如果 key 已经存在，则不做任何操作，返回 0。通过 setnx 命令，我们可以实现一个简单的分布式锁，即只有一个客户端能够成功地设置 key 的值，其他客户端都会失败。
    应该满足如下几个核心要求：
  • 互斥性：在任意时刻，只有一个客户端能够持有锁。
  • 不会发生死锁：即使持有锁的客户端崩溃或者网络异常，锁也能够被其他客户端获取。
  • 具有容错性：只要大部分 Redis 节点正常运行，客户端就可以获取和释放锁。
  • 解铃还须系铃人：只有加锁的客户端才能释放锁，即使是其他客户端也不能释放锁。
  • 高性能：加锁和释放锁的性能要尽可能高。
  • 高可用：加锁和释放锁的可用性要尽可能高。
  1. 为了避免死锁，我们可以给锁设置一个过期时间，即使持有锁的客户端崩溃，锁也会在一段时间后自动释放。在 Redis 中，我们可以使用 setex 命令来设置带有过期时间的锁，setex 是 set with expire 的缩写，即设置 key 的值为 value，并设置 key 的过期时间为 seconds 秒。通过 setex 命令，我们可以实现一个带有过期时间的分布式锁，即在加锁的同时，给锁设置一个过期时间，一段时间后锁会自动释放。

4.2 Zookeeper 的分布式锁

  1. Zookeeper 是一个分布式协调服务，提供了一些分布式协调的基本功能，如分布式锁、分布式队列、分布式选举等。Zookeeper 的分布式锁是通过创建临时有序节点实现的，临时有序节点是指在创建节点时，Zookeeper 会自动在节点后面添加一个递增的序号，序号是全局唯一的。通过创建临时有序节点，我们可以实现一个简单的分布式锁，即只有序号最小的客户端能够成功地获取锁。

  2. Zookeeper 的分布式锁应该满足如下几个核心要求：

    • 互斥性：在任意时刻，只有一个客户端能够持有锁。
    • 不会发生死锁：即使持有锁的客户端崩溃或者网络异常，锁也能够被其他客户端获取。
    • 具有容错性：只要大部分 Zookeeper 节点正常运行，客户端就可以获取和释放锁。
    • 解铃还须系铃人：只有加锁的客户端才能释放锁，即使是其他客户端也不能释放锁。
    • 高性能：加锁和释放锁的性能要尽可能高。
    • 高可用：加锁和释放锁的可用性要尽可能高。

4.3 PostgreSQL 死锁检测和解决

  1. PostgreSQL不对死锁进行预防，而是在发生死锁时，检测到死锁并终止一个事务，以解除死锁。PostgreSQL使用等待图来检测死锁，等待图是一个有向图，顶点表示事务，边表示事务之间的等待关系。当等待图中存在环时，就表示发生了死锁。PostgreSQL会检测到死锁并终止一个事务，以解除死锁。
  2. 检测方法
    • 等待图检测法
    • 超时检测法

4.4 锁等待队列

  1. 锁等待队列是一个队列，用来存放等待锁的线程。当一个线程请求锁时，如果锁已经被其他线程持有，那么这个线程就会进入锁等待队列，等待锁被释放。当锁被释放时，锁等待队列中的线程就会被唤醒，继续执行。