操作系统原理第3章 处理器调度

操作系统原理OperatingSystemPrinciples,四川大学计算机学院段磊leiduan2014Spring,第3章处理器调度,处理器调度指在多道程序环境下将处理器分配给各进程。在处理器调度中，合理的调度算法能够提高处理器的处理能力和系统性能，满足用户需求。,2020/4/30,计算机操作系统-第3章,3/98,本章目录,3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度,2020/4/30,计算机操作系统-第3章,4/98,3.1处理器调度的层次,内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念,2020/4/30,计算机操作系统-第3章,5/98,3.1处理器调度的层次,内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念,2020/4/30,计算机操作系统-第3章,6/98,调度的概念与本质,调度：系统将计算机资源分配给进程。单道程序环境与多道程序环境处理器调度：多道程序环境下将处理器分配给各进程,2020/4/30,计算机操作系统-第3章,7/98,调度要解决的问题：WHAT：按什么原则分配CPU调度算法WHEN：何时分配CPU调度的时机HOW：如何分配CPU调度过程,调度的概念与本质,2020/4/30,计算机操作系统-第3章,8/98,处理器调度的层次,处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响处理机调度的三个层次：高级调度中级调度低级调度,高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天,中级调度涉及进程在内外存间的交换从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问,低级调度也称微观调度从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效。,2020/4/30,计算机操作系统-第3章,9/98,高级调度-作业的概念与分类,概念：作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。分类：根据需要处理工作的类型，分为计算型作业和I/O型作业。按照作业提交方式，分为批处理作业和终端型作业。一个系统能够同时接纳作业的个数称为系统的多道程序度。,2020/4/30,计算机操作系统-第3章,10/98,作业的状态：提交状态后备状态执行状态完成状态,高级调度-作业的概念与分类,作业被调度到内存，为作业分配资源并为其创建与之对应的进程，进程获得CPU，开始运行。,从作业的第一个进程完成开始，直到作业所有的进程完成，释放作业所占用的资源，退出系统的整个进程。,系统接收输入的用户作业，并将其放入计算机磁盘。作业在磁盘上以后备队列形式进行组织，等待作业调度程序将作业调度到内存。,用户将作业提交给操作系统，等待输入程序和数据到磁盘。,2020/4/30,计算机操作系统-第3章,11/98,高级调度-概念与模型,作业调度概念：按照操作系统预先规定的策略，从磁盘的作业后备队列中选择作业调入内存，为作业分配所需要的资源并建立与作业相对应的进程。当作业运行的准备工作完成后，作业调度启动作业运行。在作业运行结束后，作业调度归还并释放作业占用的资源，结束作业。模型：,2020/4/30,计算机操作系统-第3章,12/98,高级调度-策略与因素,接纳多少个作业作业数目太多时，可能会影响到系统的服务质量;作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低接纳哪些作业先来先服务调度算法短作业优先调度算法基于作业优先级的调度算法响应比高者优先的调度算法,2020/4/30,计算机操作系统-第3章,13/98,高级调度-OS任务,作业调度中操作系统需要完成如下主要工作：确定作业的数据结构确定作业的调度算法为作业分配资源回收作业资源,操作系统为每个进入系统的作业分配一个与进程控制块（PCB）类似的作业控制块（JCB）JCB是作业的标志，OS根据JCB中的信息对作业进行调度和管理。,作业运行需要各种资源，包括硬件资源和软件资源。硬件资源有内存、处理器和各种输入输出设备。软件资源有各种共享变量等。作业的资源分配策略主要考虑的是作业所包含的进程所需要的资源，在一般情况下，资源按照进程需求进行分配。资源分配中需要避免由进程之间的资源竞争而造成的死锁等现象。,作业完成后，作业调度程序除了要输出相关的作业信息之外，还要回收作业所占用的全部资源，撤销与作业相关的进程和作业控制块。在作业调度工作中，大多数工作由作业的调度程序完成。内存和输入输出设备的分配和释放不是由作业调度程序完成，而是由存储器管理和设备管理程序完成的。作业调度程序只是将作业对内存的要求和对设备的要求转交给相应的内存管理程序和设备管理程序，由内存管理程序和设备管理程序完成内存和设备的分配与回收。,2020/4/30,计算机操作系统-第3章,14/98,高级调度-作业状态转换,作业调度将作业从后备状态转换到内存执行状态作业执行状态包含作业所对应进程的就绪、运行和阻塞状态,2020/4/30,计算机操作系统-第3章,15/98,3.1处理器调度的层次,内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念,2020/4/30,计算机操作系统-第3章,16/98,中级调度-概念与功能,又称为中程调度，是为了提高内存利用率和平衡系统负载而采取的一种利用外存补充内存的措施。多进程环境下，内存中存在多个进程，其中有些进程可能需要挂起，这些进程暂时不参与对处理器的竞争。为了充分利用内存资源，系统会采用进程对换的方法将进程换出到外存，将这些进程占用的内存空间释放，让内存能够接纳新的进程或使得内存中的进程能够更快推进。当被换出到外存中的进程挂起时间到时，又需要将这些进程换入到内存。中级调度是在换出内存的进程中确定需要进入内存的进程的一种调度操作。,2020/4/30,计算机操作系统-第3章,17/98,3.1处理器调度的层次,内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念,2020/4/30,计算机操作系统-第3章,18/98,低级调度-概念与功能,又称为进程调度、短程调度按照一定的调度算法从内存的就绪进程队列中选择进程，为进程分配处理器，避免进程对处理器竞争的方法。与作业调度和中级调度比较，进程调度发生的频率最高，作业调度发生的频率最低，中级调度主要用于内存管理，特别是虚拟存储器管理。,2020/4/30,计算机操作系统-第3章,19/98,3.1.2进程调度模型,只有进程调度的调度队列模型,低级调度-模型,2020/4/30,计算机操作系统-第3章,20/98,3.1.2进程调度模型,具有高、低两级调度的调度队列模型,低级调度-模型,2020/4/30,计算机操作系统-第3章,21/98,具有三级调度时的调度队列模型,3.1.2进程调度模型,低级调度-模型,2020/4/30,计算机操作系统-第3章,22/98,低级调度-原因与机制,引起进程调度的主要原因如下：处理器执行的进程完成任务，处理器空闲处理器执行的进程转入阻塞状态，此时处理器空闲处理器执行的进程被其它进程抢占处理器执行的进程被挂起机制：排队器分派器上下文切换机制,2020/4/30,计算机操作系统-第3章,23/98,低级调度-调度方式,非抢占方式：简单，实时性差抢占方式时间片原则优先权原则短作业优先原则,如果执行进程正好在执行一个没有资源的无限循环，则执行进程不会放弃处理器，所有的就绪进程会永久等待，系统进入了一种僵持的状态。,指一个进程正在处理器中运行时，操作系统可以根据规定的抢占原则，将已经分配给进程的处理器从进程剥夺，并分配给其他的进程。,在系统允许抢占调度，并满足抢占条件的情况下，系统才可以采用抢占调度方式。,满足抢占条件的进程能够抢占当前正在执行进程的处理器。被抢占的进程状态从执行状态变为就绪状态，其进程控制块进入到进程就绪队列。,思考：“抢占”可能带来的问题及原因？,2020/4/30,计算机操作系统-第3章,24/98,本章目录,3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度,2020/4/30,计算机操作系统-第3章,25/98,3.2评价调度算法的准则,内容准则评价指标要点指标含义计算方式,2020/4/30,计算机操作系统-第3章,26/98,调度算法的评价准则,基本原则：具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量,面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用,面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则,2020/4/30,计算机操作系统-第3章,27/98,处理器利用率CPUutilization响应时间responsetime周转时间turnaroundtime系统吞吐量throughput,处理器利用率为CPU有效工作时间与CPU总的运行时间之比，即：CPU利用率=CPU有效工作时间/CPU总的运行时间CPU总的运行时间=CPU的有效工作时间+CPU的空闲时间,响应时间是交互环境下用户从键盘提交第1个请求开始，到系统首次产生响应为止的时间，或者是屏幕上显示出结果为止的时间。响应时间=从终端键盘输入的请求信息传送到处理机的时间+处理机对请求信息的处理时间+生成的响应信息回送到终端显示器的时间,周转时间指用户作业提交给操作系统开始到作业完成为止的时间。周转时间通常是评价批处理系统性能、选择作业调度方式与算法的重要准则之一。周转时间Ti=作业在后备队列中的等待调度时间+进程在就绪队列上等待调度的时间+进程在CPU上的运行时间+进程等待I/O或其他事件发生的时间作业的带权周转时间Tf=作业的周转时间Ti/系统为作业提供的服务时间Tsi,单位时间内处理的进程数目为CPU的工作成效，单位时间内完成的进程数目为系统的吞吐量。,在选择处理器的调度算法时，用户希望CPU利用率和系统吞吐量越大越好，响应时间和周转时间越小越好。但是，通常情况下，系统希望的是能够合理利用处理器和各类资源，使作业的平均周转时间或带权周转时间小的调度算法。对于实时系统，作业调度的关键在于能否满足作业的实时要求，对周转时间等指标并不特别着重。,调度算法的评价指标,2020/4/30,计算机操作系统-第3章,28/98,本章目录,3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度,2020/4/30,计算机操作系统-第3章,29/98,3.3调度算法,内容作业调度算法进程调度算法要点算法思想指标计算,2020/4/30,计算机操作系统-第3章,30/98,3.3调度算法,内容作业调度算法进程调度算法要点算法思想指标计算,2020/4/30,计算机操作系统-第3章,31/98,作业调度算法,概念回顾作业调度是在资源满足的条件下，将处于后备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。作业调度程序只保证被调度的作业有获得处理器的资格，而处理器的分配则需要进程调度才能完成。主要算法FCFS：先来先服务（First-ComeFirst-Served)SJF：短作业优先（Shortest-Job-First）HRRF：响应比高者优先HPF：优先权高者优先（Highest-Priority-First)分类调度,2020/4/30,计算机操作系统-第3章,32/98,FCFS：先来先服务,基本思想遵循先进入后备队列的作业，先进行调度的原则。非抢占式算法简单，易于编码实现优先考虑作业的等待时间，没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求算法评价有利于长作业，不利于短作业有利于CPU繁忙的作业，不利于I/O繁忙的作业举例？,2020/4/30,计算机操作系统-第3章,33/98,FCFS：先来先服务-例1,作业J1、J2、J3、J4依次到达作业后备队列，需要处理时间分别如下：J1为15ms，J2为5ms，J3为10ms，J4为3ms。请给出作业执行的图示（横轴为时间，纵轴为作业）请计算每个作业的等待时间和周转时间请计算上述作业的平均等待时间和平均周转时间,2020/4/30,计算机操作系统-第3章,34/98,FCFS：先来先服务-例2,如果4个作业A、B、C、D到达系统磁盘后备队列的顺序和需要执行的时间如下表所示。,请给出作业执行的图示（横轴为时间，纵轴为作业）请计算每个作业的周转时间和带权周转时间请计算上述作业的平均周转时间和平均带权周转时间,2020/4/30,计算机操作系统-第3章,35/98,SJF：短作业优先,基本思想根据作业控制块中作业申请时指出的执行时间，选取执行时间最短的作业优先调度。抢占调度方式：只要就绪队列中出现了需要执行时间比当前正在运行作业的剩余处理时间更短的作业，则该作业会抢占当前正在运行的作业。算法评价克服FCFS调度算法对短作业不利的缺点，效率高，易于编程实现不利于长作业预先估计作业的执行时间举例？,2020/4/30,计算机操作系统-第3章,36/98,SJF：短作业优先-例3,作业A、B、C、D需要处理的时间分别为20ms、15ms、10ms、5ms。如果这4个作业同时到达作业后备队列请给出采用短作业优先调度算法的作业执行图示请计算平均周转时间和平均带权周转时间,如果这4个作业不是同时到达，A作业在0时间到达，B作业在A作业之后5ms达到，C作业在A作业之后10ms达到，D作业在A作业之后15ms达到请给出采用短作业优先调度算法的作业执行图示请计算平均周转时间和平均带权周转时间,如果A作业到达的时间为0，B、C、D作业达到系统的时间分别改为1ms、2ms、3ms请给出采用短作业优先调度算法的作业执行图示请计算平均周转时间和平均带权周转时间,2020/4/30,计算机操作系统-第3章,37/98,HRRF：响应比高者优先,初衷FCFS调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。响应比高者优先调度算法为这两种算法的折中。响应比计算作业的响应时间与作业需要处理的时间之比。作业的响应时间为作业进入系统后的等待时间与作业要求处理器处理的时间之和。抢占调度方式,2020/4/30,计算机操作系统-第3章,38/98,HRRF：响应比高者优先,分析与评价响应比高，可能是因为作业等待时间长，也可能是因为作业需要处理时间短。响应比高优先调度算法不仅体现了等待时间长的作业会优先调度，而且还体现了处理时间短的作业也会优先调度。该算法能够客观地对待长作业和短作业。举例？,2020/4/30,计算机操作系统-第3章,39/98,HRRF：响应比高者优先-例4,如果4个作业A、B、C、D到达系统磁盘后备队列的顺序和需要执行的时间如下表所示。,计算各时间点的响应比及调度情况。请给出作业执行的图示（横轴为时间，纵轴为作业）请计算上述作业的平均周转时间和平均带权周转时间,2020/4/30,计算机操作系统-第3章,40/98,FCFS、SJF、HRRF：比较,思考：对上述比较结果进行分析和评价。,2020/4/30,计算机操作系统-第3章,41/98,HPF：优先权高者优先,基本思想根据作业的优先权进行作业调度，每次总是选取优先权高的作业调度。作业的优先数可由系统或用户给定。评价综合考虑了作业的执行时间和等待时间的长短、作业的缓急程度、作业对外部设备的使用情况等因素根据系统设计目标和运行环境而给定各作业的优先权，决定作业调度的先后顺序。举例？,2020/4/30,计算机操作系统-第3章,42/98,HPF：优先权高者优先-例5,作业A、B、C、D一起达到，需要处理的时间分别为25ms、5ms、10ms、3ms，优先数分别为154、139、149、130，优先数越大、优先级越低。请给出采用优先权高者优先调度算法的作业执行图示请计算平均周转时间和平均带权周转时间静态优先权动态优先权,思考：动态优先权的“动态性”体现？,2020/4/30,计算机操作系统-第3章,43/98,综合：分类调度算法,目的：均衡使用系统资源兼顾不同大小的作业基本思想按照使用系统资源或作业的大小的不同首先分别对作业进行分类然后再根据作业的类型进行调度还可以进一步将同一类别的作业再按照优先级进行排队,2020/4/30,计算机操作系统-第3章,44/98,3.3调度算法,内容作业调度算法进程调度算法要点算法思想指标计算,2020/4/30,计算机操作系统-第3章,45/98,进度调度算法,概念回顾进程调度算法是低级调度算法。在传统操作系统中，进程为资源分配和调度的基本单位，是操作系统中发生频率最高的调度。主要算法FCFS：先来先服务（略）TRR：时间片轮转调度算法优先级调度算法MQ：多级队列调度算法MFQ：多级反馈队列调度算法,2020/4/30,计算机操作系统-第3章,46/98,TRR：时间片轮转调度算法,基本思想分时思想首先将处理器的处理时间划分为大小相等的时间片。调度程序每次从就绪队列中选择队首的进程，为之分配处理器的一个时间片并让进程运行。当进程运行的时间片到时，强迫进程放弃处理器，到就绪队列中再次排队，并将处理器的下一个时间片分配给就绪队列中队首的进程。所有就绪队列中的进程按照这样的形式轮转使用处理器时间片。举例?,2020/4/30,计算机操作系统-第3章,47/98,TRR：时间片轮转调度算法-例6,进程A、B、C、D需要处理的时间分别为20ms、10ms、15ms、5ms，在0时间达到。达到的先后顺序为ABCD。请给出不同时间片下的调度图示；请计算不同时间片下的平均周转时间。A：时间片为1A：时间片为5A：时间片为10,思考：时间片大小与平均周转时间的关系？,2020/4/30,计算机操作系统-第3章,48/98,TRR：时间片轮转调度算法,分析与评价抢占式调度算法进程切换以时间片为单位，系统的花销主要体现在进程切换上。当时间片很小时，切换的频率高，时间片花销大。当时间片过大时，进程切换开销减小，但是进程轮转一次需要的等待时间增加，周转时间增加。当时间片大到每个进程足以完成时，时间片调度算法便退化为FCFS算法。时间片大小的取值需要考虑系统中进程个数、进程切换开销、响应时间、系统效率等多种因素。,思考：固定大小时间片与可变大小时间片？,2020/4/30,计算机操作系统-第3章,49/98,优先级调度算法-例7,同时达到的进程P1、P2、P3、P4，它们的优先数分别为80、70、75、65，数字越大表示进程优先级越高，需要处理的时间分别是20ms、15ms、25ms、30ms。请给出采用优先级算法的调度图示；请计算平均周转时间和平均带权周转时间。,2020/4/30,计算机操作系统-第3章,50/98,MQ：多级队列调度算法,基本思想根据进程的类型不同，将进程就绪队列分为若干个独立的就绪队列，不同的就绪队列采用不同的调度算法，同一个就绪队列采用同一种进程调度算法。主要用于有多组就绪进程的操作系统，如有批处理用户作业的进程和终端用户进程，批处理用户作业的进程运行在后台，终端用户的进程运行在前台。一个作业的进程固定划分到一个就绪队列中。按照用户作业的性质不同，就绪队列进行不同组织。,2020/4/30,计算机操作系统-第3章,51/98,作业-进程调度,某多道程序设计系统中配有一台处理器CPU和两台输入/输出设备IO1和IO2。现有优先级由高到低的3个进程P1、P2、P3同时存在，它们使用资源的先后顺序和占用时间分别是：进程P1：进程P2：进程P3：,IO2(30ms)-CPU(10ms)-IO1(30ms)-CPU(10ms)-IO2(10ms),IO1(20ms)-CPU(20ms)-IO1(40ms),CPU(30ms)-IO2(20ms),若进程采用“可抢占的最高优先级”调度算法，且忽略调度等所需的时间，请回答有下列问题：1）进程P1、P2、P3从开始到完成所用的时间分别是多少（要求用坐标画出三个进程的工作过程，其中横坐标表示时间，纵坐标表示CPU和IO设备）。2）这三个进程从开始到全部完成时CPU的利用率是多少？IO1和IO2的利用率是多少？,2020/4/30,计算机操作系统-第3章,52/98,本章目录,3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度,2020/4/30,计算机操作系统-第3章,53/98,线程调度,现代OS中，进程是资源分配的基本单位，线程是调度的基本单位。因此，低级调度为线程调度。由于线程需要进程环境的支撑，因此，线程调度与线程和进程之间的关系有关。线程的实现方式有:用户级线程内核级线程,2020/4/30,计算机操作系统-第3章,54/98,线程调度,现代OS中，进程是资源分配的基本单位，线程是调度的基本单位。因此，低级调度为线程调度。由于线程需要进程环境的支撑，因此，线程调度与线程和进程之间的关系有关。线程的实现方式有:用户级线程内核级线程,2020/4/30,计算机操作系统-第3章,55/98,用户级线程,内核看不见用户级线程，内核按照进程调度分配处理器。用户级线程存在于用户地址空间内核在进程调度时，根据相应的进程调度算法。在每个进程分得的时间片中，由线程调度算法决定该进程中的线程怎样共享这个时间片，决定哪个线程首先被处理器运行。线程调度算法与进程调度算法没有关系为实现简单，线程调度算法会选择FCFS的方式。,2020/4/30,计算机操作系统-第3章,56/98,用户级线程,内核看不见用户级线程，内核按照进程调度分配处理器。用户级线程存在于用户地址空间内核在进程调度时，根据相应的进程调度算法。在每个进程分得的时间片中，由线程调度算法决定该进程中的线程怎样共享这个时间片，决定哪个线程首先被处理器运行。线程调度算法与进程调度算法没有关系为实现简单，线程调度算法会选择FCFS的方式。,2020/4/30,计算机操作系统-第3章,57/98,内核级线程,线程调度在处理器调度中起决定作用。内核会根据线程调度算法选择一个处于就绪状态的内核级线程运行。在选择线程时，内核不会考虑该线程属于哪一个进程，对所有进程的所有线程都公平对待，任何一个线程都被看作一个独立的线程。线程最大的优势在于应用在多处理器环境下,2020/4/30,计算机操作系统-第3章,58/98,内核级线程,线程调度在处理器调度中起决定作用。内核会根据线程调度算法选择一个处于就绪状态的内核级线程运行。在选择线程时，内核不会考虑该线程属于哪一个进程，对所有进程的所有线程都公平对待，任何一个线程都被看作一个独立的线程。线程最大的优势在于应用在多处理器环境下,2020/4/30,计算机操作系统-第3章,59/98,本章目录,3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度,2020/4/30,计算机操作系统-第3章,60/98,实时调度,实时操作系统中的处理器调度为实时调度。实时调度要求能够控制实时进程，满足实时任务的时间限制。在实时系统中，衡量调度性能的指标不是周转时间和等待时间，而是能否满足实时任务的截止时间要求。,2020/4/30,计算机操作系统-第3章,61/98,3.5.1实时调度需要满足的条件,实时任务截止时间是实时调度的基本指标。实时调度需要满足如下条件：系统向实时调度提供与实时任务相关的信息对系统处理能力的衡量抢占调度和快速切换机制,2020/4/30,计算机操作系统-第3章,62/98,与实时任务相关的信息（1）,就绪起始时间实时任务对应的进程被创建并加入到进程就绪队列如果实时任务是周期任务，就绪起始时间是一个时间串如果实时任务是非周期任务，就绪起始时间是一个预知的值截止时间当实时系统中的实时任务发生时，实时系统中的就绪进程按照进程的截止时间进行排列对于周期性实时任务，截止时间为下一次任务发生的时间对于非周期性实时任务，任务的所有者需要提供截止时间,2020/4/30,计算机操作系统-第3章,63/98,与实时任务相关的信息（2）,处理时间实时任务从开始到完成所需要的时间。可由实时任务的所有者提供，也可以由系统提供实时任务的资源需求实时任务执行时所需要的一组资源实时任务的优先级用户或系统需要为每个实时任务指定优先级，作为调度的依据,2020/4/30,计算机操作系统-第3章,64/98,对系统处理能力的衡量,实时系统中，可能因为处理器的处理能力不足而影响实时任务的完成，或导致系统产生故障。单处理器情况下系统对周期性的实时任务的处理，必须满足下列条件：其中，i表示周期事件，Pi为周期事件i发生的周期，Ci为需要处理器的处理时间。,2020/4/30,计算机操作系统-第3章,65/98,对系统处理能力的衡量,当系统不能调度这些周期性实时任务时，可以通过提高处理器的处理能力的方法减少每个周期任务的处理时间；或者采用多处理器系统，提高处理能力。如果采用的处理器数目为N，则处理条件变为：,2020/4/30,计算机操作系统-第3章,66/98,抢占调度和快速切换机制,在要求严格的实时系统中，允许一个优先权高的实时任务抢占优先权低的实时任务在实际应用中，判断能否满足截止时间要求不是一件容易的事快速切换机制可以实现对实时任务的快速切换快速切换机制用硬件装置实现快速中断机构，做到尽量不漏掉实时任务的中断，禁止中断的时间越短越好在软件实现上，也可以通过提高分派程序对任务切换的速度，以提高系统的性能。,2020/4/30,计算机操作系统-第3章,67/98,3.5.2实时调度算法,实时调度算法分为:动态实时调度算法在实时任务运行时作出调度决策。静态实时调度算法在系统启动实时任务之前作出调度决策。,2020/4/30,计算机操作系统-第3章,68/98,常用的实时调度算法-抢占式调度算法,常用于要求严格的实时系统中基于时钟中断的优先权抢占调度算法如果某实时任务的优先级高于正在运行的任务，该实时任务并不立刻抢占，而是等到时钟中断到来时，才抢占。立即抢占调度算法一旦出现外部中断，只要系统不处于临界区，系统立即剥夺当前执行的任务，把处理器分配给当前紧急的任务。单比率调度算法事先为每个实时任务分配一个与任务发生频率成正比的优先级，运行频率越高的任务，其优先级越高。运行时优先级高的任务可以抢占优先级低的任务。,2020/4/30,计算机操作系统-第3章,69/98,常用的实时调度算法-非抢占式调度算法,实时调度中，对于实时要求不太严格的系统，可以采用非抢占式调度非抢占式轮转调度算法运行完一个对象的实时任务（将其挂在队列尾，等待下次运行），再运行另一个对象的实时任务。所有实时任务轮转。非抢占式优先级调度算法系统按照优先级进行非抢占调度。要求紧迫的实时任务赋予高的优先级，排在就绪队列队首，先进行调度。期限调度算法根据实时任务的截止期限进行就绪队列的排队，截至期限短的实时任务排在队首，首先进行调度。,2020/4/30,计算机操作系统-第3章,70/98,常用的实时调度算法举例,实时系统中有一组实时任务A、B、C、D、E，CPU处理时间分别为325ms、225ms、160ms、95ms、420ms，截止时间分别为690ms、675ms、无期限、135ms、1100ms。如果采用最小截止期限优先调度算法，这些进程调度的顺序为？,2020/4/30,计算机操作系统-第3章,71/98,常用的实时调度算法举例,实时系统中有一组实时任务A、B、C、D、E，CPU处理时间分别为325ms、225ms、160ms、95ms、420ms，截止时间分别为690ms、675ms、无期限、135ms、1100ms。采用最小截止期限优先调度算法，进程调度的顺序为：DBAEC,2020/4/30,计算机操作系统-第3章,72/98,本章目录,3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度,2020/4/30,计算机操作系统-第3章,73/98,多处理器调度,计算机系统有多个处理器，多个处理器的调度称为多处理器调度。多处理器调度与多处理器系统的结构形式有关：松耦合多处理器系统每个处理器相对独立，拥有自己的内存和I/O通道。多处理器调度对系统中的每个处理器，采取与单处理器调度相同的方法。紧耦合多处理器系统多个处理器共享内存和外围设备，处理器的相对独立性差。在这种多处理器系统中，处理器调度方法比较复杂。,2020/4/30,计算机操作系统-第3章,74/98,多核处理器,多核处理器是在一个处理器中封装多个处理核（单元），每个核都具有处理能力。多核处理器相当于共用内存和外围设备的多处理器，在原理上多核处理器属于紧耦合多处理器系统。,2020/4/30,计算机操作系统-第3章,75/98,3.6.1多处理器中同步的粒度,在多处理器系统中，不但存在多处理器的并行，还存在单处理器的并发。多处理器中同步的粒度指系统中的多个进程或线程之间同步的频率，是描述多处理器系统特征和进程并发度的重要指标。根据进程或线程之间同步的周期划分为5个层次：细粒度并行、中粒度并行、粗粒度并行、超粗粒度并行、独立并行。,2020/4/30,计算机操作系统-第3章,76/98,同步的周期,细粒度并行同步周期小于20条指令，非常复杂的并行操作，属于超高并行度应用中粒度并行同步周期为20200条指令。此类应用适合于多线程技术实现，多线程并发执行，降低OS在进程切换上的开销。粗粒度并行同步周期为2002000条指令，此类应用适用于多进程并发实现。超粗粒度并行同步周期为2000条指令以上，进程之间的交互频率非常小。独立并行进程之间没有明显的同步，每个进程都代表独立的应用或作业。,2020/4/30,计算机操作系统-第3章,77/98,同步的周期,一个具有细粒度和中粒度并行的线程应用，由于线程之间的交互非常频繁，线程的调度策略对整个系统的性能有很大影响。对具有独立并行的进程、具有粗粒度并行的进程和超粗粒度并行的进程，进程的调度策略与多道程序系统相似。,2020/4/30,计算机操作系统-第3章,78/98,3.6.2多处理器调度的设计要点,多处理器调度策略的设计比单处理器复杂，其设计要点包括：多处理器分配策略如何在每个处理器上支持多道线程如何从就绪队列中指派进程,2020/4/30,计算机操作系统-第3章,79/98,多处理器分配策略,（1）结构上多个处理器地位相同多处理器对内存和I/O设备的访问方式相同，地位相当所有处理器放在一个处理器池中静态分配策略在进程创建时系统把所创建的进程永久分配给一个处理器，每个处理器对应一个进程调度队列。动态分配策略所有处理器共用一个进程就绪队列，当某个处理器空闲时，系统从进程就绪队列中调度一个进程运行。,优点：实现简单，调度代价低缺点：容易造成处理器之间工作负荷不均匀,2020/4/30,计算机操作系统-第3章,80/98,多处理器分配策略,（1）结构上多个处理器地位相同多处理器对内存和I/O设备的访问方式相同，地位相当所有处理器放在一个处理器池中静态分配策略在进程创建时系统把所创建的进程永久分配给一个处理器，每个处理器对应一个进程调度队列。动态分配策略所有处理器共用一个进程就绪队列，当某个处理器空闲时，系统从进程就绪队列中调度一个进程运行。,优点:简单、方便，利于提高系统效率缺点:进程在不同处理器之间切换，系统调度进程开销大,2020/4/30,计算机操作系统-第3章,81/98,多处理器分配策略,（2）结构上多个处理器地位不同如果各处理器之间对内存和I/O设备的地位和访问方式不相同，则系统可将多个处理器分为主处理器和从处理器，主处理器管理从处理器。OS核心运行在主处理器上，所有的调度策略由主处理器上的OS核心决定，多处理器调度需要考虑每个处理器的工作负荷。优点:处理器调度效率非常高，甚至比单处理器下的多道程序系统还高。缺点:整个系统过分依赖主处理器上运行的OS核心，如果OS核心出现问题或主处理器出现问题，多处理器系统会全面崩溃。,2020/4/30,计算机操作系统-第3章,82/98,多处理器分配策略,多处理器系统如果不采用主从方式，可以采用分布式管理结构。在分布式管理结构下，OS可以在所有处理器上执行，每个处理器都可以自我调度，系统的可靠性更高。缺点：实现非常复杂，在操作系统之间很难保持同步。,2020/4/30,计算机操作系统-第3章,83/98,多处理器分配策略,综合主从式系统和分布式系统的优点，CMU的Mach操作系统就是一个典范。支持线程的操作系统建立二级线程队列，实现多处理器下线程调度第1级为一个全局共享的就绪线程队列第2级为每一个处理器的局部就绪线程队列第2级队列中所有线程都已调度完，系统才到全局就绪线程队列中按照动态调度策略分配线程,2020/4/30,计算机操作系统-第3章,84/98,如何在每个处理器上支持多道线程,如何在多处理器系统的每个处理器上支持多道线程，是多处理器系统调度的难点。（1）粗粒度并发、超粗粒度并发和独立并发的进程一个处理器上实现多进程并发，在多个处理器上实现多进程并行都是可能的（2）中粒度并发的进程，或细粒度并发的线程调度方式需分别针对不同的线程实现进行分析,2020/4/30,计算机操作系统-第3章,85/98,如何从就绪队列中指派进程,对从就绪队列中选择哪个进程运行的问题，在单处理器的进程调度算法中有先来先服务、优先级高者优先等很多方法。对多处理器系统，如果进程调度算法太复杂，调度算法的实现会使系统付出过高的代价。因此，在选择调度算法上强调的是算法使系统运行简单有效和代价低。,2020/4/30,计算机操作系统-第3章,86/98,3.6.3线程调度策略,多处理器系统中，进程与线程并发，多处理器调度中非常典型的是线程调度1负载共享调度算法2群调度算法3处理器指定调度算法4动态调度算法,2020/4/30,计算机操作系统-第3章,87/98,负载共享调度算法,如果多处理器系统是中粒度并发的进程，细粒度并发的线程，当一个处理器空闲时，系统从全局共享线程队列中选择一个就绪线程占有处理器运行。线程调度的方法有：先来先服务所有线程按照到来的先后顺序排在就绪队列最小线程数优先进程包含的未被调度线程数最少，进程获最高优先级抢占的最小数线程优先刚到达进程包含的线程数少于正执行的进程的线程数时，可抢占,2020/4/30,计算机操作系统-第3章,88/98,负载共享调度算法,优点：所有处理器均衡分配负载，不会出现作业没有完成而处理器空闲的现象。一旦有处理器空闲，OS就能在该处理器上运行调度程序，选出下一个线程。线程调度不需要集中的调度程序。就绪队列可以按照单