死锁

1. 死锁问题

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

例子：系统有两个磁带驱动器，P1和P2都有一个，都需要另一个。

2. 系统模型

从数学角度建立死锁形式化模型。

可重复使用的资源：

• 在一个时间只能一个进程使用且不能被删除
• 进程获得资源，后来释放由其他资源重用
• 处理器，I/O通道，主副存储器，设备和数据结构，如文件、数据库和信号量
• 如果每个进程拥有一个资源并请求其他资源，死锁可能发生

使用资源：

• 创建和销毁
• 在I/O缓冲区的中断，信号、信息、消息
• 如果接受信息看阻塞可能会发生死锁
• 可能少见的组合事件会引起死锁

资源分配图：

死锁存在的基本判断情况：

• 如果图中不包含循环–》无死锁
• 如果图中包含循环
  • 如果每个资源类只有一个实例，死锁
  • 如果每个资源类有多个实例，可能死锁

3. 死锁特征

出现死锁一定会出现以下四个特征，但出现以下四个特征时不一定是死锁。（必要条件）

• 互斥：在一个事件只能有一个进程使用资源
• 持有并等待：进程保持至少一个资源正在等待获取其他进程持有的额外资源
• 无抢占：一个资源只能被进程自愿释放，在该进程完成任务之后
• 循环等待：存在等待进程集合，p0正在等待p1所占用的资源，p1等待p2占用的资源，……，pn等待p0占用的资源

4. 死锁处理方式

往往采用忽略的处理方式处理出现的死锁。

4.1 Deadlock Prevention（死锁预防）

针对死锁的四个特征采取相应的预防措施。

不允许出现死锁。

4.2 Deadlock Avoidance（死锁避免）

根据运行进程的特征，设置安全运行序列，即pi进程不会与p0~p(i-1)发生死锁。

不允许出现死锁。

4.3 Deadlock Detection（死锁检测）

• 安全判断算法：将资源分配图简化成只有进程的等待图，判断是否存在环，存在即可能存在死锁
• 死锁检测算法：定期执行算法，判断是否存在死锁。需要获取进程需要的最大资源数目。更多用于调试。

允许出现死锁。

4.4 Recovery from Deadlock（死锁恢复）

• 终止所有的死锁进程
• 在一个时间内终止一个进程知道死锁消除
• 终止进程的顺序应该是
  • 进程的优先级
  • 进程开始运行的时间和需要的时间
  • 进程占用的资源
  • 进程完成需要的资源
  • 需要被终止的进程数目
  • 进程是交互的还是批处理

进程间通讯 IPC

1. 概述

保证进程相对独立的同时，在某些情况下还需要保证进程之间有效的沟通。

通讯主要有两种方式：发送和接收。

• 直接通信：进程必须正确地命名对方；通信链路的属性：
  • 自动建立链路
  • 一条链路恰好对应一对通信进程
  • 每对进程之间只有一个链接存在
  • 链接可以是单向的，但通常为双向
• 间接通信：
  • 创建一个新的消息队列
  • 通过消息队列发送和接收消息
  • 销毁消息队列

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

• 阻塞被认为是同步的
• 非阻塞被认为是异步的

通信链路缓冲：将通讯数据临时缓存，来避免发送方和接收方的不匹配，达到提高效率的目的。缓存涉及到容量问题，有三种情况：

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

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

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

2. 信号、管道、消息队列和共享内存

详见第6章