《子和白子混在一块该系统由两个并发执行的进程组成系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)死锁的缘由资源缺乏，竞争资源进程推进途径不当 恳求不同类型资源产生死锁P1：恳求打印机恳求打
3、印机恳求扫描仪恳求扫描仪运用运用释放打印机释放打印机释放扫描仪释放扫描仪P2：恳求扫描仪恳求扫描仪恳求打印机恳求打印机运用运用释放打印机释放打印机释放扫描仪释放扫描仪恳求同类资源产生死锁如内存 设有资源R，R有m个分配单位，由n个进程P1,P2,Pnn m共享。假设每个进程对R的恳求和释放符合以下原那么： * 一次只能恳求一个单位 * 满足总恳求后才干运用 * 运用完后一次性释放m=2，n=3资源分配不当导致死锁产生7.2 死锁的必要条件资源的分类死锁的必要条件一、资源的分类可抢占资源、不可抢占资源共享资源、独享资源可再次运用的永久资源、耗费性的暂时资源二、死锁的必要条件互斥条件:一个资源每次
4、只能给一个进程运用不可抢占条件:资源恳求者不能强行从资源占有者手中 夺取资源，资源只能由占有者自愿释放部分分配条件:一个进程在恳求新资源的同时坚持对原 有资源的占有循环等待条件:存在一个进程等待队列 P1 , P2 , , Pn, 其中P1等待P2占有的资源，P2等待P3占有 的资源，Pn等待P1占有的资源，构成 一个进程等待环路7.3 死锁的预防在系统设计时确定资源分配算法，保证不发生死锁。详细的做法是破坏产生死锁的四个必要条件之一预防死锁是一种较可取 的方法，但资源的利用率较低。1、破坏互斥条件互斥是正确运用非共享资源的独一手段。故不能经过取消互斥来预防死锁。2、破坏不可抢占条件适用于形状
5、容易维护，稍后又容易恢复的资源。如CPU，内存。3、破坏部分分配条件采用预先静态分配法：每个进程执行前，一次分配其一切资源允许进程仅当本人未占有资源时才恳求资源。4、破坏循环等待条件有序资源分配为使“循环等待条件不满足，我们把一切资源按类型进展排队，并赋予不同的编号。 恳求 按序号递增次序进展 每个进程 释放 按序号递减次序进展优点：较前几种，改善资源的利用率。缺陷：进程实践需求和资源顺序不一致 会呵斥资源浪费。例如：1，2，3，10P1：恳求恳求1恳求恳求3恳求恳求9P2：恳求恳求1恳求恳求2恳求恳求5P3 P107.4 死锁的防止和银行家算法死锁防止平安形状和不平安形状银行家算法数据构造银
6、行家算法一、死锁防止定义在系统运转过程中，对进程发出的每一个系统可以满足的资源恳求进展动态检查，并根据检查结果断定能否分配资源，假设分配后系统能够发生死锁，那么不予分配，否那么予以分配例 单资源的银行家算法假定某银行家有一笔资金可供一批顾客借用，并假定：每个顾客预知他的最大借款总额，且不超越银行家拥有的可用资金总和。每次借款以一万元为单位。每当顾客提出借口恳求，银行家可立刻给予，或让顾客等一段时间。只需当顾客到达他的预定最大借款额时，他才在有限时间依次归还。平安形状：假设在某时辰，银行有能够使它当时的一切的顾客在以后有限时间内完成全部成交，那么此刻的形状是平安。不平安形状：永远不具有成交的能够
7、，那么为不平安。C 2 P 44 Q 21 R 27C：现金总额， P，Q，R：顾客C 4 P 44 R 27 C 8 R 27C 10平安形状C 1 P 44 Q 21 R 36C 3 P 44 R 36 不平安形状二、平安形状和不平安形状平安形状：指系统能按某种进程顺序如 为每个进程分配资源直至最大需求。 不平安形状：在系统中不存在这样的序列。三、银行家算法数据构造Available：一个长度为：一个长度为m的向量，表示每类资源的的向量，表示每类资源的可用数目。可用数目。 假设假设Availablej=k，阐明，阐明Rj类资源有类资源有k个。个。Max：一个：一个mn矩阵，定义每个进程的最
8、大资源需矩阵，定义每个进程的最大资源需求数，假设求数，假设Maxi,j=k,表示进程表示进程i需求需求Rj类资源有类资源有k个。个。Allocation：一个：一个mn矩阵，定义当前分配给每个矩阵，定义当前分配给每个进程每类资源的数目。假设进程每类资源的数目。假设Allocation i,j=k，那么，那么表示进程表示进程I获得：获得：Rj类资源有类资源有k个个Need：一个：一个mn矩阵，表示每个进程还需多少资源。矩阵，表示每个进程还需多少资源。 假设假设 Needi,j=k，表示进程，表示进程I还需求还需求Rj类资源有类资源有k个。个。表示进程表示进程I需求需求Rj类资源有类资源有k个个四
9、、银行家算法设：Requesti是进程Pi的恳求向量当Pi发出资源恳求后，系统按如下步骤进展检查：1、假设Requesti Needi 那么go to 2,否那么以为出错。2、假设Requesti Available 那么go to 3，否那么表示无足够资源， Pi等待。3、系统进展试探分配，并求该相应数据构造数据 Available：= Available- Requesti Allocationi：= Allocationi+ Requesti Needi：= Needi-Requesti4、系统执行平安性算法：平安，把资源分配给Pi，否那么， Pi等待。平安性算法1、设Work 和 Fi
10、nish是长度分别为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、假设一切进程的Finishi= True 那么表示系统平安，否那么 为不平安。例1假定系统中五个进程P0P4和三种资源A，B，C，资源数量分别为10，5，7，在
11、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，11、T0时辰平安性 Work Need Allocation Work+ Allocation FinishP1 3 3 2 1 2 2 2 0 0 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
12、 6 0 0 3 0 2 10 4 7 T P0 10 4 7 7 4 3 0 1 0 10 5 7 TT0形状是平安2、P1恳求资源P1 恳求向量Request11，0，2系统按银行家算法进展检查：Request11，0，2Need11，2，2Request11，0，2Available3，3，2系统先假定为P1分配资源，并求该数据构造的值 Available = Available- Request1=2，3，0 Allocation1 = Allocation1+Request1=3，0，2 Need1 = Need1-Request1：=0，2，0系统调用平安性算法，检查其平安性 Wo
13、rk 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 恳求向量Request43，3，0系统按银行家算法进展检查：Request43，3，0Need44，3，1Request43，3，0Available2，3，0让P4等待。4、P0恳
14、求资源P0恳求向量Request00，2，0系统按银行家算法进展检查：Request00，2，0Need07，4，3Request00，2，0Available2，3，0系统先假定为P0分配资源，并求该数据构造的值 Available：= Available- Request0=2，1，0 Allocation0：= Allocation0+Request0=0，3，0 Need0：= Need0-Request0：=7，2，3系统调用平安性算法，检查结果为不平安银行家算法的优缺陷本算法要求被分配每类资源数量是固定不变。本算法要求用户数固定不变。本算法保证一切用户的要求在有限时间内得到，实时较
15、差。本算法要求用户事先阐明他的最大资源要求，这对用户较难。 7.5 死锁的检测与恢复死锁检测的概念资源分配图资源分配图的化简死锁检测中数据构造检测死锁的算法死锁的恢复一、死锁检测 允许死锁发生。操作系统不断监视系统进展情况，判别死锁能否发生。 一旦死锁发生那么采取专门的措施，解除死锁并以最小的代价恢复操作系统运转二、资源分配图 用有向图描画进程的死锁 资源分配图表示法资源类资源的不同类型用方框表示资源实例存在于每个资源中的假设干同种 资源用方框中的黑圆点表示进程用圆圈中加进程名表示分配边：资源实例进程的一条有向边恳求边：进程资源类的一条有向边有环有死锁有环无死锁死锁定理 假设资源分配图中没有环
16、路，那么系统中没有死锁；假设图中存在环路那么系统中能够存在死锁 假设每个资源类中只包含一个资源实例，那么环路是死锁存在的充分必要条件三、资源分配图化简假设一个进程所需的资源都满足，那么对该进程结点化简。化简的方法：移走一切分配边和恳求边。假设图中一切的进程结点均可化简成为孤立的结点，那么该形状是平安的，否那么是不平安的。四、死锁检测中数据构造可利用资源Available，它表示m类资源中每类资源可用数目。恳求矩阵Request ，一个mn矩阵，用以表示进程当前对各类资源的恳求数目。分配矩阵Allocation，一个mn矩阵，用以表示某一时辰的资源的分配情况。任务向量Work，表示系统可提供的各
17、类资源的数目。进程向量L，记录当前已不占用资源的各进程。五、检测死锁的算法把某时辰t的可用资源向量Available赋予Work把不占用资源的进程向量记入表L。从进程集合中找到一个Requesti Work的进程，做如下处置： 1.将其资源分配图化简 Work：= Work+ Allocationi 2.将它记入L表中假设不能把一切进程都记入L表，那么形状S资源分配图不可完全化简，该系统发生死锁。六、死锁的恢复强迫性吊销死锁的进程并剥夺资源 吊销的次序：运用最少处置器时间的进程运用最少输出任务量的进程具有最多剩余时间的进程分得最少资源的进程最小优先级的进程挂起和解除挂起作业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开始调度时，试写出作业调度次序。
