11-死锁
死锁问题
一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源
例子：
系统有2个磁带驱动器
P1和P2各有一个，都需要另外一个
系统模型
- 资源类型R1,R2,...,Rm
CPU cycles, memory space, I/O devices - 每个资源类型Ri都有Wi实例
- 每个进程使用资源如下
- request/get <--free resource
- use/hold <--requested/used resource
- release <--free resource
可重复使用的资源
- 在一个时间只能一个进程使用且不能被删除
- 进程获得资源，后来释放由其他进程重用
- 处理器，I/O通道，主和副存储器，设备和数据结构，如文件，数据库和信号量
- 如果每个进程拥有一个资源并请求其他资源，死锁可能发生
使用资源
- 创建和销毁
- 在I/O缓冲区的中断，信号，消息，信息
- 如果接收消息阻塞可能会发生死锁
- 可能少见的组合事件会引发死锁
资源分配图
概念：一组顶点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
1. Deadlock Prevention(死锁预防)
限制申请方式
- 互斥 - 共享资源不是必须的，必须占用非共享资源
- 占用并等待 - 必须保证当一个进程请求的资源，它不持有任何其他资源
需要进程请求并分配其所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源
资源利用率低，可能发生饥饿 - 无抢占
如果进程占有某些资源，并请求其他不能被立即分配的资源，则释放当前正占有的资源
被抢占资源加到资源列表中
只有当它能够获得旧的资源以及它请求新的资源，进程可以得到执行 - 循环等待 - 对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请
2. Deadlock Avoidance(死锁避免)
需要系统具有一些额外的先验信息提供
- 最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目
- 资源分配状态是通过限定提供与分配的资源数量，和进程的最大需求
- 死锁避免算法动态检查的资源分配状态，一确保永远不会有一个环形等待状态
当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态
系统处于安全状态是指：针对所有进程，存在安全序列
序列<P1,P2,...,PN> 是安全的：针对每个Pi,Pi要求的资源能够由当前可用的资源+所有的Pj持有的资源来满足，其中j<i
- 如果Pi资源的需求不是立即可用，那么Pi可以等到所有Pj完成
- 当Pi完成后，Pi+1 可以的带所需要的资源，执行，返回所分配的资源，并终止。
- 用同样的方法，Pi+2,Pi+3和Pn能获得其所需的资源
如果系统处于安全状态=>无死锁
如果系统处于不安全状态=>可能死锁
避免死锁：确保系统永远不会进入不安全状态
银行家算法
银行家算法（Banker's Algorithm）是一个死锁避免的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础, 判断并保证系统的安全运行。
背景
在银行系统中，客户完成项目需要申请带宽的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目锁需的最大资金量，在满足所有贷款要求并完成项目时，客户应及时归还。
银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。
在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
Banker's Algorithm 前提条件
- 多个实例
- 每个进程都必须能最大限度地利用资源
- 当一个进程请求一个资源，就不得不等待
- 当一个进程获得所有的资源就必须在一段有限的时间释放它们
基于上述前提条件，银行家算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想执行时序，来决定一个状态是否是安全的
不存在着满足要求的执行时序的状态都是不安全的。
银行家算法的数据结构
n=进程数量，m=资源类型数量
- Max(总需求量): n*m矩阵。如果Max[i,j]=k,表示进程Pi最多请求资源类型Rj的k个实例
- Available(剩余空闲量)：长度为m的向量。如果Available[j]=k,有k个类型Rj的资源实例可用
- Allocation(已分配量)：n*m矩阵。如果Allocation[i,j]=k,则Pi当前分配了k个Rj的实例
- Need(未来需要量)： n*m矩阵。如果Need[i,j]=k,则Pi可能需要至少Rj个实例完成任务
Need[i,j]=Max[i,j]-Allocation[i,j]
- Work 和Finish 分别是长度为m和n的向量
初始化：Work = Available // 当前资源剩余空间
Finish[i] = false for i -1,2,...,n // 线程i没结束 - 找这样的i:
(a) Finish[i] = false
(b) Needi<=Work
没有找到这样的i, 转到4 - Work =Work +Allocationi // 进程i的资源需求量小于当前剩余空闲资源, 所以配置给它再回收
Finish[i]=true
转2 - If Finish[i] == true for all i, // 所有进程的Finish为True, 表名系统处于安全状态
then the system is in a safe state.
Banker's Algorithm
Initial:Request = request vector for process Pi. If Requesti[j]=k then process Pi wants k instances of resource type Rj. while:
- 如果Requesti < Needi 转到步骤2。否则，提出错误条件，因为进程已经超过了其最大要求。
- 如果Requesti < Available 转到步骤3，否则Pi必须等待，因为资源不可用
- 假装给Pi分配它需要的资源：// 生成一个需要判断状态是否安全的资源分配环境
Available = Available -Requesti;
Allocationi = Allocationi +Requesti;
Needi = Needi - Requesti;
CALL Safety State Estimating Algorithm
如果返回safe, 将资源分配给Pi.
如果返回unsafe, Pi必须等待，旧的资源分配状态被恢复
3. Deadlock Detection(死锁检测)
- 死锁检测和死锁恢复允许系统进入死锁状态
死锁检测算法
- Work 和Finish分别是长度为m与n的向量，初始化
（a）Work = Available // work为当前空闲资源
（b）For i -1,2,...,n if Allocationi>0, then Finish[i] = false; otherwise, Finish[i]=true // Finish为线程是否结束 - 找出这样的索引i:
(a) Finish[i]==false // 没有结束的线程，且此线程将需要的资源量小于当前空闲资源量
(b) Requesti<=Work
如果没有找到，转到4 - Work = Work +Allocationi // 把找到的线程拥有的资源释放会当前空闲资源中
Finish[i]=true
转到2 - If Finish[i] == false, for some i, 1<=i<=n,系统处于死锁状态。此外，if Finish[i] ==false, Pi死锁。//如果有Finish[i]等于false, 这表示系统处于死锁状态
算法需要O(m*n^2) 操作检测是否系统处于死锁状态，且request需要的资源也需要提前预知，给使用造成较大困难
在实际操作系统中，不会预防也不会检测死锁，系统卡死就重启。
4. Recovery from Deadlock(死锁恢复)
- 终止所有的死锁进程
- 在一个时间内终止一个进程直到死锁消除
- 终止进程的顺序应该是
- 进程的优先级
- 进程运行了多久以及需要多少时间才能完成
- 进程占用的资源
- 进程完成需要的资源
- 多少进程需要被终止
- 进程是交互还是批处理
选择一个受害者 - 最小成本
回滚 - 返回到一些安全状态，重启进程到安全状态
饥饿 - 同一进程可能一直被选作受害者，包括回滚的数量
死锁在实际应用中还没有很好的方法，感兴趣可以关注最新的操作系统的相关论文
IPC（InterProcessCommunication - 进程间通信）
概述
通信模型
- 进程通信的机制及同步
- 不适用共享变量的进程通信
- IPC facility提供2个操作：
send(message) -消息大小固定或者可变
receive(message) - 如果P和Q想通信，需要
在它们之间建立通信链路
通过send/receive 交换消息 - 通信链路的实现
物理（例如，共享内存，硬件总线）
逻辑（例如，逻辑属性）
直接及间接通信
直接通信
-
进程必须正确的命名对方
send(P, message) - 发送信息到进程IP
receive(Q, message) - 从进程Q接受消息 -
通信链路的属性
自动建立链路
一条链路恰好对应一对通信进程
每对进程之间只有一个链接存在
链接可以是单向的，但通常为双向的
间接通信
- 定向从消息队列接收消息
每个消息队列都有一个唯一的ID
只有它们共享了一个消息队列，进程才能够通信 - 通信链路的属性
只有进程共享一个共同的消息队列，才建立链路
链接可以与许多进程相关联
每对进程可以共享多个通信链路
链接可以是单向或双向 - 操作
创建一个新的消息队列
通过消息队列发送和接收消息
销毁消息队列 - 原语的定义如下
send(A, message) - 发送消息到队列A
receive(A,message) - 从队列A接受消息
阻塞与非阻塞
-
消息传递可以是阻塞或非阻塞
-
阻断被认为是同步的
Blocking send has the sender block until the message is received
Blocking receive has the receiver block until a message is available -
非阻塞被认为是异步的
Non-blocking send has the sender send the message and continue
Non-blocking receive has the receiver revceive a valid message or null
通信链路缓冲
- 队列的消息被附加到链路；可以是以下3种方式之一：
- 0容量 - 0 message
发送方必须等待接收方 - 有限容量 - n message的有限长度
发送方必须等待，如果队列满 - 无限容量 - 无限长度
发送方不需要等待，接收方如果队列是空，还是必须要等待或者报错
- 0容量 - 0 message
信号
- signal(信号)
软件中断通知事件处理
Examples: SIGFPE, SIGKILL, SIGUSRI, SIGSTOP, SIGCONT - 接收到信号时会发生什么
Catch: 指定信号处理函数被调用
Ignore：依靠操作系统的默认操作
Example:Abort, memory dump, suspend or resume process
Mask: 闭塞信号因此不会传送
可能是暂时的（当处理同样类型的信号） - 不足
不能传输要交换的任何数据
管道
- 子进程从父进程继承文件描述符
file descriptor 0 stdin, 1 stdout,2 stderr - 进程不知道（或不关心！）从键盘，文件，程序读取或写入到终端，文件，程序。
% ls | more
shell:
创建管道
为ls创建一个进程，设置stdout为 管道写端
为more创建一个进程，设置stdin为 管道读端
消息队列
消息队列按FIFO来管理消息
- Message:作为一个字节列存储
- Meaasge Queues:消息数组
- FIFO & FILO configuration
共享内存
进程
- 每个进程搜友私有地址空间
- 在每个地址空间内，明确地设置了共享内存段
优点 - 快速，方便地共享数据
不足 - 必须同步数据访问