11.信号量与同步知识补充

(1) 死锁问题与特征
(2) 死锁处理与避免
(3) 调度算法/实时调度/多处理器调度
(4) 优先级反转

11.1 死锁问题与特征

在我们操作系统中非常容易出现死锁状态(类似于编译安装依赖),一组阻塞得进程持有一种资源等待获取另一个进程锁占有得一个资源,例如：

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

比如：桥的每一部分可以看作一个资源，流量只在一个方向上;
如果死锁可能通过一辆车倒退可以解决(抢占资源和回滚),也可能几辆车必须都倒退,可能发生饥饿;

WeiyiGeek.死锁模拟图

WeiyiGeek.死锁模拟图

为什么会出现死锁?
答：这个是由于系统进程并发执行导致的,当多个进程在一块运行得时候,这些资源是共享得大家都能去用,如果不加以约束大家都是抢占这份资源,就会导致死锁情况得发生;

(1) 系统模型
系统资源类型：R1 / R2 / R3 … Rm, 如CPU cycles , memory space , I/O devices;
每个资源类型Ri有Wi得实例;
每个进程使用资源如下：

  • request / get <— free resource
  • use / hold <— requested / used resource
  • release <— free resource

可重复使用得资源:

  • 由多个进程都能共享访问得资源,进程获得资源并再使用之后进行释放资源(即创建与销毁的过程),使其能让其它得进程重用;
  • 如果每个进程拥有一个资源并请求其他资源死锁可能发生;再I/O缓冲区的中断/信号/消息/信息,如果接收消息阻塞可能会发生死锁,再可能少见的组合事件也会引起死锁;
  • 共享资源：
    • 物理层面：CPU / I/O 通道 / 内存 / 外存储器等等设备
    • 软件层面：数据结构 / 文件 / 数据库 / 信号量

资源分配图一组顶点V和边E的集合,V 有两种类型：

  • P = {P1,P2,P3…Pn} , 集合包括系统中的所有进程; requsting / claiming edge - directed edge Pi -> Rj;
  • R = {R1,R2,R3…Rn} , 集合包括系统中的所有资源类型; assigment / holding edge - directed edge Rj -> Pi

WeiyiGeek.资源分配图模型图

R2 有一个资源分配给P1另外一个资源分配给了P2,R1的资源被P2正在占用但是需要请求R3资源,但是R3资源正在被P3占用;
资源分配例子：下面会导致死锁,由于P1请求R1的资源(仅仅存在一个资源)被P2占用,则已经造成了死锁;

WeiyiGeek.资源分配例子

WeiyiGeek.资源分配例子

基本总结：

  • 如果图中不包括循环则没有死锁;
  • 如果图种包括循环,如果每个资源类只有一个实例那么死锁,如果每个资源类有几个实例可能死锁;
WeiyiGeek.有循环的资源分配没有死锁

WeiyiGeek.有循环的资源分配没有死锁

Deadlock处理方法：

Deadlock Prevention (死锁预防)
Deadlock Avoidance (死锁避免)
Deadlock Detection (死锁检测)
Recovery from Deadlock (死锁恢复)

外碎片 - 分配单元之间未使用的内存碎片