操作系统原理 ch5 处理机调度.ppt

1,第五章处理机调度,分级调度作业调度进程调度选择调度算法时应考虑的问题调度策略的评价多处理机调度实时调度,2,调度策略考虑：周转（轮转）时间吞吐率响应时间设备利用率研究的内容有：作业与进程的关系作业调度策略与算法进程调度策略与算法几种调度策略的评价,本章主要讨论处理机调度问题,3,1.作业的状态及其转换提交状态：一个作业被提交给机房后或用户通过终端键盘向计算机键入其作业时所处的状态后备状态：作业的全部信息都已通过输入机输入，并由操作系统将其存在磁盘的某些分区（存放作业的输入井）中等待运行。运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行。完成状态：作业完成其全部运行，释放出其所占用的全部资源。准备退出系统时的作业。,一、分级调度,4,作业状态及其转换图,spooling系统,提交,收容,外存,就绪,等待,运行,就绪,等待,中程调度（交换调度）,完成,长程调度（作业调度）,短程调度（进程调度）,5,长程调度（作业调度、宏观调度）按一定原则对外存输入井上的作业进行调度，并建立进程PCB。它决定允许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就变成进程或进程组。中程调度（交换调度）它决定增加部分或全部位于内存中的进程数，即允许哪些进程竞争处理机。中程调度通过使进程挂起和激活的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标，中程调度的作用是作为作业进入系统和将中央处理机分配给这些作业二者之间的一个缓冲。,2调度类型,6,短程调度（进程调度）它决定了存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即短程调度是将处理机分配给进程）。短程调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。,2调度类型,7,作业是用户向计算机提交任务的任务实体。进程是计算机为了完成用户任务实体而设置的执行实体。显然，计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。,3作业与进程的关系,8,作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存，并创建PCB.1后备作业队列与作业控制块系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。内容：作业名、作业状态、作业调度，以及资源申请和一些控制信息。,二、作业的调度,9,作业控制块JCB,10,作业调度按照某种调度算法从后备作业队列中选取作业，使其进入内存运行。作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。,1作业调度及其功能,11,按照某种调度算法从后备作业队列中选取作业。为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。为选中的作业建立相应的进程。为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还有完成作业的善后处理工作，如收回分配给他的全部资源，它们将从系统中抹去,2.作业调度应完成如下几方面的工作,12,1)调度目标对所有作业应该是公平合理长作业，短作业；重CPU作业，重I/O作业应使设备有高的利用率高吞吐率每天执行尽可能多的作业有快的响应时间,3.作业调度目标与性能衡量,13,2）作业调度的转换过程（1）作业从后备状态到执行状态（2）作业从执行状态到完成状态,3.作业调度目标与性能衡量,14,后备作业队列空,按调度算法从作业中选出一作业,调用存储、设备管理程序，审核资源要求,资源要求能满足？,放弃该作业,否,分配资源,调用进程管理程序建立进程,进程调度,否,是,出口,作业从后备状态到执行状态,15,撤销该作业的所有进程及作业的JCB,调用存储管理，设备管理回收分配给该作业的全部资源,调用会计程序，计算该作业的执行费用,调度下一个作业,作业从执行状态到完成状态,16,3）.衡量一个作业调度算法是否满足系统设计的要求给出两个常用的评价在批处理系统中对作业调度算法优劣的性能量度1周转（轮转）时间：作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。Ti=Tei-Tsi完成提交,3.作业调度目标与性能衡量,17,作业平均周转时间为（有n个作业，n=1)nT=1/nTii=1一个作业的周转时间Ti说明了该作业在系统内停留的时间，包含两部分：一是等待时间Twi；二为执行时间TriTi=TwiTri,3.作业调度目标与性能衡量,18,2带权周转时间Wi：Wi=Ti/Tri平均带权周转时间为：nW=1/nWii=1,3.作业调度目标与性能衡量,19,（1）先来先服务（FCFS）调度算法将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。,进程调度算法和作业调度算法,20,例,（单位以十进制计）,21,先来先服务算法分析结果,22,算法对短作业不利，因为短作业运行时间短，若它等待时间较长，则带权周转时间会很长。,23,该算法总是优先调度要求运行时间最短的作业。哪个进程先开始？,（2）.最短作业优先法（SJF）,24,25,（3）最短剩余时间优先法(SRT),SRT（ShortestRemainingTime）策略是抢占式的SJF策略，总是优先运行期望剩余时间最短的作业。,26,27,和SJF策略一样，根据执行时间来选择进程执行可能会引起长进程的饥饿，但由于短作业比当前运行的长作业有优先权，所以SRT策略轮转时间性能比SJF策略好。SRT策略只产生必要的中断，比轮转法的开销小。SRT策略需要记录已执行时间，增加了开销。,28,FCFS仅考虑等待时间，而SJF仅考虑执行时间。最高响应比优先（HighestResponseRatioNext）算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义为系统对作业的响应时间与作业要求运行时间的比值R响应时间/要求运行时间(作业等待时间需运行时间)/需运行时间1已等待时间/需运行时间1W/T,(4)最高响应比作业优先算法（HRRN）,29,响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获得较高的响应比。这就克服了短作业优先算法的缺点，既照顾了先来者，又优待了短作业，是FCFS和SJF算法的一种较好的折中。,30,31,四个作业的执行次序为：1、3、2、4。算法在一个作业运行完成时计算剩余的所有作业的响应比，然后选择响应比高的运行。当作业1结束后，作业2、3、4的响应比分别为：R21+(10.00-8.50)/0.50=1+3R3=1+(10.00-9.00)/0.10=1+10(*)R4=1+(10.00-9.5)/0.20=1+2.5,32,33,进程调度的功能：从就绪队列中挑选一个进程到处理机上运行。作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤销该作业的全部进程。一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态将其组织成不同的进程队列。,三、进程调度,34,进程调度程序：负责进程调度功能的内核程序。作业调度与进程调度程序的区别：前者是挑选作业进主存运行、后者是挑选就绪进程到处理机上运行。进程调度的核心问题就是，采用什么算法把处理机分配给进程。,35,（1）进程优先数调度算法,分为可抢占CPU和不可抢占CPU两种优先数的指派A、静态在进程创建时确定，一经确定之后在整个进程运行期间不再改变B、动态综合考虑以获得较好的调度性能,36,Unix进程优先数计算：P_pri=min127,(p_cpu/16+p_nice+PUSER)其中，p_cpu和p_nice都是当前pcb的分量，p_cpu反映了进程使用CPU的程度；p_nice是程序可以设置的进程优先数偏置值；PUSER固定为100。,37,公平分享调度策略,公平分享调度Fair-ShareScheduling(FSS)每个用户被赋予某种权限，它规定了该用户所占全部资源的份额。所有用户共享一个处理机。公平分享调度的目的是监视用户使用资源的情况，使超过其份额的用户获得较少的资源，而少于其份额的用户获得更多的资源。,38,UNIX系统实现,P187图6.13,39,（2）循环轮转调度（RR）,循环轮转（RoundrobinRR）1、简单循环轮转调度2、可变时间片轮转调度,40,时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先服务原则调度，但一旦进程占有处理机仅使用一个时间片。在使用完一个时间片后，进程还没又完成其运行，它必须释放出处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队等待再次运行。,简单循环轮转调度,41,时间片SR/NmaxR响应时间Nmax最大进程数,42,时间片轮转策略特别适合于分时系统中使用，当多个进程驻留在主存中时，在进程间转接处理机的开销一般是不大的。在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间，如果时间片长度过短，则调度程序剥夺处理机的次数增多，这将使进程上下文交换次数也大大增加，加重了系统开销。如果时间片长度选择过长（大）。大到一个进程足以完成其全部运行工作所需的时间，那么时间片轮转法就退化为先来先服务策略了。最佳的时间片量值应能使分时用户得到好的响应时间,43,可变时间片轮转调度,每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次值。作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程数变化的。,44,（3）多级反馈队列(Feedback,FB),FB策略是指进程依赖于其条件的变化从一个队列移到另一队列，是抢占式调度算法。它综合考虑了多种因素，根据进程运行情况的反馈信息动态改变进程的优先级，按优先级别组织设置了规定CPU时间片的各就绪队列；对同一队列中的各就绪进程按FCFS或RR算法调度。随优先数的降低，时间片增加。FB策略不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，是目前公认为较好的一种进程调度策略。,45,进程调度的算法较多，在设计进程调度算法时应考虑的因素多，比如：尽量提高资源利用率，减少处理机的空闲时间，对于用户作业要较合理的平均响应时间，以及尽可能地增强CPU的处理能力。,四、选择调度算法时应考虑的问题,46,1.FIFO(先来先服务调度算法)最简单的调度原则是先进先出(FIFO)就绪队列,A,B,C,D,CPU,完成,五、调度策略评价,47,根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非抢占（剥夺）调度。这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。,48,在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。,49,根据作业要求系统提供的处理机时间，内存的大小和I/O设备的数量，来确定作业的优先数，如果系统赋予作业的优先数反比于系统的估计执行时间，就形成短作业优先的算法。由于作业需要的执行时间事先难于确定，只是把用户自报的估计时间作为依据，为防止用户少报自己的作业时间以获得优先服务，在采用短作业优先算法时，应采取适当的防备措施。,2.作业要求的资源,50,在有的系统中，分配给作业的优先数还取决于它所占用的内存的多少，作业越大，占用内存越多，分配给它的优先数越低。显然，不论是根据作业的执行时间，还是根据作业的大小所确定的优先数，都有利于短作业。,51,3.动态优先数,虽然基于静态优先数的调度算法比较简单，也颇为流利，但毕竟不够精确。因为进程的优先数在它执行前就已算好，且在整个执行期间都保持不变，但随着进程的推进，计算优先数所依赖的特征很多都将随之改变，因此静态优先数并非自始至终都能准确地反映出这些特性，如果能在进程运行中，不断的随着特性的改变而修改其优先数，显然可以实现更多精确的调度，从而获得更好的调度性能，这对分时系统显得格外重要.,52,4.时间片轮转算法,F,C,B,A,.,CPU,完成,A,BC,当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。当时间片非常小时，上下文转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。,53,这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程异。时间片的选取是实现各种调度算法的关键之处，而时间片的确定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。时间片轮转法亦可应用于批处理系统的处理机调度。,54,系统中有两类进程，系统进程和用户进程。系统进程的优先数比用户进程的优先数高，特别是某些系统进程，必须赋予它一种特权，当它需要处理机时，应尽快得到满足。例如，设备管理器中的I/O进程便是如此。这不仅是为了保证I/O设备尽可能忙碌，以提高设备利用率，更主要的是为了避免由于响应不及时，将造成信息的丢失。在用户进程中，I/O繁忙的进程应优先于CPU繁忙的进程，以保证CPU和I/O设备之间的并行操作。在分时系统中，前台进程应优先于后台进程。,进程类型,55,什么是多处理机系统多处理机操作系统的分类多处理机系统调度策略,六、多处理机调度,56,多处理机系统：是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的计算机系统。特点：1）有两个或多个处理机2）共享主存或高速通信网络3）共享输入输出子系统4）有单一完整的操作系统5）各级硬件和软件相互作用,什么是多处理机系统,57,主要功能：进程分配更好的利用多机硬件资源在处理机之间的分配改善程序的响应时间处理机的负载平衡处理机间的协调和同步因处理机故障引起的系统重组,58,广意上说，使用多处理机协调工作，来完成用户所要求任务的计算机系统。这包括了并行处理系统（parallelprocessingsystem），例如数据流机(dataflowmachine)和细胞阵列处理机(Celluararrayprocessors)等,也包括了在物理上分散且通过不同的物理传输媒体传输数据的机算机网络系统和计算机网络为基础的、对用户透明的分布式系统,以及在同一的计算机系统里共享内存的多处理机系统.广义的计算机系统的一个共同的特点是有n个处理器(n1),能做到真正的并行处理,也就是能同时执行n条指令.,59,本节所介绍的多处理机操作系统是指哪些用来并行执行用户的几个程序，以提高系统的吞吐率；或冗余操作以提高系统可靠性的多处理操作系统。这种系统由共享公共内存和外设的n(n1)个CPU组成。从概念上说，在多处理机系统中的各进程的行为与在单机系统下的行为相同。因此，对多处理机操作系统的要求与对多道程序的批处理系统没有太多的区别。但是，多处理环境下，进程可在各处理机间进行透明迁移，从而，由进程上下文切换等带来的系统开销将使得多处理机操作系统的复杂度大大增加。另外，由于多处理机系统并行地执行用户的几个程序（进程），这又带来了多处理机条件下的并发执行问题。,多处理机操作系统的分类,60,使用多处理机系统的主要原因是提高系统的可靠性和在发生故障时能降级使用；另一个原因是提高系统吞吐。因此，一个多处理机操作系统除了提高资原分配和管理，进程和处理机管理，内存和数据集保护以及文件系统等功能之外，还能提供系统结构重组的能力，以支持系统的降级使用。因此，多处理机的调度策略也必须考虑到降级使用和结构重组问题。目前为止的多处理机操作系统可以分为三类：(1)主从式（master-slaveconfiguration）(2)独立监控系统(Separatesupervisor)(3)移动式监控系统(floatingsupervisor),61,主从式中，指定一台特定的处理机为主处理机，由它负责对全系统的执行进行控制.在主从式操作系统中，主处理器上执行操作系统程序，以控制其它从处理机的状态，并为从处理机分配任务。DECsystem10,Cyber170以及多处理机UNIX系统MPX都是主从式结构.在主从式操作系统中,如果从处理机需要主处理机提供服务时,它们采用硬件中断方式中断处理机上执行的进程以要求主处理机提供服务.这种结构的操作系统一般重组功能较差,因为只有主处理机上执行操作系统程序.如果主处理机失败或发生不可恢复的错误时,整个系统将会瘫痪.,(1)主从式（master-slaveconfiguration）,62,独立监控系统的监控程序在每个处理机上执行,每个处理机为自己的需要提供服务又互相通报执行情况.一般来说,每个监控程序能重新装入或在不同的处理机上复制独立的副本.独立监控系统不像主从结构那样易于崩溃,但其监控程序在各处理机中的副本会占去大量的内存.,(2)独立监控系统(Separatesupervisor),63,移动式监控系统：移动式监控系统把监控程序根据需要从一个处理机移到另一个处理机上.使所有资原有比较均衡的负载.移动式监控系统的处理机调度以及服务请求冲突等大都采用优先级的方式来解决.所以移动式监控系统是一种效率最高,实现也最难的多处理操作系统.,(3)移动式监控系统(floatingsupervisor),64,（1）多处理机系统与单机调度的区别多处理机调度与单机调度的主要区别涉及两个资源分配问题：一是存放程序或数据的存储器分配及如何访问他们的问题。在多机系统中，由于各进程在物理上也同时执行而不是单机系统那样的交叉执行，这些在物理上同时执行的进程可能同时访问物理存储器的同一地址。处理机对同一存储块的访问必须是顺序的。各进程同时访问物理存储器上的同一地址是不允许的。,多处理机系统调度策略,65,二是将等待执行的就绪进程分配到哪一个处理机上执行的问题。在单机系统中，由于只有一个处理机，在调度程序中选取了某个就绪状态的进程之后，不须再选择处理机。而在多机系统中，为了尽量做到让各处理机负荷平恒，可能会会将处理机在进程之间进行多次切换。如果被切换进程正在执行其临界区部分或系统中进程数目相当多，这种频繁的上下文转换将会使系统效率大大下降。,66,为了解决进程对处理机的分配问题，在有的多出理机系统中采用了局部就绪对列的方法限制进程的转移。局部就绪队列：就是把处于就绪状态的进程分成不同的组，并使每一组进程和一个处理机对应起来。这样，每个处理机只执行以其对应就绪对列中的进程。各个就绪队列中的进程不会发生横向转移。这种方法减少了调度程序的开销。但是，处理机的使用率却因此下降。例如：系统中某个局部就绪对列中因等待进程较多而使得对应的处理机十分繁忙，而另外的处理机则因就绪对列为空而处于空闲状态。,67,多处理机系统的调度目标是：以最高的可靠性，使用最少的处理机在最短的时间内完成最多的可以并行完成的进程。,68,多处理机的调度有两种评价模型：一种是确定性模型，另一种是随机性模性。确定性模型：进程调度执性之前，估计出这些被调度进程所须要的执行时间，以及这些进程之间的相互关系。调度程序的目的：是根据给定的执行时间和相互关系，确定出一个最佳的执行顺序。因此，确定性模型只用来确定给定进程的执行顺序，而随机性模性则常被用来研究动态调度技术。,（2）多处理机的调度评价,69,调度策略,1.线程调度使用了线程这个概念之后，执行的概念就与进程分开了。一个应用程序可用一系列线程的形式完成，它们之间相互配合，并在相同的地址空间同时运行。在多处理机上调度线程和处理机分配时，较多使用以下四种方法：负载共享、群调度、专用处理机分配、动态调度。,70,调度策略,2.负载共享线程并不分配给某一特定的处理机。系统中有一个全局就绪队列，每个处理机空闲时就从该队列中选择一个线程。这里的负载共享要与负载平衡相区别。负载共享是最简单的方法，它直接继承了单处理机系统的许多好处。,71,调度策略,负载共享的优点：对处理机平均分配负载；不需要集中调度者；对就绪队列可按单处理机所采用的各种方式加以组织，其调度算法也可沿用单处理机所用的算法。负载共享的缺点：集中队列占据了部分内存，对它的访问要求互斥。因此，在许多处理机同时都要工作时，就会成为瓶颈；被抢占进程不可能再在同一台处理机上运行；如果所有进程都被放入一个公共线程池，那么同一程序的所有线程不可能同时获得处理机。,72,调度策略,3.群调度相关联的线程集被一个处理机集一对一调用。群调度用于组成一个进程的多个线程的同时调度。群调度对于中粒度和细粒度的并行应用是必要的。它提高了紧耦合进程并发执行的效率，减少了调度耗费。群调度的使用产生了对处理机分配的需求。研究表明，群调度策略的某些形式在总体上要比负载共享要好。,73,调度策略,4.专用处理机分配与自我调度相对应，其调度是隐式的，在程序执行期间，每个程序都被分配与其线程数相等的处理机，程序结束时，将所有的处理机归还，以便其他程序使用。专用处理机分配和群调度在调度时都涉及到处理机分配。多处理机系统上的处理机分配类似于单处理机系统上的请求调页式内存分配。群调度和专用处理机分配可以避免处理机抖动和处理机碎片等这些问题。,74,调度策略,5.动态调度程序的线程数可随程序的的执行而改变。操作系统负责作业的处理机分配，每个作业使用处理机，将其可运行的任务集映射成线程，由应用决定运行哪个子集。这种方法中，操作系统的调度仅限于处理机分配。这种方法并不适合所有的应用。对适合于动态调度的任务来说，这种方法比群调度和专用处理机分配要好。,75,实时调度,实时计算是一项重要的计算机科学和工程设计的方法。操作系统，特别是调度，可能是实时操作系统最重要的组件。,76,实时操作系统的特性,1.决定性与响应性决定性是指系统得知中断前的延迟时间；响应性是指系统在得知中断后多长时间内对这个中断进行服务。衡量系统决定性能力的有效方法是衡量从一个高优先权设备中断到服务开始的最大延迟。响应包括初始处理中断和开始常规中断服务(ISR)的时间、执行ISR的时间、中断嵌套的影响。决定性和响应性一起决定了对外部事件的响应。,77,实时操作系统的特性,2.用户控制用户控制在实时操作系统中要比其他操作系统应用得要广。在实时操作系统中，有必要允许用户详细控制任务优先级，也应允许用户指定分页或进程交换的特性。,78,实时操作系统的特性,3.可靠性可靠性对实时操作系统比对非实时操作系统要重要得多，实时操作系统必须实时响应和控制事件，性能下降也许会导致可怕的后果。,79,实时操作系统的特性,4.弱失效操作弱失效操作就是指系统在失效时尽量保护其数据的能力。弱失效操作的一个重要方面是稳定性。,80,实时操作系统的特性,实时系统的特性：快速现场切换；尺寸小；迅速响应外部中断；多任务并存，并有如信号量、信号、事件等进程间通信工具；使用专门的线性文件来收集数据；基于优先权的抢占调度；最小化禁止中断的时间间隔；简单地延迟任务一段时间或停止重新开始任务；特殊