操作系统教程——Linux实例分析 教学课件 作者 孟庆昌 第1－8章第8章 死锁.ppt

《操作系统教程——Linux实例分析 教学课件 作者 孟庆昌 第1－8章第8章 死锁.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章死锁8.1概述8.2产生死锁的条件8.3死锁的预防8.4死锁的避免8.5死锁的检测与恢复8.6处理死锁的综合方式习题8.1概述8.1.1死锁的概念死锁(Deadlock)是若干进程因系统资源有限且操作不当而造成的带有全局危害性的现象。我们考虑下面这个例子：设系统中只有一台打印机和一台读卡机，它们被进程A和进程B共用。这两台物理设备的特性决定了对它们的使用方式必须是顺序的，即一个进程用完了，另一个进程才能用。进程A和B各自对资源的申请使用情况如下：A：申请读卡机B：申请打印机申请打印机申请读卡机使用读卡机使用打

2、印机使用打印机使用读卡机释放读卡机释放打印机释放打印机释放读卡机由于进程并行工作，就可能出现这样的执行序列：A：申请读卡机B：申请打印机A：申请打印机B：申请读卡机所谓死锁就是指在一个进程集合中的每个进程，都在等待仅由该集合中的另一进程才能引发的事件，而无限期地僵持下去的局面。8.1.2资源概念当若干进程取得对设备、文件等资源的独占性访问权时，就可能出现死锁。资源可以是硬件设备（如打印机、磁带驱动器、扫描仪等），也可以是一组信息（如数据库中一个加锁的记录、一个信号量、系统表格中的一个表项等）。1.进程对资源的操作系

3、统中包括有限的资源，要分给大量的计算进程。资源可分为若干类型，每类都有若干个实体。CPU周期、内存空间、文件和I／O设备(如打印机、磁带驱动器、读卡机等)都是资源类型的例子。一个进程在使用资源之前要申请资源，在用完之后必须释放该资源。在通常的操作方式下，进程只能按下述序列使用资源：1）申请如果所申请的资源因被其他进程占用而不能立即得到，那么申请资源的进程必须等待，直至其他进程释放资源为止。2）使用进程对该资源进行操作(如在行式打印机上打印结果)。3)释放进程释放它以前申请并分配到的资源。2.可剥夺资源与不可剥夺资源

4、系统中一般都有多种资源。按照占用方式来分，可以分为两类：可剥夺资源与不可剥夺资源。可剥夺资源是另外进程可以从拥有它的进程那里把它剥夺过去为己所用，并且不会产生任何不良影响。在2.4.7节的同步计数例子中，如果将供者和用者代码中的前两个P操作的位置颠倒，成为：供者用者：L1：P(mutex)L2:P(mutex)P(empty)P(full)8.1.3进程推进顺序与死锁图8-1示出了进程推进顺序对引发死锁的影响。设有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源，因此必须在一段时间内独占使用。进程

5、A和B的一般形式是：进程A进程B申请R申请S申请S申请R释放R释放S释放S释放R图8-1中，X轴和Y轴分别表示进程A和B的执行过程，从原点出发的不同的折线分别表示两个进程以不同速度推进时所合成的路径。在单CPU系统中，任何时候只能有一个进程处于执行状态。路径中的水平线段表示进程A在执行，进程B等待；而垂直线段表示进程B在执行，进程A等待。图8-1进程推进顺序对死锁的影响（1）进程B获得资源S，然后又获得R，后来释放S和R。当进程A恢复执行时，它能够获得这两个资源。A和B都可进行下去。（2）进程B获得资源S，

6、然后又获得R；接着进程A执行，因未申请到资源R而阻塞，B释放S和R。当A恢复执行时，能够获得这两个资源。（3）进程B获得资源S，而进程A申请到R。此时，死锁不可避免，因为B向下执行会阻塞在R上，而A会阻塞在S上。（4）进程A获得资源R，接着进程B获得资源S。此时，死锁不可避免。因为向下执行，B将在R上阻塞，A将在S上阻塞。（5）进程A获得资源R，接着获得S。进程B执行，由于未申请到S而阻塞。之后，A释放资源R和S，当B恢复执行时，它能获得这两个资源。（6）进程A获得资源R和S，然后释放R和S。当进程B恢复执行时，它

7、能获得这两个资源。可见，是否产生死锁既取决于动态执行过程，也取决于应用程序的设计。例如，若进程A不必同时申请两个资源，代码改为：进程A申请R释放R申请S释放S8.2产生死锁的条件8.2.1产生死锁的必要条件1.互斥条件即某个资源在一段时间内只能由一个进程占有，而不能同时被两个或两个以上的进程占有。这种独占资源如平板式绘图仪、CD-ROM驱动器、打印机等等，必须在占有该资源的进程主动释放它之后，其他进程才能占有该资源，这是由资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。2.占有且等待条

8、件进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占有已分到的资源。3.不可抢占条件一个进程所占有的资源在未使用完毕之前，其他进程不能强行地从资源占有者手中夺取该资源，而只能由该资源的占有进程自行释放。4.循环等待条件存在一个进程等待序列{P1,P2,…,Pn}，其中P1等待P2所占有的