《操作系统》ppt电子课件教案第七章死锁

《《操作系统》ppt电子课件教案第七章死锁》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章死锁§1死锁的产生§2资源分配图及死锁定理§3预防死锁§4避免死锁§5检测与解除死锁§１死锁的产生假设系统中有这样一个资源集合Ｒ＝（ｒ１，ｒ２，…ｒｎ），其中ｒｉ（ｉ＝１，２，…，ｎ）为临界资源；又设有进程集合Ｐ＝（ｐ１，ｐ２，…,ｐｎ），其中每个进程都至少要求使用Ｒ中的某两个资源，且以下面的方式要求资源：即每个进程pi都是先申请ri,后申请riMODn+1。如果进程pi在进程piMODn+1到达L１之前到达L２,那么pi就能获得它所要求的资源ri和riMODn+1,从而可以继续运行下去。但是,由于各进程都是

2、异步前进的,如果没有一个进程Pi先于进程PiMODn+1到达L１之前到达L２,即所有进程同时处于L1～L２之间,此时任一进程到达L２都将被阻塞,它们都在等待本集合中另一进程已占用但又无法释放的资源。于是进程集合P陷入了死锁。假设资源Ｒ（如内存）有ｍ个分配单位，进程集合Ｐ＝（ｐ１，ｐ２，…，ｐｎ）共享Ｒ，且ｍ和ｎ满足关系式２≤ｍ≤ｎ。如果各进程对Ｒ的申请和释放都以一个分配单位进行，并且均采取如下方式：当有ｍ个进程均处于Ｌ１～Ｌ２之间时，由于Ｒ的ｍ个单位已全部被占用，它们中的任一个到达Ｌ２时均要被阻塞。而其余ｎ－ｍ个进程将

3、在Ｌ１处被阻塞。于是进程集合Ｐ因共享资源Ｒ而陷入死锁。在进程通讯中曾说过，若不适当地使用Ｐ、Ｖ操作容易导致死锁。例如在生产崐者与消费者算法中，如果把生产者进程的两个Ｐ操作执行次序调换一下，即先执行P(mutex)，后执行P(empty)。那么，当缓冲区已满且消费者不在临界区中，即有empty.v=0及mutexv=1。若此时生产者希望进入临界区，它先执行P(mutex)，使mutexv=0，当它执行P(empty)时被阻塞。以后,当消费者执行P(mutex)也被阻塞。于是两个进程无限止地相互等待对方来唤醒自己，陷入了死

4、锁产生死锁的四个必要条件：（１）互斥条件：进程访问的是临界资源，即一个资源一次只能被一个进程所使用。（２）请求和保持条件：一进程在请求新的资源的同时，保持对某些资源的占有。（３）不剥夺条件：一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。（４）环路等待条件：存在一个进程的环路，环路中每一个进程占有着某个或某些资源，又在等待被环路中的另一个进程占有的资源。§２资源分配图及死锁定理首先，我们引入用来表示资源使用状态的资源分配图RAG(ResourcesAllocationGraph)。一个ＲＡＧ可定义为一

5、个二元组，即ＲＡＧ＝（Ｎ，Ｅ），其中Ｎ是节点集合（ｎｏｄｅｓ），Ｅ是有向边集合（ｅｄｇｅｓ）。Ｎ又包含两个子集合，Ｎ＝（Ｐ，Ｒ），子集Ｐ＝｛p１，p2，…，pｍ｝是进程集合，每个元素pｉ表示一个进程，在图形中用矩形框表示；子集Ｒ＝｛ｒ１，ｒ２，…ｒｋ｝是资源集合，每个元素ｒｉ表示一类资源，在图形中用圆圈表示，某类资源可能有多个分配单位，这在图形中用圆圈中的小圆圈表示。边集Ｅ中的每个元素是pｉ→ｒｊ或ｒｊ→ｐｉ，这也可用有序偶表示，即〈ｐｉ，ｒｊ〉或〈ｒｊ，ｐｉ〉，其中ｐｉ∈P,rj∈R。若ｐｉ→ｒｊ∈Ｅ，则

6、在图形中存在一条从节点ｐｉ指向节点ｒｊ的有向边，称作请求边，它表示进程ｐｉ请求分配资源ｒｊ或ｒｊ中的一个单位；若ｒｊ→ｐｉ∈Ｅ，则在图形中存在一条从节点ｒｊ指向节点ｐｉ的有向边，称作分配边，它表示资源ｒｊ或ｒｊ中的一个单位已分配给了进程ｐｉ。当进程ｐｉ请求分配资源ｒｊ或ｒｊ的一个单位时，一条请求边被加入ＲＡＧ中，只要这个请求是可满足的，则该请求边便立即转换成分配边；当进程ｐｉ释放了某个资源ｒｊ时，则删除ＲＡＧ中相应的分配边。图７-１ＲＡＧ示例·集合Ｐ、Ｒ、Ｅ分别为：·资源单位数为：·进程状态为：进程p１已占用了ｒ２类资

7、源的一个单位，正在等待再获得ｒ１类资源；进程p２已占用了ｒ１类资源和一个单位的ｒ２类资源，且正在等待获得r3资源。进程p3已占用了r3类资源。这里假定，在某个时刻系统中有一组进程使用一组资源的状态为S,ＲＡＧ是状态Ｓ所对应的图，于是（１）若ＲＡＧ中未出现任何环路，则Ｓ为非死锁状态，或称安全状态。（２）若ＲＡＧ中出现了环路，且该环路中的各资源均为单单位资源（只有一个分配单位），则Ｓ为死锁状态。换言之，由若干单单位资源构成的环路，是Ｓ为死锁状态的充分必要条件。（３）若ＲＡＧ中出现了环路，但该环路中的各资源不全为单单位资

8、源，则Ｓ不一定是死锁状态。换言之，由若干不全为单单位资源构成的环路，是Ｓ为死锁状态的必要条件但非充分条件。化简方法如下：（１）从ＲＡＧ中找一个只有分配边的，或虽有请求边但该请求边能立刻转换为分配边（即该请求能立即得到满足）的非孤立节点ｐｉ，然后消去ｐｉ的全部有向边，即释放进程ｐｉ所占用的全部资源，使之成为孤立节点。