OS处理机调度MRPPT课件.ppt

计算机操作系统计算机操作系统计算机操作系统计算机操作系统第第4章处理机调度章处理机调度本章主要教学内容本章主要教学内容分级调度分级调度作业调度作业调度进程调度进程调度调度算法调度算法实时系统调度方法实时系统调度方法2本章主要教学目标v掌握处理机的三级调度掌握处理机的三级调度v掌握作业调度及进程调度的概念掌握作业调度及进程调度的概念v理解调度算法的评价准则理解调度算法的评价准则v掌握并灵活运用常用的几种作业掌握并灵活运用常用的几种作业调度、进程调度算法调度、进程调度算法34.14.1分级调度分级调度v作业的状态及其转换作业的状态及其转换v调度的层次调度的层次v作业与进程的关系作业与进程的关系4作业的状态及转换u提交状态：一个作业在其处于从输入设备进入外提交状态：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。部存储设备的过程称为提交状态。u收容状态：也称为后备状态。若一个作业的全部收容状态：也称为后备状态。若一个作业的全部信息已全部被输入进输入井，则在它还未被调度去信息已全部被输入进输入井，则在它还未被调度去执行之前，该作业处于收容状态。执行之前，该作业处于收容状态。u执行状态：作业调度程序从后备作业中选取若干执行状态：作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程个作业到内存投入运行。它为被选中作业建立进程并分配必要的资源，这些被选中的作业处于执行态并分配必要的资源，这些被选中的作业处于执行态u完成状态：当作业运行完毕，但它所占用的资源完成状态：当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。尚未全部被系统回收时，该作业处于完成状态。5调度的层次1作业调度作业调度 作业调度又称为高级调度或长调度作业调度又称为高级调度或长调度，将，将已进入系统并处于后备状态的作业按某种已进入系统并处于后备状态的作业按某种算法选择一个或一批，为其建立进程，并算法选择一个或一批，为其建立进程，并进入主机。当该作业执行完毕时，还负责进入主机。当该作业执行完毕时，还负责回收系统资源。在回收系统资源。在批处理系统中批处理系统中，需要有，需要有作业调度的过程，以便将它们分批地装入作业调度的过程，以便将它们分批地装入内存。在内存。在分时系统和实时系统分时系统和实时系统中，通常也中，通常也不需要作业调度。不需要作业调度。6图图 批处理系统中的作业处理及状态批处理系统中的作业处理及状态7调度的层次2交换调度：交换调度：又称又称中级调度中级调度。其主要任务是按。其主要任务是按照给定的原则和策略，将处于外存照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到状态或内存等待状态的进程交换到外存交换区。外存交换区。8调度的层次 3进程调度进程调度进程调度又称为进程调度又称为低级调度低级调度或或微观调度微观调度。其。其主要任务是按照某种策略和算法，将处理主要任务是按照某种策略和算法，将处理机分配给一个处于就绪状态的进程。进程机分配给一个处于就绪状态的进程。进程调度可分为下列两种方式：调度可分为下列两种方式：非抢占方式非抢占方式：抢占方式：抢占方式：把处理器分配给某个进程后，在把处理器分配给某个进程后，在该进程尚未终止或阻塞时，允许系统调度该进程尚未终止或阻塞时，允许系统调度程序根据某种原则，暂停正在执行的进程，程序根据某种原则，暂停正在执行的进程，回收已经分配的处理器，并将处理器重新回收已经分配的处理器，并将处理器重新分配给其它更为紧急的进程。分配给其它更为紧急的进程。4.线程调度线程调度9图 三种调度进程调度交换调度作业调度10作业与进程的关系v作业是用户向计算机提交任务的任务作业是用户向计算机提交任务的任务实体。进程则是计算机为了完成用户实体。进程则是计算机为了完成用户任务实体而设置的执行实体，是系统任务实体而设置的执行实体，是系统分配资源的基本单位。分配资源的基本单位。v一个作业总是由一个或多个进程组成一个作业总是由一个或多个进程组成的，且至少由一个进程组成，但反过的，且至少由一个进程组成，但反过来不成立来不成立。v作业的概念主要用在批处理系统中；作业的概念主要用在批处理系统中；而进程的概念则用在几乎所有的多道而进程的概念则用在几乎所有的多道系统中。系统中。114.2作业调度作业调度主要是完成作业从后备状作业调度主要是完成作业从后备状态到执行状态的转换，以及从执行态到执行状态的转换，以及从执行状态到完成状态的转换状态到完成状态的转换。v作业调度功能作业调度功能v作业调度目标与性能衡量作业调度目标与性能衡量12作业调度的功能1记录系统中各作业的状态记录系统中各作业的状态作业名作业名 作业类型作业类型 计算型、管理型、图形设计型计算型、管理型、图形设计型 资源要求资源要求 内存量内存量外存量外存量外设类型及数量外设类型及数量软件支持工具库函数软件支持工具库函数 当前状态当前状态 提交状态、后备态、运行态、完成提交状态、后备态、运行态、完成 资源使用情况资源使用情况 进入系统的时间开始执行时间已运进入系统的时间开始执行时间已运行时间内存地址外设台数行时间内存地址外设台数作业的优先级作业的优先级 13作业调度的功能2从后备队列中挑选出一部分作业投入执行。作从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法，从后备作业业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行。队列中挑选出若干作业去投入执行。3为被选中作业做好执行前的准备工作。作业调为被选中作业做好执行前的准备工作。作业调度程序为选中的作业建立相应的进程，并为这度程序为选中的作业建立相应的进程，并为这些进程分配它们所需要的系统资源，如分配给些进程分配它们所需要的系统资源，如分配给它们内存、外存、外设等。它们内存、外存、外设等。4在作业执行结束时做好善后处理工作。包括输在作业执行结束时做好善后处理工作。包括输出作业管理信息；回收该作业所占用的资源；出作业管理信息；回收该作业所占用的资源；撤销与该作业有关的全部进程和该作业的作业撤销与该作业有关的全部进程和该作业的作业控制块等等。控制块等等。作业从后备状态到执行状态以及从执行状态到作业从后备状态到执行状态以及从执行状态到完成状态的转换过程如图完成状态的转换过程如图.所示。所示。14图图4 4.3 3作作业业调调度度中中状状态态的的转转换换过过程程15作业调度目标1.对所有作业应该是公平合理的；对所有作业应该是公平合理的；2.应使设备有高的利用率；应使设备有高的利用率；3.每天执行尽可能多的作业；每天执行尽可能多的作业；4.有快的响应时间。有快的响应时间。16作业调度性能衡量1.周转时间周转时间 周转时间：是指作业被提交给系统开始，周转时间：是指作业被提交给系统开始，到作业终止为止的这段时间间隔，也称为到作业终止为止的这段时间间隔，也称为作业周转时间。它包括四部分时间：作业周转时间。它包括四部分时间：a作业在外存后备队列上等待调度的时间。作业在外存后备队列上等待调度的时间。b进程在就绪队列上等待进程调度的时间。进程在就绪队列上等待进程调度的时间。c进程占用进程占用CPU执行的时间。执行的时间。d进程等待进程等待I/O操作完成的时间。操作完成的时间。17作业调度性能衡量作业作业i的周转时间的周转时间Ti可定义为：可定义为：Ti=Tei-Tsi其中，其中，Tei为作业为作业i的完成时间的完成时间 Tsi为作业为作业i的提交时间。的提交时间。平均周转时间为：平均周转时间为：18作业调度性能衡量2.带权周转时间带权周转时间:作业的周转时间作业的周转时间T与作业执行的与作业执行的时间时间Ts之比。即带权周转时间之比。即带权周转时间 WiT/Ts 因为周转时间因为周转时间 T=等待时间等待时间Tw+运行时间运行时间Ts，因此，因此，Wi也可表示为：也可表示为：Wi1+TwTs 从公式可以看出，从公式可以看出，Wi=1，即，即Wi的最小值为的最小值为1。可以看出，带权周转时间越接近。可以看出，带权周转时间越接近1，则该作，则该作业相对等待时间越短，系统性能越高。业相对等待时间越短，系统性能越高。而平均带权周转时间可表示为：而平均带权周转时间可表示为：19图 三种调度复习复习204.3进程调度v进程调度的功能进程调度的功能v进程调度的时机进程调度的时机v进程上下文切换进程上下文切换v进程调度性能评价进程调度性能评价21进程调度的功能进程调度的功能可总结为如下几个方面：进程调度的功能可总结为如下几个方面：1记录系统中所有进程的执行情况记录系统中所有进程的执行情况2从就绪态队列中选择一个进程从就绪态队列中选择一个进程3进行进程上下文的切换进行进程上下文的切换22进程调度的时机v在并发执行的环境下，引起进程调度在并发执行的环境下，引起进程调度的事件有：的事件有：1完成任务完成任务2等待资源等待资源3运行时间到运行时间到4进入睡眠状态进入睡眠状态5优先级变化优先级变化23进程调度性能评价v进程调度性能的衡量是操作系统进程调度性能的衡量是操作系统设计的一个重要指标。其方法可设计的一个重要指标。其方法可分为：分为：1定性衡量：定性衡量：可靠性。可靠性。简洁性简洁性。2定量评价：定量评价：244.4调度算法v先来先服务调度算法先来先服务调度算法 v时间片轮转调度算法时间片轮转调度算法v多级反馈轮转调度算法多级反馈轮转调度算法v优先级调度算法优先级调度算法v最短进程优先调度算法最短进程优先调度算法 v最高响应比优先调度算法最高响应比优先调度算法 25先来先服务（FCFS）调度算法v原理原理每次调度是从就绪队列中，选择一个每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件下去，直到该进程完成或因发生事件而阻塞，才退出处理器。而阻塞，才退出处理器。v特点特点利于长进程，而不利于短进程。利于长进程，而不利于短进程。26先来先服务（FCFS）调度算法进程进程名名到达到达时间时间执行执行时间时间开始开始执行执行时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A A0 01 1B B1 1100100C C2 21 1D D3 31001000111110110011011021001001022021991.9927最短作业优先调度算法(SJF)v原理：原理：它是从就绪队列中选择一个估计它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。退出处理器，再重新调度。v特点：特点：照顾到了系统中占大部分的短进照顾到了系统中占大部分的短进程，有效地降低了进程的平均等待时间，程，有效地降低了进程的平均等待时间，提高了系统的吞吐量，但对长进程不利。提高了系统的吞吐量，但对长进程不利。28图图 FCFSFCFS和和SJFSJF调度算法的性能调度算法的性能 进程名进程名A AB BC CD DE E平均平均到达时间到达时间0 01 12 23 34 4执行时间执行时间4 43 35 52 24 4FCFSFCFS完成时间完成时间周转时间周转时间带权周转时间带权周转时间SJFSJF完成时间完成时间周转时间周转时间带权周转时间带权周转时间4417621210214115.518143.592.8441631.5982.71392.2518163.282.129时间片轮转调度算法(RR)v原理：系统将所有的就绪进程按进入原理：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度就绪队列的先后次序排列。每次调度时把时把CPU分配给队首进程，让其执行分配给队首进程，让其执行一个时间片一个时间片q，当时间片，当时间片q用完，由计用完，由计时器发出时钟中断，调度程序则暂停时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一将它送到就绪队列的末尾，等待下一轮调度执行。轮调度执行。图图4.44.4轮转法调度轮转法调度30时间片轮转调度算法v时间片时间片q的长度选择：的长度选择：v时间片时间片q的取值方式：的取值方式：固定大小时间片：固定大小时间片：可变时间片：可变时间片：v特点：为了保证人机交互的及时性，特点：为了保证人机交互的及时性，系统使每个进程依次按时间片方式系统使每个进程依次按时间片方式轮流地执行轮流地执行。31时间片轮转调度算法例：考虑下述四个进程例：考虑下述四个进程A、B、C和和D的执行情况。设它们依次进入就绪的执行情况。设它们依次进入就绪队列，但前后时间忽略不计。四个队列，但前后时间忽略不计。四个进程分别需要运行进程分别需要运行12，5，3和和6个时间单位。如下表所示。个时间单位。如下表所示。计算当时间片分别为计算当时间片分别为q=1、q=4时各进程的开始运行时间、完成时时各进程的开始运行时间、完成时间、周转时间及带权周转时间。间、周转时间及带权周转时间。32解：通过分析及计算，我们可以得到下表：进程名进程名到达时间到达时间到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间时时间间片片q=1A012B05C03D06平均周转时间平均周转时间T=平均带权周转时间平均带权周转时间W W=时时间间片片q=4A012B05C03D06平均周转时间平均周转时间T=平均带权周转时间平均带权周转时间W=当当q=1、q=4时，时，RR调度算法的比较调度算法的比较012326171120261711202.173.43.673.3318.53.143.3819.7504811262011222.1743.673.672620112233优先级调度算法v优先级调度算法也叫做优先权调度算优先级调度算法也叫做优先权调度算法，可做为作业调度或进程调度策略。法，可做为作业调度或进程调度策略。这种算法可用于批处理系统，也可用这种算法可用于批处理系统，也可用于实时系统中于实时系统中。v在优先级调度算法中，优先级用来表在优先级调度算法中，优先级用来表示作业或进程所享有的调度优先权。示作业或进程所享有的调度优先权。该算法的关键是确定进程或作业的优该算法的关键是确定进程或作业的优先级。确定优先级的方法有两类：静先级。确定优先级的方法有两类：静态法和动态法。态法和动态法。34静态优先级v静态优先级是在创建作业或进程时确定静态优先级是在创建作业或进程时确定的，且在作业或进程的整个运行期间保的，且在作业或进程的整个运行期间保持不变。持不变。v作业调度中确定静态优先级的依据如下作业调度中确定静态优先级的依据如下三个方面原则：三个方面原则：由用户自己根据作业的紧急程度输入一由用户自己根据作业的紧急程度输入一个适当优先级。个适当优先级。由系统或操作员根据作业类型指定优先由系统或操作员根据作业类型指定优先级。级。系统根据作业要求资源情况确定优先级。系统根据作业要求资源情况确定优先级。35静态优先级v进程调度中确定静态优先级的依据进程调度中确定静态优先级的依据如下：如下：根据进程的类型给予不同的优先级。根据进程的类型给予不同的优先级。将作业的静态优先级作为它所属进将作业的静态优先级作为它所属进程的优先级。程的优先级。36动态优先级v动态优先级是指在创建进程时所赋予动态优先级是指在创建进程时所赋予的优先级是随进程的推进或随其等待的优先级是随进程的推进或随其等待时间的增加而改变的，以便获得更好时间的增加而改变的，以便获得更好的调度性能。的调度性能。v进程调度中确定动态优先级的依据如进程调度中确定动态优先级的依据如下：下：根据进程占有根据进程占有CPU时间的长短来决定。时间的长短来决定。根据就绪进程等待根据就绪进程等待CPU时间的长短来决时间的长短来决定。定。37两种占有两种占有CPU的方式的方式v可剥夺式可剥夺式(可抢占式可抢占式)当有比正在运行的进程优先级更高当有比正在运行的进程优先级更高的进程就绪时的进程就绪时,系统可强行剥夺正在系统可强行剥夺正在运行进程的运行进程的CPU,提供给具有更高优提供给具有更高优先级的进程使用先级的进程使用v不可剥夺式不可剥夺式(不可抢占式不可抢占式)某一进程被调度运行后某一进程被调度运行后,除非由于它除非由于它自身的原因不能运行自身的原因不能运行,否则一直运行否则一直运行下去下去38多级反馈轮转调度算法v将就绪队列分为将就绪队列分为N级，每个就绪队列分配级，每个就绪队列分配给不同的时间片，队列级别越高，时间给不同的时间片，队列级别越高，时间片越小，级别越低，时间片越大，最后片越小，级别越低，时间片越大，最后一级采用时间片轮转，其他队列采用先一级采用时间片轮转，其他队列采用先进先出；进先出；系统从第一级调度，当第一级系统从第一级调度，当第一级为空时，系统转向第二队列，为空时，系统转向第二队列，当运当运行进程用完一个时间片，放弃行进程用完一个时间片，放弃CPU时，时，进入下一级队列；进入下一级队列；等待进程被唤醒时，等待进程被唤醒时，进入第一级就绪队列；进入第一级就绪队列；当进程第一次就当进程第一次就绪时，进入第一级就绪队列绪时，进入第一级就绪队列39图图 多级反馈队列调度算法多级反馈队列调度算法 40最高响应比优先调度算法v原理：是从就绪队列中选择一个响应原理：是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出直到该进程完成或因等待事件而退出处理器为止。响应比处理器为止。响应比R可定义如下：可定义如下：由由于于等等待待时时间间与与服服务务时时间间之之和和，就就是是系系统统对对该该作业的响应时间，据此，又可表示为：作业的响应时间，据此，又可表示为：41最高响应比优先调度算法v特点特点：(1)如果如果作业的等待时间相同作业的等待时间相同，则要求服务的时，则要求服务的时间愈短，其优先权愈高，因而该算法有利于间愈短，其优先权愈高，因而该算法有利于短作业短作业(2)当当要求服务的时间相同时要求服务的时间相同时，作业的优先权决，作业的优先权决定于其等待时间，等待时间愈长，其优先权定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。愈高，因而它实现的是先来先服务。(3)对于长作业，对于长作业，作业的优先级可以随等待时间作业的优先级可以随等待时间的增加而提高，的增加而提高，当其等待时间足够长时，其当其等待时间足够长时，其优先级便可升到很高，优先级便可升到很高，从而也可获得处理机。从而也可获得处理机。42调度算法例：有一个具有两道作业的批处理系统，作业调度采用短例：有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，抢占式调度算法，假设优先数小的优先级别高。假设优先数小的优先级别高。如下表如下表所示的作业序列。所示的作业序列。（1）列出所有作业进入内存的时间及作业结束时间。）列出所有作业进入内存的时间及作业结束时间。（2）计算平均周转时间。）计算平均周转时间。作业名作业名到达时间到达时间估计运行时间估计运行时间优先数优先数A10：0040分钟分钟5B10：2030分钟分钟3C10：3050分钟分钟4D10：5020分钟分钟643调度算法解：解：（1）各作业进入时间和结束时间如下：）各作业进入时间和结束时间如下：作业名作业名进入时间进入时间结束时间结束时间A10：0011：10B10：2010：50C11：1012：00D10：5012：2044调度算法（2）根据周转时间）根据周转时间=完成时间提交时间，完成时间提交时间，可得各作业的周转时间为：可得各作业的周转时间为：TA=11：1010：00=70（分钟）（分钟）TB=10：5010：20=30（分钟）（分钟）TC=12：0010：30=90（分钟）（分钟）TD=12：2010：50=90（分钟）（分钟）平均周转时间（平均周转时间（TA+TB+TC+TD）/4=70（分钟）（分钟）45调度算法v练习练习：在单道批处理系统中，有四个作业到达：在单道批处理系统中，有四个作业到达输入井和需要的计算时间如表所示，现采用响输入井和需要的计算时间如表所示，现采用响应比最高者优先算法。忽略作业调度所花的时应比最高者优先算法。忽略作业调度所花的时间。当第一个作业进入系统后可开始调度。间。当第一个作业进入系统后可开始调度。（1）填充表中空白处；（）填充表中空白处；（2）四个作业的执行）四个作业的执行次序为：（次序为：（3）四个作业的平均周转时间为：）四个作业的平均周转时间为：作业作业到达输入井时间到达输入井时间需计算时间需计算时间开始时间开始时间完成时间完成时间周转时间周转时间1 18 8：00002 2小时小时2 28 8：30303030分钟分钟3 39 9：00006 6分钟分钟4 49 9：30301212分钟分钟8:0010:0012010:0610:006610:3610:0612610:3610:4878464.6实时系统调度方法v实时系统的特点实时系统的特点 v实时调度算法的分类实时调度算法的分类v时限调度算法与频率单调调度算时限调度算法与频率单调调度算法法47实时系统的特点v根据对处理外部事件的时限要求，根据对处理外部事件的时限要求，实时系统中处理的外部事件可分为实时系统中处理的外部事件可分为硬实时任务和软实时任务。硬实时任务和软实时任务。v实时系统所处理的外部任务可分为实时系统所处理的外部任务可分为周期性的与非周期性的两大类。周期性的与非周期性的两大类。48实时操作系统的特点v有限等待时间（决定性）有限等待时间（决定性）v有限响应时间有限响应时间v用户控制用户控制v可靠性高可靠性高v系统出错处理能力强系统出错处理能力强49实时操作系统应具有的能力v很快的进程或线程切换速度很快的进程或线程切换速度 v快速的外部中断响应能力快速的外部中断响应能力v基于优先级的随时抢先式调度策略基于优先级的随时抢先式调度策略基于优先级的时间片轮转调度算法。基于优先级的时间片轮转调度算法。基于优先级的非抢占式调度算法。基于优先级的非抢占式调度算法。基于优先级的固定点抢占式调度算法。基于优先级的固定点抢占式调度算法。基于优先权的立即抢占基于优先权的立即抢占(Immediate Preemption)的调度算法。的调度算法。50实时调度算法的分类v静态表格驱动类静态表格驱动类 v静态优先级驱动抢先式调度算法类静态优先级驱动抢先式调度算法类v动态计划调度算法类动态计划调度算法类v尽力而为调度算法类尽力而为调度算法类51时限调度算法v时限调度算法是一种以满足用户要求的时限调度算法是一种以满足用户要求的时限为调度原则的算法。在实时系统是时限为调度原则的算法。在实时系统是的用户要求时限有处理开始时限和处理的用户要求时限有处理开始时限和处理结束时限。结束时限。v时限调度算法所需要输入信息有：时限调度算法所需要输入信息有：任务就绪时间或事件到达时间任务就绪时间或事件到达时间开始时限开始时限完成时限完成时限处理时间处理时间资源需求资源需求优先级优先级52时限调度算法v例：设实时系统从两个不同的数据源例：设实时系统从两个不同的数据源DA和和DB周周期性地收集数据并进行处理，其中期性地收集数据并进行处理，其中DA的时限为的时限为30ms为周期，为周期，DB的时限要求以的时限要求以75ms为周期。为周期。设设DA所需处理时限为所需处理时限为15ms，DB所需处理时所需处理时限为限为38ms，则与，则与DA和和DB有关进程的事件发有关进程的事件发生时限、执行时限及结束时限生时限、执行时限及结束时限53时限调度算法图图4.124.12时限调度算法给出的调度顺序时限调度算法给出的调度顺序如果使用时限调度算法，并按最近结束时限如果使用时限调度算法，并按最近结束时限优先级最高的方法进行排列，有下图：优先级最高的方法进行排列，有下图：54频率单调调度算法v频率单调调度算法是一种被广泛用于多周频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。期性实时处理的调度算法。v基本原理是频率越低（周期越长）的任务基本原理是频率越低（周期越长）的任务的优先级越低。的优先级越低。v对于对于n(n1)个周期的不同任务来说，设个周期的不同任务来说，设每个周期为每个周期为 Ti，其相应任务的执行时间为其相应任务的执行时间为Ci，则使用频率单调调度算法的充分条件则使用频率单调调度算法的充分条件是：是：C1/T1+C2/T2+Ci/Ti+Cn/Tnn(21/n-1)55Linux 进程调度 v调度方式调度方式 Linux内核的调度方式基本上采内核的调度方式基本上采用用“抢占式优先级抢占式优先级”方式，方式，即当进即当进程在用户模式下运行时，不管是否程在用户模式下运行时，不管是否自愿，自愿，在一定条件下，在一定条件下，核心就可以核心就可以暂时剥夺其运行而调度其他进程进暂时剥夺其运行而调度其他进程进入运行。入运行。56表表 调度策略标志调度策略标志 调度策略标志调度策略标志调度算法调度算法SCHED_RR用用于于实实时时进进程程，基基于于优优先先级级的轮转法的轮转法SCHED_FIFO用用于于实实时时进进程程，基基于于优优先先级级的先进先出算法的先进先出算法SCHED_OTHER用用于于普普通通进进程程，基基于于优优先先级级的轮转法的轮转法Linux 进程调度进程调度57Windows 2000中线程的调度v线程调度特征：线程调度特征：处理机调度是严格针对线程队列进行的，不处理机调度是严格针对线程队列进行的，不考虑被调度线程属于哪个进程的。例如：进考虑被调度线程属于哪个进程的。例如：进程程P有有5个可运行的线程，进程个可运行的线程，进程Q有有2个可运行个可运行的线程，如果这的线程，如果这7个线程的优先级相同，则每个线程的优先级相同，则每个线程将得到个线程将得到1/7的处理机时间。的处理机时间。Windows 2000的处理机调度对象是线程，的处理机调度对象是线程，进程仅作为资源对象和线程运行环境的提供进程仅作为资源对象和线程运行环境的提供者。者。Windows 2000实现了一个基于优先级实现了一个基于优先级抢占式的多处理器调度系统，系统总是运行抢占式的多处理器调度系统，系统总是运行优先级最高的就绪线程。优先级最高的就绪线程。58Windows 2000中线程的调度v当一个线程被调度进入运行状态时，它可运行当一个线程被调度进入运行状态时，它可运行一个被称为时间配额的时间单位。时间配额是一个被称为时间配额的时间单位。时间配额是允许一个线程连续运行的最大时间总和，随后允许一个线程连续运行的最大时间总和，随后系统会中断线程的运行，判断是否需要降低该系统会中断线程的运行，判断是否需要降低该线程的优先级，并查找是否有其他高优先级或线程的优先级，并查找是否有其他高优先级或相同优先级的线程等待运行。相同优先级的线程等待运行。v由于系统具有抢占式调度特征，因此，一个线由于系统具有抢占式调度特征，因此，一个线程的一次调度执行可能并没有用完它的时间配程的一次调度执行可能并没有用完它的时间配额。如果一个高优先级的线程进入就绪状态，额。如果一个高优先级的线程进入就绪状态，当前运行的线程可能在用完它的时间配额前就当前运行的线程可能在用完它的时间配额前就被抢占。事实上，一个线程甚至可能在被调度被抢占。事实上，一个线程甚至可能在被调度进入运行状态之后开始运行之前就被抢走。进入运行状态之后开始运行之前就被抢走。59Windows 2000中线程的调度线程优先级：线程优先级：vWindows 2000的调度是基于内核级线程的抢占式的调度是基于内核级线程的抢占式调度，包括多个优先级层次。在某些层次，线程的优调度，包括多个优先级层次。在某些层次，线程的优先级是固定的，在另一些层次线程的优先数根据执行先级是固定的，在另一些层次线程的优先数根据执行的情况动态调整。它的调度策略是一个动态优先数多的情况动态调整。它的调度策略是一个动态优先数多级反馈队列，每一个优先数都对应于一个就绪队列，级反馈队列，每一个优先数都对应于一个就绪队列，而每一个进程队列中的进程按照时间片方式轮转调度。而每一个进程队列中的进程按照时间片方式轮转调度。v进程的一个属性是进程基本优先权类型为实时、高级、进程的一个属性是进程基本优先权类型为实时、高级、中上、中级、中下和空闲。中上、中级、中下和空闲。v一个进程只有基本优先级，而一个线程有基本优先级一个进程只有基本优先级，而一个线程有基本优先级和当前优先级两个优先级取值。线程的当前优先级可和当前优先级两个优先级取值。线程的当前优先级可在一定范围（在一定范围（015）内动态变化。系统不调整在实）内动态变化。系统不调整在实时范围（时范围（1631）内的线程优先级。）内的线程优先级。60Windows 2000中线程的调度v线程调度的策略：线程调度的策略：自愿切换。自愿切换。抢占。抢占。时间配额用完。时间配额用完。终止。终止。61本章小结v处理机的三级调度：处理机的三级调度：高级调度是作业调度；高级调度是作业调度；中级调度是内外存对换；中级调度是内外存对换；低级调度是进程调度低级调度是进程调度;v作业有四个基本状态：作业有四个基本状态：提交状态、后备状态、运行状态、完提交状态、后备状态、运行状态、完成状态。成状态。62本章小结调度算法的评价准则调度算法的评价准则周转时间周转时间带权周转时间带权周转时间作业调度算法和进程调度算法有：作业调度算法和进程调度算法有：先来先服务算法先来先服务算法轮转法调度算法轮转法调度算法多级反馈轮转调度算法多级反馈轮转调度算法短作业优先调度算法短作业优先调度算法高响应比优先调度算法高响应比优先调度算法优先级调度算法优先级调度算法非抢占式优先级调度算法非抢占式优先级调度算法抢占式优先级调度算法抢占式优先级调度算法63复习:作业和进程调度算法进进程程名名到达到达时间时间执行执行时间时间优优先先级级开始开始执行执行时间时间完成完成时间时间周转周转时间时间带权带权周转周转时间时间A A0 02 22 2B B1 16 61 1C C2 21 14 4D D3 35 53 3优先级调度算法：优先级数大者优先级低优先级调度算法：优先级数大者优先级低65