[系统运维]清华向勇《操作系统》学习笔记11：死锁和进程通信

11.1 死锁

窄桥上，互不相让，就会发生“死锁”。
窄桥上一方持续车流，另一方就无法通过，就是“饥饿”。

根源是没有讲窄桥本身视作一个整体资源，“互斥访问”

11.1.1死锁概念

我们将死锁使用进程和资源的关系进行描述。
资源类型R₁, R₂, R₃…R_m。

• CPU执行时间、内存空间、I/O设备等

每类资源R_i有W_i个实例。

资源可以分为如下两类：

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

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

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

进程和资源之间的分配和占用可以用资源分配图表示，这是一个有向图

另一类边是资源分配边，由资源指向进程，表示资源R_j分配给进程P_i

出现死锁的必要条件

• 互斥
• 持有并等待
• 非抢占
• 循环等待

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

11.1.2 死锁处理方法

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

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

或许这就是手机卡死之后往往退出这个APP就好了的原因。说到底还是APP没设计好

消除死锁的必要条件：

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

都不同程度上使用了时间换时间、空间换时间的思路。所以效率相对较低。

所以我们可以尝试使用额外的先验信息，在分配资源时动态判断是否为系统资源安全状态，只在不会死锁时分配资源。

• 要求进程声明需要资源的最大数目
• 限定提供和分配的资源数目

系统资源安全状态：原理上不会死锁的状态。
实现思路是，进程排成一个序列，前一个进程依次释放的资源+已有可用资源能满足后一个的需求。

11.1.3 银行家算法

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

为了利益的最大化，要考虑两个方面的因素

• 不能超出贷款限额，防止资金链断裂
• 要使得资金流通起来，增大资金利用率

对应就是尽可能利用资源且不超出资源总量。

实现银行家算法时需要的数据结构如下：

• 总需求矩阵：各个线程对应每种资源的最大需求量
• 总剩余向量：各个资源的剩余量
• 已分配矩阵：各个线程对应每种资源的已有量
• 未来需要矩阵：各个线程对应每种资源的需求差量

Need[i,j] = Max[i,j] - Allocation[i,j]

银行家算法的核心就是进行安全状态判断。

1. 确定资源余量和每个线程的完成状态
2. 寻找可以利用当前资源完成的线程。
3. 完成线程之后，释放当前线程的资源，留待下一个线程使用。
4. 最后检查所有线程是否做完。

举如下的情形为例，对当前任意一个进程，可用资源都不足以满足请求矩阵的任意一行。因此这些线程的资源需求对于当前计算机系统来说不安全。

11.1.4 死锁检测

允许系统进入死锁状态。

方法和银行家算法的系统安全状态判断是一样的。

只不过最后一步判断有一个false就认为是

死锁恢复
终止所有的死锁进程，一次只终止一个进程直到死锁消除

终止的顺序应该是

• 进程的优先级
• 进程已运行时间以及还需运行时间
• 进程已占用资源
• 进程完成需要的资源
• 终止进程数目
• 进程是交互还是批处理

资源抢占：

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

11.2 进程通信

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

11.2.1 进程通信概念

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

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

进程通信流程

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

进程链路特征

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

直接通信和间接通信

对于直接通信：

• 进程必须正确地命名对方
• 自动建立链路
• 一条链路恰好对应一对通信进程
• 链接可以是单向的，但通常为双向的

对于间接通信

• 通过操作系统维护的消息队列实现进程间的消息接收和发送
  • 每个消息队列都有一个唯一的标识
  • 只有共享了相同消息队列的进程，才能够通信
• 通信链路属性：
  • 只有共享了相同消息队列的进程，才能够通信
  • 连接可以是单向或双向
  • 消息队列可以与多个进程相关联
  • 每对进程可以共享多个消息队列

间接通信流程：

• 创建一个新的消息队列
• 通过消息队列发送和接收消息
• 销毁消息队列

IPC可以分为阻塞和非阻塞。
阻塞通信可以分为：

• 阻塞发送：发送后等待，直到对方接收
• 阻塞接收：在接收请求之后等待，直到接收

相对应的，非阻塞分为：

• 非阻塞发送：消息发送之后，立即进行其他操作
• 非阻塞接收：没有消息发送时，即便有接收请求也不管。

通信链路缓冲分为三种：

• 0容量：发送方必须等待接收方（的存在）
• 有限容量：通信链路缓冲队列满时，发送方必须等待
• 无限容量：发送方不需要考虑等待接收方的问题

接下来讨论IPC的四种实现

11.2.2 信号

信号是进程间软件中断通知和处理机制。如SIGKILL，SIGSTOP，SIGCONT等

流程示意如下，在接受到信号时，进程X执行相应的信号处理函数。

接收信号之后，一般有如下的几种处理方式：

• 捕获（catch）：执行进程指定的信号处理函数
• 忽略（ignore）：执行操作系统指定的缺省处理（例如进程终止，进程挂起等等）
• 屏蔽（mask）：禁止进程接收和处理信号，可能是暂时的

信号的传送量小，一次只有一个确定的信号类型。

11.2.3 管道

进程间基于内存文件的通信机制。

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

进程并不关心另一端的性质：

• 可能从键盘、文件或程序读取
• 可能写入到终端、文件或程序

与管道相关的系统调用：

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

管道示例：

11.2.4 消息队列

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

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

有点类似于信号量的机制。如果先知道消息队列的话，可以使用消息队列的模式来讲解信号量。

消息队列相关系统调用如下：

• msgget(key, flags) 获取消息队列标识
• msgsnd(QID, buf,size,flags) 发送消息
• msgrcv(QID,buf,size,type,flags) 接收消息
• msgctl(…)消息队列控制

更多可以查询手册

11.2.5 共享内存

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

进程

• 每个进程都有私有内存地址空间
• 每个进程的内存地址空间需要明确设置共享段

线程

• 同一个进程中的线程总是共享相同的内存地址空间

特点

• 快速方便地共享数据
• 还需要同步机制才能实现通信