第3章处理机调度与死锁

1、重邮移通学院12022-3-27重邮移通学院22022-3-273.3 调度算法调度算法3.4 实时调度实时调度重邮移通学院32022-3-27q先来先服务和短作业优先算法先来先服务和短作业优先算法q优先级调度算法和高响应比调度优先级调度算法和高响应比调度算法算法q基于时间片的轮转调度算法基于时间片的轮转调度算法重邮移通学院42022-3-271 1、优先级调度算法的类型、优先级调度算法的类型调度时，系统把处理机分配给优先级最高的就绪进程。调度时，系统把处理机分配给优先级最高的就绪进程。分为两大类：分为两大类：（1 1）非抢占式非抢占式优先级调度算法优先级调度算法（2 2）抢占式抢占式优先级调

2、度算法优先级调度算法重邮移通学院52022-3-27q把处理机分配给就绪队列中把处理机分配给就绪队列中优先级最高优先级最高的进程后的进程后便便一直执行下去一直执行下去直至完成；或发生某事件使该进直至完成；或发生某事件使该进程放弃处理机时，可再将处理机重新分配给另一程放弃处理机时，可再将处理机重新分配给另一优先级最高的进程。优先级最高的进程。q用于用于批处理系统批处理系统和某些和某些对实时性要求不严对实时性要求不严的实时的实时系统中。系统中。重邮移通学院62022-3-27q把处理机分配给把处理机分配给优先级最高优先级最高的进程，使之执行。的进程，使之执行。在执行期间，只要又出现优先级更高的进程

3、，就在执行期间，只要又出现优先级更高的进程，就重新重新将处理机分配给新到的优先级最高的进程。将处理机分配给新到的优先级最高的进程。q能更好地满足紧迫作业的要求，常用于能更好地满足紧迫作业的要求，常用于要求比较要求比较严格的实时系统严格的实时系统中，以及对性能要求较高的批处中，以及对性能要求较高的批处理和分时系统中。理和分时系统中。重邮移通学院72022-3-272、优先级的类型、优先级的类型（1）静态优先级）静态优先级（2）动态优先级）动态优先级重邮移通学院82022-3-27（1）静态优先级）静态优先级r在创建进程时确定在创建进程时确定r在进程的整个运行期间保持不变。在进程的整个运行期间保持

4、不变。r一般地，用某一范围内的一个整数来表示的，例一般地，用某一范围内的一个整数来表示的，例如，如，07或或0255中的某一整数，又把该整数称为中的某一整数，又把该整数称为优先数。优先数。 重邮移通学院92022-3-27（1）静态优先级）静态优先级q确定进程静态优先级的依据确定进程静态优先级的依据进程类型:系统进程，用户进程（系统进程高于用户进程）进程对资源的需求：要求少的进程应赋予较高优先级。用户要求：这是由用户进程的紧迫程度及所付费多少来确定。重邮移通学院102022-3-27r简单，系统开销小简单，系统开销小r不精确，仅在要求不高的系统中使用。可能会出不精确，仅在要求不高的系统中使用。

5、可能会出现优先级低的进程长期没有被调度的情况。现优先级低的进程长期没有被调度的情况。（1）静态优先级）静态优先级静态优先级法优缺点：静态优先级法优缺点：重邮移通学院112022-3-27进程进程到达到达时间时间服务服务时间时间静态优静态优先级先级开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均静态优先级，静态优先级，非抢占式非抢占式（1为高优先级）为高优先级）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93重邮移通学院122022-3-27（2）动态优先级）动态优先级在创建之初，先赋予其

6、一个优先级。在创建之初，先赋予其一个优先级。随随进程的推进进程的推进或随其或随其等待时间等待时间的增加而改变，的增加而改变，以获得更好的调度性能；以获得更好的调度性能；可规定，在就绪队列中的进程，随其等待时可规定，在就绪队列中的进程，随其等待时间的增长，其优先级以速率间的增长，其优先级以速率a a提高；提高；当采用抢占式优先级调度算法时，如果再规当采用抢占式优先级调度算法时，如果再规定当前进程的优先级以速率定当前进程的优先级以速率b b下降，则可防止下降，则可防止一个长作业长期地垄断处理机。一个长作业长期地垄断处理机。重邮移通学院132022-3-273、高响应比优先调度算法、高响应比优先调度

7、算法v是FCFS和SJF的结合，克服了两种算法的缺点v调度策略：响应比最高的作业优先调度时时间间务务时时间间权权务务时时间间等等待待+ + 要要求求服服优优先先= =要要求求服服重邮移通学院142022-3-27 说明：说明：v等待时间相同，服务时间愈短，优先级愈高，等待时间相同，服务时间愈短，优先级愈高，v服务时间相同，等待时间愈长，优先级愈高，服务时间相同，等待时间愈长，优先级愈高，v长作业优先级随等待时间的增加而提高，等待长作业优先级随等待时间的增加而提高，等待时间足够长时，其优先级可升到很高，时间足够长时，其优先级可升到很高， 从而也从而也可获得处理机可获得处理机。v优点：兼顾长短作业

8、。优点：兼顾长短作业。v缺点：由于做相应比计算故增加了系统开销。缺点：由于做相应比计算故增加了系统开销。重邮移通学院152022-3-27q先来先服务和短作业优先算法q优先级调度算法和高响应比调度算法q基于时间片的轮转调度算法重邮移通学院162022-3-271、时间片轮转法、时间片轮转法q 分时系统中多采用时间片轮转法分时系统中多采用时间片轮转法q 把就绪进程组织成把就绪进程组织成FIFO队列，队列，q 把把CPU分配给队首进程，分配给队首进程，q 规定它执行一个时间片。规定它执行一个时间片。q 时间片完时排在就绪队列的末尾，重新把处理机时间片完时排在就绪队列的末尾，重新把处理机分配给就绪队

9、列中新的队首进程，也执行一个时分配给就绪队列中新的队首进程，也执行一个时间片。间片。q 就绪队列中的所有进程在一给定时间内，均可获就绪队列中的所有进程在一给定时间内，均可获得一个时间片的得一个时间片的CPU时间时间.q 时间片的大小从几时间片的大小从几ms到几百到几百ms重邮移通学院172022-3-27说明：说明：（1）时间片选择问题）时间片选择问题固定时间片固定时间片可变时间片可变时间片时间片大小时间片大小（2）与时间片大小有关的因素）与时间片大小有关的因素系统响应时间系统响应时间就绪进程个数就绪进程个数CPU能力能力 重邮移通学院182022-3-27说明：说明： 时间片大小对系统性能有

10、很大影响：时间片大小对系统性能有很大影响：r 很小，有利于短作业，因为它能在该时间很小，有利于短作业，因为它能在该时间片内完成，但时间片小，意味着频繁进行进片内完成，但时间片小，意味着频繁进行进程调度和上下文切换，会增加系统开销。程调度和上下文切换，会增加系统开销。r 如果过大，每个作业都可以在一个时间片如果过大，每个作业都可以在一个时间片内完成，直接褪化为内完成，直接褪化为FCFS算法，无法满足短算法，无法满足短作业和交互式作业的需求。作业和交互式作业的需求。重邮移通学院192022-3-27进程名进程名到达时到达时间间服务时服务时间间开始时开始时间间完成时完成时间间周转时周转时间间带权周带

11、权周转时间转时间A04015153.75B13112113.67C24216143.5D323963E44417133.33平均平均11.83.46重邮移通学院202022-3-27进程名进程名到达时到达时间间服务时服务时间间开始时开始时间间完成时完成时间间周转周转时间时间带权周带权周转时间转时间A040441B134762C2481192.25D321113105E441317133.33平均平均8.42.5重邮移通学院212022-3-27v为多个就绪队列赋为多个就绪队列赋不同的优先级不同的优先级。v多级队列：队列时间片长递增；新进程进入最多级队列：队列时间片长递增；新进程进入最上级队列上

12、级队列v每级队列：先进先出，时间片机制每级队列：先进先出，时间片机制v时间片完，自动降级时间片完，自动降级v上级队列未空，下级队列不能调度上级队列未空，下级队列不能调度v抢占条件：下级队列进程运行时，上级队列有抢占条件：下级队列进程运行时，上级队列有新进程进入，发生抢占新进程进入，发生抢占v抢占处理：被抢进程不降级，排到队列末尾，抢占处理：被抢进程不降级，排到队列末尾，等待剩余时间的完成等待剩余时间的完成重邮移通学院222022-3-27就绪队列就绪队列1 1就绪队列就绪队列2 2就绪队列就绪队列3 3就绪队列就绪队列n nS1S2S3至至CPU至至CPU至至CPU至至CPU( (时间片：时间

13、片：S1 S2 S3) )2、多级反馈队列调度算法、多级反馈队列调度算法高高低低优先级优先级时间片时间片小小大大Sn重邮移通学院232022-3-273、多级反馈队列调度算法的性能、多级反馈队列调度算法的性能（1）终端型作业用户）终端型作业用户所提交的作业属于所提交的作业属于交互型交互型作业，通常作业，通常较小较小，系统只要能使这些作业在第一队列所系统只要能使这些作业在第一队列所规定规定的时间片内完成的时间片内完成即可；即可；（2）短批处理作业用户）短批处理作业用户若在第若在第1队列中执行队列中执行一个时间片一个时间片即可完成，即可完成，便可获得与终端型作业一样的响应时间；便可获得与终端型作业

14、一样的响应时间；如在第一个队列中不能完成，只需在第如在第一个队列中不能完成，只需在第2、3队列中各执行一个时间片；队列中各执行一个时间片；重邮移通学院242022-3-273、多级反馈队列调度算法的性能、多级反馈队列调度算法的性能（3）长批处理作业用户）长批处理作业用户长作业将依次在第长作业将依次在第1，2，3，n队列中执队列中执行，行，最终按轮转方式运行。最终按轮转方式运行。重邮移通学院252022-3-27q实现实时调度的基本条件实现实时调度的基本条件q实时调度的分类实时调度的分类q实时调度算法实时调度算法重邮移通学院262022-3-27v提供必要的信息提供必要的信息 v系统处理能力强系

15、统处理能力强 v采用抢占式调度机制采用抢占式调度机制v具有快速切换机制具有快速切换机制 重邮移通学院272022-3-271 1、提供必要的信息、提供必要的信息（1 1）就绪时间）就绪时间（2 2）开始截止时间和完成截止时间）开始截止时间和完成截止时间（3 3）处理时间）处理时间（4 4）资源要求）资源要求（5 5）优先级）优先级重邮移通学院282022-3-272、系统处理能力强、系统处理能力强 假定单处理机系统中有假定单处理机系统中有M个个周期性周期性的硬实时任务，的硬实时任务，它们的处理时间可表示为它们的处理时间可表示为Ci，周期时间表示为，周期时间表示为Pi。则必须满足下面的限制条件：

16、则必须满足下面的限制条件： Ci/ Pi 1 系统才是可调度的。系统才是可调度的。 重邮移通学院292022-3-272、系统处理能力强、系统处理能力强例例:单处理机系统单处理机系统中有中有6个硬实时任务，它们的周期个硬实时任务，它们的周期时间都是时间都是50MS，而每次的处理时间为，而每次的处理时间为10MS，则，则 Ci/ Pi=6/51 所以系统是不可调度的所以系统是不可调度的 重邮移通学院302022-3-272、系统处理能力强、系统处理能力强 解决的方法是提高系统的处理能力，其途径有解决的方法是提高系统的处理能力，其途径有二：二：q其一仍是采用单处理机系统，其一仍是采用单处理机系统，

17、 但须增强其处理能但须增强其处理能力，力， 以显著地减少对每一个任务的处理时间；以显著地减少对每一个任务的处理时间；q其二是采用多处理机系统。假定系统中的处理机其二是采用多处理机系统。假定系统中的处理机数为数为N，则应将上述的限制条件改为：，则应将上述的限制条件改为：miiiNPC1重邮移通学院312022-3-273、采用抢占式调度机制、采用抢占式调度机制q 当一个优先权更高的任务到达时，允许将当前任务暂时挂当一个优先权更高的任务到达时，允许将当前任务暂时挂起，令高优先权任务立即运行，这样可满足硬实时任务对起，令高优先权任务立即运行，这样可满足硬实时任务对截止时间的要求。但这种调度机制比较复

18、杂。截止时间的要求。但这种调度机制比较复杂。q 对于小实时系统，如果能预知任务的开始截止时间，则可对于小实时系统，如果能预知任务的开始截止时间，则可采用非抢占调度机制，以简化调度程序和对任务调度时所采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。花费的系统开销。q 但在设计这种调度机制时，应使所有的实时任务都比较小，但在设计这种调度机制时，应使所有的实时任务都比较小，在执行完关键性程序和临界区后，能及时自我阻塞，释放在执行完关键性程序和临界区后，能及时自我阻塞，释放处理机，供调度程序去调度那种开始截止时间即将到达的处理机，供调度程序去调度那种开始截止时间即将到达的任务。任务。

19、重邮移通学院322022-3-274、具有快速切换机制、具有快速切换机制该机制应具有如下两方面的能力：该机制应具有如下两方面的能力：q (1) 对外部中断的快速响应能力。为使在紧迫的对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，间隔尽量短， 以免耽误时机以免耽误时机(其它紧迫任务其它紧迫任务)。q(2) 快速的任务分派能力。在完成任务调度后，快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务便应

20、进行任务切换。为了提高分派程序进行任务切换时的速度，切换时的速度， 应使系统中的每个运行功能单应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。位适当的小，以减少任务切换的时间开销。 重邮移通学院332022-3-27硬实时调度算法硬实时调度算法 软实时调度算法软实时调度算法 重邮移通学院342022-3-27非抢占调度算法非抢占调度算法 抢占调度算法抢占调度算法 重邮移通学院352022-3-271、非抢占式调度算法、非抢占式调度算法p算法简单，用在小型实时系统或要求不严的实时算法简单，用在小型实时系统或要求不严的实时控制系统中。控制系统中。p分两种：分两种：（1 1）非抢占式

21、轮转调度算法）非抢占式轮转调度算法（2 2）非抢占式优先调度算法）非抢占式优先调度算法 重邮移通学院362022-3-271、非抢占式调度算法、非抢占式调度算法（1 1）非抢占式轮转调度算法）非抢占式轮转调度算法r用于工业群控系统中用于工业群控系统中r由一台计算机控制若干个相同的（或类似的）对由一台计算机控制若干个相同的（或类似的）对象，为每一个被控对象建立一个实时任务，并将象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。它们排成一个轮转队列。r调度程序每次选择队列中的第一个任务运行。完调度程序每次选择队列中的第一个任务运行。完成后，便把它挂在轮转队列的末尾，等待下次调成后，便

22、把它挂在轮转队列的末尾，等待下次调度运行，这次调度程序在选择下一个（队首）任度运行，这次调度程序在选择下一个（队首）任务运行。务运行。r可获得数秒至数十秒的响应时间可获得数秒至数十秒的响应时间 重邮移通学院372022-3-271、非抢占式调度算法、非抢占式调度算法（2 2）非抢占式优先调度算法）非抢占式优先调度算法r针对有一定要求的系统针对有一定要求的系统r为实时要求高的任务赋予较高的优先级。优先安为实时要求高的任务赋予较高的优先级。优先安排在排在就绪对列队首就绪对列队首，待，待当前任务结束当前任务结束后，被调度后，被调度执行。执行。r响应时间为数秒至数百毫秒响应时间为数秒至数百毫秒重邮移通

23、学院382022-3-272、抢占式调度算法、抢占式调度算法r应用于响应时间在数十毫秒以下的系统。应用于响应时间在数十毫秒以下的系统。r根据抢占发生时间不同分类：根据抢占发生时间不同分类： （1 1）基于时钟中断的抢占式优先级调度算法。）基于时钟中断的抢占式优先级调度算法。 （2 2）立即抢占的优先级调度算法。）立即抢占的优先级调度算法。重邮移通学院392022-3-272、抢占式调度算法、抢占式调度算法 （1 1）基于时钟中断的优先级调度算法）基于时钟中断的优先级调度算法 高优先级的实时任务到达后高优先级的实时任务到达后不立即不立即抢占，等抢占，等到到时钟中断时钟中断到来时再重新分配处理机。

24、到来时再重新分配处理机。 调度时间延迟：几十到几百毫秒。调度时间延迟：几十到几百毫秒。重邮移通学院402022-3-272、抢占式调度算法、抢占式调度算法 （2 2）立即抢占的优先级调度算法）立即抢占的优先级调度算法 高优先级的实时任务到达后，只要当前任务高优先级的实时任务到达后，只要当前任务未处于未处于临界区临界区就就立即立即把处理机分配给它。把处理机分配给它。重邮移通学院412022-3-27进程1进程2进程n实时进程实时进程实时进程要求调度实时进程要求调度实时进程运行实时进程运行非抢占轮转调度算法非抢占轮转调度算法调度时间调度时间重邮移通学院422022-3-27 当前进程实时进程实时进

25、程实时进程要求调度实时进程要求调度当前进程完成当前进程完成非抢占优先级调度算法非抢占优先级调度算法调度时间调度时间重邮移通学院432022-3-27 当前进程实时进程实时进程实时进程要求调度实时进程要求调度时钟中断到来时钟中断到来基于时钟中断的抢占式优先级调度算法基于时钟中断的抢占式优先级调度算法调度时间调度时间重邮移通学院442022-3-27 当前进程实时进程实时进程实时进程要求调度实时进程要求调度抢占并立即执行抢占并立即执行立即抢占的优先级调度算法立即抢占的优先级调度算法调度时间调度时间重邮移通学院452022-3-27q 最早截止时间优先算法即最早截止时间优先算法即EDF算法算法（EA

26、RLIEST DEADLINE FIRST）q 最低松弛优先算法即最低松弛优先算法即LLF算法（算法（LEAST LAXITY FIRST）重邮移通学院462022-3-271 1、最早截止时间优先调度算法、最早截止时间优先调度算法q根据任务的根据任务的开始截止时间开始截止时间来确定任务的优先级。来确定任务的优先级。截止时间愈早，其优先级愈截止时间愈早，其优先级愈高高；q在系统中保持一个实时任务在系统中保持一个实时任务就绪队列就绪队列，该队列按，该队列按各任务截止时间的早晚排序；调度程序选择队各任务截止时间的早晚排序；调度程序选择队首首任务任务分配处理机。分配处理机。q可采取抢占式和非抢占式调度。可采取抢占式和非抢占式调度。重邮移通学院472022-3-271 1、最早截止时间优先调度算法、最早截止时间优先调度算法（1）非抢占式调度方式用于非周期实时任务）非抢占式调度方式用于非周期实时任务1342开始截止时间任务执行任务到达12 341342t重邮移通学院482022-3-27A1 B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3 B2 A4B2A5