04 处理机调度.ppt

《04 处理机调度.ppt》由会员分享，可在线阅读，更多相关《04 处理机调度.ppt（56页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四章第四章 处理机调度处理机调度4.1 分级调度4.2 作业调度4.3 进程调度4.4 调度算法 处理机调度的工作是对处理机调度的工作是对CPU资源进行合理的分配使用，资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。以提高处理机利用率，并使各用户公平地得到处理机资源。所以，本章的主要问题是：所以，本章的主要问题是：n n 学习目标：1 1.掌握掌握：作业和进程的关系、作业的状态及其转换；：作业和进程的关系、作业的状态及其转换；作业调度和进程调度的功能；常用的调度算法。作业调度和进程调度的功能；常用的调度算法。2 2.理解理解：性能评价标准；调度算法的评价。：性能评

2、价标准；调度算法的评价。3 3.了解了解：其他调度算法。：其他调度算法。n n 学习要点：本章的重点在于掌握系统中对本章的重点在于掌握系统中对作业和进程如何实作业和进程如何实施调度施调度，作业调度和进程，作业调度和进程调度的功能调度的功能；掌握；掌握常用调度常用调度算法的实现思想算法的实现思想，并能计算出各个算法的，并能计算出各个算法的性能指标性能指标；能简单分析常用调度算法的性能。能简单分析常用调度算法的性能。4.1 分级调度分级调度返回1.调度层次2.作业的状态及转换3.作业和进程的关系4.调度的性能准则 调度：选出待分派的作业或进程。处理机调度的目的是分配调度：选出待分派的作业或进程。处

3、理机调度的目的是分配处理机。处理机。1.调度层次调度层次n n高级调度（宏观调度、作业调度）n n把外存上处于后备队列中的那些作业调入内存，把外存上处于后备队列中的那些作业调入内存，并创建进程，分配资源，将进程加入就绪队列。并创建进程，分配资源，将进程加入就绪队列。由于这种调度由于这种调度决定哪些作业可以进入系统决定哪些作业可以进入系统，所以，所以也称也称收容调度收容调度。作业一旦被系统收容，就便成进。作业一旦被系统收容，就便成进程或进程组。程或进程组。n n中级调度（交换调度：内外存交换）n n从存储器资源的角度看，将把暂时不能运行的进从存储器资源的角度看，将把暂时不能运行的进程调至外存就绪

4、，将当前所需部分换入到内存，程调至外存就绪，将当前所需部分换入到内存，提高内存利用率和系统吞吐量。提高内存利用率和系统吞吐量。中级调度实际上中级调度实际上是存储器之间的对换。是存储器之间的对换。n n低级调度（微观调度、进程调度）n n决定就绪队列中的哪个进程应获得处理机决定就绪队列中的哪个进程应获得处理机（即低（即低级调度是将处理机分配给进程）级调度是将处理机分配给进程），低级调度是由，低级调度是由每秒可操作许多次的处理机调度程序执行，处理每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。机调度程序应常驻内存。n n两种调度方式：两种调度方式：非抢占方式：进程一直执行直到完成或

5、发生某事件被阻塞。抢占方式：由于优先权、短作业优先或时间片到等因素，终止现行进程。n n线程调度：可有OS内核完成，也可由用户程序进行。调度队列模型调度队列模型仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型就 绪 队 列阻 塞 队 列CPU时间片完交互用户进程调度进程完成等待事件事件发生 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型就 绪 队 列阻 塞 队 列CPU时间片完作业调度进程调度进程完成等待事件1阻 塞 队 列阻 塞 队 列等待事件2等待事件n事件1发生事件2发生事件n发生后 备 队 列 具有高、低、中三级调度的调度队列模型具有高、低、中三级调度的调度队

6、列模型就 绪 队 列绪就、挂 起 队 列CPU时间片完作业调度进程调度进程完成事件出现阻 塞 队 列挂起等待事件中级调度事件发生后 备 队 列塞阻、挂 起 队 列挂起2.作业的状态及其转换作业的状态及其转换 作业从提交给系统，直到完成任务退出系统前，在整个活动过程中它会处于不同的状态。通常，作业的状态分为：提交、后备（收容）、运行和完成。提交状态：一个作业处于从输入设备进入外部存储设备的过程时所处的状态后备状态：作业的全部信息都已通过输入设备输入作业的输入井中等待进入内存。运行状态：作业一旦被作业调度程序选中，分配所需的资源，为其建立进程，而被送入内存中投入运行。完成状态：作业完成其全部运行，

7、释放出其所占用的资源，准备退出系统时的作业。作业状态及其转换图 spoolingspooling系统系统提交提交后备后备外存外存就绪就绪等待等待运行运行就绪就绪等待等待交换调度交换调度完完成成作业调度作业调度进程调度进程调度线程调度线程调度3.作业与进程的关系作业与进程的关系 作业是用户向计算机提交任务的任务实体；进程是计算机为了完成用户任务实体而设置的执行实体。计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。分时系统中无作业的概念，进程几乎存在于所有多道程序设计系统中。4.调度的性能准则 我们可从不同的角度来判断调度算法的我们可从不同的角度来判断调

8、度算法的性能，如性能，如用户的角度用户的角度、处理机的角度处理机的角度和和算算法实现的角度法实现的角度。实际的调度算法选择是一。实际的调度算法选择是一个综合的判断结果。个综合的判断结果。面向用户的调度性能准则面向用户的调度性能准则n n周转时间：周转时间：作业从提交到完成（得到结果）所作业从提交到完成（得到结果）所经历的时间。包括：在后备队列中等待，经历的时间。包括：在后备队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输上执行，就绪队列和阻塞队列中等待，结果输出等待出等待批处理系统批处理系统n n平均周转时间平均周转时间Tn n平均带权周转时间平均带权周转时间W（带权周转时间带权周转

9、时间W是是 T(周转周转)/T(CPU执行执行)n n响应时间：响应时间：用户输入一个请求（如击键）到系用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间统给出首次响应（如屏幕显示）的时间分分时系统时系统面向系统的调度性能准则面向系统的调度性能准则n n吞吐量：吞吐量：吞吐量：吞吐量：单位时间内所完成的作业数，跟作业本身特性和调单位时间内所完成的作业数，跟作业本身特性和调单位时间内所完成的作业数，跟作业本身特性和调单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系度算法都有关系度算法都有关系度算法都有关系批处理系统。批处理系统。批处理系统。批处理系统。n n平均周转时间平

10、均周转时间平均周转时间平均周转时间不是吞吐量的倒数，因为并发执行的作业在不是吞吐量的倒数，因为并发执行的作业在不是吞吐量的倒数，因为并发执行的作业在不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在时间上可以重叠。如：在时间上可以重叠。如：在时间上可以重叠。如：在2 2小时内完成小时内完成小时内完成小时内完成4 4个作业，而每个周个作业，而每个周个作业，而每个周个作业，而每个周转时间是转时间是转时间是转时间是1 1小时，则吞吐量是小时，则吞吐量是小时，则吞吐量是小时，则吞吐量是2 2个作业个作业个作业个作业/小时。小时。小时。小时。n n处理机利用率：处理机利用率：处理机利用率：处理

11、机利用率：大中型主机。大中型主机。大中型主机。大中型主机。n n各种设备的均衡利用：各种设备的均衡利用：各种设备的均衡利用：各种设备的均衡利用：如如如如CPUCPU繁忙的作业和繁忙的作业和繁忙的作业和繁忙的作业和I/OI/O繁忙的作业繁忙的作业繁忙的作业繁忙的作业搭配搭配搭配搭配大中型主机。大中型主机。大中型主机。大中型主机。公平性：公平性：不因作业或进程本身的特性而使上述指标过分恶化。不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。如长作业等待很长时间。优先级：优先级：可以使关键任务达到更好的指标。可以使关键任务达到更好的指标。调度算法本身的调度性能准则调度算法本身的调度

12、性能准则n易于实现易于实现n执行开销比执行开销比4.2 作业调度作业调度返回1.作业控制块2.作业调度及功能3.作业调度目标与性能衡量 作业调度的任务：完成作业从后备状态到运行状态的转变，以及从运行态到完成态的转变。1.1.作业控制块作业控制块 在多道批处理系统中通常有若干作业被收容在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。内容：作业名、作业状态、作业调度，以及资源申请和一些控制信息。作业控制块JCB作业名作业名作业名作业名作业类型作业类型作业类型作业类型资源要求资源要求资源要求资源要求资源使用情况资源使用情况资源使用情况

13、资源使用情况 优先级优先级优先级优先级当前状态当前状态当前状态当前状态其它其它其它其它2.作业调度及功能 作业调度的任务：完成作业从后备状态到运行状态的转变，以及从运行态到完成态的转变。作业调度的转换过程 (1)作业从后备状态到执行状态 P85(a)框图 (2)作业从执行状态到完成状态 P85(b)框图后备作业队列空按调度算法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建立进程进程调度否是出口作业从后备状态到执行状态作业从后备状态到执行状态是调用存储管理、设备管理程序回收分配该作业的全部资源要求撤消该作业的所有进程及作业的JCB调用

14、统计程序，计算该作业的执行费用调度下一个作业作业从执行状态到完成状态作业从执行状态到完成状态作业调度的功能作业调度的功能 具体说来，作业调度的功能如下：记录系统中各个作业的情况；（记录情况）按照某种调度算法从后备作业队列中选取作业；（挑选作业）为被选取的作业分配内存和外设资源；（分配资源）为选中的作业建立相应的进程。（建立进程）在作用运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还有完成作业的善后处理工作，如收回分配给他的全部资源，它们将从系统中撤消。（善后处理）3.作业调度的目标与性能衡量 调度的目标调度的目标 对所有作业应该是公平合理 应使设备有高的利用率 每天执行尽可能多的作业

15、有快的响应时间 要设计一个理想的调度算法是一件十分困难的要设计一个理想的调度算法是一件十分困难的要设计一个理想的调度算法是一件十分困难的要设计一个理想的调度算法是一件十分困难的事事事事,在实际系统中，调度算法往往折衷考虑。在实际系统中，调度算法往往折衷考虑。在实际系统中，调度算法往往折衷考虑。在实际系统中，调度算法往往折衷考虑。设计调设计调设计调设计调度算法时应考虑的因素：度算法时应考虑的因素：度算法时应考虑的因素：度算法时应考虑的因素：n n 调度算法应与系统设计目标保持一致调度算法应与系统设计目标保持一致调度算法应与系统设计目标保持一致调度算法应与系统设计目标保持一致n n 注意系统资源均

16、衡使用注意系统资源均衡使用注意系统资源均衡使用注意系统资源均衡使用n n 保证提交的作业在截止时间内完成保证提交的作业在截止时间内完成保证提交的作业在截止时间内完成保证提交的作业在截止时间内完成n n 设法缩短作业平均周转时间设法缩短作业平均周转时间设法缩短作业平均周转时间设法缩短作业平均周转时间 大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法 假定某一作业到达的时间为假定某一作业到达的时间为T Tsisi，它被选它被选中执行，得到计算结果的时间为中执行，得到计算结果的时间为T Teiei

17、 。作业的周转时间为作业的周转时间为T Ti i T Teiei T Tsisi 作业平均周转时间为：作业平均周转时间为：T T 其中，其中，n n为作业流中的作业数为作业流中的作业数 作业平均周转时间 调度算法性能的衡量 平均带权周转时间 作业的带权周转时间为作业的带权周转时间为W Wi i T Ti i/riri W=W=其中，其中，riri 为某作业为某作业i i的实际执行时间的实际执行时间4.3 进程调度进程调度 要解决的问题：要解决的问题：要解决的问题：要解决的问题：WHATWHAT：按什么原则分配按什么原则分配按什么原则分配按什么原则分配CPU CPU 进程调度算法进程调度算法进程

18、调度算法进程调度算法 WHENWHEN：何时分配何时分配何时分配何时分配CPU CPU 进程调度的时机进程调度的时机进程调度的时机进程调度的时机 HOWHOW：如何分配如何分配如何分配如何分配CPU CPUCPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）调度过程（进程的上下文切换）调度过程（进程的上下文切换）1.进程调度的功能2.进程调度的时机3.进程调度的方式4.进程调度的过程5.进程调度性能衡量1.进程调度的功能进程调度的功能 进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPUCPUCPUCP

19、U的竞争，的竞争，的竞争，的竞争，即按一定的调度算法从就绪队列中选中即按一定的调度算法从就绪队列中选中即按一定的调度算法从就绪队列中选中即按一定的调度算法从就绪队列中选中一个一个一个一个进程，把进程，把进程，把进程，把CPUCPUCPUCPU的使用权交给被选中的进程。的使用权交给被选中的进程。的使用权交给被选中的进程。的使用权交给被选中的进程。进程调度的功能：进程调度的功能：1.记录记录所有进程的运行状况（静态和动态）；所有进程的运行状况（静态和动态）；2.选择选择适当的进程分派适当的进程分派CPU；3.完成进程完成进程上下文切换上下文切换。在进程（上下文）中切换的步骤在进程（上下文）中切换的

20、步骤在进程（上下文）中切换的步骤在进程（上下文）中切换的步骤n n 保存处理器的上下文，包括程序计数器和其它寄保存处理器的上下文，包括程序计数器和其它寄存器存器 n n 用新状态和其它相关信息更新正在运行进程的用新状态和其它相关信息更新正在运行进程的PCB PCB n n 把原来的进程移至合适的队列把原来的进程移至合适的队列-就绪、阻塞就绪、阻塞 n n 选择另一个要执行的进程选择另一个要执行的进程 n n 更新被选中进程的更新被选中进程的PCB PCB n n 从被选中进程中重装入从被选中进程中重装入 CPU CPU 上下文上下文2.进程调度的时机进程调度的时机n当一个进程运行完毕，或由于某

21、种错误而终止运行。当一个进程运行完毕，或由于某种错误而终止运行。(完成任务完成任务)n执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。从而可调度选择一新的用户进程执行。(完成任务完成任务)n执行中的进程自己调用的阻塞原语将自己阻塞起来进入等待状态。执行中的进程自己调用的阻塞原语将自己阻塞起来进入等待状态。(等待等待资源资源)n执行中的进程执行了执行中的进程执行了P原语操作，从而因资源不足而被阻塞，或调用了原语操作，从而因资源不足而被阻塞，或调用了V原语操作激活了等待资源的进程队

22、列。原语操作激活了等待资源的进程队列。(等待资源等待资源)n执行中的进程提出执行中的进程提出I/O请求后被阻塞。请求后被阻塞。(等待资源等待资源)n分时系统中时间片到。分时系统中时间片到。(时间片到时间片到)n当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪。一个等待进程变成就绪。(发现重调标志发现重调标志)引起进程调度的原因有以下几类：引起进程调度的原因有以下几类：3.进程调度的方式进程调度的方式可抢占式可抢占式非抢占式非抢占式进程调度的方式有进程调度的方式有 可抢占式可抢占式 Preempt

23、ivePreemptive（可剥夺式可剥夺式）：）：当有比正在运行的进程优先级更高的进程就绪时，当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的系统可强行剥夺正在运行进程的CPUCPU，提供给具有更高提供给具有更高优先级的进程使用。优先级的进程使用。不可抢占式不可抢占式 Non-preemptiveNon-preemptive（非剥夺式）：非剥夺式）：某一进程被调度运行后，除非由于它自身的原因某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。不能运行，否则一直运行下去。4.进程调度过程进程调度过程保存现场保存现场选择要运行的程序选择要运行的程序恢复现

24、场恢复现场作业调度与进程调度作业调度与进程调度n n 作业调度为进程活动做准备，进程调度使进作业调度为进程活动做准备，进程调度使进程活动起来；程活动起来；n n 作业调度次数少，进程调度频率高；作业调度次数少，进程调度频率高；n n 有的系统无作业调度，但进程调度必不可少。有的系统无作业调度，但进程调度必不可少。5.进程调度性能衡量进程调度性能衡量 具有公平性具有公平性 资源利用率高（特别是资源利用率高（特别是CPUCPU利用率）利用率）在交互式系统情况下要追求响应时间在交互式系统情况下要追求响应时间（越短越好）（越短越好）在批处理系统情况下要追求系统吞吐量在批处理系统情况下要追求系统吞吐量4

25、.4 调度算法调度算法1.先来先服务算法2.时间片轮转算法3.短作业优先算法4.最高响应比优先算法5.多级队列算法6.优先级算法7.多级反馈队列算法返回 针对不同的系统，往往采用的调度算法不相同，在操作系统中存在着多种调度算法，通常有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。1.先来先服务调度算法先来先服务调度算法 （FCFS，First Come First Serve）n n基基本本思思想想：按按照照作作业业提提交交或或进进程程变变为为就就绪绪状状态态的的先先后后次次序序，调调入入系系统统或或分分派派CPU CPU，换换句句话话说说，调调度度程程序序每每次次选选择择的的

26、作作业业/进进程程是是等等待待时时间间最最久久的的，而而不不管管其其运运行行时时间间的的长长短短。这这种种调调度度算算法法突突出出的的优优点点是是实实现现简简单单，效效率率较较低低，在在一一些些实实际际的的系系统统和和一一般般应应用用程序中采用这种算法的较多程序中采用这种算法的较多。n n既可用于作业调度，也可用于进程调度既可用于作业调度，也可用于进程调度 先来先服务（先来先服务（先来先服务（先来先服务（FCFSFCFS）调度算法举例调度算法举例调度算法举例调度算法举例2.时间片轮转算法时间片轮转算法(Round Robin)将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFSFCFS

27、原则，排成一个原则，排成一个队列队列。每次调度时将每次调度时将CPUCPU分派给分派给队首进程队首进程，让其，让其执行一个时间片执行一个时间片。时间片的。时间片的长度长度从几个从几个msms到几百到几百msms。在一个时间片结束时，发生在一个时间片结束时，发生时钟中断时钟中断。调度程序据此。调度程序据此暂停当前进程的执行暂停当前进程的执行，将其送到将其送到就绪队列的末尾就绪队列的末尾，并通过上下文切换，并通过上下文切换执行当前的队首进程执行当前的队首进程。进程可以进程可以未使用完一个时间片未使用完一个时间片，就，就出让出让CPUCPU（如阻塞）。如阻塞）。一般用于进程调度（为什么不用于作业调度

28、？）一般用于进程调度（为什么不用于作业调度？）基本思想：基本思想：时间片长度的确定时间片长度的确定n n时间片长度变化的影响n n过长过长 退化为退化为FCFSFCFS算法，进程在一个时间片内都执行完。算法，进程在一个时间片内都执行完。n n过短过短 用户的一次请求需要多个时间片才能处理完，上下文切换次数用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。增加。n n对响应时间的要求：n nT(T(响应时间响应时间)=N()=N(进程数目进程数目)*q()*q(时间片时间片)n n时间片长度的影响因素：n n系统的响应时间：系统的响应时间：时间片越大，响应时间越长（当进程数目一定时）；

29、时间片越大，响应时间越长（当进程数目一定时）；n n就绪进程的数目就绪进程的数目：数目越多，时间片越小（当响应时间一定时）；：数目越多，时间片越小（当响应时间一定时）；n n进程的转换时间能力进程的转换时间能力：为保证系统开销不大于某个标准，应使进程的转：为保证系统开销不大于某个标准，应使进程的转换时间换时间/时间片不大于某一数值，如时间片不大于某一数值，如1/101/10；n nCPUCPU运行指令速度运行指令速度：CPUCPU运行速度快，则时间片可以短些，反之，则取运行速度快，则时间片可以短些，反之，则取长些。长些。04年考题年考题n n简答题简答题 某系统中，进程调度采用某系统中，进程调

30、度采用“时间片轮转时间片轮转”的策略。每个进程的策略。每个进程得到的时间片随进程执行情况而变化，在过去的时间里，若进得到的时间片随进程执行情况而变化，在过去的时间里，若进程经常产生中断，则给它分配较短的时间片；若中断次数很少，程经常产生中断，则给它分配较短的时间片；若中断次数很少，则分给一个较长的时间片则分给一个较长的时间片?请回答：请回答：(1)(1)为什么给经常产生中断的进程分配较短的时间片，而很少为什么给经常产生中断的进程分配较短的时间片，而很少产生中断的进程分得较长的时间片？产生中断的进程分得较长的时间片？(2)(2)如果有两个就绪队列，一个是时间片较短的进程就绪队列，如果有两个就绪队

31、列，一个是时间片较短的进程就绪队列，另一个时间片较长的进程就绪队列，在进程调度时应该优先从另一个时间片较长的进程就绪队列，在进程调度时应该优先从哪个队列中选取一个就绪进程占有哪个队列中选取一个就绪进程占有CPUCPU？为什么？为什么？3.短作业优先调度算法短作业优先调度算法 (SJF,Shortest Job First)n n 基本思想：对预计执行时间短的作业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。在在一一般般情情况况下下这这种种调调度度算算法法比比先先来来先先服服务务调调度度算算法法的的效效率率要要高高一一些些。实实现现相相对对先先来来先先服服务务调调度度算算法法要要困困难

32、难些些，如如果果作作业业的的到到来来顺顺序序及及运运行行时时间间不不合合适适，会会出出现现饿饿死死现现象象，例例如如，系系统统中中有有一一个个运运行行时时间间很很长长的的作作业业J J，和和几几个个运运行行时时间间小小的的作作业业，然然后后，不不断断地地有有运运行行时时间间小小于于J J的的作作业业的的到到来来，这这样样，作作业业J J就就得得不不可可调调度度而饿死。另外，作业运行的估计时间也有问题。而饿死。另外，作业运行的估计时间也有问题。又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。既可用于作业调度，也可用于进

33、程调度既可用于作业调度，也可用于进程调度 SJF的特点的特点n n优点：n n缩短作业的等待时间；缩短作业的等待时间；n n提高系统的提高系统的吞吐量吞吐量；n n比比FCFSFCFS平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间短短n n缺点：n n对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执行；n n未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来划分执行的优先级；n n难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影，从而影响调度性能。响调度性能。SJF的变的变型型n n最短剩余时间优先SRT(S

34、hortest Remaining Time)n n允许比当前进程剩余时间更短的进程来抢占允许比当前进程剩余时间更短的进程来抢占先来先服务调度算法和短作业优先调度算法比较举例先来先服务调度算法和短作业优先调度算法比较举例先来先服务调度算法和短作业优先调度算法比较举例先来先服务调度算法和短作业优先调度算法比较举例4.最高响应比优先最高响应比优先调度算法调度算法 HRN(Highest Response_Ratio Next)n n基本思想：（FCFSFCFS和和SJFSJF的折衷）的折衷）n n先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只先来先服务和短作业优先算法都有其片面性，先

35、来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。高者优先调度算法是介于这两种算法之间的一种拆衷的算法。既可用于作业调度，也可用于进程调度既可用于作业调度，也可用于进程调度 5.多级队列算法多级队列算法 (Multiple-level Queue)n n根据作业或进程的性质或类型的不同，将后备或就绪队列再分为若干个子队列。n n各队列有

36、不同的调度算法。n n既可用于作业调度，也可用于进程调度6.优先级算法优先级算法(Priority cheduling)(1)静态优先级(2)动态优先级(3)线性优先级调度算法（SRR,SRR,SelfishRoundSelfishRound Robin)Robin)本算法是对优先级高的作业（进程）优先处理。用于作业调度和进程调度，可分成抢先式和非抢先式。(1)静态优先级静态优先级n n依据：n n进程类型（系统进程优先级较高）进程类型（系统进程优先级较高）n n对资源的需求（对资源的需求（对对CPUCPU和内存需求较少的进程，和内存需求较少的进程，优先级较高）优先级较高）n n用户要求（紧迫

37、程度和付费多少）用户要求（紧迫程度和付费多少）优先级在创建进程时就确定，直到进程终止前都不改变。通常是一个整数。(2)动态优先级动态优先级n n在就绪队列中，在就绪队列中，等待时间等待时间延长则优先级提高，从延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；优先级提高到可被调度执行；n n进程每进程每执行一个时间片执行一个时间片，就降低其优先级，从而，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让一个进程持续执行时，其优先级降低到出让CPUCPU。在创建进程时赋予的优先级，在进程运行过程中可以自动改变，

38、以便获得更好的调度性能。如：(3)线性优先级调度算法线性优先级调度算法（SRR,Selfish Round SRR,Selfish Round RobinRobin）n n就绪进程队列分成两个就绪进程队列分成两个：n n新创建进程队列：按新创建进程队列：按FCFSFCFS方式排成；进程优先级按速率方式排成；进程优先级按速率a a增加；增加；n n享受服务队列：已得到过时间片服务的进程按享受服务队列：已得到过时间片服务的进程按FCFSFCFS方式方式排成；进程优先级按速率排成；进程优先级按速率b b增加；（增加；（ab0ab0）n n新创建进程转入享受服务队列的确定新创建进程转入享受服务队列的确

39、定：当：当新创建进新创建进程优先级程优先级与享受服务队列中与享受服务队列中最后一个进程优先级最后一个进程优先级相相同时，转入享受服务队列；或当同时，转入享受服务队列；或当享受服务队列为空享受服务队列为空时，新创建进程队列的头一个进程可以转入享受服时，新创建进程队列的头一个进程可以转入享受服务进程队列。务进程队列。SRR算法基本思想：n n 某时刻某时刻t t进程的优先级为：设时刻进程的优先级为：设时刻t1 t1进程被创建，进程被创建，t2 t2时刻转入享受服务队列时刻转入享受服务队列 p(t)=a*(t2-t1)+b*(t-t2)（ab0ab0）SRR算法的优先级变化SRRSRR与与与与FCF

40、SFCFS和和和和RRRR算法的关系算法的关系算法的关系算法的关系n n当当ba0ba0时，享受服务队时，享受服务队列中永远只有一个进程；列中永远只有一个进程；SRRSRR算法退化成算法退化成FCFSFCFS算算法；法；n n当当ab=0ab=0时，时，SRRSRR算法就算法就是是RRRR算法；算法；7.多级反馈队列算法多级反馈队列算法(Round Robin with Multiple Feedback)n n多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。多级反馈队列算法思想多级反馈队列算法思想n n设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列

41、执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍n n新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，最后一个队列（最低级），则按时间片轮转算法调度直到完成。n n仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。多级反馈队列调度算法示意图多级反馈队列调度算法示意图CPU时间片完进程调度进程完成就 绪 队 列 一就 绪 队 列 二就 绪 队 列 三就 绪 队 列 n时间片完时间片完n n多级反馈队列算法的优点：n n为提高系统吞吐量和缩短平均周转时间而照顾短为提高系统

42、吞吐量和缩短平均周转时间而照顾短进程进程n n为获得较好的为获得较好的I/OI/O设备利用率和缩短响应时间而设备利用率和缩短响应时间而照顾照顾I/OI/O型进程型进程n n不必估计进程的执行时间，动态调节不必估计进程的执行时间，动态调节本章小结本章小结n n分级调度分级调度n n作业的状态及转换作业的状态及转换n n作业调度和进程调度的任务及功能作业调度和进程调度的任务及功能n n常用的调度算法思想，及性能评价指标的计算常用的调度算法思想，及性能评价指标的计算思考题思考题n n选择题 在各种作业调度算法中，若所有的作业同时到达，则平均等待时间最短的算法是（）A.FCFS B.HRN C.SJF

43、 D.Priority Priority chedulingchedulingn n简答题 现有两道作业同时执行，一道以计算为主，另一道以I/O为主，你将怎样赋予作业进程占有处理机的优先级？为什么？n n某系统采用如图所示的进程状态变迁，试回答：某系统采用如图所示的进程状态变迁，试回答：1.1.该系统采用怎样的调度策略，如何调度？该系统采用怎样的调度策略，如何调度？2.2.采用这样的调度策略，对哪一类进程有利？采用这样的调度策略，对哪一类进程有利？运行低优先就绪高优先就绪因I/O而阻塞时间片到其次选择500ms首先选择100ms请求I/OI/O完成n n 计算题 假设有四个作业，它们提交，运行的时间如下，假设有四个作业，它们提交，运行的时间如下，若采用若采用HRNHRN调度算法，试问平均周转时间和平均带调度算法，试问平均周转时间和平均带权周转时间为多少？（以十进制计算）权周转时间为多少？（以十进制计算）作业号作业号 到达时间到达时间 运行时间运行时间 1 8.0 2.01 8.0 2.0 2 8.3 0.5 2 8.3 0.5 3 8.5 0.1 3 8.5 0.1 4 9.0 0.4 4 9.0 0.4