死锁和进程间通信

死锁

一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源

系统模型

• 可重复使用的资源

在一个时间内只能一个进程使用且不能被删除

进程获得资源，后来释放由其他进程重用

处理器，I/O通道，主和副存储器，设备和数据结构；

如果每个进程拥有一个资源并请求其他资源，死锁可能发生

• 使用资源

创建和销毁

在I/O缓冲区的中断，信号，消息，信息

如果接收消息阻塞可能会发生死锁

可能少见的组合事件会引起死锁

• 资源分配图

一组顶点v和边e的集合

v有两种类型

p 集合包含系统中的所有进程

r 集合包括系统中的所有资源类型

• 基本情况

如果图中不包含循环==》没有死锁

如果图中包含循环==》

如果每个资源类只有一个实例，那么死锁

如果每个资源类有几个实例，则可能死锁

死锁特征

• 互斥：在一个时间段内只能有一个进程使用资源
• 持有并等待：进程保持至少一个资源正在等待获取其他进程所持有的额外资源
• 无抢占：一个资源只能被进程自愿释放，进程已经完成了他的任务之后
• 循环等待：存在等待继承集合{p0 p1… pn}p0正在等待p1的资源，p1正在等待p2的资源，…,pn-1正在等待pn所占用的资源，pn在等待p0所占用的资源

死锁的处理办法

• 确保系统永远不会进入死锁状态
• 运行系统进入死锁状态，然后恢复
• 忽略这个问题，假装系统中从来没有发生死锁；用于大多数操作系统，包括unix

死锁的预防和避免

• 限制申请方式

互斥 - 共享资源不是必须的，必须占用非共享资源

占用并等待 - 必须保证当一个进程请求的资源，它不再持有任何其他资源

需要进程请求并分配其所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源

资源利用率低，可能发生饥饿现象

无抢占 -

如果进程占用某些资源，并请求其它不能被立即分配的资源，则释放当前正占有的资源

被抢占资源添加到资源列表中

只有当它能够获取旧的资源以及它请求新的资源，进程可以得到执行

循环等待 - 对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请

• 需要系统有一些额外的先验信息提供

最简单和最有效的模式是要求每个进程声明它可能需要的每个类型的资源的最大数目

资源的分配状态是通过限定提供与分配的资源数量，和进程的最大需求

死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待的状态

当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态

系统处于安全状态是指：针对所有进程吗，存在安全序列

序列<p1,p2,p3>是安全的，诊断每个pi，pi要求资源能够由当前可用干的资源加所有的pj持有的资源来满足（其中j<i）

银行家算法

银行家算法是一种避免死锁喊声的算法， 它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行

• 前提条件

多个实例

每个进程都必须能最大限度的利用资源

当一个进程请求一个资源就不得不等待

当一个进程获得所有的资源就必须在一段有限的时间内释放它们

死锁的检测和恢复

• 死锁检测 ： 。。。

• 死锁恢复

终止所有的死锁进程

在一个时间内终止一个进程直到死锁解除

终止进程的顺序应该是

进程的优先级

进程运行了多久以及需要多少时间才能完成

进程占用的资源

进程完成需要的资源

多少进程需要被终止

进程时交互还是批处理

选择一个受害者 - 最小成本

回滚 - 返回到一些安全状态，重启进程到安全状态

饥饿 - 同一进程可能一直被选为受害者，包括回滚数量

进程间通信

IPC概述

• 进程通信的机制和同步
• 不使用共享变量的进程通信
• ICP 提供的两个操作：

send:

recv:

• 如果p和q想要通信，需要

在他们之间建立通信链路

通过send/recv交换信息

• 通信链路的实现

物理 共享内存，硬件总线

逻辑 逻辑属性

• 直接通信

进程必须能正确的命名对方

通信链路属性

自动建立链路

一条链路恰好对应一对通信进程

每对进程之间只有一个链接存在

链接可以是单向的，但通常是双向的

• 间接通信

定向从消息队列中接收消息

每个消息都有唯一的ID

只有他们共享了一个消息队列，进程间才能通信

通信链路属性

只有进程共享一个共同的消息队列，才建立链路

连接可以与许多进程相关联

没对进程可以共享多个通信链路

连接可以是单向或双向的

操作

创建一个新的消息队列

通过消息队列发送和接收消息

销毁消息队列

原语定义如下：

send(A, message) 发送消息到队列A

recv(A, message) 从队列A中接收消息

• 阻塞和非阻塞

消息传递可以是阻塞或者非阻塞的

阻断被认为是绒布的

非阻断被认为是异步的

• 通信链路缓冲

0容量：发送方必须等待接收方

有限容量：发送方必须等待，如果队列满了

无限容量：发送方不需要等待

信号SIGNAL

软件中断通知事件处理

• 接收到信号时候会发生什么

catch：指定信号处理函数被调用

Ignore：依靠操作系统的默认操作

Mask：闭塞信号因此不会传送

可能是暂时的

• 不足

不能传输要交换的任何数据

管道 |

• 子进程从父进程继承文件描述
• 进程不知道（或者不关心）从键盘，文件，程序读取或写入到终端，文件，程序。

消息队列

消息队列按照FIFO的来管理消息

• message : 作为一个字节序列存储
• message queues ：消息数组
• FIFO&FILO configuration

共享内存

• 进程

每个进程都有私有地址空间

每个地址空间内，明确的设置了共享内存段

• 优点

快速，方便的共享数据

• 不足

必须同步数据访问

特点：

• 最快的方法
• 一个进程写另外一个进程立即可见
• 没有系统调用干预
• 没有数据复制
• 不提供同步：由程序员提供