作业系统L7－死结

死结特性

• 互斥:一次一个行程占用资源
• 占用与等候:至少一个行程占用资源且正等待其他资源
• 不可抢先:一个资源完成工作後才会被释放
• 循环式等候:一组形成被循环占用

资源配置图

• 要求边
• 分配边
• 
• 

处理死结

预防死结

• 互斥(Mutual Exclusion) :可共用资源可打破互斥，但不可共用资源无法，天生较难预防
• 占用与等候(Hold and Wait):一个行程要求其他资源时不得占有资源
  • 资源长时间被分配又长时间不用，使用率低
  • 可能无限期等待，饥饿
• 不可抢先(No Preemption):程序申请资源必须等待时，强制取消原资源的程序给新程序
  • 只试用容易取消与方便保存资讯的资源，EX:cpu暂存
• 循环式等候(Circular Wait): 强迫要求j>i的线性顺序要求
• 缺点:装置使用率低 生产量低

避免死结

    定义资源配置状态(资源数量 最大要求量)，并利用死结演算法确保安全状态

银行家演算法

• Available:可用的例证数
• Max:行程最多可要求的例证量
• Allocation:行程已占用的数量
• Need:行程还需要的例证

1. 当要求量小於需求，跳到步骤2，无法给与要求量
2. 当要求量小於可用量，跳到步骤3 无法取得资源
3. 修改配置数量
4. 执行安全演算法验证，如果是回传安全状态就分配资源，不行就回原状态

Available= Available –Request;//可用量被要求後剩下的量
Allocationi= Allocationi+ Requesti;//占用量增加运行的要求
Needi=Needi–Requesti//要求量完成後剩下的需求量

安全演算法

1. 定义初始值

Work = Available
Finish [i] =false 
//对i= 0, 1, ..., n-1

2. (需求不足可用资源 || 行程都完成时)，跳出回圈到步骤4

(a) Finish[i] = false
(b) Needi<=Work

3. 在回圈中持续执行程序

Work= Work + Allocationi
Finish[i] =true
//回到步骤2

4. 若所有行程都完成，则为安全状态

侦测死结

侦测图型是否循环

侦测演算法

• 跟安全演算法相似，m*(n^2)
• 

资源有多个装置

• 优点:执行频率太高，浪费时间
• 缺点:可知道死结处

资源有一个装置

• 优点:频率低
• 缺点:不知死结处

恢复死结

• 程序中止

  • 中止所有程序:时间费用高，先前结果要重新计算
  • 一次中止一个程序:每次中止一个要执行死结演算法判断

• 资源抢夺

    抢夺三因素
  

  • 选择牺牲者(Victim):尽可能减少成本
  • 撤回(Rollback):被剥夺者回到安全状态
  • 饥饿(Starvation):保证被牺牲者抢夺次数