【操作系统笔记】OS_死锁和进程通信(11)

李明燮(li_mingxie)
OS
Page content

这一篇整理了操作系统的死锁和进程通信相关的内容。

1.死锁问题

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

示例:

  • 系统有2个磁带驱动器
  • P1和P2各有一个,都需要另外一个

2.系统模型

资源类型R1,R2,..,Rm(CPU, memory space, IO devices)

每个资源类型Ri有Wi个实例.

每个进程使用资源如下:

  • require,get ← free resource
  • use,hold ← requested,used resource
  • release ← free resource

可重复使用的资源

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

使用资源

  • 创建和销毁
  • 在IO缓存区的中断,信号,消息,信息
  • 如果接收消息阻塞可能会发生死锁
  • 可能少见的组合事件会引起死锁

资源分配图

一组顶点V和边E的集合

  • V有两种类型:
    • P={P1,P2,…,Pn},集合包括系统中的所有进程
    • R={R1,R2,…,Rm},集合包括系统中的所有资源类型
  • requesting,claiming edge - directed edge Pi → Rj
  • assignment,holding edge - directed edge Rj → Pi

基本情况

如果图中不包含循环:

  • 没有死锁

如果图中包含循环:

  • 如果每个资源类只有一个实例,那么死锁
  • 如果每个资源类有几个实例,可能死锁

3.死锁特征

死锁出现一定会出现以下四个条件,但是出现以下四个条件不一定死锁:

  • 互斥: 在一个时间只能有一个进程使用资源
  • 持有并等待: 进程保持至少一个资源正在等待获取其他进程持有的额外资源
  • 无抢占: 一个资源只能被进程资源释放,进程已经完成了它的任务之后
  • 循环等待: 存在等待进程集合{P0,P1,…,Pn},P0正在等待P1所占用的资源,P1正在等待P2占用的资源…Pn-1在等待Pn的资源,Pn正在等待P0所占用的资源

4.死锁处理方法

常见方法

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

Deadlock Prevention 预防

限制申请方式

  • 互斥 - 共享资源不是必须的,必须占用非共享资源
  • 占用并等待 - 必须保证当一个进程请求的资源,它不持有任何其他资源
    • 需要进程请求并分配其所有资源,它开始执行之前或允许进程请求资源仅当进程没有资源
    • 资源利用率低,可能发生饥饿
  • 无抢占 -
    • 如果进程占有某些资源,并请求其他不能被立即分配的资源,则释放当前正占有的资源
    • 被抢占资源添加到资源列表中
    • 只有当它能够获得旧的资源以及它请求新的资源,进程可以得到执行
  • 循环等待 - 对所有资源类型进行排序,并要求每个进程按照资源的顺序进行申请

Deadlock Avoidance 避免

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

  • 最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目
  • 资源的分配状态是通过限定提供与分配的资源数量,和进程的最大需求
  • 死锁避免算法动态检查的资源分配状态,以确保永远不会有一个环形等待状态
  • 当一个进程请求可用资源,系统必须判断立即分配是否能使系统处于安全状态
  • 系统处于安全状态指: 针对所有进程,存在安全序列
  • 序列<P1,P2,…,Pn>是安全的: 针对每个Pi,Pi要求的资源能够由当前可用的资源+所有的Pj持有的资源来满足,其中j<i.
    • 如果Pi资源的需求不是立即可用,那么Pi可以等到所有Pj完成
    • 当Pi完成后,Pi+1可以得到所需要的资源,执行,返回所分配的资源,并终止.
    • 用同样的方法,Pi+2,Pi+3和Pn能获得其所需的资源.
  • 如果系统处于安全状态→无死锁
  • 如果系统处于不安全状态→可能死锁
  • 避免死锁: 确保系统永远不会进入不安全状态

Deadlock Detection 检测

每个资源类型单一实例

Maintain wait-for graph

  • 节点是进程
  • Pi→Pj: Pi等待Pj

定期调用检测算法来搜索图中是否存在循环

算法需要n^2次操作,n是图中顶点的数目

数据结构:

  • Available: 长度为M的向量表示每种类型可用资源的数量
  • Allocation: 一个nxm矩阵定义了当前分配给各个进程每种类型资源的数量,如果Alocation[i, j] = k, 进程Pi拥有资源Rj的k个实例
  • Request: 一个nxm矩阵表示各进程的当前请求.如果Request[i, j] = k,表示进程Pi请求k个资源Pj的实例

具体算法(跳过了,看视频)

检查算法使用

何时,使用什么样的频率来检测依赖于:

  • 死锁多久可能会发生?
  • 多少进程需要被回滚? one for each disjoint cycle

如果检测算法多次被调用,有可能是资源图有多个循环,所以我们无法分辨出多个可能死锁进程中的哪些"造成"死锁

Recovery from Deadlock 恢复

终止所有的死锁进程

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

终止进程的顺序应该是:

  • 进程的优先级
  • 进程运行了多久以及需要多少时间才能完成
  • 进程占用的资源
  • 进程完成需要的资源
  • 多少进程需要被终止
  • 进程是交互还是批处理

选择一个受孩子 - 最小的成本

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

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

5.IPC

5.1 概述

进程通信的机制及同步

不使用共享变量的进程通信

IPC facility 提供2个操作:

  • send(message) - 消息大小固定或者可变
  • receive(message)

如果P和Q想通信,需要:

  • 在它们之间建立通信链路
  • 通过send/recevie交换消息

通信链路的实现

  • 物理(例如,共享内存,硬件总线)
  • 逻辑(例如,逻辑属性)

5.2 直接通信

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

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

通信链路的属性

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

5.3 间接通信

定向从消息队列接收消息

  • 每个消息对垒都有一个唯一的ID
  • 只有它们共享了一个消息队列,进程才能够通信

通信链路的属性

  • 只有进程共享一个共同的消息队列,才建立链路
  • 链接可以与许多进程相关联
  • 每对进程可以共享多个通信链路
  • 链接可以是单向或者双向

操作

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

原语的定义如下:

  • send(A, message)

  • receive(A, message)

  • 通信链路缓冲

    通信链路缓存大小:

    1. 0容量 - 0 message : 发送方必须等待接收方
    2. 有限容量 - n messages的有限长度 : 发送方必须等待,如果队列满
    3. 无限容量 - 无限长度 : 发送方不需要等待

5.4 信号

信号Signal

  • 软件中断通知事件处理
  • Examples: SIGFPE, SIGKILL, SIGUSRI, SIGSTOP, SIGCONT

接收到信号时会发生什么?

  • catch: 指定信号处理函数被调用
  • ignore: 依靠操作系统的默认操作(abort, memory dump, suspend or resume process)
  • mask: 闭塞信号因此不会传送(可能是暂时的,当处理同样类型的信号)

不足:

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

5.5 管道

数据交换

子进程从父进程继承文件描述符(0 stdin, 1 stdout, 2 stderr)

进程不知道(或不关心)从键盘,文件,程序读取或写入到终端,文件,程序.

例如: $ ls | more (两个进程, 管道是缓存,对于ls来说是stdout,对于more来说是stdin )

消息队列

消息队列按FIFO来管理消息

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

5.6 共享内存

进程

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

优点

  • 快速,方便地共享数据

不足

  • 必须同步数据访问

最快的方法

一个进程写另一个进程立即可见

没有系统调用干预

没有数据复制

不提供同步

  • Socket

欢迎大家的意见和交流

email: li_mingxie@163.com