高校工会网站建设,网站静态页面生成,个人建站程序,贵州专业网站建设公司哪家好进程管理4--Deadlock and Starvation Concurrency: Deadlock and Starvation 内容提要 产生死锁与饥饿的原因 解决死锁的方法 死锁/同步的经典问题#xff1a;哲学家进餐问题 Deadlock 系统的一种随机性错误 Permanent blocking of a set of processes that eith… 进程管理4--Deadlock and Starvation Concurrency: Deadlock and Starvation 内容提要 产生死锁与饥饿的原因 解决死锁的方法 死锁/同步的经典问题哲学家进餐问题 Deadlock 系统的一种随机性错误 ·Permanent blocking of a set of processes that either compete for system resources or communicate with each other. ·No efficient solution ·Involve conflicting needs for resources by two or more processes. E.g. Process P and Q compete two resources. Their general forms are: Process PProcess QGet AGet B......Get BGet A......Release ARelease B......Release BRelease A...... 死锁与进程的推进顺序有关。 若修改P的代码则不会产生死锁。 Process P ... Get A ... Release A ... Get B ... Release B ... Reusable Resources 可重用资源 ·Used by one process at a time and not depleted(耗尽) by that use. ·Processes obtain resources that they later release for reuse by other processes. ·processor main and secondary memory IO channels databases files semaphores ·Deadlock occurs if each process holds one resource and requests the other. Example of Deadlock Process P Process Q Step Action Step Action P0 Request(D) Q0 Request(T) P1 Lock(D) Q1 Lock(T) P2 Request(T) Q2 Request(D) P3 Lock(T) Q3 Lock(D) P4 Perform function Q4 Perform function P5 Unlock(D) Q5 Unlock(T) P6 Unlock(T) Q6 Unlock(D) Example of Two process competing for Reusable Resources. Another Example of Deadlock ·Space is available for allocation of 200k bytes, and the following sequence of events occur. P1 P2 ... ... ... ... Request 80k bytes Request 70k bytes ... ... ... ... Request 60k bytes Request 80k bytes ... ... ... ... ·Deadlock occurs if both processes progress to their second request. Consumable Resources 可消耗资源 ·Created(produced) and destroyed(consumed) by a process. ·Interrupts, signals, messages and information in IO buffers. Example of Deadlock ·Deadlock occurs if receive is blocking. P1 P2 ... ... ... ... Receive(P2) Receive(P1) ... ... ... ... Send(P2, M1) Send(P1, M2) ... ... ... ... 此类死锁是由于设计失误造成的很难发现且潜伏期长。 Condition for Deadlock 必要条件 ·Mutual exclusion(互斥) ---Only one process may use a resource at a time. ·Hold-and-wait(保持并等待) ---A process may hold allocated resources while awaiting assignment of other resources. ·No preemptive(不剥夺) ---No resource can be forcibly removed from a process holding it. Circular Wait 充分条件 ·Circular wait(环路等待) ---A closed chain of process exists, such that each process holds at least one resource needed by the next process in the chain. 条件Mutual exclusion、Hold-and-wait、No preemption是死锁产生的必要条件 条件Circular Wait是前3个条件产生的结果。 Deadlock Prevention 预防死锁 预防死锁是不可行的只能尽量避免 ·间接方法禁止前3个条件之一的发生工程上不实用 1、互斥是某些系统资源的固有属性不能禁止 2、禁止“保持等待”条件 要求进程一次性地申请其所需的全部资源。若系统中没有足够的资源可分配给它则进程阻塞。 3、禁止“不剥夺”条件 1若一个进程占用了某些系统资源又申请新的资源则不能立即分配给它。必须让它首先释放出已占用资源然后再重新申请 2若一个进程申请的资源被另一个进程占有OS可以剥夺低优先权进程的资源分配给高优先权进程(要求此类可剥夺资源的状态易于保存和恢复否则不能剥夺)。 ·直接方法禁止条件4环路等待的发生 即禁止“环路等待”条件可以将系统的所有资源按类型不同进行线性排队并赋予不同的序号。进程对某类资源的申请只能按照序号递增的方式进行。 显然此方法是低效的它将影响进程执行的速度甚至阻碍资源的正常分配。 Deadlock Avoidance 避免死锁 用于服务器中PC机中无 ·预防死锁通过实施较强的限制条件实现降低了系统性能。 ·避免死锁的关键在于为进程分配资源之前首先通过计算判断此次分配是否会导致死锁只有不会导致死锁的分配才可实行。 ·A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock. ·Requires knowledge of future process request. Approaches to Deadlock Avoidance ·Do not start a process if its demands might lead to deadlock. ·Do not grant an incremental resource request to a process if this allocation might lead to deadlock. Resource Allocation Denial ·Referred to as the banker’s algorithm. ·State of the system is the current allocation of resources to process. ·Safe state is where there is at least one sequence that does not result in deadlock. ·Unsafe state is a state that is not safe. Safe State ·指系统能按某种顺序如P1, P2, ..., Pn来为每个进程分配其所需资源直至最大需求使每个进程都可以顺序完成则系统处于safe state。 称P1, P2, ..., Pn为安全序列。 Determination of a Safe State Claim Matrix R1 R2 R3 P1 3 2 2 P2 6 1 3 P3 3 1 4 P4 4 2 2 Allocation Matrix R1 R2 R3 P1 1 0 0 P2 6 1 2 P3 2 1 1 P4 0 0 2 Need Matrix R1 R2 R3 P1 2 2 2 P2 0 0 1 P3 1 0 3 P4 4 2 0 Resource Vector R1 R2 R3 9 3 6 Available Vector R1 R2 R3 0 1 1 Determination of a Unsafe State Claim Matrix R1 R2 R3 P1 3 2 2 P2 6 1 3 P3 3 1 4 P4 4 2 2 Allocation Matrix R1 R2 R3 P1 1 0 0 P2 5 1 1 P3 2 1 1 P4 0 0 2 Need Matrix R1 R2 R3 P1 2 2 2 P2 1 0 2 P3 1 0 3 P4 4 2 0 Resource Vector R1 R2 R3 8 3 5 Available Vector R1 R2 R3 0 1 1 Safe State V.S. Unsafe State ·并非所有不安全状态都是死锁状态。 ·当系统进入不安全状态后便可能进入死锁状态。 ·只要系统处于安全状态则可避免死锁状态。 Sate State to Unsafe State 例假设系统中有3个进程P1,P2,P3共有12台磁带机。进程P1共需10台P2、P3分别需要4台和9台。设T0时刻进程P1、P2、P3已分别获得5台、2台、2台尚有3台未分配即图示 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 ·T0时刻是安全的因为存在一个安全序列P2,P1,P3即只要系统按此进程序列分配资源每个进程都可顺利完成。 ·但是如果不按照安全序列分配资源则系统可能会由安全状态进入不安全状态。 例如T0时刻以后P3又申请1台磁带机。若系统将剩余3台中的1台分配给P3则系统进入不安全状态。 进程 最大需求 已分配 可用 P1 10 5 2 P2 4 2 P3 9 3 ———————————————————————————————————————————————————————————————————————————— 银行家算法 ·该算法可用于银行发放一笔贷款钱预测该笔贷款是否会引起银行资金周转问题。 ·这里银行的资金就类似于计算机系统的资源贷款业务类似于计算机的资源分配。 银行家算法能预测一笔贷款业务对银行是否是安全的也能预测一次资源分配对计算机系统是否是安全的。 ·为实现银行家算法系统中必须设置若干数据结构。 数据结构 1、可利用资源向量Available 是一个具有m个元素的数组其中的每一个元素代表一类可利用资源的数目其初始值为系统中该类资源的最大可用数目其值将随着该类资源的分配与回收而动态改变。 Available[j]k表示系统中现有Rj类资源k个。 2、最大需求矩阵Max 是一个n*m的矩阵定义了系统中n个进程中的每一个进程对m类资源的最大需求。 Max(i,j)k表示进程i对Rj类资源的最大需求数目为k个。 3、分配矩阵Allocation 是一个n*m的矩阵定义了进程中每一类资源的数量。 Allocation(i,j)k表示进程i当前已分得Rj类资源的数目为k个。 4、需求矩阵Need:Max-Allocation Need(i,j)k表示进程i还需要Rj类资源k个方能完成任务。 Need[i,j] Max[i,j] - Allocation[i,j] 设Requesti是进程Pi的请求向量。 Requesti[j] k表示进程Pi需要k个Rj类资源。当进程Pi放出资源请求后系统按下述步骤进行检查 1、如果Requesti Needi则转向步骤2否则出错。 2、如果Requesti Available则转向步骤3否则表示尚无足够资源可供分配进程Pi必须阻塞等待。 3、系统试探性的将Pi申请的资源分配给它并修改下列数据结构中的值 Available : Available - Requesti; Allocation : Allocation Requesti; Needi : Needi - Requesti; 4、系统利用安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式将资源分配给进程Pi完成本次资源分配否则试探分配失效让进程Pi阻塞等待。 安全性算法 1、设置两个工作向量 a)设置一个数组Finish[n]。当Finish[i] True (0 i n, n为系统中的进程数)时表示进程Pi获得其所需的全部资源而顺利执行完成。 b)设置一个临时向量work表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行时work : Available。 2、从进程集合中找到一个满足下列条件的进程 Finish[i] false and Need Work; 若找到执行步骤3否则执行步骤4。 3、当进程Pi获得资源后将顺利执行直至完成并释放其所拥有的全部资源故应执行以下操作 Work : work Allocationi and Finish[i] True转向步骤2 4、如果所有进程的Finish[i] True则表示系统处于安全状态否则系统处于不安全状态。 ———————————————————————————————————————————————————————————————————————— 举例 T0时刻的资源分配情况 ·假定系统中有四个进程P1,P2,P3,P4和三种类型的资源R1,R2,R3每一种资源的数量分别为9,3,6。 T0时刻的资源分配情况如下表所示 Claim Matrix R1 R2 R3 P1 3 2 2 P2 6 1 3 P3 3 1 4 P4 4 2 2 Allocation Matrix R1 R2 R3 P1 1 0 0 P2 6 1 2 P3 2 1 1 P4 0 0 2 Need Matrix R1 R2 R3 P1 2 2 2 P2 0 0 1 P3 1 0 3 P4 4 2 0 Available Vector R1 R2 R3 0 1 1 T0时刻的安全性 ·从T0时刻的安全性分析可知T0时刻存在着一个安全序列P2,P1,P4,P3故T0时刻系统是安全的。 ·假设T0时刻进程P1申请资源其请求向量为Request1(0,0,1)系统按银行家算法进行检查 Request1(0,0,1) Need1(2,2,2) Request1(0,0,1)Available(0,1,1) ·故系统试探性地为P1分配资源并修改Available1Allocation1Need1向量。 Allocation Matrix R1 R2 R3 P1 1 0 1 P2 6 1 2 P3 2 1 1 P4 0 0 2 Need Matrix R1 R2 R3 P1 2 2 1 P2 0 0 1 P3 1 0 3 P4 4 2 0 Available Vector R1 R2 R3 0 1 0 ·利用安全性算法检查此时系统是否安全 此时系统的可用资源向量为Available(0,1,0)。比较进程的需求向量Need系统不能满足任何进程的资源请求。系统进入不安全状态。 所以P1请求的资源不能分配只能让P1阻塞等待。 ·假设T0时刻进程P4申请资源其请求向量为Request4(1,2,0)系统按银行家算法进行检查 Request4(1,2,0) Need1(4,2,0) Request1(1,2,0) Available(0,1,1) ·P4的请求向量超过系统的可用资源向量故P4的请求不能满足进程P4阻塞等待。 Deadlock Avoidance ·Maximum resource requirement must be stated in advance 必须预先申明每个进程需要的资源总量。 ·Process under consideration must be independent; no synchronization requirements 进程之间相互独立其执行顺序取决于系统安全而非进程间的同步要求。 ·There must be a fixed number of resources to allocate 系统必须提供固定数量的资源供分配。 ·No process may exit while holding resources 若进程占有资源则不能让其退出系统。 ---Collection of programs, data, stack and attributes —————————————————————————————————————————————————————————————————————— 若系统不提供任何措施保证不进入死锁状态则必须提供检测和解除死锁的手段。 Deadlock Detection 检测死锁 ·检测死锁不同于预防死锁不限制资源访问方式和资源申请。 ·OS周期性的执行死锁检测例程检测系统中是否出现“环路等待”。 Strategies once Deadlock Detected ·Abort all deadlock processes. ·Back up each deadlock process to some previously defined checkpoint , and restart all process. ---Original deadlock may occur. ·Successively abort deadlocked processes until deadlock no longer exists. ·Successively preempt resources until deadlock no longer exists. Selection Criteria Deadlock Processes ·Least amount of processor time consumed so far. ·Least number of lines of output produced so far. ·Most estimated time remaining. ·Least total resources allocated so far. ·Lowest priority. Dining Philosophers Problem ·描述 有5个哲学家它们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌分别坐在周围的5把椅子上。 圆桌中间放有一大碗面条每个哲学家分别有一个盘子和一支叉子。 如果哲学家想吃面条则必须拿到靠其最近的左右两支叉子。进餐完毕放下叉子继续思考。 ·要求 设计一个合理的算法使全部哲学家都能进餐(非同时)算法必须避免死锁和饥饿哲学家互斥共享叉子。 By Semaphores Program dining philosophers:
Var fork:array[0...4] of semaphore(:1)
i:integer
Procedure philosopher(i:integer) Begin Repeat Think //哲学家正在思考 Wait(fork[i]) //取其左边的筷子 Wait(fork[i1]%5) //取其右边的筷子 Eat //吃面条 Signal(fork[i1]%5) //放回右边的筷子 Signal(fork[i]) //放回左边的筷子 Forever
End Begin Par-begin Philosopher(0); Philosopher(1); ... ... Philosopher(n); Par-end
End ·可能产生死锁
·可行的解决方案只允许4个哲学家同时进餐厅就餐则至少有一个哲学家可以拿到两只叉子进餐完毕放下叉子其他哲学家就可进餐。不会出现死锁和饥饿。 Program dining philosophers:
Var fork:array[0...4] of semaphore(:1)
Room:semaphore(:4)
i:integer Procedure philosopher(i:integer)
Begin Repeat Think //哲学家正在思考 Wait(room) //第5位哲学家被阻塞在room信号量队列 Wait(fork[i]) //取其左边的筷子 Wait(fork[i1]%5) //取其右边的筷子 Eat //吃面条 Signal(fork[i1]%5) //放回右边的筷子 Signal(fork[i]) //放回左边的筷子 Signal(room) //唤醒阻塞在room信号队列中的哲学家 Forever
End Begin Par-begin Philosopher(0); Philosopher(1); ... ... Philosopher(n); Par-end End 回顾
·进程概述
·进程调度
·进程并发控制 同步与互斥 死锁
