《OS-04处理机调度1.ppt》由会员分享，可在线阅读，更多相关《OS-04处理机调度1.ppt（92页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4章章 处理机调度处理机调度处理器调度的类型处理器调度的类型调度算法调度算法传统的传统的UNIX调度调度多处理器调度多处理器调度实时调度实时调度Windows 2000调度调度UNIX SVR4调度调度Linux调度调度第第4章章 处理机调度处理机调度操作系统必须为多个进程可能有竞争的请求分配计算机资操作系统必须为多个进程可能有竞争的请求分配计算机资源。对处理器而言，可分配的资源是在处理器上的执行时源。对处理器而言，可分配的资源是在处理器上的执行时间，分配途径是调度间，分配途径是调度调度功能必须设计成可以满足多个目标，例如公平、任何调度功能必须设计成可以满足多个目标，例如公平、任何进程都不
2、会饿死、有效地使用处理器时间和低开销等进程都不会饿死、有效地使用处理器时间和低开销等调度功能还需要为某些进程的启动或结束考虑不同的优先调度功能还需要为某些进程的启动或结束考虑不同的优先级和实时最后期限级和实时最后期限调度已经实现了许多不同的算法。如今，调度研究的重点调度已经实现了许多不同的算法。如今，调度研究的重点是开发多处理器系统，特别是用于多线程应用的调度和实是开发多处理器系统，特别是用于多线程应用的调度和实时调度时调度4 处理器调度的类型处理器调度的类型多道程序的关键是调度。典型的调度类型有：多道程序的关键是调度。典型的调度类型有：长程调度长程调度(作业调度作业调度,高级调度）决定加入到
3、待高级调度）决定加入到待执行的进程池中执行的进程池中中程调度中程调度（交换调度（交换调度,中级调度）将进程调入内中级调度）将进程调入内存存,或者将进程交换到硬盘或者将进程交换到硬盘短程调度短程调度（进程调度，低级调度）决定哪一个（进程调度，低级调度）决定哪一个就绪进程将被处理器执行就绪进程将被处理器执行线程调度线程调度P86P86图图图图就绪就绪就绪就绪/挂起挂起挂起挂起新建新建新建新建就绪就绪就绪就绪运行运行运行运行退出退出退出退出阻塞阻塞阻塞阻塞短程调度短程调度短程调度短程调度阻塞阻塞阻塞阻塞/挂起挂起挂起挂起中程调度中程调度中程调度中程调度长程调度长程调度长程调度长程调度长程调度长程调度
4、长程调度长程调度中程调度中程调度中程调度中程调度处理器处理器处理器处理器就绪队列就绪队列就绪队列就绪队列就绪、挂起队列就绪、挂起队列就绪、挂起队列就绪、挂起队列短程调度短程调度短程调度短程调度释放释放释放释放超时超时超时超时阻塞、挂起队列阻塞、挂起队列阻塞、挂起队列阻塞、挂起队列阻塞队列阻塞队列阻塞队列阻塞队列事件等待事件等待事件等待事件等待交互用户交互用户交互用户交互用户批作业批作业批作业批作业长程调度长程调度长程调度长程调度中程调度中程调度中程调度中程调度中程调度中程调度中程调度中程调度事件事件事件事件发生发生发生发生用于调度的队列图用于调度的队列图用于调度的队列图用于调度的队列图下一次允
5、许哪一个进程进入的下一次允许哪一个进程进入的决策决策可以基于简单可以基于简单的先来先服务原则，或者也可以基于管理系统性的先来先服务原则，或者也可以基于管理系统性能的工具能的工具使用的原则包括优先级、期待执行时间和使用的原则包括优先级、期待执行时间和I/O需求需求同样，可以根据请求哪个同样，可以根据请求哪个I/O资源和试图平衡资源和试图平衡I/O使用的目的进行决策使用的目的进行决策长程调度长程调度 中程调度是交换功能的一部分，换入决策基于管中程调度是交换功能的一部分，换入决策基于管理多道程序程度的要求理多道程序程度的要求对不使用虚存的系统，存储器管理也是一个问题。对不使用虚存的系统，存储器管理也
6、是一个问题。因此，换入决策将考虑换出进程的存储需求因此，换入决策将考虑换出进程的存储需求中程调度中程调度从执行的频率看从执行的频率看长程调度程序的执行频率相对低些，并且仅仅是长程调度程序的执行频率相对低些，并且仅仅是粗略地决定是否接受新进程以及接受哪一个粗略地决定是否接受新进程以及接受哪一个为进行交换决策，中程调度程序执行得略微频繁为进行交换决策，中程调度程序执行得略微频繁一些一些短程调度程序，即分派程序执行得最频繁，并且短程调度程序，即分派程序执行得最频繁，并且精确地决定下一次执行哪一个进程精确地决定下一次执行哪一个进程短程调度短程调度4 调度算法调度算法进程调度的主要问题就是采用某种算法合
7、理有效地进程调度的主要问题就是采用某种算法合理有效地把处理机分配给进程把处理机分配给进程调度算法的设计原则：调度算法的设计原则：尽可能提高资源的利用率，减少处理机的空闲时间尽可能提高资源的利用率，减少处理机的空闲时间对于用户作业采用较合理的平均响应时间对于用户作业采用较合理的平均响应时间尽可能地增强处理机的处理能力，避免有些进程长期不尽可能地增强处理机的处理能力，避免有些进程长期不能投入运行能投入运行短程调度的主要目标是按照可以优化系统行为的短程调度的主要目标是按照可以优化系统行为的方式分配处理器时间。通常，需要相对于可能评方式分配处理器时间。通常，需要相对于可能评估的各种调度策略建立一组准则
8、估的各种调度策略建立一组准则使用的准则可以按两维来分类使用的准则可以按两维来分类面向用户的准则面向用户的准则面向系统的准则面向系统的准则短程调度准则面向用户准则所关心的性能指标面向用户准则所关心的性能指标周转时间周转时间 指一个进程从提交到完成之间的时间间隔，指一个进程从提交到完成之间的时间间隔，包括实际执行时间时间加上等待资源包括实际执行时间时间加上等待资源(包括处理器资源包括处理器资源)的时间。对批处理作业来说，这是一种很适宜的度量的时间。对批处理作业来说，这是一种很适宜的度量响应时间响应时间 对一个交互进程，这是从提交一个请求到开对一个交互进程，这是从提交一个请求到开始接收响应之间的时间
9、。该调度原则将试图达到较低的始接收响应之间的时间。该调度原则将试图达到较低的响应时间，并且在响应时间可接受的范围内，交互用户响应时间，并且在响应时间可接受的范围内，交互用户的数目最多的数目最多最后期限最后期限 当可以指定进程完成的最后期限时，调度原当可以指定进程完成的最后期限时，调度原则将服从于其他目标，使得距最后期限最近则将服从于其他目标，使得距最后期限最近短程调度准则短程调度准则其它：其它：带权的周转时间：带权的周转时间：周转时间与执行时间的比值周转时间与执行时间的比值可预测性可预测性 无论系统的负载如何，一个给定的工无论系统的负载如何，一个给定的工作运行的总时间量和总代价是相同的。用户不
10、希作运行的总时间量和总代价是相同的。用户不希望响应时间或周转时间的变化太大望响应时间或周转时间的变化太大短程调度准则短程调度准则面向面向系统准则所关心的性能指标系统准则所关心的性能指标吞吐量吞吐量 调度策略将试图使得每个时间单位完成的进调度策略将试图使得每个时间单位完成的进程数目最大。它取决于一个进程的平均长度，也受调程数目最大。它取决于一个进程的平均长度，也受调度策略的影响，调度策略会影响使用率度策略的影响，调度策略会影响使用率处理器使用率处理器使用率 这是处理器忙的时间百分比。对昂贵这是处理器忙的时间百分比。对昂贵的共享系统来说，这是一个重要的准则。在单用户系的共享系统来说，这是一个重要的
11、准则。在单用户系统和一些别的系统如实时系统中，这个准则与其他相统和一些别的系统如实时系统中，这个准则与其他相比显得不太重要比显得不太重要短程调度准则短程调度准则其它：其它：公平公平 在没有来自用户的指导或其他系统提供的指导时，在没有来自用户的指导或其他系统提供的指导时，进程应该被平等对待，没有一个进程会被饿死进程应该被平等对待，没有一个进程会被饿死强制优先级强制优先级 当进程被指定了优先级，调度策略会先选择当进程被指定了优先级，调度策略会先选择高优先级的进程高优先级的进程平衡资源平衡资源 调度策略将保持系统中所有资源忙，对负担较调度策略将保持系统中所有资源忙，对负担较重的资源使用较少的进程更受
12、欢迎。这个准则也可用于中重的资源使用较少的进程更受欢迎。这个准则也可用于中程调度和长程调度程调度和长程调度短程调度准则短程调度准则这些重要的调度准则是互相依赖的，不可能同时使这些重要的调度准则是互相依赖的，不可能同时使它们都达到最优它们都达到最优例如，提供较好的响应时间可能需要调度算法在进程间例如，提供较好的响应时间可能需要调度算法在进程间频繁地切换，这就增加了系统开销，降低了吞吐量频繁地切换，这就增加了系统开销，降低了吞吐量设计一个调度策略涉及到在互相竞争的各种要求之设计一个调度策略涉及到在互相竞争的各种要求之间进行折衷，根据系统的本质和使用情况，给各种间进行折衷，根据系统的本质和使用情况，
13、给各种要求设定相对权值要求设定相对权值在大多数交互式操作系统中，不论是单用户系统还在大多数交互式操作系统中，不论是单用户系统还是分时系统，适当的响应时间是最重要的要求是分时系统，适当的响应时间是最重要的要求短程调度准则短程调度准则作业调度性能评价（作业调度性能评价（p90）平均周转时间平均周转时间带权的平均周转时间带权的平均周转时间进程调度性能评价（进程调度性能评价（p93）可靠性可靠性简洁性简洁性CPUCPU利用率利用率进程在就绪队列的等待时间和执行时间比进程在就绪队列的等待时间和执行时间比进程调度进程调度根据已占有处理机的进程是否可被剥夺这一原则，根据已占有处理机的进程是否可被剥夺这一原则
14、，调度方式（策略）可分为：调度方式（策略）可分为：非剥夺方式：非剥夺方式：一旦某个就绪进程分得处理机之后，一旦某个就绪进程分得处理机之后，只要不是其自身的原因被阻塞只要不是其自身的原因被阻塞 (如要求如要求I/OI/O操作操作)而不能继续运行时，就一直运行下去，直至运行而不能继续运行时，就一直运行下去，直至运行结束结束缺点：紧急进程无法立即运行，实时性差；缺点：紧急进程无法立即运行，实时性差；短进程周转时间长，公平性差。短进程周转时间长，公平性差。进程调度方式进程调度方式剥夺方式：剥夺方式：当一个正在运行的进程没有运行完时，当一个正在运行的进程没有运行完时，系统采取某种手段强行剥夺已分配给该进
15、程的处理系统采取某种手段强行剥夺已分配给该进程的处理器资源。而被剥夺的进程重新回到就绪队列中等待器资源。而被剥夺的进程重新回到就绪队列中等待在剥夺方式下，可以通过剥夺处理器所有权的方式，在剥夺方式下，可以通过剥夺处理器所有权的方式，暂停当前进程的运行，已满足更紧急进程的处理要暂停当前进程的运行，已满足更紧急进程的处理要求。求。进程调度方式进程调度方式进程调度方式进程调度方式v有三个进程有三个进程p1，p2，p3到达时间为：到达时间为：0，3，4，优先级依，优先级依次增高，运行所需的时间分别为次增高，运行所需的时间分别为20，4，2，假设现按优先，假设现按优先级策略调度执行，并且不采用时间片原则
16、，请分别求出非剥级策略调度执行，并且不采用时间片原则，请分别求出非剥夺方式和剥夺方式下各个进程的周转时间。夺方式和剥夺方式下各个进程的周转时间。P1P1（2020）P3(2)P3(2)P2(4)P2(4)周转时间：周转时间：周转时间：周转时间：p1p12020；p2p22323；p3p31818P1P1（1717）P3(2)P3(2)P2(1)P2(1)P1(3P1(3)P2(3P2(3)周转时间：周转时间：周转时间：周转时间：p1p12626；p2p26 6；p3p32 2当时间片为当时间片为当时间片为当时间片为5 5时，采用优先级策略，问非剥夺和剥时，采用优先级策略，问非剥夺和剥时，采用优
17、先级策略，问非剥夺和剥时，采用优先级策略，问非剥夺和剥夺方式下，求各进程的周转时间和响应时间夺方式下，求各进程的周转时间和响应时间夺方式下，求各进程的周转时间和响应时间夺方式下，求各进程的周转时间和响应时间先来先服务先来先服务先来先服务先来先服务 (FCFS First Come First Service)(FCFS First Come First Service)按照进程就绪的先后顺序来调度进程，到达的按照进程就绪的先后顺序来调度进程，到达的按照进程就绪的先后顺序来调度进程，到达的按照进程就绪的先后顺序来调度进程，到达的越早，其优先级越高越早，其优先级越高越早，其优先级越高越早，其优先级
18、越高获得处理机的进程，在未遇到其他情况时一直获得处理机的进程，在未遇到其他情况时一直获得处理机的进程，在未遇到其他情况时一直获得处理机的进程，在未遇到其他情况时一直运行下去运行下去运行下去运行下去采用的是非剥夺方式采用的是非剥夺方式采用的是非剥夺方式采用的是非剥夺方式系统只需具备一个先进先出的队列，在管理优系统只需具备一个先进先出的队列，在管理优系统只需具备一个先进先出的队列，在管理优系统只需具备一个先进先出的队列，在管理优先级的就绪队列时，这种方法是一种最常见策先级的就绪队列时，这种方法是一种最常见策先级的就绪队列时，这种方法是一种最常见策先级的就绪队列时，这种方法是一种最常见策略，并且在没
19、有其他信息时，也是一种最合理略，并且在没有其他信息时，也是一种最合理略，并且在没有其他信息时，也是一种最合理略，并且在没有其他信息时，也是一种最合理的策略的策略的策略的策略调度算法调度算法p93p93轮转调度轮转调度轮转调度轮转调度 (简单轮转法简单轮转法简单轮转法简单轮转法RRRR)系统把所有就绪进程按先后次序排队，处理机总是优先系统把所有就绪进程按先后次序排队，处理机总是优先系统把所有就绪进程按先后次序排队，处理机总是优先系统把所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个就绪进程，并分配它一个固分配给就绪队列中的第一个就绪进程，并分配它一个固分配给就绪队列中的第一个就
20、绪进程，并分配它一个固分配给就绪队列中的第一个就绪进程，并分配它一个固定的时间片定的时间片定的时间片定的时间片 (如如如如50505050毫秒毫秒毫秒毫秒)当该运行进程用完规定的时间片时，被迫释放处理机给当该运行进程用完规定的时间片时，被迫释放处理机给当该运行进程用完规定的时间片时，被迫释放处理机给当该运行进程用完规定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程下一个处于就绪队列中的第一个进程下一个处于就绪队列中的第一个进程下一个处于就绪队列中的第一个进程,自己回到就绪队列自己回到就绪队列自己回到就绪队列自己回到就绪队列的尾部，并等待下次调度的尾部，并等待下次调度的尾部，并等待
21、下次调度的尾部，并等待下次调度 当某个正在运行的进程的时间片尚未用完，但进程需要当某个正在运行的进程的时间片尚未用完，但进程需要当某个正在运行的进程的时间片尚未用完，但进程需要当某个正在运行的进程的时间片尚未用完，但进程需要 I/OI/OI/OI/O时，该进程被送到相应阻塞队列，等时，该进程被送到相应阻塞队列，等时，该进程被送到相应阻塞队列，等时，该进程被送到相应阻塞队列，等I/OI/OI/OI/O完成重新返完成重新返完成重新返完成重新返回到就绪队列尾部，等待调度。回到就绪队列尾部，等待调度。回到就绪队列尾部，等待调度。回到就绪队列尾部，等待调度。调度算法调度算法简单轮转法简单轮转法简单轮转法
22、简单轮转法RRRR处理器处理器处理器处理器就绪队列就绪队列就绪队列就绪队列阻塞队列阻塞队列阻塞队列阻塞队列分派分派分派分派释放释放释放释放超时超时超时超时等待事件等待事件等待事件等待事件事件发生事件发生事件发生事件发生轮转调度轮转调度简单轮转法是以就绪队列中的所有进程均以相同的速简单轮转法是以就绪队列中的所有进程均以相同的速度往前推进为其特征。其时间片的长短，影响着进程度往前推进为其特征。其时间片的长短，影响着进程的进展速度的进展速度当就绪进程很多时，如果时间片很长，就会影响一些当就绪进程很多时，如果时间片很长，就会影响一些需要需要“紧急紧急”运行的作业。同样这对短作业和要求运行的作业。同样这
23、对短作业和要求 I/O 操作多的作业显然是不利的操作多的作业显然是不利的因而，在简单轮转法的基础上又提出了分级轮转法因而，在简单轮转法的基础上又提出了分级轮转法调度算法调度算法分级轮转法分级轮转法将一个就绪队列根据进程的优先级不同，划分二将一个就绪队列根据进程的优先级不同，划分二个或二个以上的就绪队列，并赋给每个队列不同个或二个以上的就绪队列，并赋给每个队列不同的优先级的优先级一般情况下，调度算法把相同的时间片分配给优一般情况下，调度算法把相同的时间片分配给优先级高的就绪队列中的队首进程先级高的就绪队列中的队首进程只有当优先级高的就绪队列中的所有进程全部运只有当优先级高的就绪队列中的所有进程全
24、部运行完毕或等待行完毕或等待I/OI/O操作而没有进程运行时，才把操作而没有进程运行时，才把处理机分配给低优先级就绪队列中的进程处理机分配给低优先级就绪队列中的进程调度算法调度算法高优先级就绪队列高优先级就绪队列高优先级就绪队列高优先级就绪队列低优先级就绪队列低优先级就绪队列低优先级就绪队列低优先级就绪队列处理器处理器处理器处理器分级轮转调度分级轮转调度分级轮转调度分级轮转调度分派分派分派分派超时超时超时超时等待事件等待事件等待事件等待事件阻塞队列阻塞队列阻塞队列阻塞队列释放释放释放释放超时超时超时超时事件发生事件发生事件发生事件发生高优先级队列空高优先级队列空高优先级队列空高优先级队列空调度
25、算法调度算法分级轮转法分级轮转法为了公平性，低优先级就绪队列的进程如果获为了公平性，低优先级就绪队列的进程如果获得调度，将得到比高优先级就绪队列进程更多得调度，将得到比高优先级就绪队列进程更多的时间片，加以弥补的时间片，加以弥补这样能大大降低长作业的交换频率，减少系统这样能大大降低长作业的交换频率，减少系统在交换作业时的时间消耗，又给了短作业较高在交换作业时的时间消耗，又给了短作业较高的优先级的优先级两个优先级队列特例：前台和后台进程。两个优先级队列特例：前台和后台进程。优先级调度算法：按进程的优先级调度优先级调度算法：按进程的优先级调度非抢占的优先级调度法非抢占的优先级调度法：一旦一个高优先
26、级的进程占有：一旦一个高优先级的进程占有了处理器，就一直运行下去，直到因等待某事被阻塞或了处理器，就一直运行下去，直到因等待某事被阻塞或执行结束，才选择就绪队列中优先级最高的进程来执行。执行结束，才选择就绪队列中优先级最高的进程来执行。可抢占的优先级调度法可抢占的优先级调度法：任何时刻都按照高优先级进程：任何时刻都按照高优先级进程在处理器上运行的原则进行进程调度。当一高优先级进在处理器上运行的原则进行进程调度。当一高优先级进程运行时，若有一更高优先级进程到达就绪队列，则当程运行时，若有一更高优先级进程到达就绪队列，则当前运行进程立刻将处理器让给更高优先级的进程（即使前运行进程立刻将处理器让给更
27、高优先级的进程（即使未处理完，也无遇到阻塞情况）未处理完，也无遇到阻塞情况）调度算法调度算法动态优先级法动态优先级法指进程的优先级在该进程的生存期间可以改变指进程的优先级在该进程的生存期间可以改变大多数动态优先级设计方案大多数动态优先级设计方案把交互式和把交互式和I/OI/O频繁的进程移到优先级队列的顶端，而频繁的进程移到优先级队列的顶端，而让计算量大的进程移到较低的优先级上让计算量大的进程移到较低的优先级上对与优先级相同的进程，按先来先服务或轮转法则分对与优先级相同的进程，按先来先服务或轮转法则分配处理机配处理机对于一给定时间周期，一个正在运行的进程，每请求对于一给定时间周期，一个正在运行的
28、进程，每请求一次一次I/OI/O操作后其优先级就自动加操作后其优先级就自动加 1 1，直接反映出，直接反映出I/OI/O请求的频率，从而使请求的频率，从而使I/OI/O设备具有很高的利用率设备具有很高的利用率调度算法调度算法最短进程最短进程SPN（短进程优先调度算法）（短进程优先调度算法）减少减少FCFSFCFS固有的对长进程的偏爱的另一种方法是固有的对长进程的偏爱的另一种方法是最短进程最短进程 (SPN)(SPN)策略，策略，这是一种非剥夺的策略这是一种非剥夺的策略，其原则是下一次选择所需处理时间最短的进程，其原则是下一次选择所需处理时间最短的进程，因此，短进程将会越过长进程，跳到队列头因此
29、，短进程将会越过长进程，跳到队列头SPNSPN策略的难点在于需要知道或至少需要估计每策略的难点在于需要知道或至少需要估计每个进程所需要的处理时间个进程所需要的处理时间长进程可能被长进程可能被“饿死饿死”调度算法调度算法最短剩余时间优先调度算法最短剩余时间优先调度算法(SRT)对对SPNSPN增加剥夺机制。当一个时钟中断周期到后，增加剥夺机制。当一个时钟中断周期到后，调度程序总是调度程序总是选择预期剩余时间最短选择预期剩余时间最短的进程的进程当一个新进程加入就绪队列时，它可能比当前运当一个新进程加入就绪队列时，它可能比当前运行的进程具有更短的剩余时间，因此，调度程序行的进程具有更短的剩余时间，因
30、此，调度程序将剥夺当前程序，将处理器分配给新进程。将剥夺当前程序，将处理器分配给新进程。和和SPNSPN一样，调度程序必须有关于处理时间的估一样，调度程序必须有关于处理时间的估计，并且存在长进程被饿死的危险计，并且存在长进程被饿死的危险调度算法调度算法最高响应比优先调度算法（最高响应比优先调度算法（HRRN）响应比：响应比：R=(w+s)/s=1+w/sR=(w+s)/s=1+w/s w w表示等待时间；表示等待时间；s s表示执行所需时间表示执行所需时间最高响应比也是对最短进程法的一种改进，当当最高响应比也是对最短进程法的一种改进，当当前进程完成或被阻塞时，前进程完成或被阻塞时，选择响应比最
31、大的进程选择响应比最大的进程先执行先执行，是一种，是一种非剥夺非剥夺的策略。的策略。响应比响应比R R，代表了进程的年龄，算法在保证短进，代表了进程的年龄，算法在保证短进程优先的同时又兼顾了长进程程优先的同时又兼顾了长进程折中折中调度算法调度算法最高响应比优先调度算法（最高响应比优先调度算法（HRRN）R=(w+s)/s=1+w/sR=(w+s)/s=1+w/s当一系列进程同时进入系统时，由于短作业当一系列进程同时进入系统时，由于短作业s s值值小，小，R R值就大，因此短作业得到了优先执行。值就大，因此短作业得到了优先执行。但随着长作业等待的时间但随着长作业等待的时间(w)(w)增长，增长，
32、R R值不断增大，值不断增大，到达一定的等待时间，长进程最终将凭借年龄的到达一定的等待时间，长进程最终将凭借年龄的增长战胜短进程，从而获得处理器。增长战胜短进程，从而获得处理器。可见，在可见，在HRRNHRRN算法中，长作业不会被饿死算法中，长作业不会被饿死 调度算法调度算法反馈反馈FB（多级反馈队列调度算法）（多级反馈队列调度算法）分级轮转调度和动态优先级算法的结合，分级轮转调度和动态优先级算法的结合，采用剥夺策略采用剥夺策略划分多个就绪队列，优先级逐步降低。划分多个就绪队列，优先级逐步降低。新建进程进入优先级最高的队列中，每当进程规定的时新建进程进入优先级最高的队列中，每当进程规定的时间片
33、用完，被剥夺时，就送往低一级的就绪队列。间片用完，被剥夺时，就送往低一级的就绪队列。进程调度时总是先执行高优先级队列中的进程。高优先进程调度时总是先执行高优先级队列中的进程。高优先级队列为空后，才转去处理低一级优先级队列中的进程。级队列为空后，才转去处理低一级优先级队列中的进程。同一优先级队列（除最低）的进程，按同一优先级队列（除最低）的进程，按FIFOFIFO机制调度。机制调度。最低优先级队列，按时间片轮转调度算法执行最低优先级队列，按时间片轮转调度算法执行调度算法调度算法允许进入允许进入允许进入允许进入CPUCPURQ0RQ0RQ1RQ1RQ2RQ2RQnRQn释放释放释放释放CPUCPU
34、释放释放释放释放CPUCPU释放释放释放释放CPUCPU释放释放释放释放反馈调度反馈调度反馈调度反馈调度不同优先级的不同优先级的不同优先级的不同优先级的就绪队列可以就绪队列可以就绪队列可以就绪队列可以给予相同的时给予相同的时给予相同的时给予相同的时间片，也可以间片，也可以间片，也可以间片，也可以不同。不同。不同。不同。调度算法调度算法反馈反馈FB在反馈调度算法中，长进程也存在饿死的现象在反馈调度算法中，长进程也存在饿死的现象当比运行进程更高优先级队列到来一个新进程时，则当比运行进程更高优先级队列到来一个新进程时，则应该处理高优先级队列的进程。有两种方案：应该处理高优先级队列的进程。有两种方案：
35、抢占方式：即当高优先级进程到来时，立即抢占处抢占方式：即当高优先级进程到来时，立即抢占处理进程的处理器，被抢占进程回到原来就绪队列的理进程的处理器，被抢占进程回到原来就绪队列的末尾。末尾。非抢占方式：当前进程用完规定的时间片后，再调非抢占方式：当前进程用完规定的时间片后，再调度高优先级的进程。度高优先级的进程。调度算法调度算法反馈反馈FB对于被阻塞的进程，当阻塞取消后的处理方法：对于被阻塞的进程，当阻塞取消后的处理方法：进入低一级的就绪队列进入低一级的就绪队列回到原就绪队列回到原就绪队列放入高一级的就绪队列中放入高一级的就绪队列中时间片的长短由如下四个因素决定：时间片的长短由如下四个因素决定：
36、系统的响应时间系统的响应时间 当进程数目一定时，时间片的长短直接当进程数目一定时，时间片的长短直接影响系统的响应时间影响系统的响应时间就绪队列中进程的数目就绪队列中进程的数目 当系统对响应时间要求一定时，当系统对响应时间要求一定时，就绪队列中进程数少则时间片长，反之亦然就绪队列中进程数少则时间片长，反之亦然进程状态转换进程状态转换(即进程由就绪态到运行，或反之即进程由就绪态到运行，或反之)的时间的时间开销开销计算机本身的处理能力计算机本身的处理能力 执行速度和可运行作业的道数执行速度和可运行作业的道数调度算法调度算法调度算法例题调度算法例题v现有现有5各进程，到达就绪队列的时间和所需的服务各进
37、程，到达就绪队列的时间和所需的服务时间如下表所示时间如下表所示 求求：FCFS,RR(q=1、4),SPN,SRT,HRRN,FB(q=1、2i)进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE先来先服务先来先服务先来先服务先来先服务(FCFS)(FCFS)调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE01234567
38、8910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE循环循环循环循环(RR)(RR)q q=1=1调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE循环循环循环循环(RR)(RR)q q=4=4调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C4
39、4D65E82012345678910111213141516171819ABCDE最短进程最短进程最短进程最短进程Next(SPN)Next(SPN)调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE01
40、2345678910111213141516171819ABCDE最短剩余最短剩余最短剩余最短剩余时间时间时间时间 (SPT)(SPT)调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE最高响应比最高响应比最高响应比最高响应比(HRRN)(HRRN)调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE0
41、12345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE反馈反馈反馈反馈(队列有队列有队列有队列有2 2个）个）个）个）q q=1=1调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE反馈（采用剥夺方式）反馈（采用剥夺方式）反馈（采用剥夺方式）反馈（采用剥夺方式）
42、q q=2=2i i调度算法例题调度算法例题进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82各种调度算法各有其特点，但分级轮转法和反馈各种调度算法各有其特点，但分级轮转法和反馈法较为理想法较为理想除了从就绪进程中选取一合理的进程投入运行外，除了从就绪进程中选取一合理的进程投入运行外，进程调度程序还必须给该进程分配运行时间片进程调度程序还必须给该进程分配运行时间片为了保证终端用户提供服务请求之后，能及时得为了保证终端用户提供服务请求之后，能及时得到响应，一般规定的时间片在几十毫秒到几百毫到响应，一般规定的时间片在几十毫秒到几百毫秒之间不等秒之间不等调度算法调度算法可以可以可
43、以可以有针对性地确定时间片的长短，让运行时间长的进程在有针对性地确定时间片的长短，让运行时间长的进程在有针对性地确定时间片的长短，让运行时间长的进程在有针对性地确定时间片的长短，让运行时间长的进程在不太频繁的时间间隔里获得较大的时间片不太频繁的时间间隔里获得较大的时间片不太频繁的时间间隔里获得较大的时间片不太频繁的时间间隔里获得较大的时间片让经常相互制约的进程有更多的机会获得处理机，但每次获让经常相互制约的进程有更多的机会获得处理机，但每次获让经常相互制约的进程有更多的机会获得处理机，但每次获让经常相互制约的进程有更多的机会获得处理机，但每次获得的时间片应较短得的时间片应较短得的时间片应较短得
44、的时间片应较短系统优先考虑那些短的、相互制约的进程，而要求时间片长系统优先考虑那些短的、相互制约的进程，而要求时间片长系统优先考虑那些短的、相互制约的进程，而要求时间片长系统优先考虑那些短的、相互制约的进程，而要求时间片长的进程虽然不经常运行，但其运行周期较长，能减少处理机的进程虽然不经常运行，但其运行周期较长，能减少处理机的进程虽然不经常运行，但其运行周期较长，能减少处理机的进程虽然不经常运行，但其运行周期较长，能减少处理机分配所造成的开销分配所造成的开销分配所造成的开销分配所造成的开销进程调度算法有许多种，在具体实施中，是将几种算法结合进程调度算法有许多种，在具体实施中，是将几种算法结合进
45、程调度算法有许多种，在具体实施中，是将几种算法结合进程调度算法有许多种，在具体实施中，是将几种算法结合起来使用，这样效率更高起来使用，这样效率更高起来使用，这样效率更高起来使用，这样效率更高选择调度策略选择调度策略因等待因等待因等待因等待I/OI/O而堵塞而堵塞而堵塞而堵塞运行运行运行运行高优先级高优先级高优先级高优先级就绪就绪就绪就绪低优先级低优先级低优先级低优先级就绪就绪就绪就绪首先选择首先选择首先选择首先选择其次选择其次选择其次选择其次选择超过时间片超过时间片超过时间片超过时间片请求请求请求请求I/OI/OI/OI/O完成完成完成完成调度时的进程状态变迁图调度时的进程状态变迁图调度时的进
46、程状态变迁图调度时的进程状态变迁图分析其使用的调度策略与调度算法分析其使用的调度策略与调度算法分析其使用的调度策略与调度算法分析其使用的调度策略与调度算法分析这一调度策略的设计出发点分析这一调度策略的设计出发点分析这一调度策略的设计出发点分析这一调度策略的设计出发点调度算法分析：调度算法分析：将就绪进程分成高和低优先级两个队列。如果进将就绪进程分成高和低优先级两个队列。如果进程运行中超过了规定的时间片就进入低优先级队程运行中超过了规定的时间片就进入低优先级队列，而列，而I/OI/O操作完成的进程，即由阻塞状态进入操作完成的进程，即由阻塞状态进入高优先级就绪队列高优先级就绪队列调度算法是调度算法
47、是:首先从高优先就绪队列中选择一个首先从高优先就绪队列中选择一个进程来运行，如果在高优先级就绪队列中没有进进程来运行，如果在高优先级就绪队列中没有进程，则从低优先级就绪队列中选择一个进程运行程，则从低优先级就绪队列中选择一个进程运行调度时的进程状态图调度时的进程状态图此算法此算法对于要求对于要求 I/O 量大的就绪进程有利量大的就绪进程有利(高优先级高优先级)，而对，而对于那些于那些计算量大的就绪进程不利计算量大的就绪进程不利(未计算完毕就进入低优先未计算完毕就进入低优先级就绪队列级就绪队列)由于外部设备的运行速度大大低于主机的运行速度，所以为由于外部设备的运行速度大大低于主机的运行速度，所以
48、为了保持了保持I/O通道和设备处于忙碌状态，受通道和设备处于忙碌状态，受I/O限制的进程优先限制的进程优先于受于受CPU限制的进程运行。只有当所有的受限制的进程运行。只有当所有的受I/O限制的进程限制的进程全部被阻塞，才选取某个受全部被阻塞，才选取某个受CPU限制的低优先级就绪进程在限制的低优先级就绪进程在处理机上运行处理机上运行对交互式用户来说，对交互式用户来说，这个策略提供了良好的响应这个策略提供了良好的响应，也保持了，也保持了I/O和中央处理机之间的高度并行和中央处理机之间的高度并行调度时的进程状态图调度时的进程状态图在大多数传统的多处理器系统中，进程并不是被指定到一个在大多数传统的多处
49、理器系统中，进程并不是被指定到一个专门的处理器。不是所有处理器只有一个队列专门的处理器。不是所有处理器只有一个队列而是有多条基于优先级的队列，并且都送进相同的处理器池而是有多条基于优先级的队列，并且都送进相同的处理器池中。在任何情况下，我们都可以把系统看作是多服务器排队中。在任何情况下，我们都可以把系统看作是多服务器排队结构结构对各种情况进行分析，对于多处理器，调度原则的选择没有对各种情况进行分析，对于多处理器，调度原则的选择没有在单处理器中显得重要。因此，在多处理器系统中使用简单在单处理器中显得重要。因此，在多处理器系统中使用简单的的FCFS(先来先服务先来先服务)原则或者在静态化先级方案中
50、使用原则或者在静态化先级方案中使用FCFS就足够了就足够了多处理器进程调度多处理器进程调度CPUCPU就绪队列就绪队列就绪队列就绪队列n n释放释放释放释放CPUCPU释放释放释放释放CPUCPU释放释放释放释放CPUCPU释放释放释放释放多处理器调度多处理器调度多处理器调度多处理器调度就绪队列就绪队列就绪队列就绪队列3 3就绪队列就绪队列就绪队列就绪队列2 2就绪队列就绪队列就绪队列就绪队列1 1分派分派分派分派CPUCPU池池池池在单处理器中在单处理器中，线程可以用作辅助构造程序，并，线程可以用作辅助构造程序，并在处理过程在处理过程中重叠执行中重叠执行I/O。由于在进行线程切换时的性能损失