OS-04处理机调度1.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《OS-04处理机调度1.ppt》由会员分享,可在线阅读,更多相关《OS-04处理机调度1.ppt(92页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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、算法调度算法分级轮转法分级轮转法为了公平性,低优先级就绪队列的进程如果获为了公平性,低优先级就绪队列的进程如果获得调度,将得到比高优先级就绪队列进程更多得调度,将得到比高优先级就绪队列进程更多的时间片,加以弥补的时间片,加以弥补这样能大大降低长作业的交换频率,减少系统这样能大大降低长作业的交换频率,减少系统在交换作业时的时间消耗,又给了短作业较高在交换作业时的时间消耗,又给了短作业较高的优先级的优先级两个优先级队列特例:前台和后台进程。两个优先级队列特例:前台和后台进程。优先级调度算法:按进程的优先级调度优先级调度算法:按进程的优先级调度非抢占的优先级调度法非抢占的优先级调度法:一旦一个高优先
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- OS 04 处理机 调度
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内