多线程中的死锁问题.ppt

Chapter 8: Deadlocks 死锁 8.1 死锁问题 一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源 例 系统有两个磁带设备 进程P1和P2各占有一个磁带设备并且实际需要两个磁带 例 semaphores A and B, initialized to 1 信号量A，B初始化为1 P0 P1 wait (A); wait(B) wait (B); wait(A) 过桥的例子 只有一个方向 桥的每一个部分都可以看成资源 如果死锁发生，它可以由一辆车返回而解决，抢占资源并回退 如果死锁发生，可能很多车都不得不返回 有可能产生饥饿 系统模型 Resource types资源类型R1, R2, . . ., Rn CPU cycles, memory space, I/O devices CPU周期，内存空间，I/O设备 每一种资源Ri有Wi 种实例 每一个进程按如下顺序利用资源 request申请 use使用 release释放 8.2 死锁特点 8.2.1 必要条件 以下四个条件同时出现，死锁将会发生 互斥：一次只有一个进程可以使用一个资源 占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源 非抢占：一个资源只有当持有它的进程完成任务后，自由的释放 循环等待：等待资源的进程之间存在环 有一组进程 {P0, P1, …, Pn} ， P0 等待的资源为P1所占有, P1等待的资源为P2所占有, …, Pn–1等待的资源为Pn所占有, Pn等待的资源为P0所占有. 8.2.2 资源分配图 节点集合V被分为两种类型： P = {P1, P2, …, Pn}, P：含有系统中全部的进程 R = {R1, R2, …, Rm}, R：含有系统中全部的资源 申请边：Pi ? Rj assignment edge – directed edge Rj ? Pi 分配边：Rj ? Pi 资源分配图 Process进程 Resource Type with 4 instances有四个实例的资源类型 Pi requests instance of Rj Pi 请求一个Rj的实例 Pi is holding an instance of Rj Pi 持有一个Rj的实例 资源分配图的例子 有死锁的资源分配图 有环但没有死锁的资源分配图 基本事实 如果图没有环，那么不会有死锁 如果图有环 如果每一种资源类型只有一个实例，那么死锁发生 如果一种资源类型有多个实例，可能死锁 8.3 处理死锁的方法 确保系统永远不会进入死锁状态 允许系统进入死锁状态，然后恢复系统 忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX 8.4 死锁的预防 8.4.1 互斥：共享资源不要求互斥访问，非共享资源必须要有互斥条件 8.4.2 占有并等待：必须保证进程申请资源的时候没有占有其他资源 要求进程在执行前一次申请全部的资源 例：一个进程，将数据从磁带驱动器复制到磁盘文件，并对磁盘文件排序，再将结果打印到打印机上。 一开始就申请磁带驱动器，磁盘文件，打印机 只有没有占有资源时才可以分配资源 先申请磁带驱动器，磁盘文件，再申请磁盘文件，打印机 缺点：资源利用率低，可能发生饥饿 死锁的预防 8.4.3 No Preemption – 非抢占 如果一个进程的申请没有实现，那么其现已分配的资源都被抢占 先占的资源放入进程等待资源链表中 只有当进程获得其原有资源和所申请的新资源时，进程才可重新执行 死锁的预防 8.4.4 循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源 8.5 死锁避免 一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数 死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况 资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量 死锁避免 8.5.1 Safe State安全状态 如果系统能按某个顺序为每个进程分配资源（不超过其最大值）并能避免死锁，那么系统状态就是安全的。 如果存在一个安全序列，那么系统处于安全态， Safe State (Cont.) 进程序列P1, P2, …, Pn是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数 进程Pi所需要的资源即使不能立即可用，那么 Pi可等待直到所有 Pj 完成并释放其资源.