操作系统原理第三章处理机调度与死锁内容处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念处理机调度的基本概念内容调度算法采用FCFS调度算法时的调度性能短作业（进程）优先(SJF)既可用于作业调度，也可用于进程调度算法描述有效降低作业平均等待时间，提高系统吞吐量。调度算法SJ（P）F调度算法也存在不容忽视的缺点（1）该算法对长作业非常不利。（2）该算法完全未考虑作业的紧迫程度（3）不一定能真正做到短作业优先调度。高优先权优先调度算法既可用于作业调度，也可用于进程调度优先权调度算法类型非抢占式优先权算法主动交出CPU，用于批处理系统抢占式优先权算法被动交出CPU，实时性更好高优先权优先调度算法优先权类型静态优先权进程的整个运行期间保持不变特点：简单，但低优先权作业可能长期不被调度。动态优先权如：优先权随执行时间而下降，随等待时间而升高。调度算法调度算法调度算法基于时间片的轮转调度算法时间片轮转法时钟中断时间片大小的确定太大：退化为FCFS；太小：系统开销过大多级反馈队列调度基于时间片的轮转调度算法多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。有5个批处理作业（A、B、C、D、E）几乎同时到达，估计的运行时间分别为2、4、6、8、10分钟，它们的优先数分别为1、2、3、4、5（1为最低优先数）。对下面的每种调度算法，分别计算作业的平均周转时间。（1）最高优先级优先。（2）时间片轮转（时间片为2分钟）。（3）FIFO（作业的到达顺序为C、D、B、E、A）（4）短作业优先。内容实时调度实时调度算法的分类按照调度方式的不同对调度算法进行分类非抢占式调度算法简单，易于实现，应用在小型实时系统或要求不太严格的实时控制系统中。非抢占式轮转调度算法实时任务到达时，插入就绪队列队尾非抢占式优先调度算法实时任务具有较高优先权，当到达时插入就绪队列队首进程1实时调度算法的分类抢占式调度算法用于要求比较严格的实时系统中，响应时间为数十毫秒以下。根据抢占发生时间的不同而进一步分成以下两种调度算法：基于时钟中断的抢占式优先权调度算法某实时任务到达时，若该任务优先级高于当前任务优先级，并不立即抢占，而是等到时钟中断到来时立即抢占的优先权调度算法见下页举例视图实时调度常用的几种实时调度算法最早截止时间优先根据任务的开始截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式常用的几种实时调度算法最低松弛度优先调度算法松弛度=必须完成时间–本身运行时间–当前时间按松弛度确定优先权，松弛度越低，优先权越高主要用于可抢占的调度方式中例如：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90实时调度内容多处理机系统中的调度进程分配方式对称MPS系统中进程分配方式由于结构相同，可将进程分配到任一处理器上运行把处理器作为一个处理器池，将进程分配到任一处理器静态：一个进程从开始执行直到其完成，都被分配到一个固定的CPU上去执行，此时需要配置一个专用就绪队列多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度多处理机系统中的调度内容产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件内容预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法银行家算法中的数据结构分配矩阵Allocation已分配给每一进程的资源数n×m矩阵，Allocation[i,j]表示进程i已获得的j类资源数。需求矩阵Need一个进程尚需的各类资源数Need=Max-Allocationn×m矩阵，Need[i,j]表示进程i还需要的j类资源数。预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法预防死锁的方法内容死锁的检测与解锁小结小结