死锁

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟

死锁的条件

共享资源访问

锁机制

  • 锁获取：是一个原子操作；一个进程获得锁后，其他进程等待
  • 锁释放：锁释放后，请求锁的某一个进程可以获得锁
  • 锁的原子性：通过进入临界区的原子性保证锁的原子性

资源持有与请求

当资源持有与请求图中形成环路，则代表形成死锁

例如：进程A持有资源R，进程B持有资源S。A在持有R的时候请求S，而B在持有S的时候请求R，这样就导致了死锁。

死锁

在讨论死锁的时候，进程和线程等价！

定义

两个或两个以上进程/线程在执行过程中，因争夺资源而造成的一种相互等待的现象。

影响

  • 发生死锁的进程/线程无法执行
  • 被占有的资源无法释放
  • 浪费系统资源，降低了系统性能

与饥饿的关系

  • 饥饿：进程无限等待
  • 死锁可能导致饥饿

死锁的必要条件

互斥

  • 某个资源在一段时间内只能由一个进程占有，且其他进程无法访问

占有且等待

  • 一个进程占有资源，同时请求新资源
  • 新资源被其他进程占有，进程等待资源被释放

不可抢占

  • 资源不可被抢占，只能由占有者主动释放

环路等待

  • 多个进程以环路的方式进行等待

处理死锁的策略

忽略问题（鸵鸟算法）

认为产生死锁是用户的错

  • 操作系统内核死锁
    • 重启
  • 设备驱动死锁
    • 卸载设备是否重启
  • 应用程序死锁（程序挂起或“不响应”）
    • 方法一：杀死并重启程序
    • 方法二：给程序设定一个checkpoint；在改变运行环境后，从上一个checkpoint重新开始

检测并恢复

检测

  • 扫描资源分配图，检测环路

恢复

  • 杀死进程/线程
    • 全部终止或逐个终止
  • 有时需要回滚死锁线程（例如数据库）
    • 代价大

避免

安全状态

  • 未发生死锁
  • 存在一个调度方案
    • 使得所有进程能够按照某一次序分配资源，依次运行完成
    • 且满足所有进程同时请求最大资源

安全状态判断

核心思想：寻找一个使系统安全的进程资源分配序列

  1. 初始化
    • 当前可用资源：Available；进程需求资源：Need
    • 进程已分配资源：Allocation；进程完成标记：Finish=true
  2. 寻找一个进程Ti，满足Need<=Available & Finish=False，否则执行4
  3. 执行进程Ti，完成后释放所有资源，更新如下信息，重复2
    • Available+=Allocation
    • Finish=True
  4. 若此时所有进程的Finish=True，则系统安全，否则系统不安全

银行家算法

核心思想：再分配资源前，假设已经给资源做了分配，若分配后保证系统处于安全状态，则分配

  • 单个资源
    • 每个进程都有一个资源需求
    • 总的资源可能不能满足所有的资源需求
    • 跟踪已分配的资源和仍然需要的资源
    • 每次进程请求资源时，系统分配前检查安全性
  • 多个资源
    • n代表线程数量，m代表资源类型数量，i代表线程编号，j代表资源编号
    • Available（剩余空闲量）：长度为m的向量
    • Allocation（已分配量）：大小为\(n\times m\)的矩阵
    • Need（未来需要量）：大小为\(n\times m\)的矩阵
      • \(Need[i,j]=Max[i,j]-Allocation[i,j]\)

银行家算法的描述

  1. 初始化\(Request_i[j]\)代表线程Ti请求资源Rj的实例

循环处理线程Ti

  1. 如果\(Request_i \leq Need[i]\)，则跳转到步骤2。否则拒绝资源申请，因为线程请求的资源已经超过了其最大的要求
  2. 如果\(Request_i \leq Available\)，则跳转到步骤3。否则该线程必需等待，因为当前资源不足
  3. 假设资源已经分配给了Ti，执行如下what-if判断，进行如下更新计算
$$ Available=Available-Request_i \\\\ Allocation[i]=Allocation[i]+Request_i \\\\ Need[i]=Need[i]-Request_i $$
  1. 调用安全状态判断此时系统是否安全
    • 若返回结果是安全，则将资源分配给Ti
    • 若返回结果是不安全，系统则拒绝Ti的资源请求

预防

消除死锁四个必要条件中的一个

避免互斥

  • 资源设计成可共享，不用互斥
    • 只读文件、只读内存、读/写锁等
    • 缺点：有些资源必须互斥访问
  • 增加资源
    • 使用临时缓存，使得一个资源看起来像有多个资源（虚拟化）
    • 使用队列进行调度
  • Lock-Free设计
    • 使用原子操作，例如CAS指令

避免占有和等待

采用两阶段加锁的策略

  • 阶段一：试图对所有所需的资源进行加锁
  • 阶段二：
    • 如果成功则使用资源，然后释放资源
    • 否则释放所有资源，再从头开始

允许抢占

使调度器了解资源分配情况

  • 方法一：
    • 如果系统无法满足一个已占有资源的进程的请求，则抢占该进程并释放所有资源
    • 只在系统能满足所有资源时在进行调度
  • 方法二
    • 抢占正占有被请求的资源的进程

减少抢占带来的开销

  • 将已完成工作（例如数据、状态等）复制到一个缓冲区，再释放资源

避免环路等待

对所有资源制定请求顺序

  • 方法一：
    • 对每个资源分配唯一的id
    • 所有请求必须按照id升序提出
  • 方法二：
    • 对每个资源分配唯一的id
    • 进程不能请求比当前所占有资源编号低的资源
    • 占用高资源标号的进程需要释放资源

权衡和应用

  • 死锁处理
    • 处理死锁是应用开发者的工作
    • OS应该要提供打破应用程序死锁的机制
  • 内核不应该出现死锁
    • 使用预防方法
    • 流行做法：在所有地方使用避免环路等待原则