操作系统第三章调度与死锁2016-10详解.ppt

§3.7 死锁的基本概念（一） 死锁（deadlock）— 是OS的一种随机故障，是指两个或 两个以上的进程都无限制的地等待永远不会出现的 事件而发生的状态。 1、争夺资源引起死锁 例1：P1，P2两个进程争夺打印机和读卡机。 一、死锁的原因 P1 P2 打印机 读卡机 ? P1已经申请到打印机， 又申请读卡机。 ? P2已经申请到读卡机， 又申请打印机。 打印机和读卡机为 非剥夺性资源。 例3、 P1，P2，P3 三个进程之间通信： P1产生消息S1，接收P3产生的消息S3； P2产生消息S2，接收P1产生的消息S1； P3产生消息S3，接收P2产生的消息S2； 按以下次序运行： P1：Request（S3）；Release（S1） P2：Request（S1）；Release（S2） P3：Request（S2）；Release（S3） §3.7 死锁的基本概念（二） 2、进程推动顺序不当引起的死锁 P1 P3 P2 S2 S3 S1 P1 P2 P3 按照以上的顺序执行会产生死锁吗？ ？问题？ 例2、 在生产者—消费者问题中如果交换两个P操作 的次序，可能引起死锁。 Si临时性资源 §3.7 死锁的基本概念（三） 生产者进程： 生产一个产品 m ； . . . P（empty）； P（mutex）； 将产品 m放入缓冲区； in ：=（in +1） mod n ； V （mutex）； V（ full）； 消费者进程： P （ full）； P （ mutex ）； 从缓冲区取产品m； out ：=（out+1） mod n ； V （mutex）； V （empty）； 生产者—消费者问题算法： §3.7 死锁的基本概念（四） 由于 产生死锁的根本原因是争夺共享资源，从而得到产生死锁的必要条件是： 二。死锁的必要条件 互斥条件 进程互斥使用临界资源。 不剥夺条件 资源只能由占有它的进程释放，不能 被其它进程剥夺。 —非剥夺资源 部分分配条件 进程在申请新资源的同时，保持对某 些资源的占有。 环路等待条件 存在循环等待链，在链中每个进程都 在等待它的前一进程所持有的资源。 §3.7 死锁的基本概念（五） 显然，如果出现死锁将对操作系统造成极大的危害，甚至使系统瘫痪，如何解决死锁是操作系统设计的重要问题。 限制并发进程对于资源的需求，破坏产生死 锁的必要条件。严格限制死锁的发生。 三。解决死锁的方法 预防死锁 避免死锁 在资源的动态分配过程中，采用某种算法防止系统进入不安全状态，避免死锁发生。 检测与解除死锁 对资源的分配不加限制，系统定时运行“死锁 检测”程序，如检测到死锁，设法加以解除。 §3.7 死锁的基本概念（六） ◆ 采用资源的静态分配策略，破坏“部分分配”条件。 即只有当进程所需要的全部资源满足时，系统予以 一次分配。 ◆ 允许进程剥夺使用其他进程占有的资源，破坏“不 剥夺条件”。 进程动态申请资源，当进程申请不到新资源时，应立即释放已占有的 所有资源。 ◆ 采用资源顺序分配法，破坏“环路等待”条件。 将系统中的所有资源按类型线性排队，并赋予唯一编号，进程申请资源时，严格按编号递增顺序分配。 预防死锁 §3.7 死锁的基本概念（七） 1）系统的安全状态 在分配资源时，分析计算系统的安全性，避免系统进入不安全状态，则可避免死锁。 系统状态安全 存在一个进程序列?P1，P2，。。。Pn? ，如果