死锁
死锁问题
一列系列阻塞的进程持有一种资源等待获取另一个阻塞的进程所占有的资源， 两个进程都因为没有获取到自己所需要的资源而不释放锁， 所以就会出现死锁问题。
类似行车道：
死锁的系统化模型
每个进程都使用
可重复使用的资源
- 一个时间内只能一个进程使用并且不能被释放删除
- 进程获取资源 ，后来释放由其他进程使用
- 处理器、IO通道、主和副存储器等等
- 如果每个进程拥有一个资源并请求其他资源， 死锁就有可能发生
资源分配图
一组顶点V和边E的集合
- V有两种类型 :
P={P1,P2,…,Pn},集合包括系统中的所有进程。
R={R1,R2,…,Rm},集合包括系统中的所有资源类型。
- requesting,claiming edge - directed edge Pi → Rj
- assignment,holding edge - directed edge Rj → Pi
死锁的特征
死锁一定会出现的四个条件，但是出现这些特征不一定是死锁。
- 互斥: 在一个时间只能有一个进程使用资源
- 持有并等待: 进程保持至少一个资源正在等待获取其他进程持有的额外资源
- 无抢占: 一个资源只能被进程资源释放,进程已经完成了它的任务之后
- 循环等待: 存在等待进程集合{P0,P1,…,Pn},P0正在等待P1所占用的资源,P1正在等待P2占用的资源…Pn-1在等待Pn的资源,Pn正在等待P0所占用的资源
死锁的处理方法
- 确保系统永远不会进入死锁状态
- 运行系统进入死锁状态,然后恢复.
- 忽略这个问题,假装系统中从来没有发生死锁,用于大多数操作系统,包括UNIX
Deadlock Prevention 预防
限制申请方式
- 互斥 — 共享资源不是必须的,必须占用非共享资源
- **占用并等待 **—-必须保证当一个进程请求的资源,它不持有任何其他资源;;;;
需要进程请求并分配其所有资源,它开始执行之前或允许进程请求资源仅当进程没有资源
资源利用率低,可能发生饥饿
- 无抢占 -
如果进程占有某些资源,并请求其他不能被立即分配的资源,则释放当前正占有的资源
被抢占资源添加到资源列表中
只有当它能够获得旧的资源以及它请求新的资源,进程可以得到执行
- 循环等待 - 对所有资源类型进行排序,并要求每个进程按照资源的顺序进行申请
Deadlock Avoidance 避免
需要系统具有一些额外的先验信息提供
- 最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目
- 资源的分配状态是通过限定提供与分配的资源数量,和进程的最大需求
- 死锁避免算法动态检查的资源分配状态,以确保永远不会有一个环形等待状态
- 当一个进程请求可用资源,系统必须判断立即分配是否能使系统处于安全状态
- 系统处于安全状态指: 针对所有进程,存在安全序列
- **序列<P1,P2,…,Pn>是安全的(我们需要其安装这个序列来执行资源): **针对每个Pi,Pi要求的资源能够由当前可用的资源+所有的Pj持有的资源来满足,其中j<i.
如果Pi资源的需求不是立即可用,那么Pi可以等到所有Pj完成
当Pi完成后,Pi+1可以得到所需要的资源,执行,返回所分配的资源,并终止.
用同样的方法,Pi+2,Pi+3和Pn能获得其所需的资源.
- 如果系统处于安全状态→无死锁
- 如果系统处于不安全状态→可能死锁
- 避免死锁: 确保系统永远不会进入不安全状态
Deadlock Detection 检测
每个资源类型单一实例
Maintain wait-for graph
- 节点是进程
- Pi→Pj: Pi等待Pj
定期调用检测算法来搜索图中是否存在循环
算法需要n^2次操作,n是图中顶点的数目
数据结构:
- Available（可用量）: 长度为M的向量表示每种类型可用资源的数量
- Allocation(已分配的量): 一个nxm矩阵定义了当前分配给各个进程每种类型资源的数量,如果Alocation[i, j] = k, 进程Pi拥有资源Rj的k个实例
- Request（当前进程的请求）: 一个nxm矩阵表示各进程的当前请求.如果Request[i, j] = k,表示进程Pi请求k个资源Pj的实例
具体算法
检查算法使用
检测算法：
何时,使用什么样的频率来检测依赖于:
- 死锁多久可能会发生?
- 多少进程需要被回滚? one for each disjoint cycle
如果检测算法多次被调用,有可能是资源图有多个循环,所以我们无法分辨出多个可能死锁进程中的哪些”造成”死锁
Recovery from Deadlock 恢复
终止所有的死锁进程
在一个时间内终止一个进程直到死锁消除
终止进程的顺序应该是:
- 进程的优先级
- 进程运行了多久以及需要多少时间才能完成
- 进程占用的资源
- 进程完成需要的资源
- 多少进程需要被终止
- 进程是交互还是批处理
选择一个受孩子 - 最小的成本
回滚 - 返回到一些安全状态,重启进程到安全状态
饥饿 - 同一进程可能一直被选作受害者,包括回滚的数量
进程通信
概念/概述
为什么要进行进程间通信 ？
答：
进程之间要相对保持独立，一个进程不能随便访问另一个进程（目的是为了保证进程正确的运行）。 与此同时， 我们还需要保证进程之间能够有效的沟通， 这就是我们为什么要有进程间通信。
进程通信的机制及同步
不使用共享变量的进程通信
IPC facility 提供2个操作:
- send(message)发送 —- 消息大小固定或者可变
- receive(message)接收
直接通信
要求 ：
- 进程必须正确的命名对方
如果P和Q想通信,需要:
- 在它们之间建立通信链路
- 通过send/recevie交换消息
通信链路的实现
- 物理(例如,共享内存,硬件总线)
- 逻辑(例如,逻辑属性)
间接通信
定向从消息队列接收消息
- 每个消息对垒都有一个唯一的ID
- 只有它们共享了一个消息队列,进程才能够通信
通信链路的属性
- 只有进程共享一个共同的消息队列,才建立链路
- 链接可以与许多进程相关联
- 每对进程可以共享多个通信链路
- 链接可以是单向或者双向
操作：
- 创建一个新的消息队列
- 通过消息队列发送和接收消息
- 销毁消息队列
原语的定义：
- send(A, message) —– 发送消息到队列A
- receive（A，message） ——从队列A接收消息
消息传递可以是阻塞或者非阻塞的
- 阻塞被认为是同步的
- 非阻塞被认为是异步的（send成功与否他都会很快的被返回）
队列的消息被附加到链路；可以是以下几种方式
- 0 容量 ；[发送方必须等待接收方]
- 有效容量 ； [ n messages的有限长度 。 发送方必须等待， 如果队列满. ]
- 无限容量 ； [ 无限长度 ，发送方不需要等待]
信号[ Signal ]
信号
- 软件中断通知事件处理 【打断了当前正在处理的事情】
- Examples: SIGFPE, SIGKILL, SIGUSRI, SIGSTOP, SIGCONT
接收到信号时会发生什么?
- catch: 指定信号处理函数被调用
- ignore: 依靠操作系统的默认操作(abort, memory dump, suspend
- or resume process)
- mask: 闭塞信号因此不会传送(可能是暂时的,当处理同样类型的信号)
大致处理流程 ：
这段可以尝试着自己找资料更加深入的去学习了解。
不足:
- 不能传输要交换的任何数据
管道：
每个程序应该单独完成一个小的功能， 但是我们又希望把这些程序灵活的组合起来 ，使它能够完成一个更加复杂的功能。
上述的想法如何实现 ？
在90年代， 科学家们想出了一个管道 ，让左边的输出作为右边的输入。
数据交换
- 子进程从父进程继承文件描述符(0 stdin, 1 stdout, 2 stderr)
- 进程不知道(或不关心)从键盘,文件,程序读取或写入到终端,文件,程序.
例如: $ ls | more (两个进程, 管道是缓存,对于ls来说是stdout,对于more来说是stdin )
通过shell:
- 创建一个管道
- 为1s创建一个进程， 设置stdout 为管道写端
- 为more 创建一个进程，设置为stdin 为管道读端
消息队列
消息队列按FIFO来管理消息
- message: 作为一个字节序列存储
- message queues: 消息数组
- FIFO & FILO configuration
共享内存
上述的管道和消息队列 都是一种间接通信的方式， 而我们的共享内存则是一种直接通信的方式。
他会在最开始的时候创建一块数据共享的区域，让多个进程来共享这个内存块。
进程
- 每个进程都有私有地址空间
- 在每个地址空间内,明确地设置了共享内存段
优点
- 快速,方便地共享数据
不足
- 必须同步数据访问
举例
两个进程共享DRAM区域
通过将共享进程的虚地址保存到每个进程中去
- 最快的方法
- 一个进程写另一个进程立即可见
- 没有系统调用干预
- 没有数据复制
- 不提供同步
