第七章节死锁的预防避免和检测.ppt

死锁问题 ? 系统中有进程处于相互的无限等待状态 （被阻塞） ? 资源死锁和通信死锁 ? 等待图：将系统中进程对资源的占用与需求共享情况用有向图表示 – 进程集合{P0, P1 ,……, Pn}为节点集，当且仅当进程Pi等待一个被进程Pj占用的资源时，边(Pi, Pj)存在于图中。 资源(resources)分类 根据资源性质：可剥夺资源(抢占)和不可剥夺资源 可抢占资源：指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。 不可抢占资源：指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。 可抢占资源如：CPU、主存、硬盘，该类资源可为多个进程共享（可抢占） 不可抢占资源如：打印机、读卡机，磁带驱动器，该类资源可为某个进程独享（不可抢占） 资源分类 根据使用方式：共享资源和独享资源 根据使用期限：永久资源和临时性资源 永久资源是可顺序重复使用的资源 临时性资源是由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源。 产生死锁的原因 竞争资源。当系统中供多个进程所共享的资源 ，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。 进程推进的顺序不当。进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。 竞争资源 竞争非剥夺性资源 竞争临时性资源 S1，S2，S3是临时资源 P1:Release(S1);Request(S3) P2:Release(S2);Request(S1) P3:Release(S3);Request(S2) 不可能发生死锁 P1:Request(S3) ; Release(S1) P2:Request(S1) ; Release(S2) P3:Request(S2) ; Release(S3) 可能发生死锁 死锁问题一实例：哲学家问题 死锁问题一条件 ? 死锁发生的充要条件 – 互斥：一个资源在同一时刻不能被共享； – 占有并等待：必然有一个进程占用了至少一个资源，同时在等待获得被其它进程占用的资源； – 不可剥夺：已占用的资源不能被剥夺 – 循环等待：等待图中有一个回路 ? 死锁的形式 – AND条件：当进程获得所有所需的资源后才能继续执行 – OR条件：当进程至少获得一个所需的资源后才能继续执行 – P-out-of-Q：进程同时请求Q个资源但至少获得P个之后才能继续执行 处理死锁的策略—死锁的避免 动态检查资源的分配情况，只有在结果状态是安全的情况下，才将资源分配给进程；在分布式系统中实现的开销较大 银行家算法：至少总可以满足一个客户的要求 银行共有资金800万：A的余额是600万，B的余额是400万，C的余额是500万；A要求一次提走300万，B要求一次提走200万，C要求一次提走100万，假设客户在存款后会立即重新全额存入。 当以上提款要求被满足后，银行当前存款余额还剩200万。这时，A、B和C均要求提取剩余款，则服务次序B→C→A是安全的，其他的服务顺序或上述条件的违反都可能导致不安全的结果状态。 死锁避免的方法 死锁避免，即动态检查资源状态，以保证没有循环等待发生。 在集中式系统中，银行家算法是死锁避免的一个经典算法。 基于Petri网的死锁避免方法适合应用在分布式系统中。 基于Petri网的死锁避免方法步骤 1)给出描述特定系统的模型 2)得到相应的Petri网的可达树 3)由可达树确定死锁状态 4)根据死锁状态，找到所有的临界状态和它们的抑制变迁。 Petri网描述的状态 安全状态：包括临界状态和非临界状态 不安全状态：包括死锁状态和死锁边界状态 临界状态：如果一个状态接近死锁状态但是仍可以到达其他不导致死锁的状态。 非临界状态：如果在某个状态下总不会到达死锁状态，则称该状态为非临界状态。 死锁状态：导致死锁的不安全状态称为死锁状态 死锁边界状态：可能导致死锁的不安全状态称为死锁边界状态。 分布式系统处理死锁的策略 基于死锁预防的策略 基于死锁检测的策略 分布式系统死锁的特点：由于信息散布在多台机器上，死锁难以检测和处理。 分布式系统预防死锁的方法 要求进程在开始执行前就已经获得了所有了所有需要的资源。 所有资源都被唯一编号，进程必须按资源编号单调申请。 进程具有优先级编号，优先级低的首先放弃资源。 为了提高公平性，进程的优先级可以动态变化。 用预防策略解决哲学家问题 基于资源编号：所有哲学家均要先拿编号大的叉子，再拿编号小的叉子，在没有获得大编号的叉子前，即使编号小的叉子没有被占有，也不允许使用。 基于进程编号：优先级高的哲学家可以等待优先级低的哲学家的叉子，反之不然。即当一个哲学家发现自己在等待另一个比自己有更高优先级的哲学家的资源时，他必须放弃已经控制的叉子