操作系统os5-09.ppt

第五章 资源分配与调度 5.4 死锁5.4.1 死锁的概念 死锁定义： 死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态。 5.4 死锁5.4.1 死锁的概念 5.4 死锁5.4.2 死锁的起因 5.4 死锁5.4.2 死锁的起因 产生死锁的必要条件： 1、互斥条件 2、不可剥夺条件 3、部分分配 4、环路条件 5.4.3 解决死锁问题的策略 一、解决死锁问题策略 为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。 5.4.3 解决死锁问题的策略 互斥条件：难以否定，但可采用虚拟设备技术（例如：假脱机技术）。 不可剥夺条件：容易否定，可采用相应的资源分配策略。例如，当一个进程申请某资源被拒绝，则必须释放已占用的资源。对CPU还可进行可剥夺分配。 5.4.3 解决死锁问题的策略 5.4.4 死锁的预防 预先分配一个进程要用的所有资源（静态分配）是防止死锁的一种安全而简单的方法。 设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分枝语句。 5.4.5 死锁的避免 一、有序资源分配法 系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等）， 申请时必须以上升的次序。 系统要求： 1、对必须使用的而且属于同一类的资源，必须一次申请完； 2、在申请不同类资源时，必须按设备编号依次申请。 5.4.5 死锁的避免 例如：进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1； 若采用动态分配有可能形成环路条件，造成死锁。 采用有序资源分配法： R1的编号为1，R2的编号为2； PA：申请次序应是：R1，R2 PB：申请次序应是：R1，R2 这样就破坏了环路条件，避免了死锁的发生。 5.4.5 死锁的避免 二、银行家算法 避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法： 该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。 这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。 5.4.5 死锁的避免 例：假定系统有10个资源 5.4.6 死锁的检测和恢复 死锁的检测： 很难找到切实可行的办法，教材（P126）上的方法难以实现； 通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间。在UNIX系统中有命令PS可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁。 5.4.6 死锁的检测和恢复 死锁排除的方法： 1、撤消陷于死锁的全部进程； 2、逐个撤消陷于死锁的进程，直到死锁不存在； 3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。 Full：缓冲区产品数目，初值为0； Empty：缓冲区可存放产品的空位，初值为n； Mutex：缓冲区互斥信号灯，初值为1。 main（） { int full，empty=n； int mutex=1； cobegin producer（）； consumer（）； coend； } 例1：生产者－消费者问题 5.4 死锁5.4.0 引例 Consumer（） { while（还要继续消费）{ p（full）； p（mutex）； 从缓冲区中取出一个产品； v（mutex）； v（empty）； 消费产品； } } producer（） { while（生产未完成）{ 生产一个产品； p（empty）； p（mutex）； 将产品放入缓冲区； v（mutex）； v（full）； } } 例1：生产者－消费者问题 p（empty）； p（mutex）； 放影显示 main（） { int mutex = 0； cobeginm ppa（）； ppb（）； coend } ppa（） { ???； p（mutex）； 使用打印机； v（mutex）； ???； } ppb（） { ???； p（mutex）； 使用打印机； v（mutex）； ???； }