操作系统课程第3章处理机调度.ppt

Page 1,2023/10/27,第三章 处理机调度与死锁,Page 2,2023/10/27,第三章 处理机调度与死锁,处理机调度的基本概念 处理机调度的目标充分有效地利用处理机（CPU）资源 调度算法 实时调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除,Page 3,2023/10/27,3.1 处理机调度的基本概念,操作系统调度级别进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则,Page 4,2023/10/27,3.1 处理机调度的基本概念,3.1.1 操作系统调度级别,1.高级调度,2.低级调度,3.中级调度,Page 5,2023/10/27,3.1.1 高级、中级和低级调度,1.高级调度 又称作业调度主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，插入就绪队列，以使该作业的进程获得竞争处理机的权利,作 业 调 度,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等作业状态:作业从提交给系统，直到完成任务后退出系统前，在整个活动过程中它会处于不同的状态。通常，作业状态分为四种：提交、后备、执行和完成，如图3-1所示。,Page 7,2023/10/27,作 业 调 度,后备状态,完成状态,就绪,阻塞,执行,I/O完成,I/O请求,时间片完,作业状态间转换,图3-1 作业的基本状态,Page 8,2023/10/27,（1）提交状态即用户向系统提交一个作业时，该作业所处的状态。（2）后备状态即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放，等待进入内存时所处的状况。（3）执行状态即作业分配到所需的资源，被调入内存，并且在处理机（CPU）上执行相应的程序时所处的状况。（4）完成状态即作业完成了计算任务，结果由打印机输出，最后由系统回收分配给它的全部资源，准备退出系统时的作业状况。,作业状态,作业控制块（JCB）在多道批处理系统中通常有上百个作业被收容在输入井（磁盘）中。为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。JCB的主要内容如图3-2所示。,作 业 调 度,图3-2 作业控制块,作业调度的功能 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。(1)记录系统中各个作业的情况。(2)按照某种调度算法从后备作业队列中挑选作业。(3)为选中的作业分配内存和外设等资源。(4)为选中的作业建立相应的进程。(5)作业结束后进行善后处理工作，如输出必要的信息，收回该作业所占用的全部资源，撤消与该作业相关的全部进程和该作业的JCB。,Page 13,2023/10/27,高级、中级和低级调度,在每次作业调度时，须决定：接纳多少个作业 即允许多少个作业同时在内存中运行作业太多 服务质量下降作业太少 资源利用率低接纳哪些作业 取决于作业调度算法先来先服务短作业优先作业优先权调度响应比调度,周转时间太长,系统吞吐量太低,适当的折衷,周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。吞吐量：是指在单位时间内系统所完成的作业数。,Page 14,2023/10/27,3.1.1 高级、中级和低级调度,2.中级调度目的：是为了提高内存利用率和系统吞吐量。功能：暂时不能运行的进程挂起，释放宝贵的内存资源。具备条件时：把外存上的就绪进程，重新调入内存，挂在就绪队列上等待进程调度。,Page 15,2023/10/27,3.1.1 高级、中级和低级调度,3.低级调度 进程调度主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它常见的低级调度有非抢占式和抢占式两种,Page 16,2023/10/27,处理机调度的层次,Page 17,2023/10/27,作业调度又称为1，它决定将那些在外存储器上的处于2状态的作业调入主机内存，系统经作业调度程序选中一个或多个作业后，就为它们分配必要的内存、设备及软资源。然后控制权就交给了3，由3将它们变为一个或一组4。1()：A、高级调度 B、低级调度 C、中级调度 D、进城调度 2（）：A、就绪 B、阻塞 C、提交 D、后备 3（）：A、存储管理模块 B、处理机管理模块 C、文件管理模块 D、设备管理模块 4（）：A、指令 B、子程序 C、进程 D、程序段,Page 18,2023/10/27,处于后备状态的作业存放在（）中。A、外存 B、内存 C、A和B D、扩展内存在操作系统中，作业处于（）状态时，已处于进程的管理之下。A、后备 B、阻塞 C、执行 D、完成,Page 19,2023/10/27,3.1处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 20,2023/10/27,3.1.2 进程调度的任务,进程调度的任务 是控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,Page 21,2023/10/27,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 22,2023/10/27,3.1.3 确定算法的原则,具有公平性 资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量,Page 23,2023/10/27,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 24,2023/10/27,进程调度方式,非抢占方式抢占方式,Page 25,2023/10/27,进程调度方式,非抢占方式(Non-preemptive Mode)引起进程调度的因素正在执行的进程执行完毕，或因发生某事件而不能再继续执行执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语,优点：算法简单，系统开销小缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束,Page 26,2023/10/27,进程调度方式,抢占方式 抢占式调度主要有以下原则优先权原则 允许高优先权的新到进程抢占当前进程的处理机短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机 时间片原则 时间片用完后停止执行，重新进行调度，适用于分时系统,优点：适于时间要求严格的实时系统缺点：调度算法复杂，系统开销大,Page 27,2023/10/27,3.1处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 28,2023/10/27,3.1.5 调度队列模型,仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型,Page 29,2023/10/27,3.1.5 调度队列模型,仅有进程调度的调度队列模型在分时系统中，通常仅设有进程调度系统把这些进程组织成一个就绪队列每个进程在执行时，可能有以下几种情况进程获得CPU正在执行任务在给定时间片内已完成，释放处理机后为完成状态任务在时间片内未完成，进入就绪队列末尾在执行期间因某事件而阻塞,Page 30,2023/10/27,3.1.5 调度队列模型,仅有进程调度的调度队列模型,进程调度,进程完成,等待事件,交互用户,时间片完,Page 31,2023/10/27,3.1.5 调度队列模型,具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且还要有作业调度就绪队列的形式在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队首进程设置多个阻塞队列根据事件的不同设置多个队列提高效率,Page 32,2023/10/27,3.1.5 调度队列模型,进程调度,进程完成,时间片完,与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列,Page 33,2023/10/27,3.1.5 调度队列模型,同时具有三级调度的调度队列模型,进程调度,中级调度,等待事件,进程完成,时间片完,作业调度,交互型作业,批量作业,挂起,事件出现,事件出现,Page 34,2023/10/27,3.1 处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型选择调度方式和调度算法的若干准则,如果你是用户，你希望系统如何为你服务，如何考虑？如果你是调度者，从系统整体角度出发，应如何考虑？,Page 35,2023/10/27,3.1.6 选择调度方式和调度算法的若干准则,1.面向用户的准则,2.面向系统的准则,Page 36,2023/10/27,3.1.6 选择调度方式和调度算法的若干准则,1.面向用户的准则,(1)周转时间短。,(2)响应时间快。(3)截止时间的保证。(4)优先权准则。,Page 37,2023/10/27,选择调度方式和调度算法的若干准则,面向用户的准则周转时间短平均周转时间,带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS。而平均带权周转时间则可表示为:,Page 38,2023/10/27,通常把周转时间作为评价批处理系统的性能、选择作业调度方式与算法的准则。所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括：(1)作业在外存后备队列上等待(作业)调度的时间；(2)进程在就绪队列上等待进程调度的时间；(3)进程在CPU上执行的时间；(4)等待IO操作完成的时间。其中，第(2)、(3)、(4)项在一个作业的处理过程中，可能发生多次。,Page 39,2023/10/27,可把平均周转时间描述为：,作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:,系统以多个用户都满意为目标,周转时间服务时间周转时间完成时间到达时间,Page 40,2023/10/27,选择调度方式和调度算法的若干准则,面向用户的准则响应时间快响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间截止时间保证截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标,Page 41,2023/10/27,选择调度方式和调度算法的若干准则,面向用户的准则等待时间短等待时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间优先权准则在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理有时还选择抢占式调度方式,Page 42,2023/10/27,选择调度方式和调度算法的若干准则,面向系统的准则系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高,基于这样的准则，你设计操作系统的调度策略应如何？,Page 43,2023/10/27,（）是指从作业提交给系统到作业完成的时间间隔。A周转时间 B、响应时间 C、等待时间 D、运行时间 作业从进入后备队列到被调度程序选中的时间间隔成为（）。A周转时间 B、响应时间 C、等待时间 D、触发时间在批处理系统中，周转时间是（）。A、作业运行时间 B、作业等待时间和运行时间之和 C、作业的相对等待时间 D、作业被调度进入内存到运行完毕的时间,Page 44,2023/10/27,第三章 处理机调度与死锁,处理机调度的基本概念 调度算法 实时调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除,Page 45,2023/10/27,3.2 调度算法,在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法问题提出如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优先，时间片轮转等有些算法适用于作业调度，有些适用于进程调度，有些两者皆可,Page 46,2023/10/27,调度算法,先来先服务和短作业优先算法 高优先权优先调度算法 基于时间片的轮转调度算法,Page 47,2023/10/27,先来先服务和短作业优先算法,先来先服务(FCFS)/先进先出(FIFO)调度算法按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程是一种最简单的调度算法，即可用于作业调度，也可用于进程调度几个术语到达时间、服务时间、开始时间完成时间、等待时间周转时间：完成时间-到达时间带权周转时间：周转时间/服务时间,Page 48,2023/10/27,先来先服务和短作业优先算法,0,4,4,4,7,6,先来先服务（先进先出）：,7,12,10,12,14,11,14,18,14,Page 49,2023/10/27,先来先服务和短作业优先算法,先来先服务（先进先出）优缺点,比较有利于长作业（进程），而不利于短作业（进程）有利于CPU繁忙型作业（进程），而不利于I/O繁忙型作业（进程）用于批处理系统，不适于分时系统,Page 50,2023/10/27,先来先服务和短作业优先算法,短作业(进程)优先调度算法SJ(P)F短作业(进程)优先调度算法SJ(P)F，以要求运行时间长短进行调度，即启动要求运行时间最短的作业可以分别用于作业调度和进程调度短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行；而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度,Page 51,2023/10/27,先来先服务和短作业优先算法,0,4,4,1,短作业/短进程优先（SJF/SPF）：,4,6,3,3/2,6,9,8,8/3,9,13,9,9/4,13,18,16,16/5,40/5,2.1,Page 52,2023/10/27,FCFS/SJF调度算法的性能,先来先服务和短作业优先算法,SJF平均周转时间和平均带权周转时间明显改善,Page 53,2023/10/27,SJF的特点,优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量。缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。,Page 54,2023/10/27,调度算法,先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调度算法,Page 55,2023/10/27,高优先权优先（HPF，Highest Priority First）调度算法,优先权调度算法的类型非抢占式优先权调度算法抢占式优先权调度算法,Page 56,2023/10/27,高优先权优先（HPF，Highest Priority First）调度算法,优先权调度算法的类型非抢占式优先权调度算法特点：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处理机重新分配给另一优先权最高的进程主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中,Page 57,2023/10/27,高优先权优先调度算法,优先权调度算法的类型抢占式优先权调度算法把处理机分配给优先权最高的进程，但在执行期间，只要出现另一个优先权更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先权最高的进程注意：只要系统中出现一个新的就绪进程，就进行优先权比较该调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中,Page 58,2023/10/27,高优先权优先调度算法,优先权的类型静态优先权动态优先权,Page 59,2023/10/27,高优先权优先调度算法,优先权的类型静态优先权静态优先权在创建进程时确定，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255，又把该整数称为优先数确定进程静态优先权的依据进程类型:系统进程，用户进程进程对资源的需求(对CPU和内存需求较少的进程，优先级较高)用户要求（紧迫程度和付费多少）,Page 60,2023/10/27,高优先权优先调度算法,动态优先权在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。可规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高具有相同优先权初值的进程，则最先进入就绪队列，其将因其动态优先权变得最高而优先获得处理机，此即FCFS算法具有各不相同的优先权初值的就绪进程，则优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机,Page 61,2023/10/27,静态优先权，非抢占式（1为高优先权）,高优先权优先调度算法,0,4,4,1,4,8,4,1,8,11,10,10/3,11,16,14,14/5,16,18,15,15/2,9.4,2.93,考虑一下抢占式，情况如何？,Page 62,2023/10/27,高优先权优先调度算法,高响应比优先调度算法（HRF）是FCFS和SJF的结合，克服了两种算法的缺点 性能分析:如果作业的等待时间相同，则要求执行的时间愈短，则响应比高，故有利于短作业；当要求执行的时间相同时，响应比决定于其等待时间，因而实现了先来先服务；对于长作业，当其等待时间足够长时，其响应比便可升到很高，也可获得处理机。,响应比Rp定义如下：Rp=作业响应时间tR/要求执行的时间,Page 63,2023/10/27,调度算法,先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调度算法,Page 64,2023/10/27,基于时间片的轮转调度算法,简单的时间片轮转法(RRRound Robin)将系统中所有的就绪进程按照FCFS原则，排成一个队列；每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms；在一个时间片结束时，发生时钟中断；调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程；进程可以未使用完一个时间片，就出让CPU（如阻塞）。,优点：公平。保证就绪队列中所有进程在一给定的时间内，均能获得一时间片的处理机执行时间,缺点：紧迫任务响应慢。UNIX中采用：时间片+优先权,Page 65,2023/10/27,基于时间片的轮转调度算法,A,B,C,D,E,A,B,C,D,E,A,B,C,E,A,C,E,C,0,1,2,3,4,9,12,15,17,18,15,15/4,11,11/3,16,16/5,6,6/2,13,13/4,12.2,2.12,若到达时间为0、1、2、3、4，又如何？,Page 66,2023/10/27,3.2.3 基于时间片的轮转调度算法,时间片长度变化的影响过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求：R(响应时间)=Nmax(进程数目)*q(时间片)时间片长度的影响因素：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。,Page 67,2023/10/27,2.多级队列调度,前台的就绪队列是交互性作业的进程，采用时间片轮转。后台的就绪队列是批处理作业的进程，采用优先权或短作业优先算法。调度方式有两种：(1)优先调度前台，若前台无可运行进程，才调度后台。(2)分配占用CPU的时间比例，如：前台80%，后台20%。,3.2.3 基于时间片的轮转调度算法,Page 68,2023/10/27,基于时间片的轮转调度算法,多级反馈队列调度算法 设置多个就绪队列，并为各个队列赋予不同的优先级第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍,Page 69,2023/10/27,就绪队列1,基于时间片的轮转调度算法,就绪队列2,就绪队列3,就绪队列n,调度方式,按FIFO原则排队等待调度,尚未完成转入第二队列的末尾，按FIFO原则等待调度,采取按时间片轮转的方式运行,因等待而放弃CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列,Page 70,2023/10/27,基于时间片的轮转调度算法,注意仅当第1(i-1)队列均空时，才会调度第i队列中的进程运行第i队列中某进程正在运行时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，调度程序把正在运行的进程放回到第i队列的末尾第i队列中某进程正在运行时，该进程因等待事件发生而进入阻塞队列，等待事件发生后，调度程序把进程放回到第i队列的末尾,Page 71,2023/10/27,基于时间片的轮转调度算法,多级反馈队列调度算法的性能终端型作业用户终端型作业用户所提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列所规定的时间片内完成即可短批处理作业用户若在第1队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间如在第一个队列中不能完成，只需在第2、3队列中各执行一个时间片长批处理作业用户长作业将依次在第1，2，3，n队列中执行，最终按轮转方式运行,Page 72,2023/10/27,进程调度要解决的问题WHAT：按什么原则分配CPU 进程调度算法WHEN：何时分配CPU 进程调度的时机HOW：如何分配CPU CPU调度过程（进程的上下文切换）,Page 73,2023/10/27,补充:进程调度的时机,当一个进程运行完毕或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待I/O）分时系统中时间片到当有一个优先级更高的进程就绪（可抢占式）例如：新创建一个进程，一个阻塞进程变成就绪在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）,Page 74,2023/10/27,*保存现场：顺序保存，最后一步保存PSW*选择要运行的程序（如果没有就绪进程,系统会安排一个闲逛进程(idle)，没有其他进程时该进程一直运行,在执行过程中可接收中断）*恢复现场：最后一步恢复选中进程的PSW,补充：调度的实施过程,CPU调度过程,Page 75,2023/10/27,课堂练习:,假如有4道作业，它们的提交时间及运行时间如下表所示：采用单道运行，试问下述调度算法下，它们的调度顺序，并分别计算各调度算法下三个作业的平均周转时间 T 和平均带权周转时间 W。（1）FCFS（先来先服务）（2）SJF（短作业优先）（3）HRF（响应比高者优先）n n T=1/N（Ti）,Ti=结束时刻-提交时刻;W=1/N（Wi）,Wi=Ti/作业 i 实际执行时间 i=1 i=1,Page 76,2023/10/27,（1）FCFS：调度顺序为1 2 3 4T=1/4（120+120+96+78）=103.5分钟W=1/4（1+4+16+6.5）=6.875,Page 77,2023/10/27,（2）SJF(SPF)：调度顺序为1 3 4 2T=1/4（120+66+48+138）=93分钟W=1/4（1+11+4+4.6）=5.15,Page 78,2023/10/27,（3）HRF作业1最先到达并运行，当作业 1 完成时（10：00），作业 2、3、4都到达，则计算它们的响应比：作业2响应比=（90+30）/30=4作业3响应比=（60+6）/6=11作业4响应比=（30+12）/12=3.5由于作业3的响应比最高，所以作业3先运行。当作业3完成时（10：06），计算作业2、4的响应比：作业2响应比=（96+30）/30=4.2作业4响应比=（36+12）/12=4由于作业2的响应比大于作业4，所以接着作业2运行；最后由作业4运行。,Page 79,2023/10/27,（3）HRF：调度顺序为1 3 2 4T=1/4（120+66+126+78）=97.5分钟W=1/4（1+11+4.2+6.5）=5.675,Page 80,2023/10/27,（1）先来先服务算法（FCFS：First Come First Serve）（2）最短作业优先算法（SJF：Shortest Job First）（3）最高响应比优先算法（HRN：Highest Response Ratio Next）响应比R=（作业运行时间+作业等待时间）/作业运行时间=1+（作业等待时间/作业运行时间）（4）基于优先数调度算法（HPF：Highest Priority First）,常见的作业调度算法,Page 81,2023/10/27,3.3 实时调度,实时系统实时系统的特点对实时系统的要求实时调度算法,Page 82,2023/10/27,实时系统是那些时间因素非常关键的系统。实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。,Page 83,2023/10/27,3.3.1实时系统,实时任务的类型根据对截止时间的要求来划分硬实时任务：系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果；软实时任务：它也联系着一个截止时间，但并不严格，若偶尔超过时间限制也是可以容忍的。实时系统响应的事件分为周期性实时任务：要求按指定的周期循环执行，以便周期性地控制某个外部事件；非周期性实时任务：任务的执行无明显的周期性，但都必须联系着一个截止时间。,Page 84,2023/10/27,实时系统的特点,有限等待时间有限响应时间用户控制可靠性高系统出错处理能力强,Page 85,2023/10/27,对实时系统的要求,要求更详细的调度信息：如，就绪时间、开始或完成截止时间、处理时间、资源要求、优先级（绝对优先级或相对优先级）；采用基于优先级的随时抢先式调度；快速中断响应，具有快速硬件中断机构，应使禁止中断的时间尽量短；快速上下文切换：相应地采用较小的调度单位（如线程）。,Page 86,2023/10/27,为了保证满足实时任务对截止时间的要求，实时系统必须具备足够强的处理能力和快速的切换机制。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：才可能处理所有的负载。满足该条件的实时系统称作任务可调度的。,Page 87,2023/10/27,3.3.2 实时调度算法,最早截止时间优先算法 该算法根据任务的开始截止时间来确定任务的优先级，即任务的开始截止时间愈早，其优先级愈高。这种算法既可采用非抢占调度方式，也可采用抢占调度方式。最低松弛度优先算法 算法根据实时任务的松弛度（松弛度任务必须完成的时间任务本身的运行时间当前时间）来确定任务的优先级，即任务的松弛度愈低，其优先级愈高。该算法主要用于可抢占调度方式中，当一任务的最低松弛度减为0时，它 便必须立即抢占CPU，以保证按截止时间的要求完成任务。,Page 88,2023/10/27,3.3.2 常用的几种实时调度算法,1.最早截止时间优先即EDF算法(Earliest Deadline First),图 3-3 EDF算法用于非抢占调度方式,Page 89,2023/10/27,2.最低松弛度优先即LLF算法(Least Laxity First),该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的紧急程度(松弛程度)为100ms。又如，另一任务在400ms时必须完成，它本身需要运行150ms，则其松弛程度为250ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。,Page 90,2023/10/27,图 3-8 A和B任务每次必须完成的时间,假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。,Page 91,2023/10/27,t1=0A1 的松驰度：20-10=10(ms)B1 的松驰度：50-25=25(ms)调度A1执行,t2=10，A1 完成任务A尚未进入第2周期任务B已经进入第1周期调度B1执行,t3=30A2 的松驰度：40-10-30=0(ms)B1 的松驰度：50-5-30=15(ms)抢占B1调度A2执行,t4=40A3 的松驰度：60-10-40=10(ms)B1 的松驰度：50-5-40=5(ms)调度B1执行,t5=45，B1 完成A3 的松驰度：60-10-45=5(ms)任务B尚未进入第二周期调度A3执行,t6=55 任务A尚未进入第4周期任务B已经进入第2周期调度B2执行,t7=70 A4 的松驰度：80-10-70=0(ms)B2 的松驰度：100-10-70=20(ms)抢占B2调度A4执行,t8=80 A5 的松驰度：100-10-80=10(ms)B2 的松驰度：100-10-80=10(ms)调度B2执行,图 3-4 利用LLF算法进行调度的情况,0,10,20,30,40,50,60,70,80,t1,t2,t3,t4,t545,t655,t7,t8,Page 92,2023/10/27,3.5 死锁（Deadlock）,产生死锁的原因死锁的预防死锁的避免死锁的检测与恢复,Page 93,2023/10/27,Page 94,2023/10/27,早期的操作系统对申请某种资源的进程，若该资源尚未分配时，立即将该资源分配给这个进程。后来发现，对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局面称为死锁(deadlock)。死锁问题在1965年由Dijkstra发现，并随着计算机技术的发展，逐渐成为人们关心的问题。那么，什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？这些正是今天我们要讨论的问题。,Page 95,2023/10/27,死锁(Deadlock)的定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。,关于死锁的一些结论：参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集,Page 96,2023/10/27,3.5.1 产生死锁的原因,产生死锁的原因有两点：(1)竞争资源：为多个进程所共享的资源不够，引起它们对资源的竞争而产生死锁；(2)进程推进顺序不当：在进程运行过程中，请求资源和释放资源的顺序不当，也会产生死锁。,Page 97,2023/10/27,例1.日常生活中常有许多有关死锁的事件。,当然，各路车队等待的事件都不会发生(假设它们都不改变行车方向)。这样若不采用特殊方法，它们将永远停留在这“井”字形的路上，而处于死锁状态。,1.竞争非剥夺性资源的例子,Page 98,2023/10/27,共享资源的严重缺乏，多个进程对共享资源的竞争，使它们都处于无止境的等待状态。在计算机系统中，进程发生死锁的现象与上述事例实质上是一样的。进程是因相互竞争资源而导致死锁的，与四路车队(可视为进程)竞争路口(可视为资源)类似。计算机系统中有各种资源，如外设、数据、文件、程序等。,Page 99,2023/10/27,例2.竞争外部设备。设系统中有打印机、磁带机各一台，进程A、B的申请如下：,磁带机,进程A,进程B,打印机,Page 100,2023/10/27,2.竞争临时性资源：临时性资源是指由一个进程产生的被另一进程使用一短暂时间后便无用的资源。也称消耗性资源。如信号量,中断信号，同步信号等,Page 101,2023/10/27,若按下列顺序进行：P1:Release(S1);Request(S3);P2:Release(S2);Request(S1);P3:Release(S3);Request(S2);则不会产生“死锁”。若按下列顺序进行：P1:Request(S3);Release(S1);P2:Request(S1);Release(S2);P3:Request(S2);Release(S3);则很可能发生“死锁”。,Page 102,2023/10/27,由于进程具有异步特征，这就使得进程可能按下列两种顺序向前推进：1.进程推进顺序合法：进程P1和P2并发执行时，若按曲线 即：P1:Request(S1);P1:Request(S2);P1:Release(S1);Release(S2);P2:Request(S1);P2:Request(S2);P2:Release(S1);Release(S2)；则两个进程可顺利完成，不会产生“死锁”。类似地，曲线和曲线也不会产生“死锁”。,进程推进顺序不当引起的死锁,Page 103,2023/10/27,Page 104,2023/10/27,2.进程推进顺序非法：进程P1和P2并发执行时，若按曲线 即：P1:Request(S1);P2:Request(S2);P1:Request(S2);阻塞。P2:Request(S1);阻塞。则两个进程间互相产生了阻塞，从而产生“死锁”。把区域D称为是“系统不安全区”。,Page 105,2023/10/27,只有4个条件都满足时，才会出现死锁。互斥：任一时刻只允许一个进程使用资源不剥夺：进程已经占用的资源，不会被强制剥夺请求和保持（部分分配）：进程在请求其余资源时，不主动释放已经占用的资源环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。,3.5.2 产生死锁的必要条件,Page 106,2023/10/27,1.互斥：在一段时间内某资源仅为一个进程所占有，如果此时还有其它进程要求访问该资源，则要求者只能被阻塞，直到该资源的占用进程用毕释放；2.请求和保持：当进程已经占有了至少一个资源，若又提出了新的资源请求，而该资源又被其它进程所占用，则此请求被阻塞，但对它对已获得的资源保持不放；,Page 107,2023/10/27,3.不剥夺：进程已获得的资源，在未使用完之前，不能被剥夺，只能由使用者在使用完后释放；4.环路等待：在发生死锁时，必然存在一个进程资源的环形链。即进程集合P1、P2、Pn中的P1正在等待一个P2占用的资源，P2正在等待一个P3占用的资源，、Pn正在等待一个P1占用的资源。这四个必要条件中只要有一个条件不满足，都不会形成“死锁”。,Page 108,2023/10/27,3.5.