操作系统课件-第三章进程管理7(死锁问题1)

进程管理1§3.8死锁问题在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障――死锁。在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果。进程管理23.8.1死锁的基本概念资源死锁的定义产生死锁的原因产生死锁的必要条件处理死锁的基本方法进程管理3资源的概念OS是计算机系统中资源的管理者，而进程是竞争资源的基本单位，故对系统中所有进程的资源分配工作，都由OS完成。研究资源分配时，我们必须搞清该资源是可以被几个进程同时使用，还是只能为一个进程使用，资源的不同使用性质正是引起系统死锁的原因。进程管理4根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。可抢占资源—指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。不可抢占资源—指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。资源的分类进程管理5根据使用方式：共享资源和独享资源。根据使用期限；永久资源和临时性资源。资源CPU、主存、硬盘，该类资源可为几个进程共同使用（可抢占）打印机，读卡机，磁带驱动器，可为某个进程独享（不可抢占）可顺序重复使用的资源由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源进程管理6死锁的定义死锁Deadlock：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。陷入死锁状态的进程称为死锁进程，所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。进程管理7产生死锁的原因1竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；2进程推进的顺序不当。进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。进程管理8竞争资源1竞争非剥夺性资源：2竞争临时性资源打印机R1磁带机R2P1P2进程管理9P1S1S3P2P3S2P1：Release(S1);Request(S3)P2：Release(S2);Request(S1)P3：Release(S3);Request(S2)不可能发生死锁P1：Request(S3);Release(S1)P2：Request(S1);Release(S2)P3：Request(S2);Release(S3)可能发生死锁S1、S2、S3是临时资源进程管理10P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③④③③③②②①①进程P1、P2并发执行。资源R1、R2曲线4将进入不安全区域（进程推进顺序非法）进程管理11死锁模型R1R2P1P2申请r2已分配给p2申请r1已分配给P1R2已经分配给P1、R1已经分配给P2进程管理12产生死锁的四个必要条件⑴互斥条件:进程访问的是临界资源，那个资源一次只能被一个进程所使用。⑵不剥夺条件:一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。⑶部分分配:（请求和保持条件）一个进程在请求新的资源的同时，保持对某些资源的占有。⑷环路等待条件:存在一个进程的环路链，链中每一个进程占用有着某个或某些资源，又在等待链中的另一个进程占有的资源。进程管理13生产者—消费者问题avail－生产者用信号量，记录缓冲区空单元个数。Full—消费者信号量，记录产品个数。Mutex—互斥信号量。进程管理14deposit(data)remove(data)beginbeginp(avail)p(full)p(mutex)p(mutex)送数据入缓冲区某取缓冲区中某单元单元数据v(full)v(avail)v(mutex)v(mutex)endend进程管理15在前述若pv操作使用不当，会引起死锁。把生产者进程两个p操作次序调换一下，先执行P（mutex）,后执行P(avail)P（mutex）互斥P（avail）判断缓冲区满，不能送，从消费者执行。那么当缓存区满且消费者此时不再临界区中，执行到互斥P（mutex）后，消费者进程想进入临界区，但被阻塞在外。若生产者希望进入临界区，也被阻塞，于是两个进程无限止地相互等待对方来唤醒自己，两个进程陷入死锁。进程管理163.8.2死锁的排除方法1鸵鸟算法2预防死锁3避免死锁4检测和解除死锁进程管理171鸵鸟算法（置之不理）解决死锁的最简单方法就是鸵鸟算法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。以UNIX系统为例，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。进程管理18UNIX系统允许创建的进程总数是由进程表中包含的PCB个数决定的。因此，PCB资源是有限资源。如果由于进程表中已经无空闲的PCB而使创建子进程操作(FORK)失败，则执行FORK操作的程序可以等待一段时间之后再试。出现这种情况的可能性是非常小的，但还是有可能发生的。一旦出现，只要忽略原进程已运行情况的现场，重新启动机器让它们重新运行即可。假定UNIX系统有100个PCB项，10个进程正在运行，每个需要创建12个子进程。进程管理19在每个进程已经创建9个进程后，原来的10个进程和新创建的90个子进程已用完了进程表。这样，原来的10个进程现在都处于创建子进程的无限循环中——死锁。出现这种情况的可能性是非常小的，但还是有可能发生的。一旦出现，只要忽略原进程已运行情况的现场，重新启动机器让它们重新运行即可。进程管理202预防死锁根据生产死锁的四个必要条件，只要使用其中之一不能成立，死锁就不会出现。但必要条件是由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。预防死锁是一种较易实现的方法，已被广泛使用，但由于所施加的限制条件往往太严格，可能导致系统资源利用率和系统吞吐量降低。1互斥条件2请求和保持条件3不剥夺条件4环路等待条件进程管理211:防止部分分配（摒弃请求和保持条件）系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要由一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源，所以，再分配就不会发生（摒弃了部分分配）。特点：资源严重浪费进程延迟进行进程管理223防止“不剥夺”条件的出现采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）进程管理232.防止“环路等待”条件的出现。采用资源顺序使用法，基本思想是：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号。例如输入机＝1，打印机＝2，磁带机＝3，磁盘＝4等等。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。缺点：1为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加2作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；进程管理243死锁避免避免死锁与预防死锁的区别在于，预防死锁是设法至少破坏产生死锁的必要条件之一，严格地防止死锁的出现。避免死锁，它是在进程请求分配资源时，采用银行家算法等防止系统进入不安全状态。进程管理25在资源的动态分配的过程中，使用某种方法去防止系统进入不安全状态，从而避免死锁的发生。系统状态：安全状态：指系统能按照某种顺序如P1,P2,…,Pn(称为P1,P2,…,Pn序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。非安全状态：即在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态。进程管理26虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。进程管理27安全状态的例子例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列P2，P1，P3进程管理28作业图书馆阅览室问题问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。进程管理29吃水果问题问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用P、V操作实现四人正确活动的程序。进程管理30司机—售票员问题设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上下乘客正常行车关车门到站停车售票开车门上下乘客在汽车不断到站，停车，行驶过程中，这两个活动的同步关系。进程管理31理发师问题问题描述：一个理发店由一个有几张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待；若理发师在睡觉，则顾客就唤醒他，设计一个协调理发师和顾客的程序。