操作系统之 死锁和进程通信

死锁

由于竞争资源或者通信关系 两个或更多线程在执行中出现 用于相互等待只能由其他进程引发的事件

资源分类

• 可重用资源(Resuable Resource)
  • 资源不能被删除且在任何时刻只能有一个进程使用
  • 进程释放资源后 其他进程可重用
  • 处理器 I/O通道 存储器 设备
  • 文件(进程访问过程中不能被删除) 数据库 信号量
  • 可能出现死锁(每个进程占用一部分资源并请求其它资源)
• 消耗资源(Consumable Resource)
  • 资源创建和消耗
  • 在I/O缓冲区的中断 信号 消息
  • 可能出现死锁(进程间相互等待接受对方的消息)

资源分配图

资源和进程间的分配和占用关系有向图

出现死锁的必要条件

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

死锁处理方法

通常操作系统忽略死锁 由应用进程处理死锁

• 死锁预防(Deadlock Prevention)
  • 确保系统永远不会进入死锁状态(资源利用率低)
• 死锁避免(Deadlock Avoidance)
  • 在使用前进行判断 只允许不会出现死锁的进程请求资源
• 死锁检测和恢复(Deadlock Detection & Recovery)
  • 在检测到系统进入死锁状态后 进行恢复

死锁预防(Deadlock Prevention)

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

• 互斥
  • 把互斥的共享资源封装成可同时访问
• 持有并等待
  • 进程请求资源时 要求它不持有任何其他资源
  • 仅允许进程在开始执行时 一次请求所有需要的资源
  • 资源利用率低
• 非抢占
  • 如进程请求不能立即分配的资源 则释放已占有资源
  • 只在能够同时获得所有需要资源时 才执行分配操作
• 循环等待
  • 对资源排序 要求进程按顺序请求资源
  • 资源利用率低

死锁避免(Deadlock Avoidance)

利用额外的先验信息 在分配资源时判断是否会出现死锁 只在不会死锁时分配资源

• 要求进程声明需要资源的最大数目
• 限定 提供 与 分配的资源数量 确保满足进程的最大需求
• 动态检查资源分配状态 确保不会出现环形等待

系统资源分配的安全状态

当进程请求资源时 系统判定分配后是否处于安全状态

• 系统处于安全状态
  • 针对所有已占有进程存在安全序列
• 序列<P1, P2, …, PN> 是安全的
  • Pi要求的资源 <= 当前可用资源 + 所有Pj持有资源 其中 j < i
  • 如Pi的资源请求不能立即分配 则Pi等待所有Pj(j < i) 完成
  • Pi完成后 Pi + 1 可得到所需资源 执行并释放所分配的资源
  • 最终整个序列的所有Pi都能获得所需资源
• 系统处于安全状态 一定没有死锁
• 系统处于不安全状态 可能出现死锁
  • 避免死锁就是确保系统不会进入不安全状态

银行家算法(Banker’s algorithm)

是一个避免死锁产生的算法

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

银行家算法数据结构

n = 线程数量
m = 资源类型数量

• Max(总需求量) = n x m 矩阵
• Available(剩余空闲量) 长度为 m 的向量
• Allocation(已分配量) = n x m 矩阵
• Need(未来需要量) = n x m 矩阵

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

银行家算法安全状态判断

• Work 和 Finish 分别是长度为 m 和 n 的向量初始化

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

1. 寻找线程Ti:
   • Finish[i] = false
   • Need[i] <= Work
   • 去 步骤3
2. 找到线程Ti
   • Work = Work + Allocation[i]
   • Finish[i] = true
   • 回到 步骤1
3. 检查所有线程是否满足 Finish[i] == true
   • 若等 则系统处于安全状态

init: Requesti 线程Ti的资源请求向量
      Requesti[j] 线程Ti请求资源Rj的实例
do-while:
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;
若安全 则分配资源给Ti
若不安全 则拒绝Ti的资源请求

银行家算法示例

满足安全序列 T2->T1->T3->T4

死锁检测(Deadlock Detection)

• 允许系统进入死锁状态
• 系统维护资源分配图
• 定期调用死锁检测算法来搜索图中是否存在死锁
• 出现死锁时 用死锁恢复机制进行恢复

死锁检测算法数据结构

和银行家算法相比 没有最大资源请求量的判断

Available 长度为 m 的向量 每种类型可用资源的数量
Allocation 一个 n x m 的矩阵 当前分配给各个进程每种类型资源的数量

算法需要O(n^2 x m) 操作检测是否系统处于死锁状态 开销大 因此实际操作系统不管死锁

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 则系统处于死锁状态

死锁检测算法的使用

• 死锁检测的时间和周期选择依据
  • 死锁多久可能会发生
  • 多少进程需要被回滚
• 资源图可能有多个循环
  • 难于分辨造成死锁的关键进程

死锁恢复(Deadlock Recovery)

选择哪个进程去终止?

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

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

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

进程通信(IPC Inter-Process Communication)

进程通信是进程进行通信和同步的机制

• IPC提供2个基本操作
  • 发送操作 send(message)
  • 接受操作 receive(message)
• 进程通信流程
  • 在通信进程间建立通信链路
  • 通过 send/receive 交换信息
• 进程链路特征
  • 物理(共享内存 硬件总线)
  • 逻辑(逻辑属性)

进程通信实现与划分

• 进程通信实现
  • 间接通信
  • 直接通信
• 进程通信可划分为
  • 阻塞与非阻塞通信

间接通信(通过系统维护的消息队列)

生命周期可以不同(两个进程不需要同时存在)

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

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

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

阻塞与非阻塞通信

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

阻塞通信

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

非阻塞通信

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

通信链路缓冲

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

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

信号(Signal)

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

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

信号的实现

信号的使用示例

#include <stdio.h>
#include <signal.h>
void sigproc() { 		
signal(SIGINT, sigproc);   /* NOTE some versions of UNIX will reset 
				            * signal to default after each call. So for 
				            * portability reset signal each time */
	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 是注册信号的系统调用 
    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] 是写文件描述符

管道示例

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

消息队列

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

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

消息队列的系统调用

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

共享内存

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

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

共享内存的实现

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

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

共享内存的系统调用

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

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