作业系统L7－死结

死结特性

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

资源配置图

要求边分配边

处理死结

预防死结

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

避免死结

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

银行家演算法

Available:可用的例证数Max:行程最多可要求的例证量Allocation:行程已佔用的数量Need:行程还需要的例证当要求量小于需求，跳到步骤2，无法给与要求量当要求量小于可用量，跳到步骤3 无法取得资源修改配置数量执行安全演算法验证，如果是回传安全状态就分配资源，不行就回原状态

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

安全演算法

定义初始值

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

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

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

在迴圈中持续执行程序

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

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

侦测死结

侦测图型是否循环

侦测演算法

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

资源有多个装置

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

资源有一个装置

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

恢复死结

程序中止

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

资源抢夺

  抢夺三因素

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