处理机调度的基本概念

1、3.1 3.1 处理机调度的基本概念处理机调度的基本概念一、调度的层次一、调度的层次二、调度队列模型二、调度队列模型三、选择调度方式和算法的若干准则三、选择调度方式和算法的若干准则返回目录返回目录提交提交输入管理系统输入管理系统作业调度作业调度后备后备退出退出完成完成就绪就绪阻塞阻塞就绪就绪阻塞阻塞运行运行交换调度交换调度(中级调度中级调度)进程调度（线程调度）进程调度（线程调度）一、一、调度的层次调度的层次二、二、调度队列模型调度队列模型 在在OSOS中的任何一种调度中，都将涉及到进中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。程队列，由此形成了三种类型的调度队列

2、模型。1.1.仅有进程调度的调度队列模型仅有进程调度的调度队列模型2.2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型3.3.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型返回本节返回本节1 1、仅有进程调度的调度队列模型、仅有进程调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列进程调度进程调度时间片完时间片完CPU进程完成进程完成等待事件等待事件事事件件出出现现交互用户交互用户返回返回2 2、具有高级和低级调度的调度队列模型、具有高级和低级调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完后后备备队队列列进程调度进程

3、调度CPU进程完成进程完成事事件件出出现现等待事件等待事件1等待事件等待事件2等待事件等待事件n作业作业调度调度返回返回3 3、同时具有三级调度的调度队列模型、同时具有三级调度的调度队列模型就就 绪绪 队队 列列就就 绪绪 挂挂 起起 队队 列列时间片完时间片完阻阻 塞塞 队队 列列后后备备队队列列进程调度进程调度CPU进程完成进程完成事事件件出出现现等待事件等待事件作业作业调度调度阻阻 塞塞 挂挂 起起 队队 列列中程调度中程调度返回返回三、三、选择调度方式和算法的若干准则选择调度方式和算法的若干准则周转时间（常用于批处理系统）周转时间（常用于批处理系统）v 定义：作业从提交定义：作业从提交

4、 完成的时间完成的时间v 时间组成：时间组成：（1）驻外等待调度时间）驻外等待调度时间（2）驻内等待调度时间）驻内等待调度时间（3）执行时间）执行时间（4）阻塞时间）阻塞时间周转时间不具有周转时间不具有区分实际运行时区分实际运行时间长短的性质。间长短的性质。三、三、选择调度方式和算法的若干准则选择调度方式和算法的若干准则返回返回v平均周转时间平均周转时间v带权周转时间带权周转时间 （R：系统为它提供服务的时间）：系统为它提供服务的时间） v平均带权周转时间平均带权周转时间RTW 11niiTnT平均周转时间可以衡量平均周转时间可以衡量不同调度算法对相同任不同调度算法对相同任务流的调度性能。务流

5、的调度性能。带权周转时间衡量长短带权周转时间衡量长短任务的差别，故带权周任务的差别，故带权周转时间转时间W越小越好越小越好niniiiiRTnWnW1111三、三、选择调度方式和算法的若干准则选择调度方式和算法的若干准则返回返回u响应时间快（对交互性作业）响应时间快（对交互性作业）v 概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间v 时间组成时间组成（1）输入传送时间）输入传送时间（2）处理时间）处理时间（3）响应传送时间）响应传送时间u截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统）u优先权准则（即需要抢占调度）优先权准则（即需要抢占调度）3.3 3.3 调

6、度算法调度算法一、先来先服务（一、先来先服务（FCFS）调度算法）调度算法一、先来先服务（一、先来先服务（FCFS）调度算法）调度算法二、短作业二、短作业/ /进程优先调度算法进程优先调度算法三、时间片轮转调度算法三、时间片轮转调度算法Round RobinRound Robin 轮转法是一种基于时钟的抢占策略，以一个轮转法是一种基于时钟的抢占策略，以一个周期性间隔产生的时钟中断依次进行各个进程的周期性间隔产生的时钟中断依次进行各个进程的调度。调度。 当时钟中断发生时，当前正在运行的进程被当时钟中断发生时，当前正在运行的进程被置于就绪队列中，然后再基于置于就绪队列中，然后再基于FCFSFCFS

7、策略选择下一策略选择下一个就绪进程运行。个就绪进程运行。 它主要用于分时系统中。轮转法设计的问题它主要用于分时系统中。轮转法设计的问题是时间片的长度。是时间片的长度。nqTT 为系统响应时间为系统响应时间q 为时间片为时间片n 为就绪队列中进程数目。为就绪队列中进程数目。举例举例例：一个分时例：一个分时OS，10个终端，时间片个终端，时间片100ms，每，每个用户的请求进程要个用户的请求进程要300ms的时间处理，问终端的时间处理，问终端用户提出二次请求的时间间隔最少是多少？用户提出二次请求的时间间隔最少是多少？解：响应时间解：响应时间100ms101s，每个用户的请求，每个用户的请求要获得要

8、获得3个时间片才能处理完，要轮转个时间片才能处理完，要轮转3次，才能次，才能都处理完，所以终端用户的二次请求时间间隔最都处理完，所以终端用户的二次请求时间间隔最少应为少应为3s。三、时间片轮转调度算法三、时间片轮转调度算法RRRR注：注：保证了就绪队列中的所有进程在给定的时间内，保证了就绪队列中的所有进程在给定的时间内，均能获得一时间片来执行。均能获得一时间片来执行。若进程的执行时间少于时间片，则自愿释放若进程的执行时间少于时间片，则自愿释放CPUCPU。时间片将影响：时间片将影响：太长太长-FCFS-FCFS；太短太短-上下文切换频繁；上下文切换频繁；uHPF(Highest-Priorit

9、y-First)u需为每个进程设置一个由数字表示的优先数。需为每个进程设置一个由数字表示的优先数。u进程优先数的大小应与进程所对应事件的紧迫程度进程优先数的大小应与进程所对应事件的紧迫程度相对应。相对应。u当需要进行处理机分配时，系统在可运行的进程中当需要进行处理机分配时，系统在可运行的进程中选择优先数最高者使其投入运行。选择优先数最高者使其投入运行。u进程的优先数反映了进程运行的优先级别，故又将进程的优先数反映了进程运行的优先级别，故又将其称作优先级算法。其称作优先级算法。四、优先权调度算法（四、优先权调度算法（HPF）思考：优先数思考：优先数如何存放？如何存放？PCB（1）静态优先级）静态

10、优先级v优先权在创建进程时确定，且在进程的整个运行期优先权在创建进程时确定，且在进程的整个运行期间保持不变。一般用整数表示，小表示优先级高。间保持不变。一般用整数表示，小表示优先级高。v确定原则：确定原则：v进程类型（系统进程用户进程）进程类型（系统进程用户进程）v进程对资源的需求（要求少的优先权高）进程对资源的需求（要求少的优先权高）v用户要求（紧急程度和付费情况）用户要求（紧急程度和付费情况）v优点：优点：v缺点：缺点：优先权的类型优先权的类型简单、开销较少简单、开销较少公平性差（对低优先数进程）公平性差（对低优先数进程）优先权的类型优先权的类型（2）动态优先权）动态优先权v动态优先级在进

11、程的存在过程中不断发生变化。动态优先级在进程的存在过程中不断发生变化。v动态优先级的变化取决于：动态优先级的变化取决于：v进程的等待时间进程的等待时间v进程的运行时间进程的运行时间v进程使用资源的类型等进程使用资源的类型等v此优先数确定方法资源利用率高，公平性好，但此优先数确定方法资源利用率高，公平性好，但开销较大，实现较为复杂。开销较大，实现较为复杂。v最高响应比优先算法采用动态优先级。最高响应比优先算法采用动态优先级。四、优先四、优先权权调度算法调度算法( (续续) )非抢占式优先权算法：系统一旦把处理机分配给非抢占式优先权算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便

12、一直就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成或因发生某事件而放弃处理执行下去，直到完成或因发生某事件而放弃处理机时，系统方可重新分配处理机。机时，系统方可重新分配处理机。非抢占式优先非抢占式优先权权算法算法例例1 1EG1：进程进程到达时间到达时间 服务时间服务时间 优先数优先数 P1 0 7 3 P2 2 4 2 P3 4 1 4 P4 5 4 1u平均周转时间平均周转时间=(7-0)+(15-2)+(16-4)+(11-5)/4=9.5u平均等待时间平均等待时间=(0+9+11+2)/4 = 5.5P1P20 2 4 5 7 11 15 16P4P3优先数越小优先数越小

13、优先级越高优先级越高四、优先四、优先权权调度算法调度算法( (续续) )抢占式优先权算法：系统把处理机分配给就绪队抢占式优先权算法：系统把处理机分配给就绪队列中优先权最高的进程，使之执行。但在其执行列中优先权最高的进程，使之执行。但在其执行期间，只要出现了另一个优先权更高的进程，进期间，只要出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。处理机分配给新到的优先权最高的进程。抢占式优先权算法抢占式优先权算法例例2 2EG2：进程进程到达时间到达时间 服务时间服务时间 优先数优先数P10 7 3

14、 P22 4 2 P34 1 4 P45 4 1u平均周转时间平均周转时间=(15-0)+(10-2)+(16-4)+(9-5)/4=9.75u平均等待时间平均等待时间=(8+4+11+0)/4 = 5.75P1P20 2 4 5 9 10 15 16P4P3P2P1各种算法结果值的比较各种算法结果值的比较FCFSSJF-非非抢占式抢占式SJF-抢抢占式占式RR-4优先权优先权 -非抢非抢占式占式优先优先权权-抢抢占式占式平均平均周转周转时间时间8.75878.59.59.75平均平均等待等待时间时间4.75434.55.55.75返回进程进程到达时间到达时间服务时间服务时间 P107 P22

15、4 P341 P454SJF抢占抢占P1P3P242110P457P2P116u平均周转时间平均周转时间=(16-0)+(7-2)+(5-4)+(11-5)/4=7u平均等待时间平均等待时间=(11-2)+(5-4)+(4-4)+(7-5)/4 = 3五、高响应比优先权调度算法五、高响应比优先权调度算法HRPHRPv优先权的变化为优先权的变化为 PR要求服务时间响应时间要求服务时间要求服务时间等待时间优先权PR为响应比。为响应比。如等待时间相同如等待时间相同, ,则要求服务时间愈短则要求服务时间愈短, ,其优先权愈高其优先权愈高-SPF.-SPF.如要求服务时间相同如要求服务时间相同, ,优先

16、权决定于等待时间优先权决定于等待时间-FCFS-FCFS。对长作业对长作业, ,若等待时间足够长，优先权也高，也能获得若等待时间足够长，优先权也高，也能获得CPUCPU。算法算法HRPHRP示例示例 HRP 的调度性能的调度性能 WT作业作业到达时间到达时间T Tinin服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时间结束时间T Tc c =2.14=2.140 03 39 9151513133 39 9131320201515T TA A=3=3T TB B=7=7T TC C=9=9T TD D=14=14T TE E=7=7=8.00=8.008 83 36 64 45

17、 52 22 20 04 46 6ABCDE W WE E=3.50=3.50W WA A=1=1W WB B=1.17=1.17W WC C=2.25=2.25W WD D=2.80=2.80E EC CD DA AB B周转时间周转时间T=T=结束时间结束时间T Tc c- -到达时间到达时间T Tinin=3-0=3=3-0=3周转时间周转时间 T T带权周转时间带权周转时间W W= =周转时间周转时间T/T/服务时间服务时间T Tr r=3/3=1=3/3=1带权周转时带权周转时 间间W W平均平均=(9-4)+4/4=2.25=(9-6)+5/5=1.6=(9-8)+2/2=1.5R

18、CRDRERD=(13-6)+5/5=2.4RE=(13-8)+2/2=3.5五、高响应比优先权调度算法五、高响应比优先权调度算法HRPHRP不同调度算法对同一个不同调度算法对同一个 作业作业/ /进程的性能分析进程的性能分析: :作业作业到达时间到达时间T Tinin服务时间服务时间T Tr r从平均周转时间及从平均周转时间及其平均带权周转时其平均带权周转时间来看，间来看，HRP HRP 刚好刚好介于介于FCFSFCFS与与SJPSJP之之间，即好于间，即好于FCFSFCFS，次于次于SJPSJP。 A A0 03 3B B2 26 6C C4 44 4D D6 65 5E E8 82 2F

19、CFS8.602.56SJF7.601.84HRP8.002.14返回返回六、多级反馈队列调度算法六、多级反馈队列调度算法MFQMFQ就绪队列就绪队列1（8ms）就绪队列就绪队列2（16ms）就绪队列就绪队列3（32ms）就绪队列就绪队列n（FCFS）多级反馈队列调度多级反馈队列调度处 理处 理机机终止终止设置多个就绪队列，并为每个队列赋予不同的优先级。设置多个就绪队列，并为每个队列赋予不同的优先级。队列队列1 1的优先级最高，其余队列逐个降低。的优先级最高，其余队列逐个降低。每个队列中进程执行时间片的大小也各不相同，进程所每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其

20、相应的时间片就越短。在队列的优先级越高，其相应的时间片就越短。当一个新进程进入系统时，首先将它放入队列当一个新进程进入系统时，首先将它放入队列1 1的末尾，的末尾，按按FCFSFCFS等待调度。如能完成，便可准备撤离系统，反之由等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列调度程序将其转入队列2 2的末尾，按的末尾，按FCFSFCFS再次等待调度，如再次等待调度，如此下去，进入队列此下去，进入队列n n按按RRRR算法调度执行。算法调度执行。仅当队列仅当队列1 1为空时，才调度队列为空时，才调度队列2 2中的进程运行。若队列中的进程运行。若队列I I中的进程正执行，此时有新进

21、程进入优先级较高的队列中，中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行。则新进程将抢占运行。六、六、多级反馈队列调度算法多级反馈队列调度算法MFQMFQ六、六、多级反馈队列调度算法多级反馈队列调度算法MFQMFQ多级反馈队列算法有如下特点：多级反馈队列算法有如下特点：短优先。短优先。运算型进程有较长的时间片。运算型进程有较长的时间片。采用了动态优先级。采用了动态优先级。采用了可变时间片。采用了可变时间片。返回返回 算法算法比较项比较项FCFSFCFSRRRRSJFSJFHRPHRPMFQMFQ调度方式调度方式非抢占式非抢占式抢占式抢占式( (按时间片按时间片) )非抢占式非抢占式非抢占式非抢占式抢占