第05讲_进程调度

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,51,第 五 讲,清华大学软件学院,2.6,进程调度,在多道系统当中，往往有多个进程同时在内存中运行。在任何时刻，一个进程只可能是以下三种状态之一：,运行状态：该进程正在,CPU,上运行，每个,CPU,上最多只能有一个进程在运行；,就绪状态：进程已经就绪，随时可以运行；,阻塞状态：如在某个信号量上被阻塞，等待,I/O,与此相对应，操作系统会维护相应的状态队列。,就绪队列和各种,I/O,设备队列,（本图摘自,Silberschatz, Galvin and Gagne,： “,Operating System Concepts”,）,选择谁去运行？,在操作系统中，负责去做这个选择的那 部分程序，称为,调度程序,(scheduler),；,调度程序在决策过程中所采用的算法， 称为是,调度算法,；,调度程序是,CPU,资源的管理者；,调度的对象是进程，也可以是线程，大 多数的调度问题对两者都是适用的。,2.6.1,关于调度的若干问题,1.,历史背景,在早期的简单批处理系统当中，调度算法很简 单：选择磁带上的下一个作业运行；,随着分时系统的出现，同时有多个用户在等待 服务，使得调度算法变得越来越复杂。有些大 型机系统还把批处理与分时结合在一起，更增 大了难度。由于当时的,CPU,时间是一种稀缺资 源，因此调度算法的好坏将直接影响到系统的 性能和用户的满意度，算法的设计很受重视。,随着个人计算机时代的到来，形势发生了变化。 首先，在,PC,上通常只有一个进程在活动，这样， 调度程序无事可做。其次，计算机变得越来越快, CPU,已不是稀缺资源了，哪个程序先运行或运行,已经不重要了。因此，调度算法的作用已经显得 微不足道了。,不过，对于那些高端联网工作站和服务器而言， 多个进程需要同时竞争,CPU,的使用权，因此调度 问题又出现了。首先，调度程序要选择合适的进 程去运行，因为对于不同的进程，用户期望的响 应时间和要求是不同的；其次，调度程序要注意,CPU,的使用效率，因为进程切换的开销很大。,2.,进程的行为,CPU,繁忙（,CPU-bound,）,的进程：大部分时间 处于运行和就绪状态；,I/O,繁忙（,I/O-bound,）,的进程：大部分时间处 于阻塞状态。,（本图摘自,Andrew S.,Tanenbaum,： “,Modern Operating Systems”,）,CPU,繁忙与,I/O,繁忙,CPU,繁忙,I/O,繁忙,内部因素：进程自身的功能决定了它的各种工作量。例如，矩阵相乘进程的计算量大，文件管理进程的,I/O,需求很大；,外部因素：计算机系统的运行速度决定了完成这些工作量所需要的时间长短。工作量和工作时间是两回事，判断一个进程是属于,CPU,繁忙还是属于输入输出繁忙，主要看它的计算时间和输入输出时间；,I/O,设备的运行速度较慢，,CPU,的运行速度较快，而且更新换代的速度快，将来进程都趋向于,I/O,繁忙。,CPU,繁忙还是,I/O,繁忙？,VCD,播放软件；,WORD,文字编辑器；,磁盘碎片整理工具,defrag,。,CPU,繁忙还是,I/O,繁忙？（续）,3.,何时调度？,当一个新的进程被创建时，是执行新进程还是继续执行父进程？,当一个进程运行完毕时；,当一个进程由于,I/O,、信号量或其他的某个原因被阻塞时；,当一个,I/O,中断发生时，表明某个,I/O,操作已经完成，而等待该,I/O,操作的进程转入就绪状态；,在分时系统中，当一个时钟中断发生时。,不可抢占调度方式,：一个进程若被选中，就一直运行下去，直到它被阻塞（,I/O,，或正在等待其他的进程），或主动地交出,CPU,。以上的情形,1,3,均可发生调度；,可抢占调度方式,：当一个进程在运行时，调度程序可以打断它。以上的情形,1,5,均可发生调度，另外，在其他的一些情形下，如就绪队列中有进程的优先级高于当前运行进程的优先级，也可能立即进行调度。,两种调度方式,4.,调度算法的类别,不同的,OS,有不同的目标，对调度程序有不同的,要求，因此需要不同类型的调度算法。,批处理系统：无须及时的用户响应，采用不可抢占的调度方式，或时间间隔很长的可抢占调度方式，从而允许进程能长时间运行，减少进程的切换次数，提高系统的性能；,交互式系统：及时的用户响应非常重要，必须采用可抢占的调度方式。以防单个进程占用太多,CPU,时间，影响到其他进程的运行。,实时系统：对响应时间要求苛刻，每个进程运行时间很短，可采用可抢占的调度方式。,5.,调度算法的目标,算法调度的目标是多元的，有些是可以共存的，,也有些是相互牵制的，对于一个实际的调度算法,来说，有一个综合权衡的过程。,所有系统普遍适用的目标：,公平：大致相当的两个进程所得到的,CPU,时间 也应是大致相同的；,对已制订的调度策略必须能贯彻执行；,均衡：尽可能使整个系统的各部分都忙起来， 提高系统资源的使用效率。,批处理系统中调度算法的评价指标：,吞吐量,（,Throughput,）：单位时间内所完成的 作业数，与作业本身特性和调度算法有关；,周转时间,（,Turnaround time,）：一个批处理作 业从提交到完成（得到结果）所经历的时间。 包括：在收容队列中等待，,CPU,上执行，就绪 队列和阻塞队列中等待，结果输出等待；,平均周转时间：一批作业的周转时间的平均值；,平均带权周转时间：权值是实际执行时间的倒数,;,CPU,的利用率,：大中型主机的,CPU,较贵，所以 让它时刻不停地转着。,周转时间：,（,E,i,表示作业,i,完成时间，,S,i,表示作业,i,提交时间）,平均周转时间：,(,N,表示作业的个数,),平均带权周转时间：,(,r,i,表示作业,i,的实际执行时间,),交换式系统中调度算法的评价指标：,响应时间：用户输入一个请求（如击键）到系统 给出首次响应（如屏幕显示）的时间。响应时间 越短越好，优先考虑交互式进程；,相称性：满足用户对程序运行时间的期望值。,实时系统中调度算法的评价指标：,实时响应：必须严格地遵守时间期限；,可预测性：在实时多媒体系统中，信号的播放必 须连贯，不能时断时续。,2.6.2,批处理系统中的调度算法,1.,先来先服务,先来先服务,（,First Come First Served,，,FCFS,；,First In First Out,，,FIFO,）：按照作业到达的 先后次序进行调度；,不可抢占方式：当前进程占用,CPU,，直到执行 完或被阻塞，才让出,CPU,给另外一个进程；,在进程被唤醒后（如,I/O,完成），并不立即恢复 执行，而是放在就绪队列的末尾；,优点：简单、公平，易于理解也易于实现。 现实生活中应用广泛：排队。,问题,1.,平均周转时间取决于各作业到达的顺序，若短作业位于长作业之后，将增大平均周转时间。,例如，三个作业,A,、,B,、,C,的运行时间为,24,、,3,、,3,时间,24 27 30,A,B,C,平均周转时间,(24+27+30)/3,27,平均等待时间,(0+24+27)/3,17,时间,3 6 30,A,B,C,平均周转时间,(3+6+30)/3,13,平均等待时间,(0+3+6)/3,3,问题,2.,无法充分利用,CPU,繁忙的作业与,I/O,繁忙的作业之间的互补关系。如果,CPU,繁忙的作业独占很长时间的,CPU,，使得,I/O,设备空闲，也使得,I/O,繁忙的作业无法运行。,作业,A,作业,B,CPU,I/O,作业,A,作业,B,时间,t0,t1,t2,t3,t4,2.,短作业优先,短作业优先,（,Shortest Job First,，,SJF,），设计 目标是改进,FCFS,算法，减少平均周转时间；,SJF,算法要求作业在开始执行时预计执行时间， 对预计执行时间短的作业优先分派处理器；,两种实现方案：,不可抢占方式：当前作业在运行时不会被打 断，只有运行完毕或阻塞时，才让出,CPU,；,可抢占方式：如果一个新的短作业到来，其 运行时间小于当前正在运行作业的剩余时间， 则抢占,CPU,运行，称为,SRTF,（,Shortest Remaining Time First,）。,可以证明：对于一组同时到达的作业，采用,SJF,算法将得到一个,最小,的平均周转时间。,D,时间,A,C,a,a+b,a+b+c a+b+c+d,例如，考察,4,个作业,A,、,B,、,C,、,D,，其运行时间分别为,a,、,b,、,c,、,d,B,A,、,B,、,C,、,D,的周转时间分别为,a,、,a+b,、,a+b+c,和,a+b+c+d,，因此平均周转时间为：,(4a+3b+2c+d)/4,显然，当,a, b c d,时，平均周转时间最小。,取得最优解的前提之一：这组作业必须同时到达；,例如：,进程,到达时间,运行时间,P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4,SJF,（不可抢占）：,P1,P3,P2,P4,0,3,7,8,12,16,平均周转时间：,(7 + 10 + 4 + 11) / 4 = 8,平均等待时间：,(0 + 6 + 3 + 7) / 4 = 4,若按,P2,P3,P4,P1,顺序,平均周转和等待时间,7.75, 3.75,进程,到达时间,运行时间,P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4,SJF,（可抢占）：,P1,P3,P2,P4,P2,P1,0,2,7,4,11,16,5,平均周转时间：,(16 + 5 + 1 + 6) / 4 = 7,平均等待时间：,(9 + 1 + 0 + 2) / 4 = 3,前提条件之二：需要事先估计作业的运行时间,如何知道作业的运行时间？,该时间只可能是一个估计值；,让提交该作业的用户来提供。不太实用；,使用前面的,CPU,运行时间来预测后面的,CPU,运 行时间，通过过去的行为来预测将来的行为。,如果一个作业已经运行很长时间了，那它可能 还会运行更长的时间；,使用指数平均值函数来预测下一段,CPU,时间,;,指数平均值函数方法,1.,t,n, 第,n,个,CPU,运行时间的实际长度；,2.,n,+1, 下一个,CPU,运行时间的预测长度；,3.,定义系数,，,0 1,4.,定义：,3.,三层调度模型,（本图摘自,Andrew S. Tanenbaum,： “,Modern Operating Systems”,）,准入调度：决定哪一些作业能够进入系统运行。 在这个层次上的调度算法主要有短作业优先进入,以及把,CPU,繁忙的作业和,I/O,繁忙的作业混合在 一起提交给系统；,存储调度：决定哪一些进程应该留在内存中，哪 一些进程应该保存在磁盘上。需要考虑的因素包 括该进程呆在内存或磁盘上的时间长短，它所用 的,CPU,时间以及它的优先级等；,CPU,调度：从内存当中，选择一个已经就绪的进 程去运行。,批处理系统中的三层调度模型,2.6.3,交互式系统中的调度算法,1.,时间片轮转法,在,时间片轮转算法,（,Round-Robin,，,RR,）中，将 所有的就绪进程按照,FCFS,原则，排成一个队列；,每次调度时将处理器分派给队首进程，让其执行 一小段,CPU,时间（时间片）；,在一个时间片结束时，如果进程还没有执行完的 话，将发生时钟中断，在时钟中断中，进程调度 程序将暂停当前进程的执行，并将其送到就绪队 列的末尾，然后执行当前的队首进程；,如果一个进程在它的时间片用完之前就已结束或 被阻塞，那么立即让出,CPU,。,开始时，进程,B,位于队列之首，因此被调度执行。当它的时间片用完后，就把它送到就绪队列的末尾。同时，进程,F,成为队首进程，被调度运行。,（本图摘自,Andrew S. Tanenbaum,： “,Modern Operating Systems”,）,Round robin, too.,优点：,公平性,：各个就绪进程平均地分配,CPU,的使用 时间。假设有,n,个就绪进程，时间片大小为,q,， 那么每个进程将得到,1/n,的,CPU,时间；,活动性,：每个进程最多等待,(n-1)q,时间就能够 再次得到,CPU,去运行；,一般来说，平均周转时间较,SJF,算法为长，但 能够得到,较短的平均响应时间,；,缺点：,q,的大小难以确定,（一般在,20,50ms,）。,q,太大：退化为,FCFS,算法，进程在一个时间片 内都执行完，响应时间长。如,q=100ms,；,q,太小：每个进程都需要更多的时间片才能处理 完，进程切换次数增加，增大系统开销。如,q=4ms,时间片轮转法的特点,进程,CPU,时间,P,1,53,P,2,17,P,3,68,P,4,24,一个例子：时间片长度,q,20,P,1,P,2,P,3,P,4,P,1,P,3,P,4,P,1,P,3,P,3,0 20 37 57 77 97 117 121 134 154 162,平均周转时间：,(134 + 37 + 162 + 121) / 4,113.5,SJF,的平均周转时间：,(94 + 17 + 162 + 41) / 4,78.5,2.,优先级算法,轮转法有一个缺省的前提，即各进程同等重要；,“人人生而平等”？ 恐怕不太现实！同样，并 不是每个进程都同等重要， 怎么办？分等级！,优先级算法,（,Priority Scheduling,）：给每个进 程设置一个优先级，然后在所有就绪进程中选择 优先级最高的那个进程去运行；,SJF,就是一个优先级算法，每个进程的优先级是 它的,CPU,运行时间（时间越短，优先级越高）；,分为,可抢占,和,不可抢占,两种方式；各进程优先级 的确定方式可分为,静态,和,动态,两种。,静态优先级方式,确定优先级的依据：,进程类型（系统进程优先级高于用户进程，交互式进程高于批处理进程）；,对系统资源的需求（对,CPU,和内存需求较少的进程，优先级较高）；,用户要求（用户级别和付费情况，如军用电脑、商用电脑）。,静态方式的缺点：高优先级的进程一直占用,CPU,，低优先级的进程“饥饿”。,静态优先级方式,是指在创建进程时确定进程优先级，并保持不变到进程结束。,动态优先级方式,为防“饥饿”,根据运行时间和等待时间调整优先级,进程每执行一个时间片就降低其优先级。当一个进程持续执行时，其优先级降低到让出,CPU,；,在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。,为了让,I/O,忙起来，可,提高,I/O,繁忙进程的优先级。但如何判定一个进程是,I/O,繁忙的？可把进程优先级设为,1/f,，,f,是在上一个时间片中所用的时间比例,动态优先级方式,是指在创建进程时赋予给进程的优先级，在进程运行过程中可以动态改变，以便获得更好的调度性能。,优先级类别,（本图摘自,Andrew S. Tanenbaum,： “,Modern Operating Systems”,）,可以把进程按照不同的优先级别分组，然后在不同级别之间使用优先级算法，而在同一级别的各个进程之间使用时间片轮转法。,3.,多级队列算法,多级队列算法,（,Multilevel Queue,）引入多个就绪队列，通过各个队列的区别对待，达到一个综合的调度目标。,根据进程的性质或类型的不同，将就绪队列再分 为,若干个子队列,，如,系统进程、用户交互进程、 批处理进程等；,不同的队列可以有,不同的优先级,；,不同的队列可以采用各自,不同的调度算法,，如前 台的交互式进程可采用,RR,算法，后台的批处理进 程可采用,FCFS,算法。,在各个队列之间也必须进行调度：,固定优先级调度,：按照各种类型的进程的优先 级别从高到低地进行，先运行最高优先级的所 有进程，再运行次一级所有进程，依此类推。 问题：可能导致“饥饿”；,时间片方法,：把,CPU,时间按比例分配给不同的 队列，然后再由各个队列的调度算法去调度， 如,80,给前台的交互式进程队列（,RR,算法），,20,给后台的批处理进程队列（,FCFS,）。,（本图摘自,Silberschatz, Galvin and Gagne,： “,Operating System Concepts”,）,多级队列算法的一个例子,4.,多级反馈队列算法,多级队列算法把每个进程按照它的类型,固定,在一 个队列中，但问题是如何来确定进程的类型？ 而且有的进程其类型可能动态变化，怎么办？ “路遥知马力，日久见人心”！,多级反馈队列算法,(Multilevel Feedback Queue),即根据一个进程的运行反馈信息，,动态地,调整它 所在的队列。,反馈,（,Feedback,）：即进程在运行当中的表 现，例如，它是否需要整个的时间片用于计 算，或者它是否经常地执行,I/O,操作？,如何实现多级反馈队列算法？需要确定以下的一 些参数：,队列的个数；,每个队列所用的调度算法；,用来确定何时给一个进程“升级”的方法；,用来确定何时给一个进程“降级”的方法；,用来确定一个进程的初始队列的方法；,多级反馈队列算法的一个例子,三种优先级别，,3,最高、,1,最低，三个就绪队列。时间片长度 分别为,N,、,2N,和,4N,；,新进程进入内存后，优先级为,3,，加入队列,3,的末尾，按,FCFS,算法调度；若一个时间片内未能执行完，则优先级降为,2,，加 入到队列,2,的末尾，同样按,FCFS,算法调度；依此类推。,如果进程在时间片用完之前即被阻塞，则增加它的优先级；,仅当较高优先级的队列为空，才调度较低优先级的队列中的进 程执行。若进程执行时有新进程进入较高优先级的队列，则抢 先执行新进程。,优先级,3,2,1,多级反馈队列算法是时间片轮转算法和优先级算法,的综合和发展。其特点是：,为提高系统吞吐量和缩短平均周转时间而照顾短进程：新进程一进来即赋予最高优先级。,为获得较好的,I/O,设备利用率和缩短响应时间而照顾了,I,/O,繁忙的进程：,I/O,繁忙进程：让其进入最高优先级队列，以及时启动,I/O,操作。通常只需一个小时间片，即可处理完一次,I/O,请求，然后转入到阻塞队列。,CPU,繁忙进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。,不必估计进程的执行时间，动态调节，能够适应一个进程在不同时间段的不同运行特点。,2.6.4,实时系统中的调度算法,在实时系统中，对时间的要求是非常严格的。典 型的例子是：一个或多个外部的物理设备定期或 不定期地生成激励信号，而计算机必须在一定的 时间期限内做出恰当的反应。,硬实时,：有一个绝对的时间期限，计算机的反应 动作必须在此期限之前完成，如核电站的控制系 统；,软实时,：偶尔错过一次期限虽然是令人不快 的，但也是可以容忍的，如,VCD,的播放系统；,实时调度算法可以是,静态的,或,动态的,，前者在系 统开始运行之前即已做好调度决策；而后者是在 运行中做出调度决策。,2.6.5,线程调度,在进程调度中，如果每个进程都带有多个的,线程，那么我们就有了两个层面上的并行关,系：进程和线程。若在这样的系统中实现调,度，取决于线程的具体实现方式：,用户线程,或,内核线程,。,1.,用户线程方式,在用户线程方式下，系统内核并不知道线程的存 在，调度程序不必做任何改动，仍然象平常一样 以进程为单位进行调度。当某个进程被调度执行 时，由它内部的线程调度程序来决定去执行哪一 个线程。,线程的管理是由一组用户级的线程库函数来完成 的，线程调度算法可以采用以上介绍的各种调度 算法，如时间片轮转法和优先级算法。唯一的限 制是：在线程一级没有时钟中断，无法阻止一个 线程运行过长的时间，只能等各个线程主动地交 出,CPU,的使用权。,考虑以下两种情形（以,RR,为背景）,情形,1,：线程的执行时间很长。 例如：调度程序选择进程,A,去运行，即给予,A,一 个时间片，,A,内部的线程调度程序选择了线程,A1,去运行，由于,A1,的运行时间很长，因此一直占据 着,CPU,直到进程,A,的时间片用完，这时系统内核 的调度程序就会选择另外一个进程,B,去运行。后 来,A,又重新获得一个时间片，线程,A1,将继续运行,又把进程,A,的时间片用完，这样持续下去，直到 在,A,的某个时间片当中，,A1,运行完毕，然后调用 线程调度程序，选择另外一个线程执行。,情形,2,：线程每次的执行时间很短。 例如：假设一个时间片的长度是,50,毫秒，而进程,A,的每个线程每次只需要,5,毫秒的执行时间，因此 当进程,A,被调度执行后，它的每个线程将运行一 小段时间，然后就把,CPU,交还给线程调度程序， 从而实现各个线程之间的轮流运行。,在用户线程方式下，可能出现的调度序列：,进程一级的时间片 长度为,50ms,；,线程每次只运行,5ms,2.,内核线程方式,在内核线程方式下，把调度单位从进程改为线程 即可。,在内核线程方式下，可能出现的调度序列：,进程一级的时间片 长度为,50ms,；,线程每次只运行,5ms,下 课 啦,!,