第7章 处理机调度与死锁1

1我们可把处理机调度分成宏观调度、中程调度和微观调度三个层次。1、作业调度（宏观调度、高级调度）任务：按一定的原则对处于外存输入井中的后备作业进行选择，给选出的作业分配内存、设备等必须资源，并建立相应的进程。在作业运行完毕后进行相应的善后工作。2、交换调度（中程调度）任务：按给定的原则和策略，将处于外存交换区的就绪状态或外存等待状态的进程调入内存，或把处于内存就绪状态或外存等待状态的进程交换到外存交换区。第7章处理机调度与死锁7.1处理机调度概述23、进程调度（微观调度、低级调度）任务：按照某种策略和方法选取一个处于就绪状态的进程占用处理机，并进行相应的上下文切换以建立与处理机进程相适应的执行环境。3具有三级调度的调度队列模型47.1.1宏观调度宏观调度在多道批处理系统中对应作业调度，就是按照系统所规定的调度算法从系统已接纳的一批作业中选取一个子集，做好运行前的准备工作，使其进入内存并运行。现代操作系统中一般不配备作业调度。作业调度完成以下几方面的工作：①按某种调度算法从后备队列中选取一个子集。②为选中的作业子集分配所需的资源，如内存、外设等。③为选中的作业子集创建相关进程。④填写修改被选中的作业的JCB及有关表格。⑤作业完成时的善后工作。57.1.2微观调度微观调度也称低级调度，微观调度才是真正的处理机调度，在实际系统中对应线程调度、进程调度或任务调度。⑴微观调度要解决的问题WHAT：按什么原则分配CPU，即调度算法。WHEN：何时分配CPU，即调度的时机。HOW：如何分配CPU，即调度过程，进程的上下文切换。6⑵进程调度器操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行状况，并在进程出让处理机或调度程序剥夺执行状态进程占用的处理机时，选择适当的进程分派处理机，完成上下文切换。我们把操作系统内核中与进程调度相关代码称为进程调度器(dispatcher)。⑶调度方式非剥夺方式：也叫非抢占方式，调度程序一旦把处理机分配给某进程或线程后便让它一直执行下去，直到进程或线程完成或等待某事件而阻塞时，才把处理机分配给另一个进程或线程。剥夺方式：也叫抢占方式，当一个进程或线程正在执行时，系统可以基于某种原则，剥夺已分配给它的处理机，将处理机分配给其他进程或线程。常用的剥夺原则有优先权原则和时间片原则。7记录系统中所有进程的执行情况选择占有处理机的进程进行进程上下文切换（5）进程调度的时机正在执行的进程执行完毕执行中的进程调用阻塞原语阻塞自己使用P操作因资源不足被阻塞或使用V操作激活了等待资源的进程队列执行中进程提出I/O请求后被阻塞分时系统中时间片已经用完在执行完系统调用返回用户进程时高优先级的进程到达（4）进程调度的功能87.2调度算法⒈选择调度方式和算法的若干准则调度算法的确定基于一定因素，我们希望好的调度算法是，系统运行尽能多的任务，使CPU保持忙，使I/O保持忙，对所有任务公平合理，也要有轻重缓急，重要的任务优先处理。衡量操作系统及计算机系统的重要指标如下：①周转时间短。②响应时间快。③截止时间的保证。④优先权准则。⑤系统吞吐量高⑥处理机利用率好⑦各类资源的平衡利用①--④是面向用户的指标，⑤--⑦是面向系统的指标。采用何种调度方法，是衡量操作系统及计算机系统的重要指标之一。指标的好与差，对系统的使用直接产生影响。9⒉调度性能评价指标①CPU的利用率：CPU是一个重要且昂贵的资源，人们需要使CPU尽可能忙，并希望它的利用率越高越好。②吞吐量：吞吐量是指单位时间内所完成任务的数量。③周转时间：将一个作业提交给计算机系统后到该作业的结果返回给用户所需的时间.周转时间Ti：Ti=Tci-Tpi(Tpi-进程提交时间，Tci-进程完成时间)。周转时间是以下所有时间段之和，包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间、在CPU上执行等。等待时间包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间。故Ti=Twi+Tsi(Twi-进程等待时间，Tsi-进程执行时间)。10为了去除进程本身因素的影响，在讨论处理机调度时也使用平均周转时间T和平均带权周转时间W作为衡量指标。④平均周转时间T利用平均周转时间可衡量不同调度算法对相同任务流的调度性能。⑤带权周转时间W：带权周转时间是用周转时间除以进程的执行时间，能够合理反映任务长短差别的指标。Wi=Ti/Tsi=（Twi+Tsi）/Tsi⑥平均带权周转时间：利用平均带权周转时间可比较某种调度算法对不相同任务流的调度性能。⑦响应时间：指从用户发出一个命令到计算机系统把相应的执行结果返回给用户所需要的时间.⑧截止时间：在实时系统中，还使用截止时间来衡量系统的实时性能，截止时间可分为开始截止时间和完成截止时间。117.2.2调度算法⒈先来先服务调度算法(FCFS)基本思想及作法：按作业（进程）到达时间先后顺序依次使用处理机。先来先服务调度算法的例子见表7-1。该算法适合于进程调度、线程调度、任务调度、作业调度和其他资源调度等。12先来先服务调度算法例子13⒉最短作业优先调度算法(SJF)(抢占和非抢占策略)基本思想及作法：按作业估计运行时间长短来组织后备作业队列，作业调度程序首先挑选运行时间最短的作业投入运行。目的是为了提高系统的吞吐率。缺点：无法满足公平性。最短作业优先调度算法的例子如表7-2所示。14⒊最高响应比优先算法基本思想及作法：它同时兼顾每个作业等待时间和运行时间两个方面的因素，挑选响应比最高的作业投入运行。响应比R=(等待时间+要求运行时间)／要求运行时间。它是FCFS和SJF的一种折中，比较好的满足了短作业用户和长作业用户的要求。采用响应比高者优先调度算法例子如表7-3所示。15⒋优先权算法挑选优先级最高的作业投入运行。优先级分为静态优先级和动态优先级两种：一、静态优先权法（1）、基本思想：是指在创建进程时确定进程优先权，并一直保持到进程结束，即“终生”不变。（2）、静态优先级确定原则：作业优先级的确定：①根据用户要求或用户身份确定作业的优先级②根据作业类型确定作业的优先级I/O型作业和CPU型作业，原则上，I/O型作业的优先级高于CPU型作业的优先级③根据作业需要资源的多少确定作业的优先级，原则上资源需要多的作业其优先级低于资源需要少的作业的优先级16进程优先级的确定①按进程的属性确定把进程分为系统进程和用户进程，系统进程的优先级应高于用户进程的优先级②按进程的类型可把进程分为I/O型进程和CPU型进程及I/O与CPU均衡的进程，一般情况下，I/O型进程的优先级高，I/O与CPU均衡型进程优先级次之，CPU型进程优先级最低。③其它方法2、动态优先级进程动态优先级确定原则：①根据进程占有CPU的时间长短来决定，进程占有CPU时间越长其优先级越低；②根据进程等待CPU时间长度来决定，进程在就绪队列中等待时间越长，其优先级越高；17⒌时间片轮转法基本思想及作法：把CPU的处理时间分成固定大小的时间片，如果一个进程在调度中被选中后，用完系统规定的时间片仍然未完成要求的任务，则让出处理机并把它排到就绪队列的末尾，等待下一次调度。同时进程调度进程又去调度当前就绪队列队首的第一个进程或作业投入运行。时间片大小对系统性能的影响：设时间片t（恒定），进程上下文切换时间为q，当前进程数为n，响应时间为R,则有：R=(n-1)*(q+t)≈n*(q+t)系统效率：q/(q+t)18时间片的选取将影响系统开销和响应时间：①t过短，处理机剥夺次数太多，进程上下文切换次数增加，导致系统开销增大；②t过长，易使就绪进程在一个时间片内完成，调度蜕化为先来先服务；③t值的确定：近似为：t=R/Nmax,其中Nmax为就绪队列所允许的最大进程数。19⒍多级队列算法多级队列算法(MLQ)是先来先服务算法、时间片轮转算法和优先权算法的综合。其基本思想是将就绪队列分成多个独立队列，相同优先权的进程按FIFO原则排成一个队列，按时间片轮转算法分派CPU。不同队列可有不同的优先权、不同的时间片长度。在多级队列算法中，优先调度优先权高的队列，当优先权高的队列为空时，才可以调度下一级队列，依次类推，同一队列按时间片轮转算法分派CPU。此算法的性能好，适合于线程调度、进程调度或任务调度。且比较容易实现，实用性好，被目前流行的操作系统采用，如NT、UNIX等。20该调度算法时间片轮转法的发展，它的出发点是：（1）、为提高系统吞吐量而照顾短作业；（2）、为得到较好的I/O设备利用率和对交互用户的及时响应而照顾I/O型作业；（3）、根据运行情况动态的考虑作业的性质，并根据其当前运行性质进行相应的调度多级反馈队列调度法实现的基本思想和方法如下：（1）系统中有多个就绪队列，每个队列对应一个调度级别，各级有不同的优先级别。第一队列优先级最高，以下各级队列优先级逐次减低；⒎多级反馈队列法21(2)各级队列中的进程具有不同的时间片.优先级最高队列中进程时间片最小,随着队列级别增加其进程的时间片增加;(3)各级队列均FCFS服务原则排序;(4)同一队列中进程调度方法:新进入的进程加入到第一级就绪队列的末尾.每级队列中的进程按FCFS方法分给处理机,并运行一个相应于该队列的时间片.如果该进程在这个时间片中完成了全部工作或因等待时间或等待I/O操作而放弃处理机,则该进程撤离系统(完成任务)或进入相应的阻塞队列,从而离开就绪队列.若进程使用完时间片后仍然要求运行(也没有I/O请求),则该进程被抢占处理机,同时将它放入下一级(优先级降低)就绪队列的末尾;22(5)不同队列调度方法:只有高优先级队列为空才调度下一级就绪队列;最低优先级队列采用时间片轮转法调度;(6)当比运行进程更高级别的队列中到来一新进程时,它将抢占运行进程的处理机.被抢占的进程回到原队列的末尾.该算法对终端用户、短作业和长作业都能获得较好的响应.23