生产围棋工人不小心把相等数量黑子和白子混在一块.ppt

《生产围棋工人不小心把相等数量黑子和白子混在一块.ppt》由会员分享，可在线阅读，更多相关《生产围棋工人不小心把相等数量黑子和白子混在一块.ppt（48页珍藏版）》请在三一办公上搜索。

1、生产围棋的工人不小心把相等数量的黑子和白子混在一块，该系统由两个并发执行的进程组成，系统功能如下：（1）进程A专门拣黑子，进程B专门拣白子；（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子（3）当一个进程拣一个子后，必让另一个进程拣一个子试用同步原语管理进程，使其能正确实现上述功能。（假定系统启动时先让进程A拣子）,P111 5.19若将读者离开与读者进入分别看成一个进程，试用同步原语描述进程间关系。读者进入进程 读者离开进程进入 注销登记 离开,一条小河上有一座独木桥，现河东河西都有人要过桥，同一方向的可连续过桥；某方向有人过桥时另一方向的人须等待。如果把每个过桥者看作

2、一个进程，为保证安全，用信号量协调他们之间的关系。,第七章 死锁(Deadlock),1、死锁问题的提出2、死锁的必要条件3、死锁的预防4、死锁的避免和银行家算法5、死锁的检测6、死锁的恢复,7.1 死锁问题的提出,死锁是指计算机系统和进程所处的一种状态。常定义为：在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，我们称这些进程处于死锁状态。,死锁的现象,A进程 B进程wait(s1)wait(s2)wait(s2)wait(s1)signal(s2)signal(s1)signal(s1)signal(s2),死锁的原因,资源不足，竞争资源进程推进路径不当,申请不同类型资源产生死

3、锁,P1：申请打印机申请扫描仪使用释放打印机释放扫描仪,P2：申请扫描仪申请打印机使用释放打印机释放扫描仪,申请同类资源产生死锁（如内存）,设有资源R，R有m个分配单位，由n个进程P1,P2,Pn（n m）共享。假设每个进程对R的申请和释放符合下列原则：*一次只能申请一个单位*满足总申请后才能使用*使用完后一次性释放,m=2，n=3资源分配不当导致死锁产生,7.2 死锁的必要条件,资源的分类死锁的必要条件,一、资源的分类,可抢占资源、不可抢占资源共享资源、独享资源可再次使用的永久资源、消耗性的临时资源,二、死锁的必要条件,互斥条件:一个资源每次只能给一个进程使用不可抢占条件:资源申请者不能强行

4、从资源占有者手中 夺取资源，资源只能由占有者自愿释放部分分配条件:一个进程在申请新资源的同时保持对原 有资源的占有循环等待条件:存在一个进程等待队列 P1,P2,Pn,其中P1等待P2占有的资源，P2等待P3占有 的资源，Pn等待P1占有的资源，形成 一个进程等待环路,7.3 死锁的预防,在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一预防死锁是一种较可取 的方法，但资源的利用率较低。,1、破坏互斥条件,互斥是正确使用非共享资源的唯一手段。故不能通过取消互斥来预防死锁。,2、破坏不可抢占条件,适用于状态容易保护，稍后又容易恢复的资源。如CPU，内存。,3

5、、破坏部分分配条件,采用预先静态分配法：每个进程执行前，一次分配其所有资源允许进程仅当自己未占有资源时才申请资源。,4、破坏循环等待条件,有序资源分配为使“循环等待”条件不满足，我们把所有资源按类型进行排队，并赋予不同的编号。申请 按序号递增次序进行,每个进程,释放 按序号递减次序进行,优点：较前几种，改善资源的利用率。缺点：进程实际需求和资源顺序不一致 会造成资源浪费。,7.4 死锁的避免和银行家算法,死锁避免安全状态和不安全状态银行家算法数据结构银行家算法,一、死锁避免定义,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统

6、可能发生死锁，则不予分配，否则予以分配,例 单资源的银行家算法,假定某银行家有一笔资金可供一批顾客借用，并假定：每个顾客预知他的最大借款总额，且不超过银行家拥有的可用资金总和。每次借款以一万元为单位。每当顾客提出借口请求，银行家可立即给予，或让顾客等一段时间。只有当顾客达到他的预定最大借款额时，他才在有限时间依次归还。,安全状态：如果在某时刻，银行有可能使它当时的所有的顾客在以后有限时间内完成全部成交，则此刻的状态是安全。不安全状态：永远不具有成交的可能，则为不安全。,C 2 P 4（4）Q 2（1）R 2（7）,C：现金总额，P，Q，R：顾客,C 4 P 4（4）R 2（7）,C 8 R 2

7、（7）,C 10,安全状态,C 1 P 4（4）Q 2（1）R 3（6）,C 3 P 4（4）R 3（6）,不安全状态,二、安全状态和不安全状态,安全状态：指系统能按某种进程顺序如 为每个进程分配资源直至最大需求。不安全状态：在系统中不存在这样的序列。,三、银行家算法数据结构,Available：一个长度为m的向量，表示每类资源的可用数目。如果Availablej=k，表明Rj类资源有k个。Max：一个mn矩阵，定义每个进程的最大资源需求数，如果Maxi,j=k,表示进程i需要Rj类资源有k个。Allocation：一个mn矩阵，定义当前分配给每个进程每类资源的数目。如果Allocation

8、i,j=k，则表示进程I获得：Rj类资源有k个Need：一个mn矩阵，表示每个进程还需多少资源。如果 Needi,j=k，表示进程I还需要Rj类资源有k个。表示进程I需要Rj类资源有k个,四、银行家算法,设：Requesti是进程Pi的请求向量当Pi发出资源请求后，系统按如下步骤进行检查：1、如果Requesti Needi 则go to 2,否则认为出错。2、如果Requesti Available 则go to 3，否则表示无足够资源，Pi等待。3、系统进行试探分配，并求该相应数据结构数据 Available：=Available-Requesti Allocationi：=Allocat

9、ioni+Requesti Needi：=Needi-Requesti4、系统执行安全性算法：安全，把资源分配给Pi，否则，Pi等待。,安全性算法,1、设Work 和 Finish是长度分别为m,n的向量 初始值Work：=Available，Finishi：=False（所有）2、从进程集合中找到一个能满足下列条件的进程 a.Finishi=False b.Needi Work 如找到go to 3，否则 go to 4 3、当进程Pi 获得资源后，顺利执行，直至完成，并释放分配给它的资源。Work：=Work+Allocationi Finishi：=True go to 24、如果所有进

10、程的Finishi=True 则表示系统安全，否则 为不安全。,例1,假定系统中五个进程P0P4和三种资源A，B，C，资源数量分别为10，5，7，在T0时刻的资源分配情况如下表。Max Allocation Need AvailableP0 7，5，3 0，1，0 7，4，3 3，3，2P1 3，2，2 2，0，0 1，2，2P2 9，0，2 3，0，2 6，0，0P3 2，2，2 2，1，1 0，1，1P4 4，3，3 0，0，2 4，3，1,1、T0时刻安全性,Work Need Allocation Work+Allocation Finish,P1 3 3 2 1 2 2 2 0 0

11、5 3 2 T,P3 5 3 2 0 1 1 2 1 1 7 4 3 T,P4 7 4 3 4 3 1 0 0 2 7 4 5 T,P2 7 4 5 6 0 0 3 0 2 10 4 7 T,P0 10 4 7 7 4 3 0 1 0 10 5 7 T,T0状态是安全,2、P1请求资源,P1 请求向量Request1（1，0，2）系统按银行家算法进行检查：Request1（1，0，2）Need1（1，2，2）Request1（1，0，2）Available（3，3，2）系统先假定为P1分配资源，并求该数据结构的值 Available=Available-Request1=（2，3，0）Allo

12、cation1=Allocation1+Request1=（3，0，2）Need1=Need1-Request1：=（0，2，0）系统调用安全性算法，检查其安全性,Work Need Allocation Work+Allocation FinishP1 2 3 0 0 2 0 3 0 2 5 3 2 TP3 5 3 2 0 1 1 2 1 1 7 4 3 TP4 7 4 3 4 3 1 0 0 2 7 4 5 TP0 7 4 5 7 4 3 0 1 0 7 5 5 TP2 7 5 5 6 0 0 3 0 2 10 5 7 T,状态是安全，P1的请求能满足,3、P4请求资源,P4 请求向量Re

13、quest4（3，3，0）系统按银行家算法进行检查：Request4（3，3，0）Need4（4，3，1）Request4（3，3，0）Available（2，3，0）,让P4等待。,4、P0请求资源,P0请求向量Request0（0，2，0）系统按银行家算法进行检查：Request0（0，2，0）Need0（7，4，3）Request0（0，2，0）Available（2，3，0）系统先假定为P0分配资源，并求该数据结构的值 Available：=Available-Request0=（2，1，0）Allocation0：=Allocation0+Request0=（0，3，0）Need0：

14、=Need0-Request0：=（7，2，3）,系统调用安全性算法，检查结果为不安全,银行家算法的优缺点,本算法要求被分配每类资源数量是固定不变。本算法要求用户数固定不变。本算法保证所有用户的要求在有限时间内得到，实时较差。本算法要求用户事先说明他的最大资源要求，这对用户较难。,7.5 死锁的检测与恢复,死锁检测的概念资源分配图资源分配图的化简死锁检测中数据结构检测死锁的算法死锁的恢复,一、死锁检测 允许死锁发生。操作系统不断监视系统进展情况，判断死锁是否发生。一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行,二、资源分配图,用有向图描述进程的死锁,资源分配图表示法资源类

15、（资源的不同类型）用方框表示资源实例（存在于每个资源中的若干同种 资源）用方框中的黑圆点表示进程用圆圈中加进程名表示,分配边：资源实例进程的一条有向边申请边：进程资源类的一条有向边,有环有死锁,有环无死锁,死锁定理 如果资源分配图中没有环路，则系统中没有死锁；如果图中存在环路则系统中可能存在死锁 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件,三、资源分配图化简,如果一个进程所需的资源都满足，则对该进程结点化简。化简的方法：移走所有分配边和申请边。如果图中所有的进程结点均可化简成为孤立的结点，则该状态是安全的，否则是不安全的。,四、死锁检测中数据结构,可利用资源Availa

16、ble，它表示m类资源中每类资源可用数目。请求矩阵Request，一个mn矩阵，用以表示进程当前对各类资源的请求数目。分配矩阵Allocation，一个mn矩阵，用以表示某一时刻的资源的分配情况。工作向量Work，表示系统可提供的各类资源的数目。进程向量L，记录当前已不占用资源的各进程。,五、检测死锁的算法,把某时刻t的可用资源向量Available赋予Work把不占用资源的进程向量记入表L。从进程集合中找到一个Requesti Work的进程，做如下处理：1.将其资源分配图化简 Work：=Work+Allocationi 2.将它记入L表中若不能把所有进程都记入L表，则状态S资源分配图不可

17、完全化简，该系统发生死锁。,六、死锁的恢复,强制性撤消死锁的进程并剥夺资源 撤消的次序：使用最少处理器时间的进程使用最少输出工作量的进程具有最多剩余时间的进程分得最少资源的进程最小优先级的进程挂起和解除挂起,作业1：,假定一个处理机上执行的作业如下：作业提交时间短暂时间段长度优先数 1 0 7 3 2 1 4 1 3 2 2 6 4 3 1 4 5 3 5 2 且规定优先数大优先级别高。试分别用先来先服务，时间片（时间片为2），短作业优先，优先级调度算法（非抢占，可抢占）调度这些作业，并计算它们的平均周转时间。,作业2：,设有三个作业，它们到达系统的时间和计算时间如下：J1：8：00到达 计算时间 2个小时J2：8：30到达 计算时间1个小时J3：9：30到达 计算时间0.5小时系统采用响应比高者优先调度，在9：30开始调度时，试写出作业调度次序。,