操作系统进程调度

1、Network Optimization Expert Team第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 Network Optimization Expert Team教学目的:u掌握优先级、吞吐量、死锁等基本概念掌握优先级、吞吐量、死锁等基本概念

2、u熟练掌握处理机的各种调度算法熟练掌握处理机的各种调度算法u掌握死锁产生原因和必要条件掌握死锁产生原因和必要条件u熟练掌握用银行家算法来避免死锁的方法熟练掌握用银行家算法来避免死锁的方法u掌握死锁的检测和解除方法掌握死锁的检测和解除方法重点与难点：u处理机的各种调度算法处理机的各种调度算法u银行家算法银行家算法u死锁的解除方法死锁的解除方法Network Optimization Expert Team3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度 3.1.2 3.1.2 调度队列模型调度队列模型3.1.3 3.1.3

3、 选择调度方式和调度算法的若干原则选择调度方式和调度算法的若干原则Network Optimization Expert Team1. 高级调度：高级调度：u 又称为又称为作业调度作业调度或或长程调度长程调度。u 用于决定把后备队列中的用于决定把后备队列中的哪些哪些作业调入内存，为作业调入内存，为它们创建进程、分配必要的资源，再将新创建的它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。进程排在就绪队列上，准备执行。u 在批处理系统中，大多配有作业调度，但在分时在批处理系统中，大多配有作业调度，但在分时和实时系统中，却往往不配置作业调度。作业调和实时系统中，却往往不配置作

4、业调度。作业调度的运行频率较低，通常为几分钟一次。度的运行频率较低，通常为几分钟一次。3.1.1 高级、中级和低级调度高级、中级和低级调度调度的类型调度的类型Network Optimization Expert Team执行作业调度时，需要解决：执行作业调度时，需要解决：（1）一次接纳多少作业：即允许多少个作业同时在一次接纳多少作业：即允许多少个作业同时在内存中运行。内存中运行。（2）接纳哪些作业：即哪些作业调入内存，取决于接纳哪些作业：即哪些作业调入内存，取决于所采用的算法。所采用的算法。 比如先来先服务调度算法；或者是短作业优先比如先来先服务调度算法；或者是短作业优先调度算法；还有基于作

5、业优先权的调度算法，响应调度算法；还有基于作业优先权的调度算法，响应比高者优先调度算法等。比高者优先调度算法等。Network Optimization Expert Team2. 2. 低级调度：低级调度：u 又称为又称为进程调度进程调度、短程调度短程调度。u 用于决定就绪队列中的用于决定就绪队列中的哪个哪个进程能获得处理器进程能获得处理器, , 并将处理机分配给该进程。并将处理机分配给该进程。u 进程调度程序是操作系统最为核心的部分，进进程调度程序是操作系统最为核心的部分，进程调度策略的优劣直接影响到整个系统的性能。程调度策略的优劣直接影响到整个系统的性能。u 三种类型的操作系统中，都必须

6、配置此级调度。三种类型的操作系统中，都必须配置此级调度。Network Optimization Expert Team低级调度方式分两类：低级调度方式分两类：(1) (1) 非抢占方式非抢占方式 一旦把处理机分配给某个进程后，让该进程一一旦把处理机分配给某个进程后，让该进程一直执行，直到该进程完成或者发生某事件而阻塞。直执行，直到该进程完成或者发生某事件而阻塞。引起进程调度的因素：引起进程调度的因素：u 正在执行的进程执行完毕；正在执行的进程执行完毕；u 执行中的进程因为提出执行中的进程因为提出I/OI/O请求而暂停执行；请求而暂停执行；u 进程通信或同步过程中执行了原语操作。进程通信或同步

7、过程中执行了原语操作。Network Optimization Expert Team(2) (2) 抢占方式抢占方式 当一进程正在处理机上执行时，系统可根据某当一进程正在处理机上执行时，系统可根据某种原则暂停它的执行，并将已分配给它的处理机重种原则暂停它的执行，并将已分配给它的处理机重新分配给另一个进程。新分配给另一个进程。抢占的原则有：抢占的原则有：u 优先权原则：优先权原则：就绪的高优先权进程有权抢占低优就绪的高优先权进程有权抢占低优先权进程的先权进程的 CPUCPU。 u 就绪的短作业就绪的短作业( (进程进程) )有权抢占有权抢占长作业长作业( (进程进程) )的的 CPUCPU。

8、u 时间片原则：时间片原则：一个时间片用完后，系统重新进行一个时间片用完后，系统重新进行进程调度。进程调度。 Network Optimization Expert Team3. 3. 中级调度中级调度u 又称又称平衡负载调度平衡负载调度、中程调度中程调度。u 目的是为了提高内存利用率和系统吞吐量。目的是为了提高内存利用率和系统吞吐量。u 实质是进程的内外存对换功能：将外存中已实质是进程的内外存对换功能：将外存中已具备运行条件的进程换入内存，而将内存中处于具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。阻塞状态的某些进程换出至外存。 在三种调度中，进程调度的运行频率最高

9、，在三种调度中，进程调度的运行频率最高，作业调度的周期较长，中级调度的运行频率在上作业调度的周期较长，中级调度的运行频率在上述两者之间。述两者之间。Network Optimization Expert Team三级调度之间的关系三级调度之间的关系Network Optimization Expert Team3.1.2 调度队列模型调度队列模型 根据根据os中所引入的调度的类型，形成了三种类中所引入的调度的类型，形成了三种类型的调度队列模型：型的调度队列模型：u 仅有进程调度的调度队列模型；仅有进程调度的调度队列模型；u 具有高级和低级调度的调度队列模型；具有高级和低级调度的调度队列模型；u

10、 同时具有三级调度的调度队列模型。同时具有三级调度的调度队列模型。Network Optimization Expert Team1. 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 Network Optimization Expert Team2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 就就 绪绪 队队 列列进程调度进程调度CPUCPU进程完成进程完成等待事件等待事件 1 1作业作业调度调度事件事件1 1出现出现时间片完时间片完等待事件等待事件 2 2事件事件2 2出现出现等待事件等待事件 n n事件事件n n出现出现后后 备备 队队列列Network

11、 Optimization Expert Team3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 就绪队列就绪队列进程调度进程调度CPUCPU就绪，挂起队列就绪，挂起队列中级调度中级调度阻塞，挂起队列阻塞，挂起队列阻塞队列阻塞队列等待事件等待事件进程完成进程完成时间片完时间片完作业调度作业调度交互型作业交互型作业后备队列后备队列批量作业批量作业挂起挂起事件出现事件出现事事件件出出现现Network Optimization Expert Team3.1.3 选择调度方式和调度算法的若干原则选择调度方式和调度算法的若干原则1. 面向用户的准则面向用户的准则(1) 周转时间短周

12、转时间短u 作业周转时间作业周转时间：作业提交计算机到作业完成为止的：作业提交计算机到作业完成为止的时间间隔。它是作业在系统里的等待时间与运行时时间间隔。它是作业在系统里的等待时间与运行时间之和。间之和。u 平均作业周转时间平均作业周转时间：u 带权周转时间：带权周转时间： W=T /Tsu u 平均作业带权周转时间：平均作业带权周转时间：u 主要用于评价批处理系统。主要用于评价批处理系统。iiiTnT11niSiiTTnW11T :作业的周转时作业的周转时间，间， Ts :作业的运作业的运行时间。行时间。Network Optimization Expert Team (2) 响应时间快响应

13、时间快 从用户通过键盘提交一个请求到系统首次产生从用户通过键盘提交一个请求到系统首次产生响应之间的时间间隔称响应之间的时间间隔称响应时间响应时间。 主要用于评价分时系统。主要用于评价分时系统。 (3) 截止时间的保证截止时间的保证 任务必须开始执行的最迟时间或必须完成的最任务必须开始执行的最迟时间或必须完成的最迟时间称迟时间称截止时间截止时间。 主要用于评价实时系统。主要用于评价实时系统。 (4) 优先权准则优先权准则 在三种在三种OS中，都可遵循。中，都可遵循。Network Optimization Expert Team2. 面向系统的准则面向系统的准则(1)系统吞吐量高系统吞吐量高 吞

14、吐量吞吐量:单位时间内系统所完成的作业数。单位时间内系统所完成的作业数。(2) 处理机利用率好处理机利用率好 CPU总的运行时间总的运行时间=CPU有效工作时间有效工作时间 +CPU空闲等待时间空闲等待时间 CPU利用率利用率=CPU有效工作时间有效工作时间 /CPU总的运行时间总的运行时间(3) 各类资源的平衡利用各类资源的平衡利用Network Optimization Expert Team3.2 3.2 调度算法调度算法3.2.1 3.2.1 先来先服务和短作业优先调度算法先来先服务和短作业优先调度算法3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法3.2.3 3.2.

15、3 基于时间片轮转调度算法基于时间片轮转调度算法Network Optimization Expert Team调度算法的概念调度算法的概念:u根据系统的资源分配策略所规定的资源分配算法根据系统的资源分配策略所规定的资源分配算法称为称为调度算法调度算法。u通常将作业或进程归入各种就绪或阻塞队列。有通常将作业或进程归入各种就绪或阻塞队列。有的算法适用于作业调度，有的算法适用于进程调的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。度，有的两者都适应。Network Optimization Expert Team3.2.1 先来先服务和短作业优先调度算法先来先服务和短作业优先调度算法

16、u最简单的调度算法。最简单的调度算法。u用于作业调度时：用于作业调度时：按照作业进入系统的先后次序按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。来挑选作业，先进入系统的作业优先被挑选。u用于进程调度时用于进程调度时按照进程就绪的先后次序来调按照进程就绪的先后次序来调度进程。度进程。u算法特点：算法特点：容易实现，效率不高，只顾及作业等容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。于短作业而优待了长作业。1. 先来先服务调度算法（先来先服务调度算法（FCFS）Network Opti

17、mization Expert Team例：例：在单道环境下，某批处理显然有四道作业，已在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：知他们的进入系统的时刻、估计运算时间如下：作业作业进入时刻进入时刻(h)(h)运行时间运行时间(h)(h)A AB BC CD D0 01 12 23 31 11001001 1100100 用用FCFSFCFS算法计算作业的运行情况、平均周转时间和算法计算作业的运行情况、平均周转时间和平均带权周转时间：平均带权周转时间：Network Optimization Expert Team作业作业进入时刻进入时刻运行时间运行时间开

18、始时刻开始时刻完成时刻完成时刻 周转时间周转时间带权周转带权周转时间时间ABCD0123110011000110110211011022021100100199111001.99平均周转时间平均周转时间T100（h）平均带权周转时间平均带权周转时间T26.00（h）Network Optimization Expert Team2. 短作业短作业(进程进程)优先调度算法（优先调度算法（SJF/ SPF）u用于作业调度时：用于作业调度时： SJFSJF调度算法。以进入系统的作调度算法。以进入系统的作业所要求的业所要求的CPUCPU时间为标准，总选取估计计算时间时间为标准，总选取估计计算时间最短的

19、作业投入运行。最短的作业投入运行。u用于进程调度时：用于进程调度时： SPF调度调度算法。从就绪队列中选算法。从就绪队列中选出估计运行时间最短的进程，将处理机分配给它。出估计运行时间最短的进程，将处理机分配给它。u算法特点：算法特点：易于实现，能有效降低作业的平均等待易于实现，能有效降低作业的平均等待时间。缺点是时间。缺点是：对长作业不利，有可能导致长作业对长作业不利，有可能导致长作业（进程）长期不被调度；（进程）长期不被调度；未能依据作业的紧迫程度未能依据作业的紧迫程度来划分执行的优先级来划分执行的优先级；难以准确估计作业（进程）难以准确估计作业（进程）的执行时间，从而影响调度性能。的执行时

20、间，从而影响调度性能。Network Optimization Expert Team例：例：在单道环境下，某批处理显然有四道作业，已在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：知他们的进入系统的时刻、估计运算时间如下：作业作业进入时刻进入时刻(h)(h)运行时间运行时间(h)(h)A AB BC CD D0 01 12 23 31 11001001 1100100 用用SJF/SPFSJF/SPF算法计算作业的运行情况、平均周转时算法计算作业的运行情况、平均周转时间和平均带权周转时间：间和平均带权周转时间：Network Optimization Exp

21、ert Team作业作业进入时刻进入时刻运行时间运行时间开始时刻开始时刻完成时刻完成时刻 周转时间周转时间带权周转带权周转时间时间ABCD0123110011000110110211011022021100100199111001.99平均周转时间平均周转时间T100（h）平均带权周转时间平均带权周转时间T26.00（h） 思考：思考：如果如果A A、B B、C C、D D四个作业四个作业同时到达，那么它们的运行情况同时到达，那么它们的运行情况如何？试计算并比较。如何？试计算并比较。Network Optimization Expert TeamFCFS与与SJF的比较的比较 作业情作业情 况

22、况调度算法调度算法进程名进程名A B C D E平平均均到达时间到达时间0 1 2 3 4服务时间服务时间4 3 5 2 4 计算下面各个进程的完成时间、周转时间、带计算下面各个进程的完成时间、周转时间、带权周转时间，并比较两种算法的优劣。权周转时间，并比较两种算法的优劣。Network Optimization Expert TeamFCFS与与SJF的比较的比较 作业情作业情 况况调度算法调度算法进程名进程名A B C D E平均平均到达时间到达时间0 1 2 3 4服务时间服务时间4 3 5 2 4FCFS（a）完成时间完成时间4 7 12 14 18周转时间周转时间4 6 10 11

23、149带权周转时带权周转时间间1 2 2 5.5 3.5 2.8SJF（b）完成时间完成时间4 9 18 6 13周转时间周转时间4 8 16 3 98带权周转时带权周转时间间1 2.67 3.1 1.5 2.252.1Network Optimization Expert Team3.2.2 高优先权优先调度算法高优先权优先调度算法系统将从后备队列中选择若系统将从后备队列中选择若干个优先权最高的作业装入内存。干个优先权最高的作业装入内存。该算法把处理机分配给就绪该算法把处理机分配给就绪队列中优先权最高的进程。队列中优先权最高的进程。非抢占式优先权算法非抢占式优先权算法抢占式优先权调度算法抢占

24、式优先权调度算法非抢占式优先权算法：一旦将非抢占式优先权算法：一旦将CPUCPU分配给分配给优先权最高的进程，该进程就一直执行下优先权最高的进程，该进程就一直执行下去，直至完成或发生某个事件。去，直至完成或发生某个事件。抢占式优先权算法：要进行优先权的比较抢占式优先权算法：要进行优先权的比较，高优先权可以进程可以通过调度程序立，高优先权可以进程可以通过调度程序立即停止当前进程，使得即停止当前进程，使得CPUCPU重新分配。重新分配。Network Optimization Expert Team优先权的类型：优先权的类型：u 静态优先权静态优先权 在创建进程时确定的，且在进程的整个运行期间保在

25、创建进程时确定的，且在进程的整个运行期间保持不变。持不变。 静态优先权法简单易行，但随着进程的推进，其优静态优先权法简单易行，但随着进程的推进，其优先权可能与进程的情况不再相符。先权可能与进程的情况不再相符。 u 动态优先权动态优先权 在创建进程时所确定的优先权，可以随着进程的推在创建进程时所确定的优先权，可以随着进程的推进而改变。进而改变。 例如：例如：可以规定就绪进程的优先权随着等待时间的可以规定就绪进程的优先权随着等待时间的增长以速度增长以速度 a 增加；正在执行进程的优先权以速度增加；正在执行进程的优先权以速度 b 下降，这样便可防止一个长作业长期垄断处理机。下降，这样便可防止一个长作

26、业长期垄断处理机。Network Optimization Expert Teamu HRRF实际上是一种实际上是一种动态优先权动态优先权调度算法。调度算法。u FCFS与与SJF/SPF是片面的调度算法。是片面的调度算法。FCFS只考只考虑作业等候时间而忽视了作业的计算时间，虑作业等候时间而忽视了作业的计算时间，SJF /SPF只考虑用户估计的作业计算时间而忽视了作业只考虑用户估计的作业计算时间而忽视了作业等待时间。等待时间。u HRRF是介乎这两者之间的折衷算法，既考虑作是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业等待时间，又考虑作业的运行时间，既照顾

27、短作业又不使长作业的等待时间过长，改进了调度性能。业又不使长作业的等待时间过长，改进了调度性能。但每次调度前，都要进行响应比的计算，会增加系但每次调度前，都要进行响应比的计算，会增加系统开销。统开销。3. 高响应比优先调度算法（高响应比优先调度算法（HRRF） ：Network Optimization Expert Team要求服务时间要求服务时间要求服务时间要求服务时间等待时间等待时间优先权优先权+ + 优先权的变化规律可描述为：优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比业的响应时间

28、，故该优先权又相当于响应比RP。据此，又可表示为：据此，又可表示为： 要求服务时间要求服务时间响应时间响应时间要求服务时间要求服务时间要求服务时间要求服务时间等待时间等待时间RP + + Network Optimization Expert Teamu 如果等待时间相同，短作业容易得到较高优先如果等待时间相同，短作业容易得到较高优先权。权。 u 长作业等待时间足够长后，也将获得足够高的长作业等待时间足够长后，也将获得足够高的优先级。优先级。u 如果要求服务时间相同时，作业的优先权决定如果要求服务时间相同时，作业的优先权决定于其等待时间，实现的是先来先服务。于其等待时间，实现的是先来先服务。N

29、etwork Optimization Expert Team例如：例如：以下四个作业先后到达系统进入调度：以下四个作业先后到达系统进入调度： 作业名作业名 到达时间到达时间 所需所需CPUCPU时间时间 作业作业1 01 0 20 20 作业作业2 52 5 15 15 作业作业3 10 53 10 5 作业作业4 154 15 10 10Network Optimization Expert Teamu FCFSFCFS调度算法：调度算法：平均作业周转时间平均作业周转时间 T = (20+30+30+35)/4 = 28.75T = (20+30+30+35)/4 = 28.75平均带权作

30、业周转时间平均带权作业周转时间 W = W = (20/20+30/15+30/5+35/10)/4 = 3.13(20/20+30/15+30/5+35/10)/4 = 3.13u SJFSJF调度算法：调度算法：调度顺序为作业调度顺序为作业1 1、3 3、4 4、2 2，平均作业周转时间平均作业周转时间 T=(20+15+20+45)/4 =25T=(20+15+20+45)/4 =25平均带权作业周转时间平均带权作业周转时间 W = W = (20/20+15/5+25/10+45/15)/4 = 2.25(20/20+15/5+25/10+45/15)/4 = 2.25Network

31、Optimization Expert Teamu 高响应比调度算法：高响应比调度算法：1)1) 开始只有作业开始只有作业1 1，被选中执行时间，被选中执行时间2020；2)2) 作业作业1 1执行完毕，响应比依次为执行完毕，响应比依次为1+15/151+15/15、1+10/51+10/5、1+5/101+5/10，作业，作业3 3被选中，执行时间被选中，执行时间5 5；3)3) 作业作业3 3执行完毕，响应比依次为执行完毕，响应比依次为1+20/151+20/15、1+10/101+10/10，作业，作业2 2被选中，执行时间被选中，执行时间1515；4)4) 作业作业2 2执行完毕，作业

32、执行完毕，作业4 4被选中，执行时间被选中，执行时间1010；平均作业周转时间平均作业周转时间T = (20+15+35+35)/4 = 26.25T = (20+15+35+35)/4 = 26.25平均带权作业周转时间平均带权作业周转时间W = W = (20/20+15/5+35/15+35/10)/4 = 2.42(20/20+15/5+35/15+35/10)/4 = 2.42Network Optimization Expert Team3.2.3 基于时间片轮转调度算法基于时间片轮转调度算法u把把CPUCPU划分成若干时间片划分成若干时间片, ,并且按顺序赋给就绪队并且按顺序赋给

33、就绪队列中的每一个进程，进程轮流占有列中的每一个进程，进程轮流占有CPUCPU，当时间，当时间片用完时，即使进程未执行完毕，系统也剥夺该片用完时，即使进程未执行完毕，系统也剥夺该进程的进程的CPUCPU，将该进程排在就绪队列末尾。同时，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。系统选择另一个进程运行。u时间片长度的选取非常重要，时间片长度的选择时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间。会直接影响系统开销和响应时间。1. 时间片轮转法（时间片轮转法（RR）Network Optimization Expert Team简单轮转法调度模型简单轮转法调度模型

34、Network Optimization Expert Team轮转法中时间片大小的影响轮转法中时间片大小的影响Network Optimization Expert Team2. 多级反馈队列调度算法（多级反馈队列调度算法（FB）u将就绪队列分为将就绪队列分为N N级，每个就绪队列分配给不同的级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越长，级别越小，时间片，队列级别越高，时间片越长，级别越小，时间片越短；时间片越短；u新进程进入内存后，放入第一队列末尾，按新进程进入内存后，放入第一队列末尾，按FCFSFCFS原原则等待调度，如果在一个时间片结束时没完成，将则等待调度，如果在一个

35、时间片结束时没完成，将该进程转入第二队列末尾重新等待调度执行该进程转入第二队列末尾重新等待调度执行如如此下去，当一个长作业从第一级队列降到最后一级此下去，当一个长作业从第一级队列降到最后一级队列时，便在该队列中采取时间片轮转方式运行。队列时，便在该队列中采取时间片轮转方式运行。Network Optimization Expert Teamu仅当第一队列空闲时，调度程序才调度第二队列仅当第一队列空闲时，调度程序才调度第二队列中的进程运行中的进程运行类推之，仅当第类推之，仅当第 1 1(i-1)(i-1)级队级队列均空时，才调度第列均空时，才调度第 i i 级队列上的进程执行。级队列上的进程执行

36、。u如果处理机正在为某队列的进程服务，又有新进如果处理机正在为某队列的进程服务，又有新进程插入到较高优先级的队列中，则新进程将抢占程插入到较高优先级的队列中，则新进程将抢占正在运行进程的处理机。正在运行进程的处理机。Network Optimization Expert Team多级反馈队列调度算法多级反馈队列调度算法Network Optimization Expert Team多级反馈队列调度算法性能：多级反馈队列调度算法性能： 较好的性能，能够较好地满足各种类型用户的较好的性能，能够较好地满足各种类型用户的需要。需要。u 终端型作业用户终端型作业用户u 短批处理作业用户短批处理作业用户u

37、 长批处理作业用户长批处理作业用户Network Optimization Expert Team补充练习补充练习进程名进程名到达时间到达时间服务时间服务时间A03B26C44D65E82Network Optimization Expert Team补充练习补充练习分别用以下调度算法：分别用以下调度算法：先来先服务（先来先服务（FCFSFCFS）非抢占短进程优先（非抢占短进程优先（SPFSPF）抢占的短进程优先（抢占的短进程优先（SPFSPF）高响应比优先（高响应比优先（HRNHRN）时间片轮转（时间片轮转（RRRR，时间片，时间片=1=1）分别分别计算计算出各进程的出各进程的完成时间完成时

38、间、周转时间周转时间、带权带权周转时间周转时间、平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间。Network Optimization Expert Team3.3 3.3 实实 时时 调调 度度 3.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类3.3.3 3.3.3 常用的两种实时调度算法常用的两种实时调度算法Network Optimization Expert Team1. 实时调度实时调度 根据实时系统的特点，对实时系统中的调度根据实时系统的特点，对实时系统中的调度有特殊的要求，故引入一种新

39、的调度方式有特殊的要求，故引入一种新的调度方式实实时调度时调度。3.3.1 实现实时调度的基本条件实现实时调度的基本条件思考：实时系统的特点是什么思考：实时系统的特点是什么Network Optimization Expert Team2. 实时系统的特点实时系统的特点u 有限等待时间（决定性）有限等待时间（决定性）u 有限响应时间有限响应时间u 用户控制用户控制u 可靠性高可靠性高u 系统出错处理能力强系统出错处理能力强Network Optimization Expert Team3. 实现实时调度的基本条件实现实时调度的基本条件u 提供必要的信息提供必要的信息u 如：就绪时间、开始或完成

40、截止时间、处理如：就绪时间、开始或完成截止时间、处理时间、资源要求、绝对或相对优先级（硬实时或时间、资源要求、绝对或相对优先级（硬实时或软实时）软实时）u 系统处理能力强系统处理能力强u 采用抢占式调度机制采用抢占式调度机制u 具有快速切换机制具有快速切换机制 对外部中断的快速响应能力、快速的任务分派对外部中断的快速响应能力、快速的任务分派能力能力Network Optimization Expert Team3.3.2 实时调度算法的分类实时调度算法的分类u根据时实任务性质，分为：根据时实任务性质，分为：硬实时调度算法硬实时调度算法软实时调度算法软实时调度算法u根据调度方式，分为（根据调度方

41、式，分为（）：）：非抢占式调度算法非抢占式调度算法抢占式调度算法抢占式调度算法u根据调度程序调度时间，分为：根据调度程序调度时间，分为：静态调度算法静态调度算法动态调度算法动态调度算法u在多处理机环境下，分为：在多处理机环境下，分为：集中式调度算法集中式调度算法分布式调度算法分布式调度算法Network Optimization Expert Team1. 非抢占式调度算法非抢占式调度算法u非抢占式轮转调度算法非抢占式轮转调度算法 将实时任务排成轮转队列，调度程序每次选将实时任务排成轮转队列，调度程序每次选择队列中的第一个任务运行，当任务自我终止或择队列中的第一个任务运行，当任务自我终止或运行

42、完成后，此时调度程序选择下一个队首任务运行完成后，此时调度程序选择下一个队首任务运行；未完成的任务被挂在轮转队列的队尾。运行；未完成的任务被挂在轮转队列的队尾。 用于要求不太严格的实时控制系统。用于要求不太严格的实时控制系统。u非抢占式优先调度算法非抢占式优先调度算法 在就绪队列中，优先级高的任务位于队首，在就绪队列中，优先级高的任务位于队首，当任务自我终止或运行完成后，调度程序选择下当任务自我终止或运行完成后，调度程序选择下一个队首任务运行。一个队首任务运行。 用于有一定要求的实时控制系统。用于有一定要求的实时控制系统。Network Optimization Expert Team2. 抢

43、占式调度算法抢占式调度算法u基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法 当新到来的实时任务的优先级高于当前任当新到来的实时任务的优先级高于当前任务，则等到时钟中断到来时，调度程序剥夺当前务，则等到时钟中断到来时，调度程序剥夺当前任务的执行，将处理机分配给新到的高优先权任任务的执行，将处理机分配给新到的高优先权任务。务。 用于大多数的实时系统。用于大多数的实时系统。u立即抢占的优先权调度算法立即抢占的优先权调度算法 操作系统能快速相应外部时间中断，一旦出操作系统能快速相应外部时间中断，一旦出现外部中断，只要当前任务未处于临界区，便立现外部中断，只要当前任务未处于临界区，

44、便立即剥夺当前任务的执行，将处理机分配给请求中即剥夺当前任务的执行，将处理机分配给请求中断的紧迫任务。断的紧迫任务。 用于实时要求比较严格的实时控制系统。用于实时要求比较严格的实时控制系统。Network Optimization Expert Team进程，并立即执行进程，并立即执行(a) 非抢占轮转调度非抢占轮转调度当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度实时进程抢占当前实时进程抢占当前(d) 立即抢占的优先权调度立即抢占的优先权调度调度时间调度时间进程进程 1进程进程 2实时进程要求调度实时进程要求调度进程进程 n实时进程实时进程调度实时进程运行调度实时进程运行(

45、b) 非抢占优先权调度非抢占优先权调度当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度当前进程运行完成当前进程运行完成调度时间调度时间当前进程当前进程实时进程请求调度实时进程请求调度 时钟中断到来时时钟中断到来时调度调度时间时间(c) 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度调度调度时间时间实时进程实时进程 实时进程调度比较图实时进程调度比较图响应时间：数秒至数十秒响应时间：数秒至数十秒响应时间：几十毫秒至几毫秒响应时间：几十毫秒至几毫秒响应时间：数秒至数百毫秒响应时间：数秒至数百毫秒响应时间：几百毫秒至几毫秒响应时间：几百毫秒至几毫秒Network O

46、ptimization Expert Team3.3.3 常用的两种实时调度算法常用的两种实时调度算法1. 最早截止时间优先算法（即最早截止时间优先算法（即EDF算法）算法） 根据任务的根据任务的开始截止时间开始截止时间来确定任务的优先来确定任务的优先级。该调度算法首先运行队首进程，即开始截止级。该调度算法首先运行队首进程，即开始截止时间最近的那个进程。时间最近的那个进程。 算法即可采用算法即可采用非抢占调度方式非抢占调度方式，也可采用，也可采用抢抢占调度方式占调度方式。Network Optimization Expert Team134212 34开始截止时间开始截止时间执行任务执行任务任

47、务到达任务到达t1342例：例：非抢占调度方式下的非抢占调度方式下的EDF算法。算法。Network Optimization Expert Team2. 最低松弛度优先算法（即最低松弛度优先算法（即LLF算法）算法） 根据任务的根据任务的紧迫程度紧迫程度（或松弛程度）来确定（或松弛程度）来确定任务的优先级。松弛度最低的任务排在就绪队列任务的优先级。松弛度最低的任务排在就绪队列的最前面，调度程序总是选择队列中的首任务执的最前面，调度程序总是选择队列中的首任务执行。行。 算法主要用于算法主要用于可抢占调度方式可抢占调度方式中。中。 松弛度松弛度=必须完成时间必须完成时间 - 其本身的运行时间其本

48、身的运行时间 - 当前时间当前时间Network Optimization Expert Team 例：例：如果系统中有两个周期性的实时任务如果系统中有两个周期性的实时任务A和和B： 任务任务A要求每要求每20ms执行一次，执行时间为执行一次，执行时间为10ms； 任务任务B要求每要求每50ms执行一次，执行时间为执行一次，执行时间为25ms； 任务任务A和和B每次必须完成的时间分别为每次必须完成的时间分别为A1、A2、A3和和B1、B2、B3见图。见图。Network Optimization Expert Team调度情况：调度情况：tNetwork Optimization Expert

49、 Team3.4 3.4 多处理机系统中的调度多处理机系统中的调度3.4.1 3.4.1 多处理机系统的类型多处理机系统的类型3.4.2 3.4.2 进程分配方式进程分配方式3.4.3 3.4.3 进程进程( (线程线程) )调度方式调度方式Network Optimization Expert Team多处理机系统简介多处理机系统简介uMPS，MultiProcessor Systemu20世纪世纪70年代出现年代出现u多处理机系统：多处理机系统：是一个具有两个或多个处理机并是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的能相互进行通信以协同一个大的给定问题求解的计算机

50、系统。计算机系统。Network Optimization Expert Team3.4.1 多处理机系统的类型多处理机系统的类型u根据多处理器之间耦合的紧密程度，分为根据多处理器之间耦合的紧密程度，分为紧密耦合紧密耦合MPSMPS松散耦合松散耦合MPSMPSu根据系统中所用处理器的相同与否，分为根据系统中所用处理器的相同与否，分为对称多处理器系统对称多处理器系统SMPSSMPS非对称多处理器系统非对称多处理器系统Network Optimization Expert Team3.4.2 进程分配方式进程分配方式1. 对称式多处理系统中的进程分配方式：对称式多处理系统中的进程分配方式：u静态分

51、配方式静态分配方式 每个每个CPU设立一个就绪队列，进程从开始执行到完成，设立一个就绪队列，进程从开始执行到完成，都在同一个都在同一个CPU上。上。优点：优点：调度算法开销小。调度算法开销小。缺点：缺点：容易出现处理机忙闲不均。容易出现处理机忙闲不均。u动态分配方式动态分配方式 各个各个CPU采用一个公共就绪队列，队首进程每次分派采用一个公共就绪队列，队首进程每次分派到当前空闲的到当前空闲的CPU上执行。上执行。 优点：优点：消除个处理机忙闲不均的现象。消除个处理机忙闲不均的现象。 缺点：缺点：对松散耦合系统，会增加调度开销。对松散耦合系统，会增加调度开销。Network Optimizati

52、on Expert Team2. 非对称式多处理系统中的进程分配方式非对称式多处理系统中的进程分配方式 主从处理机系统。操作系统核心驻留在主主从处理机系统。操作系统核心驻留在主机上，由主处理机执行调度，从机上只是用户程序；机上，由主处理机执行调度，从机上只是用户程序；主机管理一个公共就绪队列，并分派进程给从处理主机管理一个公共就绪队列，并分派进程给从处理机执行；各个处理机有固定分工，如执行机执行；各个处理机有固定分工，如执行OSOS的系统的系统功能，功能，I/OI/O处理，应用程序。处理，应用程序。系统处理较简单。系统处理较简单。存在不可靠性。当主机太忙时，会出现存在不可靠性。当主机太忙时，会

53、出现系统瓶颈；当主机出现故障时，会导致整个系统瘫系统瓶颈；当主机出现故障时，会导致整个系统瘫痪。痪。利用多台处理机（而非一台）来管利用多台处理机（而非一台）来管理整个系统。理整个系统。Network Optimization Expert Teamu注重整体运行效率（而不是个别处理机的利用注重整体运行效率（而不是个别处理机的利用率）。率）。u更多样的调度算法。更多样的调度算法。u多处理机访问多处理机访问OS数据结构时的互斥（对于共享数据结构时的互斥（对于共享内存系统）。内存系统）。u调度单位广泛采用线程。调度单位广泛采用线程。3. 多处理机调度与单处理机调度的区多处理机调度与单处理机调度的区别

54、别Network Optimization Expert Team3.4.3 进程进程(线程线程)调度方式调度方式u 指在系统中设置一个公用的进程指在系统中设置一个公用的进程(或线程或线程)队列，队列，所有的处理器在空闲时，都可自己到该队列中取一所有的处理器在空闲时，都可自己到该队列中取一进程进程(或线程或线程)来执行。来执行。u 是最简单、最常用的调度方式，采用单处理机是最简单、最常用的调度方式，采用单处理机环境下的调度方式。环境下的调度方式。u 需要对就绪队列的数据结构进行互斥访问控制。需要对就绪队列的数据结构进行互斥访问控制。1. 自调度自调度(self-scheduling)方式：方式

55、：Network Optimization Expert Team 易将单处理机系统的调度机制移植到多处易将单处理机系统的调度机制移植到多处理机系统。理机系统。 避免处理机忙闲不均的现象。避免处理机忙闲不均的现象。 瓶颈问题（对就绪队列的访问）瓶颈问题（对就绪队列的访问） 低效性低效性 线程切换频繁线程切换频繁Network Optimization Expert Teamu为了解决自调度方式中线程被频繁切换的问题。为了解决自调度方式中线程被频繁切换的问题。u是指将一组相互合作的进程或隶属于同一个进程是指将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组处理器上去同时执行。的一组线程分

56、配到一组处理器上去同时执行。u分配处理机时间时，可采用两种方式：分配处理机时间时，可采用两种方式： 面向所有应用程序平均分配处理机时间面向所有应用程序平均分配处理机时间 面向所有线程平均分配处理机时间面向所有线程平均分配处理机时间2. 成组调度成组调度(gang scheduling)方式方式Network Optimization Expert Team两种分配处理器时间的方式：两种分配处理器时间的方式：面向所有应用程序面向所有应用程序平均分配处理机时间平均分配处理机时间面向所有线程面向所有线程平均分配处理机时间平均分配处理机时间Network Optimization Expert Tea

57、mu对于一组相互合作的线程，成组调度能够提高这对于一组相互合作的线程，成组调度能够提高这些线程的执行并行度，有利于减少阻塞和加快推些线程的执行并行度，有利于减少阻塞和加快推进速度，最终提高系统的吞吐量。进速度，最终提高系统的吞吐量。u每次调度可以完成多个线程的分派，能够减少调每次调度可以完成多个线程的分派，能够减少调度次数，从而减少调度的开销。度次数，从而减少调度的开销。Network Optimization Expert Teamu是指在一个应用程序执行期间，专门为该应用程序是指在一个应用程序执行期间，专门为该应用程序分配一组处理器，每个线程分配一个分配一组处理器，每个线程分配一个CPU。

58、这组处。这组处理器仅供该应用程序专用，直至该应用程序执行完成。理器仅供该应用程序专用，直至该应用程序执行完成。u适用于适用于CPU数量众多的高度并行系统，单个数量众多的高度并行系统，单个CPU利利用率已不太重要。用率已不太重要。u线程的总和不应超过系统中的处理机数目。线程的总和不应超过系统中的处理机数目。有线程阻塞时，造成有线程阻塞时，造成CPU的闲置的闲置线程执行时不需切换，相应的开销可以大大线程执行时不需切换，相应的开销可以大大减小，推进速度更快。减小，推进速度更快。3. 专用处理机分配专用处理机分配(dedicated processor assignment)方式方式Network O

59、ptimization Expert Team以下是线程数对加速比的影响：以下是线程数对加速比的影响： 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 2122 23 241234567加速比加速比线程数线程数矩阵相乘矩阵相乘FFTFFT0例：例：具有具有16个处理器的系统，运行两个应用程序：个处理器的系统，运行两个应用程序： 矩阵矩阵相乘、快速傅立叶变换。相乘、快速傅立叶变换。Network Optimization Expert Team2022-5-1771 1.多道程序环境下，操作系统分配资源以（多道程序环境下，操作系统分配资源以（

60、）为）为基本单位。基本单位。A.程序程序 B.指令指令 C.进程进程 D.作业作业2.一个进程被唤醒意味着（一个进程被唤醒意味着（ ）。）。A. 该进程重新占有了该进程重新占有了CPU B.它的优先权变为最大它的优先权变为最大C. 其其PCB移至等待队列队首移至等待队列队首 D.进程变为就绪状态进程变为就绪状态3.通常用户进程被建立后，（通常用户进程被建立后，（ ）。）。A便一直存在于系统中，直到被操作人员撤消便一直存在于系统中，直到被操作人员撤消B随着作业运行正常或不正常结束而撤消随着作业运行正常或不正常结束而撤消C随着时间片轮转而撤消与建立随着时间片轮转而撤消与建立D随着进程的阻塞或唤醒而