w第3章 死锁.pptVIP

第3章 死 锁 3.1 资 源 资源举例： 硬件设备(打印机、硬盘、扫描仪)； 一组信息(加锁记录、信号量、系统表格)； 资源定义： 在任何时刻都只能被一个进程使用的任何对象； 3.1 资 源 3.1.1 资源使用模式 申请数量≤可用资源的总量，否则阻塞； 1．申请： 2．使用： 3．释放： 系统需要记录资源的申请、分配情况； 申请、分配、释放一般通过系统调用实现； 3.1.2 可剥夺资源与不可剥夺资源 按占用方式分类： 1．可剥夺资源 另外进程可以从拥有它的进程那里把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。 例如：A占有打印机并申请内存，B占有内存并申请打印机； 2．不可剥夺资源 不能从当前占有它的进程那里强行抢占的资源，必须由拥有者自动释放，否则会引起相关计算的失效。 例如：进程A刻录光盘；进程B申请使用光驱； 死锁和不可剥夺资源有关； 3.1.2 可剥夺资源与不可剥夺资源 按组成和功能划分： 硬件资源：CPU、内存、外设； 软件资源：信号量、消息、文件； 其它划分： 可再用资源（SR）：内存、设备、CPU； 消耗性资源（CR）：消息、I/O缓冲区信息、时钟中断； SR和CR都能导致死锁发生； 3.2 死 锁 概 念 3.2.1 什么是死锁 1．死锁示例 3.2.1 什么是死锁 在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁。 生产者进程Producer： 消费者进程consumer： while(TRUE){ while(TRUE){ P(mutex); P(mutex); P(empty); P(full); … … } } 设empty初值为N，如果Producer在填满N个缓冲区而消费者未取走的情况下，在empty = -1时阻塞；而消费者此时若正申请进入临界区(被生产者占用)，则因mutex=-1而阻塞； 3.2.1 什么是死锁 2．死锁定义 所谓死锁，是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。（是指系统中多个进程无限制地等待永远不会发生的状态；） 计算机系统产生死锁的根本原因就是资源有限，且操作不当(比如进程推进顺序不当) 3.2.1 什么是死锁 有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。 进程A 进程B …… …… 申请并占用R 申请并占用S 申请并占用S 申请并占用R …… …… 释放R 释放S 释放S 释放R …… …… 3.2.1 什么是死锁 图3-2 进程推进顺序对引发死锁的影响 3.2.1 什么是死锁 是否产生死锁既取决于动态执行过程，也取决于应用程序的设计。例如进程A不必同时申请两个资源，将代码改为： 进程A …… 申请并占用R …… 释放R 申请并占用S …… 释放S 3.2.2 死锁的条件 当计算机系统同时具备下面4个必要条件时，会发生死锁。 1．互斥条件 2．占有且等待条件 3．不可抢占条件 4．循环等待条件 只要有一个必要条件不满足，则死锁就可以排除。 3.2.3 资源分配图 1．资源分配图的构成 该图由结对组成： G = (V, E)。式中，V是顶点的集合，E是边的集合。顶点集合可分为两部分：P={p1, p2, …, pn}，它由系统中所有活动进程组成；R={r1, r2, …, rm}，它由系统中全部资源类型组成。 有向边pi →rj称为申请边，而有向边rj →pi称为赋给边。 在资源分配图中，通常用圆