死锁问题：

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

死锁示例：单向通行桥梁

桥梁只能单向通行，桥的每个部分可视为一个资源

可能出现死锁，对向行驶车辆在桥上相遇，解决方法：一个方向的车辆倒退(资源抢占和回退)

可能发生饥饿，由于一个方向的持续车流，另一个方向的车辆无法通过桥梁

进程访问资源的流程

资源类型R1, R2, . . .,Rm。CPU执行时间、内存空间、I/O设备等

每类资源Ri有Wi个实例

进程访问资源的流程

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

资源分类

可重用资源（Reusable Resource）

• 资源不能被删除且在任何时刻只能有一个进程使用
• 进程释放资源后，其他进程可重用
• 可能出现死锁，每个进程占用一部分资源并请求其它资源

可重用资源示例：
硬件：处理器、I / O通道、主和副存储器、设备等
软件：文件、数据库和信号量等数据结构

消耗资源(Consumable resource)

• 资源创建和销毁
• 可能出现死锁，进程间相互等待接收对方的消息

消耗资源示例：
在I/O缓冲区的中断、信号、消息等

出现死锁的必要条件：（不是充要条件）

互斥
任何时刻只能有一个进程使用一个资源实例

持有并等待
进程保持至少一个资源，并正在等待获取其他进程持有的资源

非抢占
资源只能在进程使用后自愿释放

循环等待
存在等待进程集合{P0，P1，…，PN} ，P0正在等待P1所占用的资源，P1 正在等待P2占用的资源，…，PN-1在等待PN所占用资源，PN正在等待P0所占用的资源

死锁处理方法

死锁预防(Deadlock Prevention)确保系统永远不会进入死锁状态

死锁避免(Deadlock Avoidance)在使用前进行判断，只允许不会出现死锁的进程请求资源

死锁检测和恢复(Deadlock Detection & Recovery)在检测到运行系统进入死锁状态后，进行恢复

由应用进程处理死锁，通常操作系统忽略死锁，大多数操作系统（包括UNIX）的做法

死锁预防：限制申请方式

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

互斥，把互斥的共享资源封装成可同时访问

持有并等待，进程请求资源时，要求它不持有任何其他资源。仅允许进程在开始执行时，一次请求所有需要的资源。资源利用率低

非抢占，如进程请求不能立即分配的资源，则释放已占有资源。只在能够同时获得所有需要资源时，才执行分配操作

循环等待，对资源排序，要求进程按顺序请求资源

死锁避免

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

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

系统资源分配的安全状态

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

系统处于安全状态，一定没有死锁

系统处于不安全状态，可能出现死锁

避免死锁就是确保系统不会进入不安全状态

死锁检测

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

死锁恢复: 进程终止

终止所有的死锁进程

一次只终止一个进程直到死锁消除

终止进程的顺序应该是

• 进程的优先级
• 进程已运行时间以及还需运行时间
• 进程已占用资源
• 进程完成需要的资源
• 终止进程数目
• 进程是交互还是批处理

死锁恢复：资源抢占

选择被抢占进程，最小成本目标

进程回退，返回到一些安全状态, 重启进程到安全状态

可能出现饥饿，一进程可能一直被选作被抢占者

进程通信（IPC, Inter-Process Communication）

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

IPC提供2个基本操作

• 发送操作：send(message)
• 接收操作：receive(message)

进程通信流程

• 在通信进程间建立通信链路
• 通过 send/receive交换消息

进程链路特征

• 物理 (如，共享内存，硬件总线）
• 逻辑 (如，逻辑属性）

通信方式

直接通信

进程必须正确的命名对方

• send (P, message) – 发送信息到进程P
• receive(Q, message) – 从进程 Q接受消息

通信链路的属性

• 自动建立链路
• 一条链路恰好对应一对通信进程
• 每对进程之间只有一个链接存在
• 链接可以是单向的，但通常为双向的

间接通信

通过操作系统维护的消息队列实现进程间的消息接收和发送

• 每个消息队列都有一个唯一的标识
• 只有共享了相同消息队列的进程，才能够通信

通信链路的属性

• 只有共享了相同消息队列的进程，才建立连接
• 连接可以是单向或双向
• 消息队列可以与多个进程相关联
• 对进程可以共享多个消息队列

通信流程

• 创建一个新的消息队列
• 通过消息队列发送和接收消息
• 销毁消息队列

基本通信操作

• send(A, message) – 发送消息到队列A
• receive(A, message) – 从队列 A接受消息

阻塞与非阻塞通信

进程通信可划分为阻塞（同步）或非阻塞（异步）

阻塞通信

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

非阻塞通信

• 非阻塞发送，发送者在消息发送后，可立即进行其他操作
• 非阻塞接收，没有消息发送时，接收者在请求接收消息后，接收不到任何消息

通信链路缓冲

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

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

有限容量，通信链路缓冲队列满时，发送方必须等待

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

信号（Signal）

信号：进程间的软件中断通知和处理机制

信号的接收处理

• 捕获(catch)：执行进程指定的信号处理函数被调用
• 忽略(Ignore)：执行操作系统指定的缺省处理。例如：进程终止、进程挂起等
• 屏蔽（Mask）：禁止进程接收和处理信号，可能是暂时的(当处理同样类型的信号)

不足，传送的信息量小，只有一个信号类型

管道(pipe)

进程间基于内存文件的通信机制

消息队列

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

每个消息(Message)是一个字节序列

相同标识的消息组成按先进先出顺序组成一个消息队列（Message Queues）

共享内存

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

进程

• 每个进程都有私有内存地址空间
• 每个进程的内存地址空间需明确设置共享内存段

线程，同一进程中的线程总是共享相同的内存地址空间

优点，快速、方便地共享数据

不足，必须用额外的同步机制来协调数据访问

cs