《第三章 处理机调度与死锁》由会员分享，可在线阅读，更多相关《第三章 处理机调度与死锁（114页珍藏版）》请在金锄头文库上搜索。
1、第三章处理机的调度和死锁处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次v在多道程环境下，进程数目往往多于处理机数目 就，致使它们争用处理机。v这要求系统能按某种算法，动态地把处理机分配 给就绪队列中的一个进程，使之执行。v分配处理机的任务是由进程调度程序完成的。它 是操作系统设计的中心问题之一。处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次3.1.1 高级调度v一个批处理型作业，从进入系统并驻留在外存的 后备队列上开始，直至作业运行完毕，可能要经 历下述三级调度。1、高级调度2、中级调度3、低级调度处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次处理机调度与死锁处理
2、机调度与死锁运行就绪阻塞挂起阻塞挂起就绪创建退出进程调度中级调度作业调度调度的层次处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次3.1.1 高级调度v高级调度又称为作业调度、宏观调度或长程调度 （Long-Term Scheduling），有时也称作业调度 为接纳调度（Admission Scheduling）。v作业。包括程序、数据和JCB（作业控制快）v作业步。如编译、连结、运行。v作业控制块。保存了系统对作业进行管理和调度 所需的全部信息。处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次v作业调度 将外存作业调入内存，创建PCB等，插入就绪 队列。 一般用于批处理系统，
3、分/实时系统一般直接入 内存，无此环节。 v调度特性 1.接纳作业数（内存驻留数） 太多周转时间T长 太少系统效率低 2.接纳策略：即采用何种调度算法：FCFS、短 作业优先等处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次v批处理系统：需要作业调度v分时系统 ：不要作业调度v实时系统 ：不要作业调度处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次3.1.2 低级调度v通常也称为进程调度、微观调度或短程调度，进 程调度是最基本的一种调度，在三种OS中都有。进程调度可采用下述两种调度方式：v非抢占方式（Non-preemptive Mode） 优点：实现简单、系统开销小，适用于大
4、多 数的批处理OS 缺点：不适合实时系统。处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次v抢占方式（Preemptive Mode）抢占的原则有：优先权原则：优先权高的可以抢占优先级低的 进程的处理机。短作业（进程）优先原则：短作业（进程）可 以抢占长作业（进程）的处理机。时间片原则：各进程按时间片运行，一个时间 片用完时，停止该进程执行重新进行调度。处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次3.1.3 中级调度又称为交换调度或中程调度v为提高系统吞吐量和内存利用率而引入的内-外存对换功能（换出时，进程为挂起或就绪驻外状态 ）处理机调度与死锁处理机调度与死锁3.2 调度
5、的队列模型和调度准则3.1.2 调度队列模型一、仅有进程调度的队列模型在分时系统中就绪进程组织成FIFO队列形式， 按时间片轮转方式运行。处理机调度与死锁处理机调度与死锁每个进程在执行时可能出现下列三种情况：v任务在给定的时间片内已经完成，该进程便在释 放处理机后进入完成状态；v任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾；v在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。3.2 调度的队列模型和调度准则处理机调度与死锁处理机调度与死锁CPU进程i进程调度进程j进程k进程p就 绪 队 列时间片完进程f进程b进程n进程l阻 塞 队 列等待事件事件出现进程完成进程
6、X处理机调度与死锁处理机调度与死锁3.2 调度的队列模型和调度准则CPU就 绪 队 列时间片完进程调 度等待事件1进程完成后备队列等待事件2等待事件n事件1出现事件2出现事件n出现作业调度2、具有高、低两级调度的调度队列模型处理机调度与死锁处理机调度与死锁作业3作业2作业1作业调度进程2就绪队列 CPU阻 塞 队 列1阻 塞 队 列n阻 塞 队 列2进程调度等待事件1进程1等待事件2等待事件n事件1出现事件2出现事件n出现处理机调度与死锁处理机调度与死锁3.2 调度的队列模型和调度准则3、同时具有三级调度的调度队列模型CPU就 绪 队 列时间片完 进程调度进程完 成后备队列等待事件事件出现作业
7、调度批量作业交互型作业中级调度就绪、挂起队列事件出现阻 塞、挂 起 队 列挂起阻 塞 队 列挂起中级调度处理机调度与死锁处理机调度与死锁3.2 调度的队列模型和调度准则3.2.2 选择调度方式和调度算法的若干准则v面向用户的准则：周转时间短；（常用于批处理系统）响应时间快；（对交互性作业）截止时间的保证；（特别于实时系统）优先权准则：（即需要抢占调度）处理机调度与死锁处理机调度与死锁3.2 调度的队列模型和调度准则v面向系统的准则：1吞吐量高（特别于批处理）：单位时间完成作业数2处理机利用率好：（因CPU贵，特别于大中型多用户系统）3各类资源的平衡利用。（？折算标准）处理机调度与死锁处理机调度
8、与死锁3.3 调度算法v考虑因素（scheduling criteria）CPU利用率 ; (max)吞吐量 ; (max)周转时间 ; (min)响应时间 ; (min)系统开销 ; (min)处理机调度与死锁处理机调度与死锁3.3.1 先来先服务和短作业(进程)优先调度算法 1先来先服务（FCFS）调度算法vv作业调度：从后备作业队列中，选择一个或多个最作业调度：从后备作业队列中，选择一个或多个最 先进入该队列的作业，将它们调入内存运行；先进入该队列的作业，将它们调入内存运行；vv进程调度：就绪队列按进入的先后次序排列，调度进程调度：就绪队列按进入的先后次序排列，调度 时，选队首进程投入运
9、行。时，选队首进程投入运行。 处理机调度与死锁处理机调度与死锁A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510先来先服务FCFS周转时间带权周转时间101301.2306353.526.252.925处理机调度与死锁处理机调度与死锁2、短作业（进程）优先调度算法（SJ(P)F）v短作业优先SJF调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调 入内存运行。v短进程SPF优先调度算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它， 使它立即执行并一直执行到完成，或发生某事件 而被阻塞放弃处理机时，再
10、重新调度。处理机调度与死锁处理机调度与死锁A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510短作业优先SJ(P)F周转时间带权周转时间101451.85110117.51.2处理机调度与死锁处理机调度与死锁进程名ABCD平均就绪时间051015要求服务时间1025510先来先服务（ FCFS）周转时间1030303526.25带权周转时间11.263.52.925短进程优先 （SPF）周转时间104551017.5带权周转时间11.8111.2FCFS和SPF调度算法的性能比较处理机调度与死锁处理机调度与死锁作业情况调度算法进程名AB
11、CD 平均到达时间051025要求服务时间20503540FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间处理机调度与死锁处理机调度与死锁3.3.2 高优先权优先调度算法1. 优先权调度算法的类型 非抢占式优先权算法抢占式优先权调度算法处理机调度与死锁处理机调度与死锁2. 优先权的类型 1) 静态优先权 确定进程优先权的依据有如下三个方面：(1)进程类型。 (2) 进程对资源的需求。 (3) 用户要求。 处理机调度与死锁处理机调度与死锁A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510优先权0132高优先权优先(
12、静态)非抢占式优先权调度处理机调度与死锁处理机调度与死锁A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间1025510优先权0132抢占式优先权调度高优先权优先(静态)处理机调度与死锁处理机调度与死锁2) 动态优先权动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。 处理机调度与死锁处理机调度与死
13、锁进程名ABCD就绪时间051015要求服务时间1025510优先权0132非抢占式优先权调度 (优先权以速率0.2/5ms提高)1.21.4A0t1020503040BC515352545D高优先权优先(动态)处理机调度与死锁处理机调度与死锁3) 高响应比优先调度算法 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作 业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 处理机调度与死锁处理机调度与死锁3.3.3基于时间片的轮转调度算法v在分时系统中，为保证能及时响应用户的请求， 必须采用基于时间片的轮转式进程调度算法。在 早期，分时系统中采用的是简单的时间片
14、轮转法 ，进入90年代后，广泛采用多级反馈队列调度算法。处理机调度与死锁处理机调度与死锁3.3.3基于时间片的轮转调度算法1.时间片轮转v基本原理u将系统中所有的就绪进程按照FCFS原则，排成一 个队列。u每次调度时将CPU分派给队首进程，让其执行一 个时间片。时间片的长度从几个ms到几百ms。u在一个时间片结束时，发生时钟中断。调度程序 据此暂停当前进程的执行，将其送到就绪队列的 末尾，并通过上下文切换执行当前的队首进程。u进程可以未使用完一个时间片，就出让CPU（如 阻塞）。处理机调度与死锁处理机调度与死锁3.3.3基于时间片的轮转调度算法v时间片长度的确定u时间片长度变化的影响过长退化为
15、FCFS算法，进程在一个时间片内都执行完，响应时间长。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间 长。u对响应时间的要求： T(响应时间)=N(进程数目)*q(时间片)处理机调度与死锁处理机调度与死锁3.3.3基于时间片的轮转调度算法u时间片长度的影响因素： 就绪进程的数目：数目越多，时间片越小（当响应时间一定时） 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间、平 均周转时间和平均带权周转时间延长。处理机调度与死锁处理机调度与死锁A0t1020503040BC515352545D进程名ABCD就绪时间051015要求服务时间102551
16、0时间片轮转法RR时间片为5个单位时间处理机调度与死锁处理机调度与死锁3.3.3基于时间片的轮转调度算法2.多级反馈队列调度v实施过程如下：（1）应设置多个队列并为各个队列赋予不同的优先 级。第一个最高，依次降低。该算法赋予各个队 列中进程执行时间片的大小也不相同，优先权越 高，时间片越短。各个队列按照先进先出调度算 法 。处理机调度与死锁处理机调度与死锁3.3.3基于时间片的轮转调度算法最高优先权队列时间片I / O至CPUS1次高优先权队列时间片至CPUS2至CPUS3最低优先权队列时间片至CPUSn（时间片：S1处理机调度与死锁处理机调度与死锁v当发现进程死锁时，便应立即把它们从死锁状 态中解脱出来。常采用的方法是：剥夺资源。从其他进程剥夺足够数量的资源 给死锁进程以解除死锁状态。撤销进程。最简单的是让全部进程都死掉； 温和一点的是按照某种顺序逐个撤销进程， 直至有足够的资源可用，使死锁状态消除为 止。3.7.2 死锁的解除 处理机调
