处理机调度与死锁汇总课件.ppt

1、Yanshan University第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 本章主要理解进程调度和死锁的基本概念，熟悉进程调度的各种算法及适用范围，了解产生死锁的原因和必要条件，掌握如何预防、避免、检测、解除死锁的各种方法，特别是银行家算法。重、难点：进程调度算法 产生死锁的原因和必要条件 银行家算法Yanshan University第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统

2、中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 Yanshan University第三章 处理机调度与死锁 3.1 处理机调度的基本概念 要解决的问题要解决的问题WHAT：按什么原则分配按什么原则分配CPU 进程调度算法进程调度算法WHEN：何时分配何时分配CPU 进程调度的时机进程调度的时机HOW：如何分配如何分配CPU CPU调度过程调度过程 （进程的上下文切换）（进程的上下文切换）CPU调度的目的：分配CPU。CPU调度方式：一级调度或二级调度

3、。调度算法有：FCFS、SPF(SJF)、时间片轮转、优先权高者优先、多级反馈队列等不同的调度算法。Yanshan University第三章 处理机调度与死锁 进程调度的分类有：按调度层次，分为高级调度高级调度中级调度中级调度低级调度低级调度按OS的类型，分为批处理调度批处理调度分时调度分时调度实时调度实时调度多处理机调度多处理机调度Yanshan University第三章 处理机调度与死锁 3.1.1 高级、中级和低级调度 一、高级调度一、高级调度(又称为作业调度、长程调度又称为作业调度、长程调度/High Scheduling)：其原因是因为分时系统中，为了能及时响应用其原因是因为分时

4、系统中，为了能及时响应用户请求，用户通过键盘输入的命令或数据等，都是户请求，用户通过键盘输入的命令或数据等，都是直接送入内存，因而无需配置作业，而在批处理系直接送入内存，因而无需配置作业，而在批处理系统中，作业进入系统时先是驻留在外存上，然后根统中，作业进入系统时先是驻留在外存上，然后根据需要才调入内存，因此需要作业调度。据需要才调入内存，因此需要作业调度。为什么在分为什么在分(实实)时系统中不配置高级调度？时系统中不配置高级调度？在每次执行作业调度时，都需要做：在每次执行作业调度时，都需要做：1.接纳多少个作业接纳多少个作业 2.接纳哪些作业接纳哪些作业Yanshan University第

5、三章 处理机调度与死锁 二、低级调度二、低级调度(又称进程调度、短程调度又称进程调度、短程调度/Low Level Scheduling)：执行分配处理机的程序称为执行分配处理机的程序称为进程调度程序进程调度程序（分（分派程序）派程序）进程调度是操作系统中进程调度是操作系统中最基本的调度最基本的调度，在批处，在批处理系统及分时系统、实时系统中都必须配置它。理系统及分时系统、实时系统中都必须配置它。Yanshan University第三章 处理机调度与死锁 进程调度有以下两种基本方式：进程调度有以下两种基本方式：1.非抢占方式：非抢占方式：这种调度方式的这种调度方式的优点优点是：简单、系统开销

6、小，是：简单、系统开销小，貌似公正。貌似公正。这种调度方式的这种调度方式的缺点缺点是：可能导致系统性能的是：可能导致系统性能的恶化。表现为：恶化。表现为：(1)一个紧急任务到达时，不能立即投入运行，一个紧急任务到达时，不能立即投入运行，以致延误时机；以致延误时机；(2)若干个后到的短作业，须等待长作业运行完若干个后到的短作业，须等待长作业运行完毕才能运行，致使短作业的周转时间增长。这对短毕才能运行，致使短作业的周转时间增长。这对短作业用户来说是不公平的。作业用户来说是不公平的。Yanshan University第三章 处理机调度与死锁 2.抢占方式：方式：剥夺原则有剥夺原则有：(1)优先权原

7、则：优先权原则：优先权高的进程可以剥夺优优先权高的进程可以剥夺优先权低的进程的运行；先权低的进程的运行；(2)短作业（进程）优先原则：短作业（进程）优先原则：短进程到达后短进程到达后可以剥夺长进程的运行；可以剥夺长进程的运行；(3)时间片原则：时间片原则：一个时间片用完后进程重新一个时间片用完后进程重新调度。调度。Yanshan University第三章 处理机调度与死锁 三、中级调度三、中级调度(中程调度中程调度/Intermediate-Level Scheduling)：中级调度中级调度实际上就是存储器管理的对换。它实际上就是存储器管理的对换。它决定哪些进程被允许参与竞争处理机资源。中

8、级调度主要只是起到短期调整系统负荷的作用，以平顺系统的操作。其所使用的方法是通过“挂起”和“激活”一些进程，来达到平顺系统操作的目的。Yanshan University第三章 处理机调度与死锁 3.1.2 调度队列模型 一、仅有进程调度的调度队列模型一、仅有进程调度的调度队列模型 在分时系统中通常只设置进程调度。在分时系统中通常只设置进程调度。处于就绪队列中的进程在依次执行时，可能会发生以下三种情况：处于就绪队列中的进程在依次执行时，可能会发生以下三种情况：(1)进程未用完一个时间片便结束，这时系统应提前调度；进程未用完一个时间片便结束，这时系统应提前调度；(2)进程在执行过程中提出进程在执

9、行过程中提出I/O请求而阻塞，系统应将它放入请求而阻塞，系统应将它放入 阻塞队列并引起调度；阻塞队列并引起调度；(3)进程用完一个时间片后尚未完成，系统应将它放入就绪队进程用完一个时间片后尚未完成，系统应将它放入就绪队 列的末尾，等待下次执行。列的末尾，等待下次执行。图 3-1 仅具有进程调度的调度队列模型 交互用户交互用户 进程调度进程调度 endend 事件出现事件出现就绪队列I/O阻塞队列I/OCPU等待事件等待事件时间片完时间片完Yanshan University第三章 处理机调度与死锁 二、具有进程调度和作业调度的调度队列模型二、具有进程调度和作业调度的调度队列模型作业后备队列作业

10、后备队列 进程调度进程调度 endend 就绪队列CPU事件事件1 1出现出现I/O阻塞队列1I/O等待事件等待事件1 1时间片完时间片完作业调度作业调度事件事件2 2出现出现I/O阻塞队列2I/O等待事件等待事件2 2事件事件n n出现出现I/O阻塞队列nI/O等待事件等待事件n n区别：区别：(1)在在OS中不仅引入进程调度之后，而且还引入了作中不仅引入进程调度之后，而且还引入了作业调度。业调度。(2)在在OS中设置了多个阻塞队列。每一阻塞队列对应一中设置了多个阻塞队列。每一阻塞队列对应一种引起进程阻塞的事件。种引起进程阻塞的事件。Yanshan University第三章 处理机调度与死

11、锁 三、同时具有三级调度的调度队列模型三、同时具有三级调度的调度队列模型RUNreadyablockedareadysblokeds后备完成作业后备状态执行内存时间片到I/O请求I/O完成高级调度(作业调度)挂起激活挂起激活进程调度低级调度中级调度Yanshan University第三章 处理机调度与死锁 3.1.3 选择调度方式和调度算法的若干准则 一、面向用户的准则一、面向用户的准则 1.周转时间短：周转时间短：是批处理系统中衡量性能的一个是批处理系统中衡量性能的一个重要指标。主要有两个具体指标：重要指标。主要有两个具体指标：(1)作业周转时间：作业周转时间：指一个作业从提交开始到完成指

12、一个作业从提交开始到完成为止的这段时间间隔。它等于下列四个部分之和。为止的这段时间间隔。它等于下列四个部分之和。作业从外存后备队列上等待进入内存的时间；作业从外存后备队列上等待进入内存的时间；在就绪队列上等待获得处理机的时间；在就绪队列上等待获得处理机的时间；在在CPU上的执行时间；上的执行时间；等待等待I/O操作完成的时间。操作完成的时间。(2)进程周转时间：进程周转时间：是指一个进程从第一次进入就是指一个进程从第一次进入就绪队列开始到进程运行完毕所经历的时间。它等于作绪队列开始到进程运行完毕所经历的时间。它等于作业周转时间中的后三部分之和。业周转时间中的后三部分之和。Yanshan Uni

13、versity第三章 处理机调度与死锁 作业的平均周转时间作业的平均周转时间或作业的平均带权周转时间作业的平均带权周转时间 前者用来衡量不同调度算法对同一作业流的调度性能，后者用来比较某一调度算法对不同作业流的调度性能。它们定义如下：作业平均周转时间：T=1/n(Ti)i=1n其中：n被测定作业流中的作业数 Ti作业 i 的周转时间：Ti=Tci-Tsi Tsi 作业 i 的提交时间 Tci 作业 i 的完成时间 作业平均带权周转时间：W=1/n(Wi)=1/n(Ti/tRi)其中：tRi作业 i 的实际执行时间i=1ni=1nYanshan University第三章 处理机调度与死锁 2.

14、响应时间快：响应时间快：它是分时系统中衡量性能的一个它是分时系统中衡量性能的一个重要指标。是指从提交一个请求开始到首次产生响重要指标。是指从提交一个请求开始到首次产生响应为止应为止(显示出结果显示出结果)的一段时间间隔。它等于下列的一段时间间隔。它等于下列三部分之和：三部分之和：(1)把请求信号从键盘传输到计算机的时间；把请求信号从键盘传输到计算机的时间；(2)计算机对请求进行处理的时间；计算机对请求进行处理的时间；(3)再将响应送回终端的时间。再将响应送回终端的时间。3.截止时间的保证：截止时间的保证：它是实时系统中衡量性能的它是实时系统中衡量性能的一个重要指标。是指某任务必须从开始执行的最

15、近一个重要指标。是指某任务必须从开始执行的最近时间，或必须完成的最迟时间。时间，或必须完成的最迟时间。4.优先权准则：优先权准则：它是紧急作业得到及时处理的重它是紧急作业得到及时处理的重要保证。要保证。Yanshan University第三章 处理机调度与死锁 二、面向系统的准则二、面向系统的准则 1.系统吞吐量大：系统吞吐量大：是用于评价批处理系统的重是用于评价批处理系统的重要指标，因而它是选择批处理系统的重要准则。要指标，因而它是选择批处理系统的重要准则。2.处理机利用率高：处理机利用率高：是大、中型计算机系统选是大、中型计算机系统选择调度算法的重要依据。但对单用户或实时系统，择调度算法

16、的重要依据。但对单用户或实时系统，它不是十分重要的准则了。它不是十分重要的准则了。3.各类资源的平衡利用：各类资源的平衡利用：也是大、中型计算机也是大、中型计算机系统选择调度算法的重要依据。对单用户或实时系系统选择调度算法的重要依据。对单用户或实时系统，它不是十分重要的准则了。统，它不是十分重要的准则了。Yanshan University第三章 处理机调度与死锁 3.2 调 度 算 法 3.2.1 先来先服务和短作业(进程)优先调度算法 1.先来先服务调度算法（先来先服务调度算法（FCFS）该算法总是把处理机分配给最先进入就绪队列该算法总是把处理机分配给最先进入就绪队列的进程，即：就绪队列按

17、进入的先后顺序排队的进程，即：就绪队列按进入的先后顺序排队。属于不可抢占策略属于不可抢占策略 优点优点:实现简单实现简单 缺点缺点:没考虑进程的优先级没考虑进程的优先级 此算法是此算法是有利于长有利于长(大大)作业作业(进程进程)，不利于短，不利于短(小小)作业作业(进程进程)；有利于；有利于CPU繁忙的作业繁忙的作业(进程进程)，不，不利于利于I/O繁忙的作业繁忙的作业(进程进程)。Yanshan University第三章 处理机调度与死锁 作业提交时间运行时间开始时间完成时间周转时间带权周转时间ts(时)tR(时)tB(时)tC(时)ti(时)Wi(Z)12348.008.509.009

18、.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.306.901.004.0016.006.5027.50平均周转时间 T=6.90/4=1.725(小时)平均带权时间 W=27.5/4=6.875FCFS算法实例算法实例Yanshan University第三章 处理机调度与死锁 2.短作业短作业(进程进程)优先调度算法（优先调度算法（SJF/SPF）是指对短作业或短进程优先调度短作业或短进程优先调度的算法。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们

19、调入内存运行。短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。属于不可抢占策略属于不可抢占策略Yanshan University第三章 处理机调度与死锁 优点：优点：该算法相对该算法相对FCFS来说调度性能要好些，来说调度性能要好些，且能满足大多数作业且能满足大多数作业(均是短作业均是短作业)用户的要求。用户的要求。缺点：缺点：该算法对长作业不利。该算法对长作业不利。该算法未考虑作业的紧迫程度，因而不能保证该算法未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程紧迫性作业

20、（进程）及时得到处理。）及时得到处理。该算法不一定能真正做到短作业优先调度。该算法不一定能真正做到短作业优先调度。计算下一个CPU执行期的预测公式如下：tn：第第n个实际的个实际的CPU执行期执行期 n：第第n个实际的个实际的CPU执行期预测值执行期预测值：用于控制最近的用于控制最近的tn和和其预测值其预测值 n n+1=tn+(1-)nYanshan University第三章 处理机调度与死锁 作业提交时间运行时间开始时间完成时间周转时间带权周转时间ts(时)tR(时)tB(时)tC(时)ti(时)Wi(Z)12348.008.509.009.502.000.500.100.20SJF算法

21、实例算法实例8.0010.3010.0010.1010.0010.8010.1010.302.002.301.100.806.201.004.6011.004.0020.60平均周转时间 T=6.20/4=1.55(小时)平均带权时间 W=20.6/4=5.15优:比FCFS，T W 缺:有的作业可能始终得不到运行Yanshan University第三章 处理机调度与死锁 3.2.2 高优先权优先调度算法 一、优先权调度算法的类型一、优先权调度算法的类型 基本原理基本原理是：是：对于进程调度，对于进程调度，它总是把处理它总是把处理机分配给就绪队列中具有最高优先权的进程机分配给就绪队列中具有最

22、高优先权的进程；对对于作业调度，于作业调度，它总选择后备队列中若干具有高优它总选择后备队列中若干具有高优先权的作业进入内存先权的作业进入内存。优先级调度算法又可分为：优先级调度算法又可分为：非抢占的优先级调度法非抢占的优先级调度法 可抢占的优先级调度法可抢占的优先级调度法Yanshan University第三章 处理机调度与死锁 1.静态优先权：静态优先权：静态优先权是在创建进程时确定的，在整静态优先权是在创建进程时确定的，在整个运行期间不再发生改变。个运行期间不再发生改变。确定静态优先权的依据有：确定静态优先权的依据有：(1)进程类型进程类型 (2)进程对资源的需求进程对资源的需求 (3)

23、用户要求的优先权用户要求的优先权。静态优先权简单易行，系统开销小，但不精确。静态优先权简单易行，系统开销小，但不精确。2.动态优先权：动态优先权：动态优先权是基于某种原则，使进程的优动态优先权是基于某种原则，使进程的优先权随时间而改变。先权随时间而改变。二、优先权的类型二、优先权的类型Yanshan University第三章 处理机调度与死锁 三、三、高响应比优先调度算法高响应比优先调度算法 响应比响应比Rp定义如下：定义如下：Rp=作业响应时间作业响应时间tR/要求执行的时间要求执行的时间 作业响应时间作业响应时间tR=作业进入系统后等待时间作业进入系统后等待时间+要求执行要求执行的时间的

24、时间 Rp=1+(作业等待时间作业等待时间tW/要求执行的时间要求执行的时间)HRN原理：原理：就是在每调度一个作业投入运行时，先计就是在每调度一个作业投入运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。高者投入运行。优点：优点：该算法既照顾了短作业用户，同时也避免了长该算法既照顾了短作业用户，同时也避免了长作业用户无限期的等待，是作业用户无限期的等待，是 FCFS 和和 SJ(P)F 两种算法的较两种算法的较好折衷方案。好折衷方案。缺点：缺点：算法较为复杂，增加了系统开销算法较为复杂，增加了系统开销(计算响应比计算

25、响应比)。Yanshan University第三章 处理机调度与死锁 作业提交时间运行时间开始时间完成时间周转时间带权周转时间ts(时)tR(时)tB(时)tC(时)ti(时)Wi(Z)12348.008.509.009.502.000.500.100.20HRN算法实例算法实例8.0010.1010.0010.6010.0010.6010.1010.802.002.101.101.306.501.004.2011.006.5022.70平均周转时间 T=6.50/4=1.625(小时)平均带权时间 W=22.7/4=5.675Yanshan University第三章 处理机调度与死锁 3

26、.2.3 基于时间片的轮转调度算法 1.时间片轮转法时间片轮转法 基本原理基本原理 轮转法是最简单又最公平的进程调度算法。轮转法是最简单又最公平的进程调度算法。主要主要用于分时系统中作为其主调度算法。用于分时系统中作为其主调度算法。属于可抢占策略属于可抢占策略。轮转法分配给每一进程在轮转法分配给每一进程在CPU上运行的时间长度，上运行的时间长度，称之为称之为时间片时间片。其其基本原理基本原理是：是：诸进程以此诸进程以此时间片时间片为为限制，轮流使用限制，轮流使用CPU。如果如果时间片时间片到期时，进程尚未到期时，进程尚未完成运行，调度程序将剥夺它正在使用的完成运行，调度程序将剥夺它正在使用的C

27、PU，转让转让给另一进程使用；如果进程在使用完它的某一给另一进程使用；如果进程在使用完它的某一时间片时间片之前已经完成运行或已阻塞，之前已经完成运行或已阻塞，CPU也立即转让给另一也立即转让给另一进程使用。进程使用。Yanshan University第三章 处理机调度与死锁 轮转法在实现上也很容易，调度程序只要维护一个先进先出的队列数据结构，将就绪进程排队，每当一个进程的时间片运行完后，便把它从原来的队头位置移到队尾，然后把现在处于队头位置的进程调度到CPU上运行。时间片的计数则可通过定时中断实现。100ms交互用户交互用户 进程调度进程调度 endend 事件出现事件出现就绪队列I/O阻塞

28、队列I/OCPU等待事件等待事件时间片完时间片完Yanshan University第三章 处理机调度与死锁 时间片大小的确定时间片大小的确定 轮转法的性能取决于时间片大小的选择。轮转法的性能取决于时间片大小的选择。例：例：若一次切换时间为若一次切换时间为5毫秒，时间片长度选择为毫秒，时间片长度选择为20毫毫秒，则秒，则20的的CPU时间花费于进程调度程序。为了改善时间花费于进程调度程序。为了改善CPU的利用率，可以增大时间片，比如说为的利用率，可以增大时间片，比如说为500毫秒，此时毫秒，此时CPU利用率达利用率达99之多，但每一进程的响应时间也因之增大。若之多，但每一进程的响应时间也因之增

29、大。若就绪队列中共有就绪队列中共有10个进程，则每一进程需要等待个进程，则每一进程需要等待5秒钟，才能秒钟，才能在在CPU上服务一次。上服务一次。通常来说，选择时间片为通常来说，选择时间片为100毫秒左右比较适宜。毫秒左右比较适宜。时间片选择有：时间片选择有：固定时间片和可变时间片；固定时间片和可变时间片；与时与时间片大小有关的因素有：间片大小有关的因素有：系统响应时间、就绪进程个系统响应时间、就绪进程个数和数和CPU处理能力三个。处理能力三个。Yanshan University第三章 处理机调度与死锁 实际中，轮转法常和优先级算法结合使用，也实际中，轮转法常和优先级算法结合使用，也就是按优

30、先级将进程分组，组间采用优先级调度算就是按优先级将进程分组，组间采用优先级调度算法，而组内优先级相同的进程则按轮转法调度（即法，而组内优先级相同的进程则按轮转法调度（即多级反馈队列调度算法）。显然，若优先级不动态多级反馈队列调度算法）。显然，若优先级不动态地进行调整，则优先级低的就绪进程就可能饿死。地进行调整，则优先级低的就绪进程就可能饿死。2.多级队列调度算法多级队列调度算法 基本思路：把终端型作业作为前台作业，并排成一个队列，称为前台队列；把批处理作业作为后台作业，也排成一个队列，称为后台队列。系统令前台队列中各进程按时间片轮转，仅当前台队列中出现空闲时间片时，才把处理机分配给后台队列中的

31、各进程，并令它们按FCFS方式依次执行。Yanshan University第三章 处理机调度与死锁 3.多级反馈队列调度算法多级反馈队列调度算法 调度算法调度算法 思路如下：把进程按优先级分组，优先级最高把进程按优先级分组，优先级最高的进程组中的进程每次在的进程组中的进程每次在CPU上运行一个时间片上运行一个时间片t长长度；优先级次之的进程组的进程每次运行二个时间度；优先级次之的进程组的进程每次运行二个时间片片2t长度；优先级再次之的进程组的进程每次运行长度；优先级再次之的进程组的进程每次运行4个时间片个时间片4t长度，以此类推，进程每次运行完它的长度，以此类推，进程每次运行完它的时间片后便

32、降低一个优先级别，移至另一优先级的时间片后便降低一个优先级别，移至另一优先级的进程组中。进程组中。Yanshan University第三章 处理机调度与死锁 多级反馈队列调度算法示意图 最高优先权队列时间片最高优先权队列时间片次高优先权队列时间片次高优先权队列时间片最低优先权队列时间片最低优先权队列时间片新进程进入s1s2s3sn至CPU至CPU至CPU至CPU(时间片：s1s2s3)Yanshan University第三章 处理机调度与死锁*首先系统中设置多个就绪队列首先系统中设置多个就绪队列*每个就绪队列分配给不同时间片，优先级高的为每个就绪队列分配给不同时间片，优先级高的为第一级队列

33、，时间片最小，随着队列级别的降低，第一级队列，时间片最小，随着队列级别的降低，时间片加大时间片加大*各个队列按照各个队列按照按时间片轮转的先来先服务按时间片轮转的先来先服务出调度出调度算法算法*一个新进程就绪后进入第一级队列一个新进程就绪后进入第一级队列*进程由于等待而放弃进程由于等待而放弃CPU后，进入等待队列，一后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列旦等待的事件发生，则回到原来的就绪队列*当有一个优先级更高的进程就绪时，可以抢占当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾被抢占进程回到原来一级就绪队列末尾*当第一级队列空时，就去调度

34、第二级队列，如此当第一级队列空时，就去调度第二级队列，如此类推类推*当时间片到后，进程放弃当时间片到后，进程放弃CPU，回到下一级队列回到下一级队列Yanshan University第三章 处理机调度与死锁 多级反馈队列多级反馈队列调度算法的性能调度算法的性能 多级反馈队列多级反馈队列调度算法具有较好的性能，能满调度算法具有较好的性能，能满足各种类型用户的需要。足各种类型用户的需要。1.终端型用户：终端型用户：作业较小，可在第一队列的时作业较小，可在第一队列的时间片内完成。间片内完成。2.短批处理型作业用户：短批处理型作业用户：大多数作业可在第一大多数作业可在第一队列的时间片内完成，稍长的也

35、可在第二队列的时队列的时间片内完成，稍长的也可在第二队列的时间片内完成。间片内完成。3.长批处理型作业用户：长批处理型作业用户：可依次在第一、二、可依次在第一、二、n队列的时间片内完成。队列的时间片内完成。Yanshan University第三章 处理机调度与死锁 3.3 实 时 调 度 3.3.1 实现实时调度的基本条件 1.提供必要的信息提供必要的信息(1)就绪时间。(2)(2)开始截止时间和完成截止时间。(3)(3)处理时间。(4)(4)资源要求。(5)(5)优先级。Yanshan University第三章 处理机调度与死锁 2.系统处理能力强系统处理能力强 在实时系统中，通常都有着

36、多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：miiiPC11Yanshan University第三章 处理机调度与死锁 系统才是可调度的。假如系统中有6个硬实时任务，它们的周期时间都是 50 ms，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少

37、对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：miiiNPC1Yanshan University第三章 处理机调度与死锁 3.采用抢占式调度机制采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地

38、将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务。Yanshan University第三章 处理机调度与死锁 4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：(1)对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2)快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。Yanshan University第三章 处理机调度

39、与死锁 3.3.2 实时调度算法的分类 1.非抢占式调度算法非抢占式调度算法(a)非抢占轮转调度当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b)非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度调度时间实时进程 (1)非抢占式轮转调度算法。非抢占式轮转调度算法。能获得秒级的响应时间，只适合于实时信息处理系统Yanshan University第三章 处理机调度与死锁(a)

40、非抢占轮转调度当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b)非抢占优先权调度当前进程实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度 时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度调度时间实时进程 (2)非抢占式优先调度算法。非抢占式优先调度算法。能获得秒级至数百毫秒级的响应时间，适合于要求不太严格的实时控制处理系统。Yanshan University第三章 处理机调度与死锁 2.抢占式调度算法抢占式调度算法(a)非抢占轮转调度当前

41、进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b)非抢占优先权调度当前进程实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度 时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度调度时间实时进程 (1)基于时钟中断的抢占式优先权调度算法。基于时钟中断的抢占式优先权调度算法。能获得数十毫秒级至数毫秒级的响应时间，适合于大多数的实时控制处理系统。Yanshan University第三章 处理机调度与死锁(a)非抢占轮转调度当前进程实时进程实时进程请求调

42、度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b)非抢占优先权调度当前进程实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度 时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度调度时间实时进程 (2)立即抢占立即抢占(Immediate Preemption)的优先权调的优先权调度算法。度算法。能获得数毫秒级至百微秒级的响应时间，适合于对响应时间要求非常严格的实时控制处理系统。Yanshan University第三章 处理机调度与死锁 3.3.3 常用的几种实时调度算法

43、1.最早截止时间优先即最早截止时间优先即EDF算法算法(Earliest Deadline First)图 3-7 EDF算法用于非抢占调度方式 1342开始截止时间任务执行任务到达12341342tYanshan University第三章 处理机调度与死锁 图 3-8 A和B任务每次必须完成的时间 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25

44、ms。2.最低松弛度优先即最低松弛度优先即LLF算法算法(Least Laxity First)Yanshan University第三章 处理机调度与死锁 t1=0A1 的松驰度：20-10=10(ms)B1 的松驰度：50-25=25(ms)调度A1执行t2=10，A1 完成任务A尚未进入第2周期任务B已经进入第1周期调度B1执行t3=30A2 的松驰度：40-10-30=0(ms)B1 的松驰度：50-5-30=15(ms)抢占B1调度A2执行t4=40A3 的松驰度：60-10-40=10(ms)B1 的松驰度：50-5-40=5(ms)调度B1执行t5=45，B1 完成A3 的松驰度

45、：60-10-45=5(ms)B2 的松驰度：100-25-45=30(ms)调度A3执行t6=55 任务A尚未进入第4周期任务B已经进入第2周期调度B2执行t7=70 A4 的松驰度：80-10-70=0(ms)B2 的松驰度：100-10-70=20(ms)抢占B2调度A4执行t8=80 A5 的松驰度：100-10-80=10(ms)B2 的松驰度：100-10-80=10(ms)调度B2执行图 利用ELLF算法进行调度的情况 010203040 50 607080A1(10)B1(20)A2(10)B1(5)A3(10)B2(15)A4(10)B2(10)t1t2t3t4t545t65

46、5t7t8Yanshan University第三章 处理机调度与死锁 3.4 多处理机系统中的调度 前面所讨论的是单CPU下的进程调度，对于多CPU，一方面由于有多台处理机，可采用的调度策略也随之增多，另一方面在调度目标上，要求的是整个系统的运行效率的提高，即不能只保证单CPU忙，而且在引入线程后，调度的基本单位已经是线程了。因此，在多CPU的OS中，广泛采用了线程调度机制，本节主要介绍对线程的调度问题。Yanshan University第三章 处理机调度与死锁 3.4.1 多处理器系统(MPS)的类型 1.紧密耦合紧密耦合MPS和松散耦合和松散耦合MPS (1)紧密耦合紧密耦合MPS结构

47、（同构型）结构（同构型）高高 速速 交交 叉叉 开开 关关M1M2M3MnI/O2I/O1.P1P2P3Pn 特点：特点：通过高速总线或高速交叉开关进行处理通过高速总线或高速交叉开关进行处理机之间的互连，并共享存储器。机之间的互连，并共享存储器。一般说，该结构里的所有处理机都是相同的。一般说，该结构里的所有处理机都是相同的。Yanshan University第三章 处理机调度与死锁 (2)松散耦合松散耦合MPS结构（异构型）结构（异构型）P1P2PnMnM2M1I/O2I/O1I/On 特点：特点：各个处理机有自己的存储器和各个处理机有自己的存储器和OS，它们它们之间通过通道或通信线路实现互

48、连。之间通过通道或通信线路实现互连。一般说，该结构里的所有处理机可以不相同。一般说，该结构里的所有处理机可以不相同。在多处理机系统中，进程调度与系统结构和在多处理机系统中，进程调度与系统结构和OS的工作模式均相关。的工作模式均相关。Yanshan University第三章 处理机调度与死锁 2.对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统 (1)对称多处理器系统对称多处理器系统SMPS(Symmetric MultiProcessor System)在系统中所包含的各处理器单元，在功能和结构上都是相同的，当前的绝大多数MPS都属于SMPS。例如，IBM公司的SR/

49、6000 Model F50,便是利用4片Power PC处理器构成的。(2)非对称多处理器系统非对称多处理器系统AMPS(Asymmetrical MultiProcessor System)在系统中有多种类型的处理单元，它们的功能和结构各不相同，其中只有一个主处理器，有多个从处理器。Yanshan University第三章 处理机调度与死锁 3.4.2 进程分配方式 1.对称多处理器系统中的进程分配方式对称多处理器系统中的进程分配方式 在SMP系统中，所有的处理器都是相同的，因而可把所有的处理器作为一个处理器池(Processor pool)，由调度程序或基于处理器的请求，将任何一个进程

50、分配给池中的任何一个处理器去处理。在进行进程分配时，可采用以下两种方式之一。Yanshan University第三章 处理机调度与死锁 1.静态分配：静态分配：是指一个进程从开始执行是指一个进程从开始执行直到完成，都被固定分配到一台处理机上去直到完成，都被固定分配到一台处理机上去执行。执行。采用该分配，需为每个处理机设置一个采用该分配，需为每个处理机设置一个专用的就绪进程队列，该队列中的诸进程先专用的就绪进程队列，该队列中的诸进程先后都被分配到该处理机上。在进程阻塞后再后都被分配到该处理机上。在进程阻塞后再次就绪时，仍被挂在原来这个就绪队列中。次就绪时，仍被挂在原来这个就绪队列中。优点：优点