1、淮海工学院计算机科学系淮海工学院计算机科学系第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 淮海工学院计算机科学系淮海工学院计算机科学系作业的状态及其转换作业的状态及其转换 批处理系统才有作业的概念，分时系统没有作业的概念；批处理系统才有作业的概念，分时
2、系统没有作业的概念；作业的状态分为：作业的状态分为：提交、后备、运行和完成；提交、后备、运行和完成；提交状态：提交状态：作业再输入设备上并准备进入外存输入井前的状态。用户作业再输入设备上并准备进入外存输入井前的状态。用户作业通常包括：程序、数据和作业说明书作业通常包括：程序、数据和作业说明书 后备状态：后备状态：由由SPOOLingSPOOLing输入程序输入到外存输入井中，为其建立作输入程序输入到外存输入井中，为其建立作业控制块（业控制块（JCBJCB），并将），并将JCBJCB插入到后备作业队列中的状态插入到后备作业队列中的状态 运行状态：运行状态：作业被作业调度程序选中，由外存输入井调入
3、到内存，为作业被作业调度程序选中，由外存输入井调入到内存，为其分配了所需的资源并建立了进程，此时作业就进入到运行状态。其分配了所需的资源并建立了进程，此时作业就进入到运行状态。完成状态：完成状态：当作业正常结束或异常终止时，就进入完成状态。由作业当作业正常结束或异常终止时，就进入完成状态。由作业调度程序做收尾工作：撤销调度程序做收尾工作：撤销JCBJCB、回收分给该作业的系统资源等。、回收分给该作业的系统资源等。3.1 3.1 处理机调度的基本概念处理机调度的基本概念淮海工学院计算机科学系淮海工学院计算机科学系作业的状态及其转换作业的状态及其转换提交后备运行就绪阻塞就绪阻塞完成SPOOLing
4、程序作业调度程序进程调度程序中级调度外存外存输入井输入设备内存淮海工学院计算机科学系淮海工学院计算机科学系在多道批处理系统中，一个作业从提交到后备作业队列，再调入内从在多道批处理系统中，一个作业从提交到后备作业队列，再调入内从经运行到完成，可能需要经历三级调度：经运行到完成，可能需要经历三级调度：1.1.高级调度（高级调度（High Scheduling)High Scheduling)高级调度又称为作业调度或宏观调度或长程调度，其主要功能高级调度又称为作业调度或宏观调度或长程调度，其主要功能是根据一定的算法，从后备作业队列（一批作业）中选出若干个是根据一定的算法，从后备作业队列（一批作业）中
5、选出若干个作业调入内存，并为它们创建进程和分配必要的资源，然后将创作业调入内存，并为它们创建进程和分配必要的资源，然后将创建的新进程放入进程就绪队列中，使其处于就绪状态。当作业运建的新进程放入进程就绪队列中，使其处于就绪状态。当作业运行结束时，还要做一些善后工作（资源回收）行结束时，还要做一些善后工作（资源回收）3.1.1 3.1.1 处理机调度的层次处理机调度的层次淮海工学院计算机科学系淮海工学院计算机科学系高级调度特点：高级调度特点：1 1）多道批处理系统需要作业调度；分时系统和实时系统一般不需要）多道批处理系统需要作业调度；分时系统和实时系统一般不需要高级调度。高级调度。2 2）每次调度
6、多少作业（程序）？需由系统规定的多道程序度而定；）每次调度多少作业（程序）？需由系统规定的多道程序度而定；3 3）调度那些作业？由调度算法（策略）而定，如先来先服务，短作）调度那些作业？由调度算法（策略）而定，如先来先服务，短作业优先调度，优先权调度算法等。业优先调度，优先权调度算法等。淮海工学院计算机科学系淮海工学院计算机科学系2.2.中级调度中级调度(Intermediate-Level Scheduling)(Intermediate-Level Scheduling)n 中级调度又称之为中程调度中级调度又称之为中程调度(Medium-Term Scheduling)(Medium-Te
7、rm Scheduling)，中级，中级调度主要任务是实施进程在内、外存间的交换；调度主要任务是实施进程在内、外存间的交换；n 中级调度的主要功能是在内存使用紧张时，将一些暂时不能运行中级调度的主要功能是在内存使用紧张时，将一些暂时不能运行的进程从内存对换到外存上等待（此时的进程状态称为挂起状态的进程从内存对换到外存上等待（此时的进程状态称为挂起状态或驻留外存状态）。以后，当外存有足够的空闲空间时，再将合或驻留外存状态）。以后，当外存有足够的空闲空间时，再将合适的进程重新换入内存，等待进程调度。适的进程重新换入内存，等待进程调度。n 引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。引
8、入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。淮海工学院计算机科学系淮海工学院计算机科学系3.3.低级调度低级调度(Low Level Scheduling)(Low Level Scheduling)n 低级调度又称进程调度或微观调度或短程调度，其主要功能是根低级调度又称进程调度或微观调度或短程调度，其主要功能是根据一定的算法，将据一定的算法，将CPUCPU分派给就绪进程队列中的某一进程。分派给就绪进程队列中的某一进程。n 执行低级调度功能的程序称为进程调度程序，由它实现执行低级调度功能的程序称为进程调度程序，由它实现CPUCPU在进在进程间的切换。程间的切换。n 进程调度是操作系
9、统中最基本的一种调度，在一般操作系统（包进程调度是操作系统中最基本的一种调度，在一般操作系统（包括：多道批处理系统、分时系统和实时系统）中都必须有进程调括：多道批处理系统、分时系统和实时系统）中都必须有进程调度，而且它的策略的优劣直接影响整个系统的性能。度，而且它的策略的优劣直接影响整个系统的性能。淮海工学院计算机科学系淮海工学院计算机科学系4 4、进程调度方式、进程调度方式 n非抢占方式（非抢占方式（NonpreemptiveNonpreemptive）：）：在这种调度方式下，一旦一个在这种调度方式下，一旦一个进程被选中运行，它就一直运行下去，直到它运行结束并自愿放进程被选中运行，它就一直运
10、行下去，直到它运行结束并自愿放弃弃CPUCPU，或者因等待某一事件而被阻塞或终止时为止，才把，或者因等待某一事件而被阻塞或终止时为止，才把CPUCPU出让给其他进程，即得到出让给其他进程，即得到CPUCPU的进程不管运行多长时间，都一直的进程不管运行多长时间，都一直运行下去，不会因为当前进程以外的原因而被迫让出运行下去，不会因为当前进程以外的原因而被迫让出CPUCPU。n引起调度的原因：引起调度的原因：1 1）当前进程运行结束或发生某事件而终止；当前进程运行结束或发生某事件而终止；2 2）当前进程因提出当前进程因提出I/OI/O请求而阻塞；请求而阻塞；3 3）进程之间通信或同步而由于进程之间通
11、信或同步而由于执行原语而等待。执行原语而等待。淮海工学院计算机科学系淮海工学院计算机科学系n抢占方式（抢占方式（PreemptivePreemptive）：）：抢占方式允许调度程序根据某种策略抢占方式允许调度程序根据某种策略中止当前进程的执行，将其移入就绪队列，并将处理机分派给另中止当前进程的执行，将其移入就绪队列，并将处理机分派给另一个进程使之投入运行。一个进程使之投入运行。n抢占原则：抢占原则：1 1）优先权原则：）优先权原则：允许高优先权进程抢占低优先权的允许高优先权进程抢占低优先权的CPUCPU；2 2）短作业原则：）短作业原则：允许短进程抢占长进程的处理机；允许短进程抢占长进程的处理
12、机；3 3）时）时间片原则：间片原则：分时系统中的当前进程，若时间片规定的时间用完，分时系统中的当前进程，若时间片规定的时间用完，不管是否运行结束，都要立即中止放到就绪队列中，再将不管是否运行结束，都要立即中止放到就绪队列中，再将CPUCPU分分派给其它进程。派给其它进程。淮海工学院计算机科学系淮海工学院计算机科学系3.1.2 3.1.2 调度队列模型调度队列模型 不同不同OSOS对高级、中级和低级调度的选取形成了不同的调度队列模对高级、中级和低级调度的选取形成了不同的调度队列模型，共有型，共有3 3种类型。种类型。1 1、仅有进程调度的调度队列模型、仅有进程调度的调度队列模型 常在分时系统中
13、设置仅有进程调度的调度队列模型。终端用户的常在分时系统中设置仅有进程调度的调度队列模型。终端用户的登录注册以及交互命令的输入执行，系统都将为其建立进程，并登录注册以及交互命令的输入执行，系统都将为其建立进程，并放在放在FIFOFIFO就绪队列中，按照时间片轮转调度执行。进程的调度和就绪队列中，按照时间片轮转调度执行。进程的调度和变化过程如下图所示。变化过程如下图所示。淮海工学院计算机科学系淮海工学院计算机科学系图图3-1 3-1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 就 绪队 列阻 塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完P1P2P4淮海工学院计算机科学
14、系淮海工学院计算机科学系2.2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且还需要作业调度。若在批处理系统中，不仅需要进程调度，而且还需要作业调度。若OSOS中仅中仅包含高级调度和低级调度就形成了具有高级和低级调度的队列模型。包含高级调度和低级调度就形成了具有高级和低级调度的队列模型。进程调度进程调度常以最高常以最高优先权优优先权优先调度算先调度算法，就绪法，就绪队列形式队列形式为优先权为优先权队列。队列。阻塞队列按照不同事件排队阻塞队列按照不同事件排队就绪队列进程调度进程调度CPU进程完成等待事件 1作业作业调度调度事件1出现时间片完
15、等待事件 2事件2出现等待事件 n事件n出现后备队列淮海工学院计算机科学系淮海工学院计算机科学系3.3.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 作业作业CPU就绪挂起队列就绪挂起队列阻塞挂起队列阻塞挂起队列阻塞队列阻塞队列就绪队列就绪队列时间片到时间片到进程调度进程调度作业调度作业调度调入调入中级调度中级调度事件出现事件出现交互式用户交互式用户等待事件等待事件进程完成进程完成挂起调出挂起调出挂起调出挂起调出事件出现事件出现 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 淮海工学院计算机科学系淮海工学院计算机科学系3.1.3 3.1.3 选择调度方式和调度算法的
16、若干准则选择调度方式和调度算法的若干准则 1.1.面向用户的准则面向用户的准则 周转时间短：周转时间短：周转周期是指作业从提交给系统开始，到作业完周转周期是指作业从提交给系统开始，到作业完成为止所消耗的时间。常用于衡量系统性能、作业调度算法的成为止所消耗的时间。常用于衡量系统性能、作业调度算法的优劣的重要指标。优劣的重要指标。可把平均周转时间描述为：可把平均周转时间描述为：iiiTnT11niSiiTTnW11作业的周转时间作业的周转时间T与系统为它提供服务的时间与系统为它提供服务的时间TS之比，即之比，即W=T/TS，称，称为带权为带权周转时间，而平均带权周转时间则可表示为周转时间，而平均带
17、权周转时间则可表示为:淮海工学院计算机科学系淮海工学院计算机科学系 响应时间快：响应时间快：分时系统性能的主要评价指标。响应时间指用分时系统性能的主要评价指标。响应时间指用户从键盘键入一个命令开始，到系统首次给出响应信息为止户从键盘键入一个命令开始，到系统首次给出响应信息为止这段时间。这段时间。截止时间的保证：截止时间的保证：评价实时系统性能的重要指标。截止时间评价实时系统性能的重要指标。截止时间是指系统为处理某事件是指系统为处理某事件/任务必须开始执行的最迟时间，或必任务必须开始执行的最迟时间，或必须完成的最迟时间。须完成的最迟时间。优先权准则：优先权准则：批处理、分时和实时系统中的调度算法
18、都应该批处理、分时和实时系统中的调度算法都应该遵循的原则。这种调度思想就是遵循的原则。这种调度思想就是“急事急办急事急办”，优先权高者，优先权高者为急。为急。淮海工学院计算机科学系淮海工学院计算机科学系2.2.面向系统的准则面向系统的准则 系统吞吐量高：系统吞吐量高：评价批处理系统整体性能的重要指标。吞吐评价批处理系统整体性能的重要指标。吞吐量是指单位时间内系统所完成的作业数。作业调度算法对系量是指单位时间内系统所完成的作业数。作业调度算法对系统吞吐量有直接影响，选择确定时应考虑这一准则。统吞吐量有直接影响，选择确定时应考虑这一准则。处理机利用率好：处理机利用率好：CPUCPU的利用率是衡量大
19、中型系统性能的重的利用率是衡量大中型系统性能的重要指标。要指标。各类资源的平衡利用：各类资源的平衡利用：选择适当调度算法，保证各种资源的选择适当调度算法，保证各种资源的利用都处于忙碌状态。利用都处于忙碌状态。淮海工学院计算机科学系淮海工学院计算机科学系3.2 3.2 调度算法调度算法 1 1、先来先服务（、先来先服务（FCFSFCFS）调度算法）调度算法F 适应范围：适应范围：适应作业调度和进程调度；适应作业调度和进程调度；F 调度过程：调度过程：FCFSFCFS用于作业（进程）调度时，从后备（就绪）队列中用于作业（进程）调度时，从后备（就绪）队列中选择若干或一个先到来的作业（进程）投入运行。
20、进程在分派到选择若干或一个先到来的作业（进程）投入运行。进程在分派到CPUCPU进入运行过程中，只有当进程运行结束或因某事件发生而被阻进入运行过程中，只有当进程运行结束或因某事件发生而被阻塞才放弃塞才放弃CPUCPU。F 算法特点：算法特点：算法容易实现，但效率不高；只顾及作业等候时间，没算法容易实现，但效率不高；只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业；作考虑作业要求服务时间的长短，不利于短作业而优待了长作业；作业调度不分轻重缓急，人人平等；业调度不分轻重缓急，人人平等；FCFSFCFS为非抢占式调度。为非抢占式调度。淮海工学院计算机科学系淮海工学院计算机
21、科学系先来先服务（先来先服务（FCFSFCFS）调度算法效率举例）调度算法效率举例表注：周转时间表注：周转时间=完成时间完成时间-到达时间；带权周转时间到达时间；带权周转时间=周转时间周转时间/服务时间服务时间淮海工学院计算机科学系淮海工学院计算机科学系2 2、短作业、短作业/进程（进程（SJF/SPFSJF/SPF）优先调度算法）优先调度算法 适应范围：适应范围：适应作业调度和进程调度。适应作业调度和进程调度。SJF/SPFSJF/SPF算法以进入系统的算法以进入系统的作业作业/进程所要求的进程所要求的CPUCPU时间为标准，总选取估计计算时间最短的时间为标准，总选取估计计算时间最短的作业作
22、业/进程投入运行。进程投入运行。算法特点：算法特点：算法易于实现，效率不高；忽视长作业等待时间，会算法易于实现，效率不高；忽视长作业等待时间，会出现饥饿现象；不考虑紧迫作业出现饥饿现象；不考虑紧迫作业/进程的需求；长短时间人为估计，进程的需求；长短时间人为估计，不可靠，会出现以长乱短。不可靠，会出现以长乱短。SPFSPF算法类型：算法类型：抢占或非抢占式。抢占式抢占或非抢占式。抢占式SPFSPF调度算法在新进程进调度算法在新进程进入就绪队列时，将其运行时间与当前进程的剩余运行时间相比，入就绪队列时，将其运行时间与当前进程的剩余运行时间相比，若更短时，可抢占若更短时，可抢占CPUCPU；非抢占式
23、；非抢占式SPFSPF算法允许当前运行进程先算法允许当前运行进程先执行直到释放执行直到释放CPUCPU为止。为止。可抢占可抢占SPFSPF调度有时称为最短剩余时间调度有时称为最短剩余时间优先（优先（shortest-remaining-time-firstshortest-remaining-time-first）调度。）调度。淮海工学院计算机科学系淮海工学院计算机科学系FCFSFCFS和和SJFSJF调度算法的性能分析调度算法的性能分析 淮海工学院计算机科学系淮海工学院计算机科学系 例题：例题：假如假如5 5个就绪进程其到达系统和所需个就绪进程其到达系统和所需CPUCPU时间如下表所示（单位
24、：时间如下表所示（单位：毫秒），如果忽略毫秒），如果忽略I/OI/O以及其他开销，分别计算采用以及其他开销，分别计算采用FCFSFCFS、非抢占式、非抢占式SPFSPF和抢占式和抢占式SPFSPF调度算法进行调度算法进行CPUCPU调度的平均周转时间和平均带权周调度的平均周转时间和平均带权周转时间。转时间。进程到达和运行时间进程到达和运行时间进程到达时间运行时间A03B26C44D65E82淮海工学院计算机科学系淮海工学院计算机科学系 解答如下：解答如下：（1 1）采用）采用FCFSFCFS的调度顺序为：的调度顺序为：ABCDE0 03 39 9131318182020平均周转时间为：平均周转
25、时间为：T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6带权平均周转时间为：带权平均周转时间为：W=2.56W=2.56淮海工学院计算机科学系淮海工学院计算机科学系 （2 2）采用非抢占）采用非抢占SJFSJF的调度顺序为：的调度顺序为：ABECD0 03 39 9111115152020平均周转时间为：平均周转时间为：T=7.6T=7.6带权平均周转时间为：带权平均周转时间为：W=1.84W=1.84淮海工学院计算机科学系淮海工学院计算机科学系 （3 3）采用抢占）采用抢占SJFS
26、JF的调度顺序为：的调度顺序为：平均周转时间为：平均周转时间为：T=7.2T=7.2带权平均周转时间为：带权平均周转时间为：W=1.59W=1.59AB1ECB20 03 38 8101015152020D4 4淮海工学院计算机科学系淮海工学院计算机科学系3 3、高优先权优先调度算法、高优先权优先调度算法（priority-scheduling algorithm）1）优先权调度算法的类型）优先权调度算法的类型非抢占式优先权算法：非抢占式优先权算法：在此方式下，系统一旦把在此方式下，系统一旦把CPU分配给就绪队列中分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成或因发生某优先
27、权最高的进程后，该进程便一直执行下去，直至完成或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给就绪队事件使该进程放弃处理机时，系统方可再将处理机重新分配给就绪队列中另一优先权最高的进程。这种调度算法主要用于批处理系统中；列中另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。也可用于某些对实时性要求不严的实时系统中。抢占式优先权算法：抢占式优先权算法：在此方式下，系统把处理机分配给优先权最高的进在此方式下，系统把处理机分配给优先权最高的进程使之执行。但在其执行期间，只要又有更高优先权新进程进入就绪程使之执行。但在其执行期间，只要又有
28、更高优先权新进程进入就绪队列，进程调度程序就立即停止当前进程的执行，重新将处理机分配队列，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。适应较严格的实时系统、性能要求较高给新到的优先权最高的进程。适应较严格的实时系统、性能要求较高的批处理和分时系统。的批处理和分时系统。淮海工学院计算机科学系淮海工学院计算机科学系2 2）优先权的类型）优先权的类型 静态优先权静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，持不变。一般地，优先权是
29、利用某一范围内的一个整数来表示的，例如，例如，0909中的某一整数，又把该整数称为优先数。中的某一整数，又把该整数称为优先数。优先权的确定准则：优先权的确定准则：系统进程者优先；资源需求少者优先；用户系统进程者优先；资源需求少者优先；用户需求紧迫者优先。需求紧迫者优先。动态优先权：动态优先权：动态优先权是指在创建进程时所赋予的优先权，可动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变的，以便获得更好的调度性能。（如等待以随进程的推进而改变的，以便获得更好的调度性能。（如等待时间与优先权成正比）时间与优先权成正比）淮海工学院计算机科学系淮海工学院计算机科学系4 4、高响应比优先调
30、度算法、高响应比优先调度算法 要求服务时间要求服务时间等待时间优先权动态优先权的变化规律可描述为：动态优先权的变化规律可描述为：系统对作业的响应时间系统对作业的响应时间=等待时间等待时间+服务时间，故该优先权又相当服务时间，故该优先权又相当于响应比于响应比R RP P。据此，优先权变化规律又可表示为：。据此，优先权变化规律又可表示为：要求服务时间响应时间要求服务时间要求服务时间等待时间Rp淮海工学院计算机科学系淮海工学院计算机科学系高响应比优先调度算法特点：高响应比优先调度算法特点：如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈
31、高，高，因而该算法有利于短作业因而该算法有利于短作业；当要求服务的时间相同时，作业的优先权决定于其等待时间，等当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，待时间愈长，其优先权愈高，因而它实现的是先来先服务因而它实现的是先来先服务；对于长作业，作业的优先级可以随等待时间的增加而提高，当其对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，等待时间足够长时，其优先级便可升到很高，从而也可获得处从而也可获得处理机，理机，避免了长作业饥饿现象避免了长作业饥饿现象。淮海工学院计算机科学系淮海工学院计算机科学系5 5、基于时
32、间片的轮转调度算法、基于时间片的轮转调度算法 时间片调度算法适用于分时系统。划分为时间片轮转和多级反馈队时间片调度算法适用于分时系统。划分为时间片轮转和多级反馈队列调度算法列调度算法1 1）时间片轮转法）时间片轮转法轮转法调度做法是：系统将所有的就绪进程按轮转法调度做法是：系统将所有的就绪进程按FIFOFIFO原则排队，每次调原则排队，每次调度时，把度时，把CPUCPU分配给队首进程，并令其执行一个时间片（如分配给队首进程，并令其执行一个时间片（如20ms20ms）。）。当执行的时间片用完时，停止该进程的执行，并将它送往就绪队尾；然当执行的时间片用完时，停止该进程的执行，并将它送往就绪队尾；然
33、后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。如此反复和轮转，就可以保证就绪队列中的所有进程，在一给时间片。如此反复和轮转，就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。定的时间内，均能获得一时间片的处理机执行时间。淮海工学院计算机科学系淮海工学院计算机科学系FCB A .CPU A B C时间片轮转算法图示完成完成淮海工学院计算机科学系淮海工学院计算机科学系2 2）多级反馈队列调度算法）多级反馈队列调度算法 多级反馈队列调度算法是目前公认的一种性能比较优良的调度算法，多
34、级反馈队列调度算法是目前公认的一种性能比较优良的调度算法，兼备了前述各种算法的优点。原理如下：兼备了前述各种算法的优点。原理如下：设置多个就绪队列，并赋予不同的优先级和时间片：设置多个就绪队列，并赋予不同的优先级和时间片：第一个队列第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。图先权愈高的队列中，为每个进程所规定的执行时间片就愈小。图 3-5 3-5
35、是多级反馈队列算法的示意。是多级反馈队列算法的示意。淮海工学院计算机科学系淮海工学院计算机科学系多级反馈队列调度算法多级反馈队列调度算法 新进程进入新进程进入（64ms）淮海工学院计算机科学系淮海工学院计算机科学系 调度原则：调度原则：当一个新进程进入内存后，首先将它放入第一队列的末当一个新进程进入内存后，首先将它放入第一队列的末尾，按尾，按FCFSFCFS原则等待调度。当轮到该进程执行时，如它能在该时原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二
36、队列的末尾，再同样地按完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFSFCFS原则等待调度执行；如果它在第二队列中运行一个时间片后原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，仍未完成，再依次将它放入第三队列，如此下去，当一个长，如此下去，当一个长作业作业(进程进程)从第一队列依次降到第从第一队列依次降到第n n队列后，在第队列后，在第n n队列中便采取按队列中便采取按时间片轮转的方式运行。时间片轮转的方式运行。淮海工学院计算机科学系淮海工学院计算机科学系 抢占原则：抢占原则：仅当第一队列空闲时，调度程序才调度第二队列中的仅当第一队列空闲时
37、，调度程序才调度第二队列中的进程运行；进程运行；仅当第仅当第1i 1i 队列均空时，才会调度第队列均空时，才会调度第i+1i+1队列中的进队列中的进程运行。如果处理机正在第程运行。如果处理机正在第i i队列中为某进程服务时，又有新进队列中为某进程服务时，又有新进程进入优先权较高的队列程进入优先权较高的队列(第第1(i-1)1(i-1)中的任何一个队列中的任何一个队列)，则此时，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第的进程放回到第ii队列的末尾，把处理机分配给新到的高优先权队列的末尾，把处理机分配给新到
38、的高优先权进程。进程。淮海工学院计算机科学系淮海工学院计算机科学系多级反馈队列调度算法的性能与特点多级反馈队列调度算法的性能与特点 (1)(1)终端型作业用户：短小作业及时完成，用户满意。终端型作业用户：短小作业及时完成，用户满意。(2)(2)短批处理作业用户：短作业优先运行结束。短批处理作业用户：短作业优先运行结束。(3)(3)长批处理作业用户：不出现饥饿现象。长批处理作业用户：不出现饥饿现象。淮海工学院计算机科学系淮海工学院计算机科学系作业3-1 P101：1、4、6、7淮海工学院计算机科学系淮海工学院计算机科学系3.3 3.3 实实 时时 调调 度度 3.3.1 3.3.1 实现实时调度
39、的基本条件实现实时调度的基本条件 为了实现对实时进程进行有效调度，系统必须满足下述条件：为了实现对实时进程进行有效调度，系统必须满足下述条件：1.1.提供必要的信息提供必要的信息 就绪时间：就绪时间：进程进入就绪状态的开始时间，有周期性和非周期性进程进入就绪状态的开始时间，有周期性和非周期性 开始截止时间和完成截止时间：开始截止时间和完成截止时间：开始处理或完成任务的最迟时间开始处理或完成任务的最迟时间 处理时间：处理时间：指一个进程从开始执行到完成需要的处理时间；指一个进程从开始执行到完成需要的处理时间；资源要求：资源要求：指处理一个任务时所需要的资源；指处理一个任务时所需要的资源；优先级：
40、优先级：用于标识一个任务得到处理的轻重缓急。用于标识一个任务得到处理的轻重缓急。实时调度：实时调度：在实时操作系统中，实现实时进程或任务的调度。实在实时操作系统中，实现实时进程或任务的调度。实时调度强调对实时进程或任务处理（响应）的及时性和紧迫性。时调度强调对实时进程或任务处理（响应）的及时性和紧迫性。淮海工学院计算机科学系淮海工学院计算机科学系2.2.系统处理能力强系统处理能力强 在实时系统中，通常都有多个实时任务（进程）等待计算机及时处理。在实时系统中，通常都有多个实时任务（进程）等待计算机及时处理。处理机能力必须满足：处理机能力必须满足：假定系统中有假定系统中有mm个周期性的硬实时任务，
41、它们的个周期性的硬实时任务，它们的处理时间分别处理时间分别CCii，周期时间分别为，周期时间分别为P Pii，则在单处理机情况下，其处理能，则在单处理机情况下，其处理能力必须满足条件：力必须满足条件：miiiPC11处理机满足此条件时，才是可调度的；否则，调度不过来。处理机满足此条件时，才是可调度的；否则，调度不过来。miiiNPC1多处理机情况下，需要满足条件为：多处理机情况下，需要满足条件为：（N为处理机个数）为处理机个数）淮海工学院计算机科学系淮海工学院计算机科学系3 3、采用抢占式调度机制采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时停止，而令当一个优先权更高的任
42、务到达时，允许将当前任务暂时停止，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。止时间的要求。但这种调度机制比较复杂。4 4、具有快速切换机制、具有快速切换机制 对外部中断的快速响应能力：对外部中断的快速响应能力：外部任务来到时能快速响应；外部任务来到时能快速响应；快速的任务分派能力：快速的任务分派能力：在完成任务调度后，便应进行任务在完成任务调度后，便应进行任务切换。切换。淮海工学院计算机科学系淮海工学院计算机科学系3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类 1.1.非抢
43、占式调度算法非抢占式调度算法 非抢占式轮转调度算法：非抢占式轮转调度算法：控制多个相同对象；每对象一个实时进程；控制多个相同对象；每对象一个实时进程；建立一个建立一个FIFOFIFO进程就绪队列，按照进程就绪队列，按照FCFSFCFS轮转调度。轮转调度。调度性能：调度性能：实现实现数秒至数十秒响应时间，适应不严格的实时控制。数秒至数十秒响应时间，适应不严格的实时控制。非抢占式优先调度算法：非抢占式优先调度算法：就绪队列按优先级进队排序，调度始终先就绪队列按优先级进队排序，调度始终先调度队首进程。调度队首进程。调度性能：调度性能：可能获得数秒至数百毫秒的响应时间，适可能获得数秒至数百毫秒的响应时
44、间，适应有一定要求的实时控制系统应有一定要求的实时控制系统实时调度算法的分类方式较多：如按照任务性质分为硬实时调度和实时调度算法的分类方式较多：如按照任务性质分为硬实时调度和软实时调度；按照调度方式分为抢占方式和非抢占方式调度等软实时调度；按照调度方式分为抢占方式和非抢占方式调度等淮海工学院计算机科学系淮海工学院计算机科学系2.2.抢占式调度算法抢占式调度算法 基于时钟中断的抢占式优先权调度算法：基于时钟中断的抢占式优先权调度算法：如果有比当前进程优先如果有比当前进程优先级更高的进程到来，需等到时钟中断到来时抢占级更高的进程到来，需等到时钟中断到来时抢占CPUCPU。调度性能：调度性能：响应达
45、到几十毫秒至几毫秒，适应大多数控制系统。响应达到几十毫秒至几毫秒，适应大多数控制系统。立即抢占立即抢占(Immediate Preemption)(Immediate Preemption)的优先权调度算法：的优先权调度算法：如果有如果有比当前进程优先级更高的进程到来，若当前进程不处在临界区，比当前进程优先级更高的进程到来，若当前进程不处在临界区，则立即抢占则立即抢占CPUCPU。调度性能：调度性能：调度延迟为几毫秒至调度延迟为几毫秒至100100微秒。微秒。淮海工学院计算机科学系淮海工学院计算机科学系非抢占实时进程调度示意图非抢占实时进程调度示意图(a)非抢占轮转调度非抢占轮转调度调度时间调
46、度时间进程进程 1进程进程 2实时进程要求调度实时进程要求调度进程进程 n实时进程实时进程调度实时进程运行调度实时进程运行(b)非抢占优先权调度非抢占优先权调度当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度当前进程运行完成当前进程运行完成调度时间调度时间淮海工学院计算机科学系淮海工学院计算机科学系抢占实时进程调度示意图抢占实时进程调度示意图当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度实时进程枪占当前实时进程枪占当前进程，并立即执行进程，并立即执行(d)立即抢占的优先权调度立即抢占的优先权调度当前进程当前进程实时进程请求调度实时进程请求调度时钟中断到来时时钟
47、中断到来时调度时间调度时间(c)基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度调度时间调度时间实时进程实时进程淮海工学院计算机科学系淮海工学院计算机科学系3.3.3 3.3.3 常用的几种实时调度算法常用的几种实时调度算法 1.1.最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法调度算法：调度算法：根据任务的开始截至时间来确定任务的优先级，开始截至根据任务的开始截至时间来确定任务的优先级，开始截至时间越早，进程的优先级越高，而愈先得到调度执行。实际上进程就时间越早，进程
48、的优先级越高，而愈先得到调度执行。实际上进程就绪队列按照开始截至时间早晚排队，每次调度队首进程。绪队列按照开始截至时间早晚排队，每次调度队首进程。适应方式：适应方式：即可用于抢占方式，也可以用于非抢占方式。即可用于抢占方式，也可以用于非抢占方式。EDFEDF算法用于非抢占调度方式算法用于非抢占调度方式 1342开始截止时间任务执行任务到达12341342t淮海工学院计算机科学系淮海工学院计算机科学系2.2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法 调度策略：调度策略：算法根据任务紧急算法根据任务紧急(或
49、松弛或松弛)的程度，来确定任务的优先级。任的程度，来确定任务的优先级。任务的紧急程度愈高（开始截至时间或完成截至时间越早），为该任务所赋务的紧急程度愈高（开始截至时间或完成截至时间越早），为该任务所赋予的优先级就愈高，予的优先级就愈高，以使之优先执行。以使之优先执行。例如说明：例如说明：一个任务在一个任务在200ms200ms时必须完成，而它本身所需的运行时间就有时必须完成，而它本身所需的运行时间就有100ms100ms，因此，调度程序必须在，因此，调度程序必须在100 ms100 ms之前调度执行，该任务的紧急程之前调度执行，该任务的紧急程度度(松弛程度松弛程度)为为100 ms100 ms
50、。实现方法：实现方法：进程在就绪队列中按松弛度排序，松弛度最低的任务排在队列进程在就绪队列中按松弛度排序，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。可抢占调度方式中。淮海工学院计算机科学系淮海工学院计算机科学系A A和和B B任务每次必须完成的时间任务每次必须完成的时间 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0举例说明：举例说明：假如在一个实时系统中，有两个周期性实时任务假如在一个实时系统中，有两个周期性实时任务A A和
