04 处理机调度.ppt

1、第四章 处理机调度,4.1 分级调度 4.2 作业调度 4.3 进程调度 4.4 调度算法,处理机调度的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。所以，本章的主要问题是：,学习目标： 1.掌握：作业和进程的关系、作业的状态及其转换；作业调度和进程调度的功能；常用的调度算法。 2.理解：性能评价标准；调度算法的评价。 3.了解：其他调度算法。 学习要点： 本章的重点在于掌握系统中对作业和进程如何实施调度，作业调度和进程调度的功能；掌握常用调度算法的实现思想，并能计算出各个算法的性能指标；能简单分析常用调度算法的性能。,4.1 分级调度,返回,1.

2、调度层次 2. 作业的状态及转换 3. 作业和进程的关系 4. 调度的性能准则,调度：选出待分派的作业或进程。处理机调度的目的是分配处理机。,1. 调度层次,高级调度（宏观调度、作业调度） 把外存上处于后备队列中的那些作业调入内存，并创建进程，分配资源，将进程加入就绪队列。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就便成进程或进程组。 中级调度（交换调度：内外存交换） 从存储器资源的角度看，将把暂时不能运行的进程调至外存就绪，将当前所需部分换入到内存，提高内存利用率和系统吞吐量。中级调度实际上是存储器之间的对换。,低级调度（微观调度、进程调度） 决定就绪队列中

3、的哪个进程应获得处理机（即低级调度是将处理机分配给进程） ，低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。 两种调度方式：非抢占方式：进程一直执行直到完成或发生某事件被阻塞。抢占方式：由于优先权、短作业优先或时间片到等因素，终止现行进程。 线程调度：可有OS内核完成，也可由用户程序进行。,调度队列模型,2. 作业的状态及其转换,作业从提交给系统，直到完成任务退出系统前，在整个活动过程中它会处于不同的状态。通常，作业的状态分为：提交、后备（收容）、运行和完成。,提交状态：一个作业处于从输入设备进入外部存储设备的过程时所处的状态 后备状态：作业的全部信息都已通过输入设

4、备输入作业的输入井中等待进入内存。 运行状态：作业一旦被作业调度程序选中，分配所需的资源，为其建立进程，而被送入内存中投入运行。 完成状态：作业完成其全部运行，释放出其所占用的资源，准备退出系统时的作业。,3. 作业与进程的关系,作业是用户向计算机提交任务的任务实体； 进程是计算机为了完成用户任务实体而设置的执行实体。 计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。 分时系统中无作业的概念，进程几乎存在于所有多道程序设计系统中。,4. 调度的性能准则,我们可从不同的角度来判断调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的调度算法

5、选择是一个综合的判断结果。,面向用户的调度性能准则,周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在后备队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待批处理系统 平均周转时间T 平均带权周转时间W （带权周转时间W是 T(周转)/T(CPU执行) 响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统,面向系统的调度性能准则,吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系批处理系统。 平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作

6、业/小时。 处理机利用率：大中型主机。 各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配大中型主机。 公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。 优先级：可以使关键任务达到更好的指标。,调度算法本身的调度性能准则,易于实现 执行开销比,4.2 作业调度,返回,1. 作业控制块 2. 作业调度及功能 3. 作业调度目标与性能衡量,作业调度的任务：完成作业从后备状态到运行状态的转变，以及从运行态到完成态的转变。,1.作业控制块,在多道批处理系统中通常有若干作业被收容在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了

7、一个作业控制块（JCB）。 内容：作业名、作业状态、作业调度，以及资源申请和一些控制信息。,作业控制块JCB,2. 作业调度及功能,作业调度的任务：完成作业从后备状态到运行状态的转变，以及从运行态到完成态的转变。,作业调度的转换过程 (1)作业从后备状态到执行状态 P85(a)框图 (2)作业从执行状态到完成状态 P85(b)框图,后备作业队列空,按调度算法从作 业中选出一作业,调用存储、设备管理 程序，审核资源要求,资源要求能满足？,放弃该 作业,否,分配资源,调用进程管理 程序建立进程,进程调度,否,是,出 口,作业从后备状态到执行状态,是,调用存储管理、设备管理程序 回收分配该作业的全部

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

9、天执行尽可能多的作业 有快的响应时间,要设计一个理想的调度算法是一件十分困难的事,在实际系统中，调度算法往往折衷考虑。设计调度算法时应考虑的因素： 调度算法应与系统设计目标保持一致 注意系统资源均衡使用 保证提交的作业在截止时间内完成 设法缩短作业平均周转时间 大多数操作系统都采用比较简单的调度算法,假定某一作业到达的时间为Tsi，它被选中执行，得到计算结果的时间为Tei 。 作业的周转时间为Ti Tei Tsi 作业平均周转时间为： T 其中，n为作业流中的作业数,作业平均周转时间,调度算法性能的衡量,平均带权周转时间,作业的带权周转时间为Wi Ti /ri W= 其中，ri 为某作业i的实

10、际执行时间,4.3 进程调度,要解决的问题： WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW： 如何分配CPU CPU调度过程（进程的上下文切换）,1. 进程调度的功能 2. 进程调度的时机 3. 进程调度的方式 4. 进程调度的过程 5. 进程调度性能衡量,1. 进程调度的功能,进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。,进程调度的功能： 1. 记录所有进程的运行状况（静态和动态）； 2. 选择适当的进程分派CPU ； 3. 完成进程上下文切换。,在进程（上下文）中

11、切换的步骤 保存处理器的上下文，包括程序计数器和其它寄存器 用新状态和其它相关信息更新正在运行进程的PCB 把原来的进程移至合适的队列-就绪、阻塞 选择另一个要执行的进程 更新被选中进程的PCB 从被选中进程中重装入 CPU 上下文,2. 进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行。(完成任务) 执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。(完成任务) 执行中的进程自己调用的阻塞原语将自己阻塞起来进入等待状态。(等待资源) 执行中的进程执行了P原语操作，从而因资源不足而被阻塞，或调用了V原语操作激活了等待资源的进程队列。

12、 (等待资源) 执行中的进程提出I/O请求后被阻塞。 (等待资源) 分时系统中时间片到。 (时间片到) 当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪。(发现重调标志),引起进程调度的原因有以下几类：,3. 进程调度的方式,可抢占式 Preemptive（可剥夺式）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用。 不可抢占式 Non-preemptive（非剥夺式）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。,4. 进程调度过程,保存现场 选择要运行的程序 恢

13、复现场,作业调度与进程调度,作业调度为进程活动做准备，进程调度使进程活动起来； 作业调度次数少，进程调度频率高； 有的系统无作业调度，但进程调度必不可少。,5. 进程调度性能衡量,具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量,4.4 调度算法,1. 先来先服务算法 2. 时间片轮转算法 3. 短作业优先算法 4. 最高响应比优先算法 5. 多级队列算法 6. 优先级算法 7. 多级反馈队列算法,返回,针对不同的系统，往往采用的调度算法不相同，在操作系统中存在着多种调度算法， 通常有的算法适用于作业调度，有的算法

14、适用于进程调度，有的两者都适应。,先来先服务调度算法 （FCFS，First Come First Serve）,基本思想：按照作业提交或进程变为就绪状态的先后次序，调入系统或分派CPU ，换句话说，调度程序每次选择的作业/进程是等待时间最久的，而不管其运行时间的长短。这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。 既可用于作业调度，也可用于进程调度,先来先服务（FCFS）调度算法举例,2. 时间片轮转算法(Round Robin),将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时

15、间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片，就出让CPU（如阻塞）。,一般用于进程调度（为什么不用于作业调度？）,基本思想：,时间片长度的确定,时间片长度变化的影响 过长退化为FCFS算法，进程在一个时间片内都执行完。 过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。 对响应时间的要求： T(响应时间)=N(进程数目)*q(时间片) 时间片长度的影响因素： 系统的响应时间：时间片越大，响应时间越长（当进程数目一定时）； 就绪进程的数目

16、：数目越多，时间片越小（当响应时间一定时）； 进程的转换时间能力：为保证系统开销不大于某个标准，应使进程的转换时间/时间片不大于某一数值，如1/10； CPU运行指令速度：CPU运行速度快，则时间片可以短些，反之，则取长些。,04年考题,简答题 某系统中，进程调度采用“时间片轮转”的策略。每个进程得到的时间片随进程执行情况而变化，在过去的时间里，若进程经常产生中断，则给它分配较短的时间片；若中断次数很少，则分给一个较长的时间片? 请回答： (1)为什么给经常产生中断的进程分配较短的时间片，而很少产生中断的进程分得较长的时间片？ (2)如果有两个就绪队列，一个是时间片较短的进程就绪队列，另一个时

17、间片较长的进程就绪队列，在进程调度时应该优先从哪个队列中选取一个就绪进程占有CPU？为什么？,3. 短作业优先调度算法 (SJF, Shortest Job First),基本思想：对预计执行时间短的作业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。 在一般情况下这种调度算法比先来先服务调度算法的效率要高一些。实现相对先来先服务调度算法要困难些，如果作业的到来顺序及运行时间不合适，会出现饿死现象，例如，系统中有一个运行时间很长的作业J，和几个运行时间小的作业，然后，不断地有运行时间小于J的作业的到来，这样，作业J就得不可调度而饿死。另外，作业运行的估计时间也有问题。,又称为“短进程优

18、先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。,既可用于作业调度，也可用于进程调度,SJF的特点,优点： 缩短作业的等待时间； 提高系统的吞吐量； 比FCFS平均周转时间和平均带权周转时间短,缺点： 对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。,SJF的变型,最短剩余时间优先SRT(Shortest Remaining Time) 允许比当前进程剩余时间更短的进程来抢占,先来先服务调度算法和短作业优先调度算法比较举例,4. 最高响应比优

19、先调度算法 HRN(Highest Response_Ratio Next),基本思想： （FCFS和SJF的折衷） 先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。,既可用于作业调度，也可用于进程调度,5. 多级队列算法 (Multiple-level Queue),根据作业或进程的性质或类型的不同，将后备或就绪队列再分为若干个子队列。 各队列有不同的调度算法。 既可用于作业调度，也可用于进程调度,6. 优先

20、级算法(Priority cheduling),(1) 静态优先级 (2) 动态优先级 (3) 线性优先级调度算法（SRR, SelfishRound Robin),本算法是对优先级高的作业（进程）优先处理 。用于作业调度和进程调度，可分成抢先式和非抢先式。,(1) 静态优先级,依据： 进程类型（系统进程优先级较高） 对资源的需求（对CPU和内存需求较少的进程，优先级较高） 用户要求（紧迫程度和付费多少）,优先级在创建进程时就确定，直到进程终止前都不改变。通常是一个整数。,(2) 动态优先级,在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调

21、度执行； 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。,在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。如：,(3) 线性优先级调度算法（SRR, Selfish Round Robin）,就绪进程队列分成两个： 新创建进程队列：按FCFS方式排成；进程优先级按速率a增加； 享受服务队列：已得到过时间片服务的进程按FCFS方式排成；进程优先级按速率b增加；（ab0） 新创建进程转入享受服务队列的确定：当新创建进程优先级与享受服务队列中最后一个进程优先级相同时，转入享受服务队列；或当享受服务队列为空时，新创建进程队列的头一个进程可以转入享受服务进程队列。,SRR算法基本思想：,某时刻t进程的优先级为：设时刻t1进程被创建，t2时刻转入享受服务队列 p(t)=a*(t2-t1)+b*(t-t2) （ab0）,SRR算法的优先级变化,SRR与FCFS和RR算法的关系,当ba0时，享受服务队列中永远只有一个进程；SRR算法退化成FCFS算法； 当ab=0时，SRR算法就是RR算法；,7. 多级反馈队列算法(Round Robin with Multiple Feedback),多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。,多级反馈队列算法思想,设置多个就绪队列，分别赋