操作系统原理-第五章 资源分配与调度

计算机学院李胜利操作系统原理第五章资源分配与调度1第五章资源分配与调度•5.1资源管理概述•5.1.1资源管理的目的和任务•目的：•1、保证资源的高利用率；•2、在“合理”时间内使所有顾客有获得所需资源的机会；•3、对不可共享的资源实施互斥使用；•4、防止由资源分配不当而引起的死锁。计算机学院李胜利操作系统原理第五章资源分配与调度25.1资源管理概述5.1.1资源管理的目的和任务•对资源的管理应包括以下几个方面：•1、资源管理的描述－－数据结构•2、确定资源的分配原则和调度原则•3、执行资源分配（实施）•4、存取控制和安全保护•5.1.2资源的几种分类方法（自学）计算机学院李胜利操作系统原理第五章资源分配与调度35.2资源分配机构•描述资源的管理和控制信息的数据结构称为资源分配的机构。•在教材上列出了两种：•资源描述器资源信息块•在实际的系统中，会根据实际需要设计相应的数据结构。例如：进程管理主要管理的机构：PCB、就绪队列和各种等待队列。计算机学院李胜利操作系统原理第五章资源分配与调度45.3资源分配策略5.3.1概述•资源分配有两种方式：•静态分配：当一个进程（或程序）运行前，将它要求的资源一次分配加该进程，直到该进程终止，释放其占用的所有资源。这种分配方法效率太低；•动态分配：当一个进程要求使用某个（类）资源时，向系统提出资源的请求，系统响应程序的请求将某种资源分配给请求者，这种方法使得系统资源的利用率提高，但有可能造成死锁。计算机学院李胜利操作系统原理第五章资源分配与调度55.3资源分配策略5.3.1概述•几种分配策略：•1、先请求先服务（FIFO）•2、优先调度•3、适应调度•4、均衡调度•5、针对设备特性的调度计算机学院李胜利操作系统原理第五章资源分配与调度65.4死锁5.4.1死锁的概念•在这两个进程并发执行时，当PA进程占有R1、PB进程占用R2时，PA要求R2，由于PB已占R2有而得不到，PA进程只有等待；PB申请R1，由于PA已占有R1，而得不到，PB进程只有等待，就出现了死等的情况。计算机学院李胜利操作系统原理第五章资源分配与调度75.4死锁5.4.1死锁的概念•例1：有两个进程PA和PB，它们在运行的过程中要共享使用两个独占设备R1和R2。设SR1：表示设备R1可用，初值为1；SR2表示设备R2可用，两个进程并发执行的程序如下：计算机学院李胜利操作系统原理第五章资源分配与调度85.4死锁5.4.1死锁的概念例2：三个进程共享使用一台打印机的程序若有一个进程少写了一个V操作。计算机学院李胜利操作系统原理第五章资源分配与调度95.4死锁5.4.1死锁的概念例3：生产者－消费者问题•当缓冲区满时，生产者仍可顺利执行p(mutex)操作，于是它对缓冲区有控制权，然后，当它执行p(empty)时，由于没有空缓冲区被挂起。能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品，并执行v(empty)操作，但由于缓冲区已被生产者占用，出现了死锁。计算机学院李胜利操作系统原理第五章资源分配与调度105.4死锁5.4.1死锁的概念•死锁简单的定义：•死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态。•教材上关于死锁的定义：•两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。计算机学院李胜利操作系统原理第五章资源分配与调度115.4死锁5.4.2死锁的起因计算机学院李胜利操作系统原理第五章资源分配与调度125.4死锁5.4.2死锁的起因•产生死锁的四个必要条件：•1、互斥条件•2、不可剥夺条件•3、部分分配•4、环路条件计算机学院李胜利操作系统原理第五章资源分配与调度135.4.3解决死锁问题的策略•一、解决死锁问题的几个策略•为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。•条件1：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；•条件2：容易不定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。计算机学院李胜利操作系统原理第五章资源分配与调度145.4.3解决死锁问题的策略•条件3：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。•条件4：实际上系统不采用部分分配，也就破坏了环路条件。•二、系统状态分析（略）计算机学院李胜利操作系统原理第五章资源分配与调度155.4.4死锁的预防•预先分配一个进程要用的所有资源是防止死锁的一种安全而简单的方法，但设备的使用效率太低。其缺点也是明显的：•1、一个用户（进程）在程序运行之前艰难提出将要使用的全部设备；•2、设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分枝语句。计算机学院李胜利操作系统原理第五章资源分配与调度165.4.5死锁的避免•为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则拒绝分配。•预防死锁：•采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁；•死锁避免：•是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能产生死锁的某个资源的请求。计算机学院李胜利操作系统原理第五章资源分配与调度175.4.5死锁的避免•一、有序资源分配法•这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。•系统要求申请进程：•1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；•2、在申请不同类资源时，必须按各类设备的编号依次申请。计算机学院李胜利操作系统原理第五章资源分配与调度185.4.5死锁的避免•例如：进程PA，使用资源的顺序是R1，R2；•进程PB，使用资源的顺序是R2，R1；•若采用动态分配有可能形成环路条件，造成死锁。•采用有序资源分配法：R1的编号为1，R2的编号为2；•PA：申请次序应是：R1，R2•PB：申请次序应是：R1，R2•这样就破坏了环路条件，避免了死锁的发生。计算机学院李胜利操作系统原理第五章资源分配与调度195.4.5死锁的避免•二、银行算法•避免死锁算法中最有代表性的算法是DijkstraE.W于1968年提出的银行家算法：•该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。•这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。计算机学院李胜利操作系统原理第五章资源分配与调度205.4.5死锁的避免•例子：假定系统有10个资源（为了说明问题的简单，不管它是什么资源），目前分配的情况如上表：•此时，系统中只剩下2个资源，这时就要考察能满足哪个进程，不能满足P和R的最大要求，能满足Q，于是将剩下的2个资源分配给Q，Q就能完成，然后释放所占用的6个资源。•可满足P，也可满足R，这时不论分给谁都能保证完成。计算机学院李胜利操作系统原理第五章资源分配与调度215.4.6死锁的检测和恢复•死锁的检测：•很难找到切实可行的办法，教材（P126）上的方法很难实现；•通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间。在UNIX系统中有命令PS可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁。计算机学院李胜利操作系统原理第五章资源分配与调度225.4.6死锁的检测和恢复•死锁排除的方法：•1、撤消陷于死锁的全部进程；•2、逐个撤消陷于死锁的进程，直到死锁不存在；•3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。