操作系统第四章处理机调度

1、第四章处理机调度处理机调度的工作是对CPU进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机。大纲三、处理机管理1. 调度的基本概念2. 调度时机、切换与过程3. 调度的基本准则4. 调度方式5. 典型调度算法先来先服务调度算法；短作业（短进程、短线程）优先调度算法； 时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。本章的主要内容是：4.1 分级调度4.2 作业调度4.3 进程调度4.4 调度算法n 学习目标：1. 掌握：作业和进程的、作业的状态及其转换；作业调度和进程调度的功能；常用的调度算法。2. 理解：性能评价标准；调度算法的评价。3. 了

2、解：其他调度算法。n 学习要点：本章的重点在于掌握系统中对作业和进程如施调度，作业调度和进程调度的功能；掌握常用调度算法的实现思想，并能计算出各个算法的性能指标； 能简单分析常用调度算法的性能。4.1 分级调度调度：选出待分派的作业或进程。处理机调度的目的是分配处理机。1. 调度层次2. 作业的状态及转换3. 作业和进程的4. 调度的性能准则返回1. 调度层次n 高级调度（宏观调度、作业调度）n 把外存上处于后备队列中的那些作业调入内存，并创建进程，分配，将进程加入就绪队列。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就便成进进程组。n 中级调度（交换调度：内外

3、存交换）n 从器的角度看，将把暂时不能运行的进程调至外存就绪，将当前所需部分换入到内存， 提高内存利用率和系统吞吐量。中级调度实际上是器之间的对换。n 低级调度（微观调度、进程调度）n 决定就绪队列中的哪个进程应获得处理机（即低级调度是将处理机分配给进程） ，低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。n 线程调度：可有OS内核完成，也可由用户程序进行。2. 作业的状态及其转换作业从提交给系统，直到完成任务系统前，在整个活动过程中它会处于不同的状态。通常，作业的状态分 为：提交、后备（收容）、执行和完成。提交状态：一个作业处于从输入进入外部的过所处的状态后备状态

4、：作业的全部信息都已通过输入入井中，等待进入内存输入到外存输的态：作业一旦被作业调度程序选中，则为其分配所需，并创建进程，送入内存中投入运行完成状态：作业运行完毕，准备系统时的状态（如打印结果，回收）作业状态及其转换图交换调度输入管理系统执行完成就绪等待后备提交等待就绪外存内存进程调度返回作业调度线程调度调度队列模型时间片完作业调度后备队列就绪队列进程调度进程完成CPU交换挂起出现挂起等待发生阻 塞 队 列具有高、中、低三级调度的调度队列模型阻 塞挂 起 队 列调度就绪挂起队列3. 作业与进程的作业是用户向计算机提交任务的任务实体； 进程是计算机为了完成用户任务实体而设置的§执行实体

5、。§计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。§分时系统中无作业的概念，进程几乎有多道程序设计系统中。4. 调度的性能准则我们可从不同的角度来调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的调度算法选择是一个综合的结果。面向用户的调度性能准则n 周转时间：作业从提交到完成（得到结果）所经历的时间。：在后备队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待时间等n 平均周转时间Tn 平均带行时间转时间W ：带转时间= 周转/CPU执n 响应时间：用户发出命令（如击键，输入一个请求）到系统响应给出

6、执行结果（如屏幕显示）所经历的时间面向系统的调度性能准则时间内所完成的作业数，跟作业本身特性和调吞吐量：n批处理系统。度算法都有n 平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，而吞吐量是2个作业/小时。处理机利用率：大中型主机。n的均衡利用：如CPU繁忙的作业和I/O繁忙的作业各种n搭配大中型主机。公平性：不因作业或进程本身的特性而使上述指标过分如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。§。§调度算法本身的调度性能准则n 易于实现n 执行开销比4.2作业调度作业调度的任务：完成作业从

7、后备状态到运行状态的转变，以及从运行态到完成态的转变。1. 作业块2. 作业调度及功能3. 作业调度目标与性能衡量返回1.作业块作业块JCB在多道批处理系统中通常有若干作业被收容在输入井中，为了管理和调度作业，就必须已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。内容：作业名、作业状态、作业调度，以及信息。申请和一些作业名作业类型要求使用情况优先级当前状态其它2. 作业调度及功能作业调度的任务：完成作业从后备状态到运行 状态的转变，以及从运行态到完成态的转变。作业调度的转换过程(1)作业从后备状态到态P85(a)框图P85(b)框图(2)作业从态到完成状态作业从后备状态

8、到态出口后备作业队列空？是分配否进程调度否是放弃该作业要求能满足？ 调用管理/管理 程序，审核要求调用进程管理程序建立进程按调度算法，从后备作业中选出一作业作业从态到完成状态调用管理/管理程序回收分配给该作业的全部调度下一个作业撤消该作业的所有进程及JCB调用计算程序，计算该作业的执行费用作业调度的具体功能系统中各个作业的情况；（情况）按照某种调度算法从后备作业队列中选取作业；（挑选作业）为被选取的作业分配内存、外设等需要的；（分配）为选中的作业建立相应的进程。（建立进程）在作业运行完毕或运行过程中因某种需要时，进行善后处理工作，回收所占用的全部，撤消相关的进程及JCB。（善后处理）3.作业调

9、度的目标与性能衡量§ 调度的目标对所有作业应该是公平合理应使有较高的利用率执行尽可能多的作业有更快的响应时间想要设计一个理想的调度算法，同时满足上述目标是不可能的。实际系统中，调度算法需折衷考虑下列因素：n 调度算法应与系统设计目标保持一致n 注意系统均衡使用n 保证提交的作业在截止时间内完成n 设法缩短作业平均周转时间大多数操作系统都采用比较简单的调度算法调度算法性能的衡量§ 平均周转时间（假定某作业i的提交时间为Tsi，完成时间为Tei）TiTei 作业的周转时间为：Tsi作业的平均周转时间为：T（其中，n为作业流中的作业数）1 ånTin i=1§

10、 平均带作业的带转时间转时间为：WiTi /ri作业的平均带转时间为：W=（其中，ri为作业i的实际执行时间）§ 平均响应时间（分时、实时系统）1ånTin i =1 ri4.3 进程调度要解决的：WHEN：何时分配CPU 进程调度的时机WHAT：按什么原则分配CPU 进程调度算法HOW： 如何分配CPU CPU调度过程（进程上下文切换）1. 进程调度的功能2. 进程调度的时机3. 进程调度的方式4. 进程调度的过程5. 进程调度性能衡量1. 进程调度的功能进程调度的任务是协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程， 把CPU的使用权交给被选中的进程

11、。进程调度的功能：1.所有进程的运行状况（静态和动态）；2. 选择适当的进程分派CPU ；3. 完成进程上下文切换。2. 进程调度的时机引起进程调度的n 当一个进程运行完毕，或由有以下几类：种错误而终止运行。(完成任务)调用，在系统程序返回用户进，可认为系统进程n毕，从而可调度选择一新的用户进程执行。(完成任务)阻塞起来进入等待状态。(等待n 执行中的进程)调用的阻塞原语将n 执行中的进程执行了P原语操作，从而因不足而被阻塞，或调用了V的进程队列。 (等待)原语操作激活了等待n 执行中的进程提出I/O请求后被阻塞。 (等待n 分时系统中时间片到。 (时间片到)n 当有一个优先级更高的进程就绪（

12、可抢占式），例如：新创建一个进程， 一个等待进程变成就绪。(发现重调标志)3. 进程调度的方式进程调度的方式有可抢占式非抢占式§可抢占式Preemptive（可式）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行正在运行进程的CPU，提供给具有更高优先级的进程使用。§不可抢占式Non-preemptive（非式）：某一进程被调度运行后，除非由于它自身的不能运行，否则一直运行下去。4. 进程调度过程（进程上下文切换）§ 保存现场§ 选择要运行的程序§ 恢复现场进程（上下文）切换的步骤：1. 检查是否可以进行进程切换（如:原语执行时不可）2

13、. 保存被切换进程的现场（如：程序计数器、寄存器），并移至合适的（就绪、阻塞）队列3. 选取一个新进程4. 恢复被选中进程的现场：装配该进程的正文，使其获得CPU权作业调度与进程调度n 作业调度为进程调度做准备n 作业调度对除了CPU之外的所有系统进行分配n 进程调度专门负责对CPU进行分配，使进程活动起来n 作业调度次数少，进程调度频率高n 有的操作系统无作业调度，但进程调度是必不可少的4. 进程调度性能衡量§ 定性衡量§ 公平性§ 可靠性（避免因调度引起的破坏）§ 简洁性（避免调度程序消耗较大的系统开销）§ 定量评价§ CPU利用

14、率§ 响应时间（交互式系统）§ 吞吐量（批处理系统）4.4 调度算法不同的系统，往往采用的调度算法不相同，在操作系统中着多种调度算法， 通常有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。1. 先来先服务算法2. 时间片轮转算法3. 短作业优先算法4. 最高响应比优先算法5. 多级队列算法6. 优先级算法7. 多级反馈队列算法返回1. 先来先服务调度算法（FCFS，First Come First Serve）n 基本思想：按照作业提交或进程变为就绪状态的先后次序，调入系统或分派CPU ，换句话说，调度程序每次选择的作业/进程是等待时间最久的，而不管其运行时

15、间的长短。这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用采用这种算法的较多。n 既可用于作业调度，也可用于进程调度先来先服务（FCFS）调度算法举例2. 时间片轮转算法(Round Robin)§ 基本思想：§ 将系统中所有的就绪进程按照FCFS原则，排成一个队列。§ 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。§ 在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。§ 进程可以未使用完一个时间片，就出让

16、CPU（如阻塞）。§ 一般用于进程调度（为什么不用于作业调度？）（P90，P93）时间片长度的确定n 时间片长度变化的影响n 过长>为FCFS算法，进程在一个时间片内都。n 过短>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。n 对响应时间的要求：n T(响应时间)=N(进程数目)*q(时间片)n 时间片长度的影响因素：n 系统的响应时间：时间片越大，响应时间越长（当进程数目一定时）；n 就绪进程的数目：数目越多，时间片越小（当响应时间一定时）；n 进程的转换时间能力：为保证系统开销不大个标准，应使进程的转换时间/时间片不大一数值，如1/10；n CPU运行

17、指令速度：CPU运行速度快，则时间片可以短些，反之，则取长些。04年考题n 简答题某系统中，进程调度采用“时间片轮转”的策略。每个进程得到的时间片随进程执行情况而变化，在过去的时间里，若进 程经常产生中断，则给它分配较短的时间片；若中断次数很少，则分给一个较长的时间片?请回答：(1) 为什么给经常产生中断的进程分配较短的时间片，而很少产 生中断的进程分得较长的时间片？(2) 如果有两个就绪队列，一个是时间片较短的进程就绪队列， 另一个时间片较长的进程就绪队列，在进程调度时应该优先从哪个队列中选取一个就绪进程占有CPU？为什么？例：某分时系统的进程出现如下图所示的状态变化。运行等磁盘读文件等待打

18、印机输出结果就绪进程队列试问：（1）你认为系统采用的是哪一种进程调度算法？（2）写出图中所示的每一个状态变化的（从到）答：（1）该分时系统采用的进程调度算法是时间片轮转法。（2）状态变化的如下：进程被选中，变成运行态；时间片到，运行的进程排入就绪队列尾部；运行的进程启动打印机，等待打印；打印输出结束，阻塞的进程排入就绪队列尾部；等待磁盘读文件工作；磁盘传输信息结束，阻塞的进程排入就绪队列尾部。例：假定在单CPU条件下有下列要执行的作业：作业达到时间运行时间1010211322431545（1） 用一个执行时间图描述在RR算法时执行这些作业的情况；（2） 计算各个作业的周转时间、平均周转时间、带

19、权周转时间、平均带转时间？时间片轮转算法RR作业54321t01234 5 6 7 89 10 11 12 13 1419执行时间图作业12345 1 35 1515151t01234 5 6 789 10 11 12 13 1419RR时间片轮转算法作业到达时间运行时间完成时间周转时间带转时间101019191.9211211.0322752.5431411.054514102.0平均周转时间T=7.2平均带转时间W=1.683. 短作业优先调度算法(SJF, Shortest Job Firs什么是饥主要区别是什么？锁和饥饿的饥饿现象是指某进程具备运又称为“短进程优先”SPN(Sho 行条

20、件，但总受到其他进程的影响，一直轮不到（或者很难轮到）FCFS算法的改进，其目标是减少平均该进程运行。系统中发生饥饿现象时至少有一个具备运行条件进基本思想：对预计执行时间程被无限期地推迟执行，但死锁n处理。通常后来的短作业不抢先是某进程等待一个决发生的，而因不具备运行条件永远在一般情况下这种调度算法比先 不可执行。高一些。实现相对先来先服务调度算法 来顺序及运行时间不合适，会出现些，如果作业的到现象，例如，系统中有一个运行时间很长的作业J，和几个运行时间小的作业，然后，不 断地有运行时间小于J的作业的到来，这样，作业J就得不可调度而。另外，作业运行的估计时间也有。§ 既可用于作业调度

21、，也可用于进程调度SJF的特点n 优点：n 缩短作业的等待时间；n 提高系统的吞吐量；n 平均周转时间和平均带n 缺点：转时间短n 对长作业非常不利，可能长时间得不到执行；n 未能依据作业的紧迫程度来划分执行的优先级；n 难以准确估计作业（进程）的执行时间，从而影响调度性能。SJF的变型n "最短剩余时间优先"SRT(Shortest RemainingTime)比当前进程剩余时间更短的进程来抢占n先来先服务调度算法和短作业优先调度算法比较举例4. 最高响应比优先调度算法HRN(Highest Response_Ratio Next)n 基本思想： （FCFS和SJF的折衷

22、）n 先来先服务和短作业优先算法都有其片面性，先来先服务 调度算法只考虑作业的等待时间，而忽视了作业的运行时 间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介 于这两种算法之间的一种拆衷的算法。§ 既可用于作业调度，也可用于进程调度11年统考题【23】下列选项中，满足短任务优先且生饥饿现象的调度算法是（ ）。n A先来先服务发n B高响应比优先n C时间片轮转n D非抢占式短任务优先n 思考题假设有四个作业，它们提交，运行的时间如下， 若采用HRN调度算法，试问平均周转时间和平均带转时间为多少？（以十进制计算）作业号1234到达时间

23、8.08.38.59.0运行时间2.00.50.10.45. 优先级算法(Priority cheduling)本算法是对优先级高的作业（进程）优先处理 。用于作业调度和进程调度，可分成抢先式和非抢先式。(1) 静态优先级(2) 动态优先级(3) 线性优先级调度算法（SRR, SelfishRound Robin)(1) 静态优先级优先级在创建进就确定，直到进程终止前都不改变。通常是一个整数。n 依据：n 进程类型（系统进程优先级较高）n 对的需求（对CPU和内存需求较少的进程，优先级较高）n 用户要求（紧迫程度和多少）(2) 动态优先级在创建进赋予的优先级，在进程运行过程中可以自动改变，以便

24、获得更好的调度性能。如：n 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；n 进程每执行一个时间片，就降低其优先级，从而 一个进程持续执行时，其优先级降低到出让CPU。(3) 线性优先级调度算法（SRR, Selfish Round Robin）SRR算法基本思想：n 就绪进程队列分成两个：n 新创建进程队列：按FCFS方式排列；进程优先级按速率a 增加；n 享受服务队列：已得到过时间片服务的进程按FCFS方式排列；进程优先级按速率b增加；（a>b>0）n 新创建进程转入享受服务队列的确定：当新创建进程就绪队列的首进程

25、优先级与享受服务队列中最后一个进程优先级相同时，转入享受服务队列；或当享受服务队列为空时，新创建进程队列的头一个进程可以转入享受服务进程队列。n 某时刻t进程的优先级为：设时刻t1进程被创建，t1时刻转入享受服务队列p(t)=a(t1- t1)+b(t - t1) （a>b>0）SRR与FCFS和RR算法的n 当b>a>0时，享受服务队列SRR算法法；只有一个进程； 成FCFS算n 当a>b=0时，SRR算法就是RR算法；SRR算法的优先级变化6. 多级队列算法(Multiple-level Queue)n 根据作业或进程的性质或类型的不同，将后备或就绪队列再分为若干个子队列。n 各队列有不同的调度算法。n 既可用于作业调度，也可用于