(最新)20-死锁-1.ppt

《(最新)20-死锁-1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章死锁本次课主要内容:死锁的基本概念死锁的四个条件死锁的表示死锁的解决方案（预防，避免，检测及解除）一、死锁的基本概念死锁是若干进程因使用系统资源不当而造成的带有全局危害性的现象。具体地说，死锁是在多道程序设计环境中，由于资源的独占性要求，就会出现若干进程竞争有限资源而构成循环等待的现象。下面我们通过一些生活中实例来说明死锁现象。例子1：在一条河上，有一座桥，桥面很窄，只能容纳一辆汽车通行，无法让两辆汽车并行。如果有两辆汽车分别从桥的左石两端驶上该桥，则会出现下述的冲突情况。此时，左边的汽车占有了桥面左

2、边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段；右边的汽车占有了桥面右边的一段，要想过桥还需等待左边的汽车让出桥向左边的一段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。例子2：考虑下面的例子：设系统中有一台打印机和一台读卡机，它们被两个进程P1和P2共用。P1已占用打印机，P2已占用读卡机，如果现在P1要求读卡机，而P2要求打印机，则P1和P2就会处于如下的死锁状态。1、进程总是要占用系统资源：系统中资源可分为若干类型，每类有若干实体。CPU周期、内存空间、文件和I/O设备等都是资

3、源类型的例子。进程按完成任务所需的资源情况来申请资源，申请到资源以后使用资源，使用完毕释放资源。对资源的申请、使用和释放均通过系统调用来实现。从进程提出申请得到资源到进程释放资源之间这段时间，我们称进程占有一个某资源。2、系统资源分配中存在死锁现象死锁是在多道程序系统中，若干个进程均互相等待对方无法释放的资源而无限地封锁下去的状态。3、关于死锁有如下的一些结论参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进

4、程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃二、产生死锁的充要条件产生死锁的条件，是下述四个条件在系统中同时存在：互相排斥（互斥使用资源）。即至少有一个资源是非共享资源。占有且等待。必存在这样的进程，它至少占有一个资源，并等待得到另外的资源，而后者当前被其它进程占有。非抢占式。资源不可以被抢占。循环等待。必存在一个进程集合{P0，P1，…，Pn}，P0等待P1占有的资源，P1等待P2占有的资源，…，Pn等待P0占有的资源。破坏上述四条的任一条即可预防死锁发生。三、死锁的表示死锁可以更精确地

5、用有向图的形式加以描述，该图称为系统资源分配图。一个系统资源分配图可以定义为一个二重组：G=（V，E），其中V是顶点的集合，E是边的集合。顶点分为两类：P={P1，P2，…，Pn}，是系统中所有进程组成的集合，每个Pi代表一个进程；R={R1，R2，…Rn}，是由系统中全部资源类型组成的，每个Ri代表一类资源。例：一个资源分配图P1P2P3R1R2R3R4P(i)代表进程，R(i)代表资源，边分为请求边和分配边边集合E中的每条边是一个有序对，〈Pi，Rj〉或〈Rj，Pi〉，Pi是进程（Pi∈P），Rj是资源

6、类型（Rj∈R）。边有两种：⑴请求边：〈Pi，Rj〉∈E，即存在一条从Pi指向Rj的有向边，它表示进程Pi提出了一个要求分配Rj类资源中的一个资源的请求，并且当前正在等待分配。⑵分配边：〈Rj，Pi〉∈E，即存在一条从Rj指向Pi的有向边，它表示Rj类资源中的某个资源已分配给了进程Pi。资源分配图的表示：用圆圈表示每个进程，用方框表示每个资源类型。由于同类资源可以有多个，用方框中的圆点表示各个单位资源。（注：请求边仅指向方框，分配边须明确指定方框中的一个圆点。）死锁的判定：⑴若资源分配图中未出现环路，则此时

7、系统中不存在死锁；⑵若资源分配图中有环路，且处于此环中的每类资源均只有一个个体，则有环就出现了死锁；⑶若资源分配图中有环路，但处于此环中的每类资源的个数不全为1，则环的存在是产生死锁的必要条件但不是充分条件。（即此情况下产生死锁必有环路，有环路不一定产生死锁）解决死锁的基本方法：⑴死锁的预防。指破坏产生死锁的四个充要条件中的一个或多个，使系统绝不会进入死锁状态。⑵死锁的避免。指允许产生死锁的四个充要条件有可能成立，但在资源动态分配过程中使用某种方法防止系统进入死锁状态。⑶死锁的检测与解除。指允许系统产生死锁

8、，然后使用检测算法及时发现并解除它。四、死锁的解决方案1、死锁的预防在系统设计时确定资源分配算法，保证不发生死锁，方法是分别根据产生死锁的四个充要条件提出预防措施。破坏互相排斥的条件非共享资源必须互斥使用，共享资源不需要互相排斥使用。因此通过破坏互斥条件预防死锁是不现实的。破坏占有且等待的条件保证无论什么时候一个进程都可申请到它想要的资源，方法有两个：方法一：资源的静态分配。在一个进程开始执行之前就申请并得到