操作系统原理（十一）之死锁与进程通信

操作系统原理

定义

死锁是进程之间由于共享资源所导致的一种无限期等待的情况
由于竞争资源或者通信关系，两个或更多线程在执行中出现永远相互等待，只能由其他进程引发的事件

进程访问资源的流程

出现死锁的必要条件

• 互斥
  任何时刻只能有一个进程使用一个资源实例
• 持有并等待
  进程保持至少一个资源，并正在等待获取其他进程特有的资源
• 非抢占
  资源只能在进程使用后自愿释放
• 循环等待

死锁检测

数据结构

• Available：长度为m的向量
  每种类型可用资源的数量
• Allocation：一个 n×m矩阵
  当前分配给各个进程每种类型资源的数量
  进程Pi拥有资源Rj的Allocation[i,j]个实例

算法及其使用

死锁处理方法

死锁预防 限制申请方式

• 采用某种策略，使得并发对资源的请求，永远不满足死锁的必要条件 ： 互斥、持有并等待、非抢占、循环等待

死锁避免

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

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

PS：当进程请求资源时，系统会判断分配后是否处于安全状态，安全状态针对所有已用进程，存在安全序列
安全状态与死锁
安全状态则一定无死锁
不安全状态可能有死锁

死锁恢复

进程终止

一次只终止一个进程直到死锁消除，直至终止所有的死锁进程。终止顺序为

      进程的优先级（由低到高）→进程已运行时间以及还需运行时间
      （保留运行时间较长者）→进程已占用资源→进程完成需要的资→
      终止进程数目（越少越好）→进程是交互还是批处理（优先让用
      户交互的进程执行下去）

资源抢占

选择被抢占资源（最小成本）、进程回退（会退到安全状态）、可能出现饥饿（同一进程可能总是选择被抢占者）

进程通信 IPC, Inter-Process Communication

进程之间进行同步和通信的机制，提供两个基本操作

• 发送操作（send）

• 接收操作（receive）
  进程间通信流程

• 建立通信链路

• 通过send/receive交换信息

直接通信

• 进程间正确命名对方
  send（P，message）
  receive（Q，message）
• 自动建立通信链路
  一条链路对应一对通信进程，每对进程只有一个链接存在，链接可以单向但一般为双向

间接通信

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

阻塞（同步）与非阻塞通信（非阻塞）

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

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

通信链路缓冲

• 0容量：发送方必须等待接收方
• 有限容量：通讯队列满时，发送方必须要等待
• 无限容量：发送方不需要等待

信号量与管道

信号：进程软件中断通知和处理机制
如，sigkill，sigstop，sigcont

信号的接收处理

• 捕获Catch：执行进程指定的信号处理函数被调用
• 忽略ignore：执行操作系统上的缺省处理，如进程终止，进程挂起
• 屏蔽Mask：禁止进程进行接收和处理信号，可能是暂时的

管道

• 进程间基于内存文件的通信机制
  子进程从父进程继承文件描述符
  缺省文件描述符：0 stdin , 1 stdout, 2 strerr
• 进程不知道（或不关心）另一端
• 可能从键盘、文件、程序读取
• 可能写入到终端、文件、程序

管道相关的系统调用

• 读管道：read(fd, buffer, nbytes) →scanf()是基于它实现的
• 创建管道：pipe(rgfd) ，rgfd是2个文件描述符组成的数组
  rgfd[0]是读文件描述符
  rgfd[1]是写文件描述符

消息队列和共享内存

消息队列

消息队列是由操作系统维护的以字节序列为基本单位的间接通信机制
- 每个消息（message）是一个字节序列
- 相同标识的消息按先进先出顺序组成一个消息队列（Message Queues）

共享内存 快速方便存取 但需额外同步协调机制

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