死锁

死锁概念

死锁是由于竞争资源或者通信关系，两个或更多线程在执行中出现的，永远相互等待只能由其他进程引发的事件 的状态。

我们使用进程和资源的关系来对死锁进行描述。系统中存在各种类型的资源（CPU执行时间、内存空间、I/O设备等），每类资源都可能有多个实例。

进程访问资源时，有如下流程：

  • 请求/获取：申请空闲资源
  • 使用/占用：进程占用资源
  • 释放：资源状态由占用变成空闲

而资源可以分为如下两类：

  • 可重用资源（Reusable）：资源不能删除，互斥，可重用，比如处理器、I/O通道，主副存、文件、数据库、信号量等等，在各占一部分资源时会出现死锁
  • 消耗资源（Consumable）：资源创建和销毁，在I/O缓冲区的中断、信号、消息等，相互等待通信时可能死锁。

进程和资源之间的分配和占用可以用资源分配图表示，这是一个有向图，其中资源和进程间的分配和占用关系如下图所示：

Resource_allocation_mapping

出现死锁的必要条件：

  • 互斥
    • 任何时刻只能有一个进程使用一个资源实例
  • 持有并等待
    • 进程保持至少一个资源 并正在等待获取其他进程持有的资源
  • 非抢占
    • 资源只能在进程使用后自愿释放
  • 循环等待

死锁和非死锁的资源分配图示例：

Resource_allocation_mapping_Deadlock

如上两个图中的情况的不同在于，图右的产生循环的资源都不止一个实例。

死锁处理方法

  • 死锁预防（prevention）：限制并发进程对资源的请求，使得系统在任何时刻都不满足死锁的必要条件（四个）。
  • 死锁避免（avoidance）：在分配资源前判断，只允许不会出现死锁的进程请求资源。
  • 死锁检测和恢复：在检测到运行系统进入死锁状态后，进行恢复。

目前大多数操作系统都是由应用程序来解决死锁问题。

死锁预防

限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件，即消除死锁的必要条件。

消除四个必要条件的做法：

  • 互斥：允许资源同时使用。比如在线编辑文档
  • 持有并等待：进程请求资源时，要求它不持有其他任何资源。即要求所有进程在开始执行时，一次性地申请在整个运行过程中所需的全部资源（资源利用效率会变低）
  • 非抢占：如果进程请求不能立即分配的资源，则释放占有资源，再分配时只对拥有所有所需资源的进程进行分配操作。
  • 循环等待：对资源排序，要求进程按顺序请求资源

死锁避免

利用额外的先验信息，在分配资源时进行动态检查，若分配后系统可能发生死锁，则不予分配，否则予以分配。

安全状态
  • 如果系统能按某种顺序为每个进程依次分配其所需的资源，直至所有进程都能运行完成，称此时系统处于安全状态
  • 这种进程的顺序，如P4,P1,…,Pn, 称为安全序列
  • 若不存在这样一个安全序列称此时系统处于不安全状态
  • 如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。

注意：不安全状态≠死锁

  • 处于不安全状态的系统不一定会发生死锁（具体原因可看这篇博文）
  • 处于安全状态的系统一定不会发生死锁

如下图所示：

image-20210907110701819

银行家算法

银行家算法就是一种基于资源安全状态判断的死锁避免算法，借鉴银行贷款的策略实现。

  • 申请资源的线程在第一次申请资源的时候需声明所需最大资源数，在满足所有资源要求并执行完成后，及时释放资源归还操作系统
  • 若线程申请的资源数量不超过操作系统拥有的最大值时，操作系统尽量满足申请资源的线程的需求

实现银行家算法时需要的数据结构如下（n 为线程数量，m 为资源类型数量）：

  • 总需求矩阵Max：各个线程对应每种资源的最大需求量（n x m 矩阵）
  • 总剩余向量Available：各个资源的剩余量（长度为 m 的向量）
  • 已分配矩阵Allocation：各个线程对应每种资源的已有量（n x m 矩阵）
  • 未来需要矩阵Need：各个线程对应每种资源的需求差量（n x m 矩阵）
1
Need[i,j] = Max[i,j] - Allocation[i,j]

银行家算法安全状态判断：

  1. 初始化长度为 m 的Work向量和 长度为 n 的Finish向量

    1
    2
    Work = Available // 当前资源剩余空闲量
    Finish[i] = false for i : 1, 2, ..., n // 线程i有没有完成

  2. 寻找线程Ti，其满足以下条件:

    • Finish[i] = false
    • Need[i] <= Work

    没有找到满足条件的线程，则跳转到步骤4

  3. 找到线程Ti，则进行以下操作：

    • Work = Work + Allocation[i]
    • Finish[i] = true
    • 回到 步骤1

  4. 检查所有线程是否满足 Finish[i] == true

    • 若都等于，则系统处于安全状态

知道了如何进行安全状态判断后，就有了整体的算法执行流程，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
初始化: Requesti 线程Ti的资源请求向量
       Requesti[j] 线程Ti请求资源Rj的实例数量
循环:
1.如果 Requesti ≤ Need[i], 转到步骤2。否则, 拒绝资源申请, 因为线程已经超过了其最大要求
2.如果 Requesti ≤ Available, 转到步骤3。否则, Ti 必须等待, 因为资源不可用
3.通过安全状态判断来确定是否分配资源给Ti: 生成一个需要判断状态是否安全的资源分配环境
	- Available = Available - Requesti;
	- Allocation[i] = Allocation[i] + Requesti;
	- Need[i]= Need[i] – Requesti;
4.调用安全状态判断方法，
	- 若安全 则分配资源给Ti
	- 若不安全 则拒绝Ti的资源请求

死锁检测(Deadlock Detection)

死锁检测方法和银行家算法的系统安全状态判断是类似的。其执行流程如下：

  1. 初始化 Work 和 Finish:
    • Work = Available // work为当前资源剩余量
    • Allocation[i] > 0时 Finish[i] = false 否则为 true // 线程是否完成
  2. 寻找线程Ti满足:
    • Finish[i] = false // 线程没有结束 且 此线程需要的资源量小于剩余资源量
    • Requesti <= Work
    • 若没有找到 则跳到步骤4
  3. 将找到的线程拥有的资源释放回当前空闲资源
    • Work = Work + Allocation[i]
    • Finish[i] = true
    • 跳到步骤2
  4. 检查所有线程的 Finish 若有一个为 false 则系统处于死锁状态

算法的时间复杂度为O(n^2 x m)，若让操作系统检测系统是否处于死锁状态，开销比较大，因此实际场景操作系统不管死锁。

死锁恢复(Deadlock Recovery)

  • 选择哪个进程去终止?

    • 终止所有死锁的进程
    • 一次只终止一个进程直到死锁消除
    • 终止进程的顺序应该是
      • 进程的优先级(选最低的)
      • 进程已运行时间以及还需运行时间(运行时间越长越考虑留下 因为已经利用资源算了很长时间了)
      • 进程已占用资源
      • 进程完成需要的资源
      • 终止进程数目(越少越好)
      • 进程是交互还是批处理(让交互的继续执行)

  • 怎么样终止进程? 资源抢占

    • 选择被抢占进程(成本最小的)
    • 进程回退 返回到一些安全状态 重启进程到安全状态
    • 可能出现饥饿 同一进程可能一直被选作抢占者

进程通信

进程间进行通信和同步的机制。

进程通信概念

Inter-Processing Communication，后面我们都将进程通信简称为IPC。

IPC提供2个基本操作，发送（send）和接收（receive）。

进程通信流程

  1. 在通信进程间建立通信链路
  2. 通过send/receive交换消息

进程链路特征

  • 物理（如共享内存、硬件总线）
  • 逻辑（如逻辑属性）

直接通信和间接通信

IPC可分为直接通信和间接通信：

间接通信(通过系统维护的消息队列)，生命周期可以不同(两个进程不需要同时存在)

  • 每个消息队列都有一个唯一的标识
  • 只有共享了相同消息队列的进程 才能够通信
  • 通信链路属性
    • 只有共享了相同消息队列的进程 才建立连接
    • 连接可以为单向也能为双向
    • 消息队列可以与多个进程相关联
  • 间接通信流程
    1. 创建一个新的消息队列
    2. 通过消息队列发送和接受消息(只关心消息队列是谁)
    3. 销毁消息队列
Indirect_communication

直接通信（两个进程必须同时存在才能进行通讯）

  • 进程必须正确命名对方
  • 通信链路的属性
    • 自动建立链路
    • 一条链路恰好对应一对通信进程
    • 每对进程之间只有一个链路存在
    • 链路可以为单向 但通常为双向
Direct_communication

阻塞与非阻塞通信

进程通信可划分为阻塞(同步)通信与非阻塞(异步)通信

阻塞通信

  • 阻塞发送
    • 发送者在发送消息后进入等待 直到接受者成功收到
  • 阻塞接受
    • 接受者在请求接受消息后进入等待 直到成功收到消息

非阻塞通信

  • 非阻塞发送
    • 发送者在消息发送后 可立即进行其他操作
    • 没有消息发送时 接受者在请求接受消息后 接受不到任何消息(可以做别的事)

通信链路缓冲

进程发送的消息在链路上可能有三种缓冲方式

  • 0 容量
    • 发送方必须等待接收方(必须有接收方)
  • 有限容量
    • 通信链路缓冲队列满时 发送方必须等待
  • 无限容量
    • 发送方不需要等待

信号(Signal)

进程间的软件中断通知和处理机制(SIGKILL SIGSTOP SIGCONT)

  • 信号的接收处理
    • 捕获(Catch)：执行进程指定的信号处理函数
    • 忽略(Ignore) ：执行操作系统指定的缺省处理(例如进程终止、进程挂起)
    • 屏蔽(Mask) ：禁止进程接受和处理信号(可能是暂时的 当处理同样类型的信号)
  • 不足
    • 传送的信息量小，只有一个信号类型

信号的实现

Signal_implementation

信号的使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <signal.h>
void sigproc() { 		
signal(SIGINT, sigproc);   // 为了兼容
	printf(“you have pressed ctrl-c - disabled \n”);  
}

void quitproc() { 		 
	printf(“ctrl-\\ pressed to quit\n”);   /* this is “ctrl” & “\” */
	exit(0);
}
int main() { 
    signal(SIGINT, sigproc);  // signal 是注册信号的系统调用，摁下 ctrl+\ 时会发送SIGQUIT信号，
  														// 摁下 ctrl+c 时会发送SIGINT信号
    signal(SIGQUIT, quitproc);
	printf(“ctrl-c disabled use ctrl-\\ to quit\n”);
	for(;;);
}

管道(Pipe)

进程间基于内存文件的通信机制，进程不知道也不关心另一端

  • 子进程从父进程继承文件描述符
  • 缺省文件描述符 0 stdin, 1 stdout, 2 stderr

管道相关系统调用

  • 读管道 read()，scanf() 是基于它实现的
  • 写管道 write()，printf() 是基于它实现的
  • 创建管道 pipe(rgfd)
    • rgfd是2个文件描述符组成的数组
    • rgfd[0] 是读文件描述符
    • rgfd[1] 是写文件描述符

管道示例

Pipe
  1. 创建管道
  2. 为ls创建一个进程，设置其 stdout 为管道写端
  3. 为more创建一个进程，设置其 stdin 为管道读端

消息队列

消息队列是由操作系统维护的以字节序列为基本单位的间接通信机制

  • 每个消息(Message)是一个字节序列
  • 相同标识的消息组成按先进先出顺序组成一个消息队列(Message Queues)
Message_Queues

消息队列的系统调用

  • msgget()
    • 获取消息队列标识
  • msgsnd()
    • 发送消息
  • msgrcv()
    • 接收消息
  • msgctl()
    • 消息队列控制
    • 因为消息队列独立于创建它的进程 需要有系统调用完成消息队列的创建和销毁

共享内存

共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制

  • 进程
    • 每个进程都有私有内存地址空间
    • 每个进程的内存地址空间需明确设置共享内存段
  • 线程
    • 同一进程中的线程总是共享相同的内存地址空间
  • 优点
    • 快速 方便地共享数据
  • 不足
    • 必须用额外的同步机制来协调数据访问

共享内存的实现

通过页表项映射到同一物理页帧

Share_memory_implement
  • 优点：速度最快
    • 没有系统调用干预 没有数据复制
  • 缺点：不提供同步

共享内存的系统调用

为了保证数据的完整性 需要信号量等机制协调共享内存的访问冲突

  • shmget()
    • 创建共享段
  • shmat()
    • 把共享段映射到进程地址空间
  • shmdt()
    • 取消共享段到进程地址空间的映射
  • shmctl()
    • 共享段的控制