死锁和进程通信

请设置文章作者
Computer Science

发布于：2019年5月6日
次浏览

1. 死锁概念 Deadlock

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

死锁示例：

单向通行桥梁

  1. 可能出现死锁
    • 解决办法：资源撤回和回退
  2. 可能出现饥饿
    • 由于一个方向的持续车流，另一个方向的车辆无法通过桥梁

进程访问资源的流程：

  1. 资源类型$R1，R2，…，R_m$
  2. 每类资源$R_i$有$W_i$个实例
  3. 请求/获取 - 使用/占用 - 释放

1.1资源分类

  1. 可重用资源
    • 资源不能被删除且在任何时刻只能有一个进程使用
    • 进程释放资源后，其他进程可重用
    • 示例：处理器，I/O通道，主辅储存器
    • 可能出现死锁
  2. 消耗资源：
    • 创建&销毁
    • 示例：中断，信号
    • 可能出现死锁

1.2 资源分配图

描述资源和进程间分配和占用关系的有向图

1

分配图示例：

2

图中p2请求R3，然而 P3已经请求完了R3在等待p2释放，但p2请求不到，形成死锁。

出现死锁的必要条件：

  1. 互斥
  2. 持有并等待
  3. 非抢占 （资源只能自愿释放）
  4. 循环等待

2. 死锁处理方法

跟消防类比

  1. 死锁预防
  2. 死锁避免
  3. 死锁检测和恢复
  4. 由应用进程处理死锁

2.1 死锁预防：限制申请方式

限制并发进程对资源的请求

  1. 互斥：把互斥的共享资源封装成可同时访问
  2. 持有并等待：请求资源时不能持有任何其他资源（请求资源应当一次请求所有需要的资源）
  3. 非抢占：进程不能申请到立即分配的资源，则释放已占有资源
  4. 循环等待：对资源排序，按顺序请求资源

2.2 死锁避免

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

类比银行信用借款

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

2.3 系统资源分配安全状态

  1. 针对所以已占用进程，存在安全序列
  2. 序列$$是安全的，那么$P_i$要求的资源 <= 当前可用资源 + $P_j$的资源，$j<i$

安全状态与死锁的关系：

  1. 处于安全状态的，一定没有死锁
  2. 不安全状态，可能出现死锁

3. 银行家算法

银行家算法，以银行借贷策略为基础，判断并保证系统处于安全状态

  1. 客户第一次申请贷款，声明所需最大资金量
  2. 银行满足客户贷款量时，应尽快满足客户需求

类比：

  • 银行家 - 操作系统
  • 资金 - 资源
  • 客户 - 申请资源的线程

数据结构：

n = 线程数量
m = 资源类型数量
Max(总需求量)：n m矩阵，线程Ti最多请求类型Rj的资源Max[i, j]个实例
Available(剩余空闲量)：长度为m的向量，当前有Available[i]个类型Rj的资源可用
Allocation(已分配量)：n m矩阵，当前分配了Allocation[i, j]个资源实例
Need(未来需要量)：n * m矩阵，未来需要Need[i, j]个资源实例

满足公式：

安全状态判断算法

3

核心：当前剩余资源可以满足某一个线程的需要

银行家算法：

4

例题：

5

6

线程T2完成分配，最后也依次满足分配

4. 死锁检测

  1. 允许系统进入死锁状态
  2. 维护系统资源分配图
  3. 周期性调用死锁检测算法
  4. 出现死锁，用死锁恢复机制来恢复

数据结构：

  1. Available(剩余空闲量)：长度为m的向量，当前有Available[i]个类型Rj的资源可用
  2. Allocation(已分配量)：n * m矩阵，当前每个进程已分配了Allocation[i, j]个资源实例

算法分析：

7

算法复杂度：$O(m * n^2)$

例题：

8

死锁检测的时间和周期选择依据：

  1. 死锁多久可能发生
  2. 多少进程需要被回滚

4.1 死锁恢复：进程终止

  1. 终止所有的死锁进程
  2. 一次只终止一个进程直到死锁消除
  3. 终止进程的顺序是：
    • 进程的优先级（低的先）
    • 进程已运行时间（短的先）
    • 进程完成需要的资源
    • 进程数目
    • 交互还是批处理（批处理先）

终止方法：

  1. 选择被抢占进程
  2. 进程回退
  3. 可能出现饥饿（可能一直被选作被抢占者）

5. 进程通信概念

进程之间进行通信和同步的机制

IPC提供2个基本操作：

  1. 发送 send
  2. 接受 receive

通信流程：

  1. 在通信进程间建立链路
  2. 通过收/发交换信息

进程链路特征：

  1. 物理：共享内存，硬件总线
  2. 逻辑：逻辑属性

通信方式：直接通信和间接通信

9

5.1 直接通信

  1. 进程必须正确的命名对方

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

  2. 通信链路的属性

    • 自动建立链路
    • 一条链路恰好对应一对通信进程
    • 每对进程之间只有一个链接存在

5.2 间接通信

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

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

  2. 通信链路的属性

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

  3. 通信流程

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

  4. 基本通信操作

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

5.3 阻塞与非阻塞通信

也称同步与异步通信

10

5.4 通信链路缓冲

3种缓冲方式：

  1. 0容量
  2. 有限容量
  3. 无限容量

6. 信号和管道

6.1 信号 Signal

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

如：SIGKILL, SIGSTOP, SIGCONT等

信号的接收处理：

  1. 捕获 catch
  2. 忽略 ignore
  3. 屏蔽 mask

不足：传送的信息量小

信号的实现：

11

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <signal.h>
void sigproc()
{
    signal(SIGINT, sigproc); // 初始化SIG
    printf("You have pressed ctrl-c - disabled.\n"); // 给个提示
}
void quitproc()
{
    printf("ctrl-\\ pressed to quit.\n"); // 程序退出
    exit(0);
}
main()
{
    signal(SIGINT, sigproc);
    signal(SIGQUIT, quitproc);
    printf("ctrl-c disabled use ctrl-\\ to quit.\n");
    for(;;);
}

6.2 管道 pipe

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

系统调用：

  1. 读管道：read(fd, buffer, nbytes)
  2. 写管道：write(fd, buffer, nbytes)
  3. 创建管道：pipe(rgfd)
    • rgfd是2个文件描述符组成的数组
    • rgfd[0]是读文件描述符
    • rgfd[1]是写文件描述符

示例：

% ls | more

12

7. 消息队列和共享内存

7.1 消息队列 Message Queue

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

  1. 每个消息是一个字节序列
  2. 相同标识的消息组成按先进先出的顺序组成一个消息队列

系统调用：

  1. msgget(key, flags) 获取消息队列标识
  2. msgsnd(QID, buf, size, flags) 发送消息
  3. msgrcv(QID, buf, size, type, flags) 接收消息
  4. msgctl( … ) 消息队列控制

7.2 共享内存

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

  1. 进程
    • 每个进程都有私有内存地址空间
    • 每个进程的内存地址空间需明确设置共享内存段
  2. 线程
    • 同一进程的线程总是共享相同的地址空间

优点：快速、方便地共享数据
缺点：必须添加同步机制

实现：

13

系统调用：

  1. shmget(key, size, flags) 创建共享段
  2. shmat(shmid, *shmaddr, flags) 把共享段映射到地址空间
  3. shmdt(*shmaddr) 取消共享段到地址空间的映射
  4. shmctl( … ) 共享段控制

需要信号量等机制协调共享内存的访问冲突

8. 总结

4种进程之间的通讯机制

信号，管道，消息队列和共享内存

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.fuujiro.com/2019/05/06/%E6%AD%BB%E9%94%81%E5%92%8C%E8%BF%9B%E7%A8%8B%E9%80%9A%E4%BF%A1/

更新于：2020年9月13日

Operating System

ucore

评论