死锁与进程通信

由于竞争资源或者通信关系，两个或更多的并发进程各自占有某种资源而又都等待别的进程释放它们所占有的资源的现象称为死锁。这些并发进程循环等待，互不相让，所以形成了死锁的僵持局面，无法向前推进。通信则可以让多个进程进行同步和共享资源。

死锁

进程访问资源的流程

资源类型R1,R2,……，Rm,例如CPU执行时间、内存空间、I/O设备等

每类资源Ri有Wi个实例

进程访问资源的流程

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

资源分类

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

资源分配图

死锁的必要条件

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

死锁处理办法

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

死锁预防

预防是采取某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。

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

死锁避免

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

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

系统资源分配时的安全状态

系统处于安全状态

• 针对所有已占有进程，存在安全序列

• 序列<P1, P2, …, PN> 是安全的

• Pi要求的资源 <= 当前可用资源 + 所有Pj持有资源，其中 j < i

• 如Pi的资源请求不能立即分配 则Pi等待所有Pj(j < i) 完成

• Pi完成后 P(i+1)可得到所需资源 执行并释放所分配的资源

• 最终整个序列的所有Pi都能获得所需资源

安全状态与死锁状态的关系

• 系统处于安全状态,一定没有死锁
• 系统处于不安全状态,可能出现死锁

银行家算法(死锁避免算法)

线程在第一次申请资源的时候声明所需最大资源量，在满足所有资源要求并完成后及时释放资源。

同时在线程申请资源不超过操作系统拥有资源最大值时，操作系统应尽量满足线程的需求。

银行家算法数据结构

n = 线程数量 m = 资源类型数量
Max(总需求量) n x m 矩阵
线程Ti最多请求类型Rj的资源Max[i, j]个实例
Available(剩余空闲量) 长度为 m 的向量
当前有Available[i]个类型Rj的资源可用
Allocation(已分配量) = n x m 矩阵
当前分配了Allocation[i, j]个资源实例
Need(未来需要量) = n x m 矩阵
未来需要Need[i, j]个资源实例
Need[i, j] = Max[i, j] - Allocation[i, j]

银行家算法安全状态判断

即判断当前资源是否满足某一线程的未来需要

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

1. Work 和 Finish 分别是长度为 m 和 n 的向量，初始化二者
2. 寻找线程Ti:
   • Finish[i] = false
   • 接下来找出Need比Work小的进程，Need[i] <= Work
   • 没有找到满足条件的线程，转4
3. 存在满足条件的线程，线程Ti可以正常运行，结束后其占用资源可以回收
   • Work = Work + Allocation[i]
   • Finish[i] = true
   • 转 2
4. 若所有线程Ti满足 Finish[i] == true,则为安全状态

银行家算法流程

init: 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;
若安全 则分配资源给Ti
若不安全 则拒绝Ti的资源请求

银行家算法示例

按照序列 T2->T1->T3->T4 运行不存在死锁

若银行家算法存在多个满足条件的线程，则多个线程之间的先后顺序并不重要，因为这些进程的资源最后都会释放，之后可以满足需求更大的线程资源请求。

死锁检测

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

死锁检测算法数据结构

与银行家算法相比，没有最大资源请求判断。

Available(剩余空闲量)：长度为m的向量，当前有Available[i]个类型Rj的资源可用

Allocation(已分配量)：n * m矩阵，当前每个进程已分配了Allocation[i, j]个资源实例

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

算法需要O(n^2 x m) 操作检测是否系统处于死锁状态，每次检查m，检查n^2轮。

死锁检测算法的使用

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

死锁恢复

死锁恢复有进程终止和资源抢占两种方法

进程终止

可以选择终止所有死锁的进程，也可以一次只终止一个进程直到死锁消除

终止进程的顺序应该是

• 进程的优先级(选最低的)
• 进程已运行时间以及还需运行时间(运行时间越长越考虑留下，占用系统资源时间久)
• 进程已占用资源
• 进程完成需要的资源
• 终止进程数目(越少越好)
• 进程是交互还是批处理(让交互进程继续执行)

资源抢占

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

进程通信

进程通信(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); /* normal exit status */
}

main()
{ 
signal(SIGINT, sigproc);    /* DEFAULT ACTION: term */
signal(SIGQUIT, quitproc);  /* DEFAULT ACTION: term */
	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] 是写文件描述符

管道示例

消息队列

消息队列的系统调用

msgget()

• 获取消息队列标识

msgsnd()

• 发送消息

msgrcv()

• 接收消息

msgctl()

• 消息队列控制
• 消息队列独立于创建它的进程，所以需要有系统调用完成消息队列的创建和销毁。

共享内存

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

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

共享内存的实现

共享内存不提供同步，因此需要有信号量等同步机制协调共享内存的访问冲突。

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