《操作系统课件os03处理机调度.ppt》由会员分享，可在线阅读，更多相关《操作系统课件os03处理机调度.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统操作系统Operating SystemsWINDOWSWINDOWSUNIXUNIXLINUXLINUXOS2OS2VxWorksVxWorksMac OSMac OS第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次 一一个个批批处处理理型型作作业业，从从进进入入系系统统并并驻驻留留在在外外存存的的后后备备队队列列上开始，直至作业运行完毕，可能要经历的三级调度：上开始，直至作业运行完毕，可能要经历的三级调度：中级调度中级调度创建创建静止就绪静止就绪静止阻塞静止阻塞高级调度高级调度低级调度低级调度执行执行就绪就绪阻塞阻塞终止终止3.1.1 3.1.1 高级调度（作业调度）
2、高级调度（作业调度）作业调度作业调度、长程调度、接纳调度、长程调度、接纳调度主要功能主要功能挑选若干作业进入内存挑选若干作业进入内存为它们创建进程、分配必要的资源为它们创建进程、分配必要的资源再将新创建的进程插入就绪队列，准备执行再将新创建的进程插入就绪队列，准备执行调度对象调度对象作业作业1.作业和作业步作业和作业步 作业作业(JOB):程序程序+数据数据+作业说明书作业说明书作业步作业步(Job Step)一个作业可划分成若干部分，每部分称一个作业步一个作业可划分成若干部分，每部分称一个作业步2 2作业控制块作业控制块JCBJCBJCBJCB是作业在系统中存在的标志是作业在系统中存在的标志
3、通常应包含的内容有：通常应包含的内容有：作业的基本情况作业的基本情况作业标识、用户名称作业标识、用户名称、作业状态等。、作业状态等。作业的作业的调度信息调度信息优先级、作业已运行时间优先级、作业已运行时间。资源需求资源需求预计运行时间、要求内存大小、要求预计运行时间、要求内存大小、要求I/O设备的类设备的类型和数量型和数量。3 3作业调度作业调度须做出以下两个决定：须做出以下两个决定：1)1)决定接纳多少个作业。决定接纳多少个作业。多多道道程程序序度度的的确确定定应应根根据据系系统统的的规规模模和和运运行行速速度度等等情情况做适当的折衷。况做适当的折衷。2)2)决定接纳哪些作业决定接纳哪些作业
4、调度算法。调度算法。先来先服务、短作业优先、基于作业优先级、先来先服务、短作业优先、基于作业优先级、“响应比高者优先响应比高者优先”。3 3作业调度作业调度分时系统要求分时系统要求及时响应及时响应无需再配置上述的作业调度机制无需再配置上述的作业调度机制需要有某些限制性措施来限制进入系统的用户数。需要有某些限制性措施来限制进入系统的用户数。如果系统尚未饱和，将接纳所有授权用户如果系统尚未饱和，将接纳所有授权用户否则，将拒绝接纳。否则，将拒绝接纳。在实时系统中通常也不需要作业调度。在实时系统中通常也不需要作业调度。3.1.2 3.1.2 低级调度低级调度也称为：也称为：进程调度进程调度、短程调度。
5、、短程调度。进程调度是进程调度是最基本最基本的一种调度的一种调度决定就绪队列中的哪个进程应获得处理机决定就绪队列中的哪个进程应获得处理机由由分派程序分派程序执行把处理机分配给该进程的具体操作。执行把处理机分配给该进程的具体操作。调度的对象调度的对象进程进程(或内核级线程或内核级线程)在多道批处理、分时和实时三种类型的在多道批处理、分时和实时三种类型的OSOS中，都必须配置中，都必须配置这级调度。这级调度。1 低级调度的功能低级调度的功能1.1.保存处理机的现场信息。保存处理机的现场信息。处理机的现场信息处理机的现场信息进程控制块进程控制块(PCB)(PCB)2.2.按某种算法选取进程。按某种算
6、法选取进程。3.3.把处理器分配给进程。把处理器分配给进程。由分派程序把处理器分配给进程。由分派程序把处理器分配给进程。恢复处理机现场恢复处理机现场:PCBPCB处理器相应的各个寄存器处理器相应的各个寄存器把处理器的控制权交给该进程把处理器的控制权交给该进程2 2进程调度中的三个基本机制进程调度中的三个基本机制（1 1）排队器。）排队器。应应事事先先将将系系统统中中所所有有的的就就绪绪进进程程按按照照一一定定的的方方式式排排成成一个或多个队列。一个或多个队列。（2 2）分派器）分派器(分派程序分派程序)。（3）上下文切换机制。上下文切换机制。两对上下文切换操作。两对上下文切换操作。保存当前进程
7、的上下文，装入分派程序的上下文保存当前进程的上下文，装入分派程序的上下文移出分派程序，新选进程的移出分派程序，新选进程的CPU现场信息装入到现场信息装入到处理机的各个相应寄存器中。处理机的各个相应寄存器中。3 3 进程调度方式进程调度方式非抢占方式非抢占方式抢占方式抢占方式非抢占方式非抢占方式一一旦旦把把处处理理机机分分配配给给某某进进程程后后，一一直直让让它它运运行行下下去去，直直至至该进程完成，自愿释放处理机，或被阻塞。该进程完成，自愿释放处理机，或被阻塞。引起进程调度的因素引起进程调度的因素1.1.正正在在执执行行的的进进程程执执行行完完毕毕，或或因因发发生生某某事事件件而而不不能能再再
8、继继续续执行；执行；2.2.执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；3.3.在进程通信或同步过程中执行了某种原语操作，在进程通信或同步过程中执行了某种原语操作，如：如：P P操作操作(wait(wait操作操作)、BlockBlock原语等。原语等。抢占方式抢占方式允许调度程序根据某种原则去暂停某个正在执行的进程，允许调度程序根据某种原则去暂停某个正在执行的进程，将处理机重新分配给另一进程。将处理机重新分配给另一进程。抢占方式的优点是：抢占方式的优点是：可以防止一个长进程长时间占用处理机可以防止一个长进程长时间占用处理机能为大多数进程提供更公平的服务能为
9、大多数进程提供更公平的服务特别是能满足对实时任务的需求特别是能满足对实时任务的需求抢占原则抢占原则1.1.优先权原则。优先权原则。允许优先权高的新到进程抢占当前进程的处理机。允许优先权高的新到进程抢占当前进程的处理机。2.2.短作业短作业(进程进程)优先原则。优先原则。短作业短作业(进程进程)可以抢占当前较长作业可以抢占当前较长作业(进程进程)的处理机。的处理机。3.3.时间片原则。时间片原则。各进程按时间片轮流运行各进程按时间片轮流运行当一个时间片用完后，便停止该进程的执行而重新当一个时间片用完后，便停止该进程的执行而重新进行调度。进行调度。3.1.3 3.1.3 中级调度（中程调度）中级调
10、度（中程调度）目的：目的：提高内存利用率和系统吞吐量。提高内存利用率和系统吞吐量。作用：作用：外存外存内存内存挂起状态（静止）挂起状态（静止）非挂起非挂起状态（活动）状态（活动）中级调度实际上就是存储器管理中的中级调度实际上就是存储器管理中的对换功能对换功能运行频率运行频率进程调度的运行频率最高进程调度的运行频率最高进程调度算法不宜太复杂。进程调度算法不宜太复杂。作业调度（长程调度）作业调度（长程调度）往往是发生在一个往往是发生在一个(批批)作业运行完毕作业运行完毕作业调度的周期较长，运行频率较低作业调度的周期较长，运行频率较低允许作业调度算法花费较多的时间允许作业调度算法花费较多的时间中级调
11、度的运行频率基本上介于上述两种调度之间中级调度的运行频率基本上介于上述两种调度之间3.2 调度队列模型和调度准则调度队列模型和调度准则 调度队列模型调度队列模型仅有进程调度的调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型1 1仅有进程调度的调度队列模型仅有进程调度的调度队列模型组织形式依赖于调度算法组织形式依赖于调度算法把处于就绪状态的进程组织成栈、树或一个无序链表把处于就绪状态的进程组织成栈、树或一个无序链表在分时系统中，常把就绪进程组织成：在分时系统中，常把就绪进程组织成：F
12、IFO队列形式队列形式处理处理处理处理器器器器进程调度进程调度进程调度进程调度完成完成完成完成时间片完时间片完时间片完时间片完就绪队列就绪队列就绪队列就绪队列交互式用户交互式用户交互式用户交互式用户阻塞队列阻塞队列阻塞队列阻塞队列等待事件等待事件等待事件等待事件2 2 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型处理处理处理处理器器器器进程调度进程调度进程调度进程调度作业调度作业调度作业调度作业调度完成完成完成完成时间片完时间片完时间片完时间片完就绪队列就绪队列就绪队列就绪队列后备队列后备队列后备队列后备队列阻塞队列阻塞队列阻塞队列阻塞队列等待事件等待事件等待事件等待事件2
13、 2 2 2阻塞队列阻塞队列阻塞队列阻塞队列等待事件等待事件等待事件等待事件1 1 1 12 2 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型在批处理系统中，最常用的是最高优先权调度算法在批处理系统中，最常用的是最高优先权调度算法就绪队列的形式。就绪队列的形式。优先权队列优先权队列无序链表无序链表就绪队列就绪队列就绪队列就绪队列就绪队列就绪队列就绪队列就绪队列3 3 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型中级调度中级调度创建创建静止就绪静止就绪静止阻塞静止阻塞低级调度低级调度执行执行活动活动就绪就绪活动阻塞活动阻塞终止终止高级调度高级调度中级调度中级调
14、度中级调度中级调度处理处理处理处理器器器器低级调度低级调度低级调度低级调度高级调度高级调度高级调度高级调度完成完成完成完成时间片完时间片完时间片完时间片完就绪队列就绪队列就绪队列就绪队列后备作业队列后备作业队列后备作业队列后备作业队列交互式用户交互式用户交互式用户交互式用户阻塞队列阻塞队列阻塞队列阻塞队列等待事件等待事件等待事件等待事件事件事件事件事件出现出现出现出现挂起就绪队列挂起就绪队列挂起就绪队列挂起就绪队列挂起阻塞队列挂起阻塞队列挂起阻塞队列挂起阻塞队列中级调度中级调度中级调度中级调度处理器三级调度模型处理器三级调度模型选择调度方式和调度算法的准则选择调度方式和调度算法的准则面向用户的
15、准则面向用户的准则周转时间短。周转时间短。响应时间快响应时间快截至时间的保证截至时间的保证优先权准则优先权准则面向系统的准则面向系统的准则系统吞吐量高系统吞吐量高处理机利用率好处理机利用率好资源的平衡利用资源的平衡利用周转时间周转时间通常把周转时间的长短通常把周转时间的长短评价评价批处理系统批处理系统的性能的重要准则之一的性能的重要准则之一从作业被提交给系统开始，到作业完成为止的这段时间间隔从作业被提交给系统开始，到作业完成为止的这段时间间隔它包括四部分时间：它包括四部分时间：作业在外存后备队列上等待作业在外存后备队列上等待(作业作业)调度的时间，调度的时间，进程在就绪队列上等待进程调度的时间
16、，进程在就绪队列上等待进程调度的时间，进程在进程在CPU上执行的时间，上执行的时间，进程等待进程等待I/O操作完成的时间。操作完成的时间。平均周转时间平均周转时间带权周转时间和平均带权周转时间带权周转时间和平均带权周转时间带权周转时间：带权周转时间：W=T/TsT：作业的周转时间作业的周转时间Ts：系统为它提供服务的时间系统为它提供服务的时间平均带权周转时间：平均带权周转时间：相关指标相关指标响应时间响应时间评价评价分时系统分时系统的性能的性能从用户通过键盘提交一个请求开始，直至系统首次产生从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止响应为止
17、的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。的一段时间间隔。截止时间截止时间评价评价实时系统实时系统性能的重要指标性能的重要指标指某任务必须开始执行的最迟时间，或必须完成的最迟指某任务必须开始执行的最迟时间，或必须完成的最迟时间。时间。相关指标相关指标系统吞吐量系统吞吐量评价评价批处理系统批处理系统性能的重要指标性能的重要指标指在单位时间内系统所完成的作业数指在单位时间内系统所完成的作业数处理的长作业多，则吞吐量低处理的长作业多，则吞吐量低资源利用率资源利用率 CPU利用率利用率=CPU有效工作时间有效工作时间/CPU总的运行时间，总的运行时间，CPU总的运行时间总的运行时间=CP
18、U有效工作时间有效工作时间+CPU空闲等待空闲等待时间时间CPU利用率利用率ABC 306080 90100110120 160210170190240230310250CPUI/O设备设备1I/O设备设备2220 CPU 利用率利用率=（20+10+20+30+10+30+30+10+20+10）/310 =190/310=61.3%03.3调调 度度 算算 法法 调度算法调度算法 根据系统的资源分配策略所规定的根据系统的资源分配策略所规定的资源分配算法资源分配算法。不同的系统和系统目标，通常采用不同的调度算法不同的系统和系统目标，通常采用不同的调度算法1 1 先来先服务（先来先服务（FCF
19、S）调度算法调度算法可用于作业调度、进程调度。可用于作业调度、进程调度。作业调度中采用该算法时作业调度中采用该算法时按照作业进入系统后备队列的先后次序来挑选作业按照作业进入系统后备队列的先后次序来挑选作业进程调度中采用进程调度中采用FCFS算法时算法时从就绪队列中选择一个最先进入该队列的进程从就绪队列中选择一个最先进入该队列的进程为之分配处理机。为之分配处理机。FCFSFCFS算法算法调度算法举例调度算法举例比较有利于长作业比较有利于长作业(进程进程)，而不利于短作业，而不利于短作业(进程进程)有利于有利于CPUCPU繁忙型的作业，不利于繁忙型的作业，不利于I/OI/O繁忙型的作业繁忙型的作业
20、(进程进程)进程进程 A 1 B 100 C 1 D 1001平均周转时间平均周转时间=(1+100+100+199)/4023101102202带权周带权周转时间转时间 服务服务时间时间1/1=1100/100=1100/1=100199/100=1.992 2 短作业短作业(进程进程)优先调度算法优先调度算法可用于作业调度、进程调度。可用于作业调度、进程调度。短作业优先短作业优先(SJF)的调度算法的调度算法从后备队列中选择从后备队列中选择一个或若干个一个或若干个估计运行时间最短的估计运行时间最短的作业，将它们调入内存运行作业，将它们调入内存运行短进程优先短进程优先(SPF)调度算法调度算
21、法从就绪队列中选出从就绪队列中选出一个一个估计运行时间最短的进程，将估计运行时间最短的进程，将处理机分配给它。处理机分配给它。SJFSJF算法算法调度算法举例调度算法举例1平均周转时间平均周转时间=(4+8+16+3+9)/5=8平均平均带权周转时间带权周转时间=（1+2.67+3.2+1.5+2.25）/5=2.10236913带权周带权周转时间转时间 服务服务时间时间4/4=18/3=2.6716/5=3.23/2=1.5作业作业ABCDE435241849/4=2.25图图3-4FCFS和和SJF调度算法的性能调度算法的性能 SJ(P)FSJ(P)F调度算法缺点调度算法缺点对长作业不利。
22、对长作业不利。完全未考虑作业的紧迫程度完全未考虑作业的紧迫程度因而不能保证紧迫性作业因而不能保证紧迫性作业(进程进程)会被及时处理。会被及时处理。无法精确知道一个作业的运行时间。无法精确知道一个作业的运行时间。作作业业(进进程程)的的长长短短只只是是根根据据用用户户所所提提供供的的估估计计执执行行时时间而定的。间而定的。3.3.2 3.3.2 高优先权优先调度算法高优先权优先调度算法优先权调度算法的类型优先权调度算法的类型非抢占式优先权算法非抢占式优先权算法用于批处理系统中；用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。也可用于某些对实时性要求不严的实时系统中。抢占式优先权调度算
23、法抢占式优先权调度算法常用于常用于要求比较严格的实时系统要求比较严格的实时系统中中对性能要求较高的批处理和分时系统中。对性能要求较高的批处理和分时系统中。2 2 优先权的类型优先权的类型静态优先权静态优先权在创建进程时确定的，且在进程的整个运行期间保持在创建进程时确定的，且在进程的整个运行期间保持不变不变动态优先权动态优先权在创建进程时所赋予的优先权在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变的可以随进程的推进或随其等待时间的增加而改变的确定静态进程优先权的依据确定静态进程优先权的依据进程类型进程类型系系统统进进程程(如如接接收收进进程程、对对换换进进程程、磁磁盘盘I/
24、OI/O进进程程)的的优优先权高于一般用户进程的优先权。先权高于一般用户进程的优先权。进程对资源的需求。进程对资源的需求。要求少的进程应赋予较高的优先权。要求少的进程应赋予较高的优先权。用户要求。用户要求。这这是是由由用用户户进进程程的的紧紧迫迫程程度度及及用用户户所所付付费费用用的的多多少少来来确定优先权的。确定优先权的。静态优先权法简单易行，系统开销小，但不够精确静态优先权法简单易行，系统开销小，但不够精确动态优先权调整例子动态优先权调整例子在就绪队列中的进程，随其在就绪队列中的进程，随其等待时间的增长等待时间的增长，其优先权以其优先权以速率速率a提高提高优先权初值低的进程优先权便可能升为
25、最高优先权初值低的进程优先权便可能升为最高，从而可以，从而可以获得处理机。获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以优先权以速率速率b下降下降占有占有CPU时间愈长的进程逐步降低优先级，时间愈长的进程逐步降低优先级，可防止一个长作业长期地垄断处理机可防止一个长作业长期地垄断处理机3 3 高响应比优先调度算法高响应比优先调度算法FCFS与与SJF是片面的调度算法。是片面的调度算法。FCFS只考虑作业只考虑作业等候时间等候时间而忽视了作业的计算时问，而忽视了作业的计算时问，SJF只考虑用户估计的作业只考虑用户估计的作业计
26、算时间计算时间而忽视了作业等待而忽视了作业等待时间。时间。高响应比优先调度算法高响应比优先调度算法是介乎这两者之间的折衷算法是介乎这两者之间的折衷算法既考虑作业等待时间，又考虑作业的运行时间既考虑作业等待时间，又考虑作业的运行时间既照顾短作业，又不使长作业的等待时间过长既照顾短作业，又不使长作业的等待时间过长改进了调度性能。改进了调度性能。响应比定义响应比定义引入动态优先权，并使作业的优先级随着等待时间的增加引入动态优先权，并使作业的优先级随着等待时间的增加而以速率而以速率a提高。提高。该优先权的变化规律可描述为：该优先权的变化规律可描述为：优先权优先权=RPHRRF算法举例算法举例作业作业作
27、业作业1 0 20作业作业2 5 15作业作业3 10 5作业作业4 15 10平均作业周转时间平均作业周转时间T=(20+(40-5)+(25-10)+(50-15)/4=26.25平均带权作业周转时间平均带权作业周转时间 W=(20/20+(40-5)/15+(25-10)/5+(50-15)/10)/4=2.46。到达系到达系统时间统时间 所需所需CPU时间时间0 20 25 40 501+(20-5)/15=2 1+(20-10)/5=3 1+(20-15)/10=1.51+(25-5)/15=2.3 1+(25-15)/10=2HRRF比较比较作业作业作业作业1 0 20作业作业2
28、5 15作业作业3 10 5作业作业4 15 10FCFS调度顺序为作业调度顺序为作业1、2、3、4。T=28.75ms W=3.125 SJF调度顺序为作业：调度顺序为作业：1、3、4、2。T=25ms W=2.25HRRF算法性能介于算法性能介于SJF与与FCFS之间。之间。T=26.25 W=2.46到达系到达系统时间统时间 所需所需CPU时间时间分析分析优点：优点：兼顾长短作业兼顾长短作业缺点：缺点：增加系统开销。增加系统开销。每要进行调度之前，都须先做响应比的计算每要进行调度之前，都须先做响应比的计算3.3.3 3.3.3 基于时间片的轮转调度算法基于时间片的轮转调度算法在早期的时间
29、片轮转法中，将所有的就绪进程按先来先在早期的时间片轮转法中，将所有的就绪进程按先来先服务的原则排成一个队列服务的原则排成一个队列每次调度时，把每次调度时，把CPU分配给队首进程，并令其执行一个分配给队首进程，并令其执行一个时间片。时间片。当这个时间片结束时，强迫一个进程让出处理器，当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。让它排列到就绪队列的尾部，等候下一轮调度。处理处理处理处理器器器器完成完成完成完成时间片到时间片到时间片到时间片到就绪队列就绪队列就绪队列就绪队列q=1时的进程运行情况时的进程运行情况ACBDE1032547698111013121
30、81743524q=4时的进程运行情况时的进程运行情况ACBDE103254769811101312181743524时间片大小的确定时间片大小的确定时间片略大于一次典型的交互所需要的时间时间片略大于一次典型的交互所需要的时间2 多级反馈队列调度算法多级反馈队列调度算法反馈循环队列或多队列策略反馈循环队列或多队列策略多级反馈队列调度允许进程在队列之间移动。多级反馈队列调度允许进程在队列之间移动。优先级优先级高高低低3 3 多级反馈队列调度算法的性能多级反馈队列调度算法的性能1.1.终端型作业用户。终端型作业用户。终端型作业用户所提交的作业通常较小，系统只要能终端型作业用户所提交的作业通常较小，
31、系统只要能使这些作业使这些作业(进程进程)在第一队列所规定的时间片内完成，在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。便可使终端型作业用户都感到满意。2.2.短批处理作业用户。短批处理作业用户。其周转时间仍然较短。其周转时间仍然较短。3.3.长批处理作业用户。长批处理作业用户。用户不必担心其作业长期得不到处理。用户不必担心其作业长期得不到处理。作业作业1（多道程序环境下）（多道程序环境下）某多道程序设计系统采用某多道程序设计系统采用可变分区内存管理可变分区内存管理，供用户使用的主存为，供用户使用的主存为200K，磁带机，磁带机5 台。采用静态方式分配外围设备，且台。采用静态
32、方式分配外围设备，且不能移动在主不能移动在主存中的作业存中的作业，进程调度采用，进程调度采用FCFS，忽略用户作业，忽略用户作业I/O时间。现有作业时间。现有作业序列如下：序列如下：作业号作业号 进入后备队列进入后备队列 运行时间运行时间 主存需求量主存需求量 磁带需求量磁带需求量 A8：3040分钟分钟30k3 B8：5025分钟分钟120k1 C9：0035分钟分钟100k2 D9：0520分钟分钟20k3 E9：1010分钟分钟60k1现求：现求：FCFS算法选中作业执行的次序及作业平均周转时间？算法选中作业执行的次序及作业平均周转时间？作业作业 2有一个具有两道作业的批处理系统，作业调
33、度采用短作业有一个具有两道作业的批处理系统，作业调度采用短作业优先的非抢式调度算法，进程调度采用以优先数为基础的优先的非抢式调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列中，作业优先数抢占式调度算法，在下表所示的作业序列中，作业优先数即为进程优先数，优先数越小优先级越高。即为进程优先数，优先数越小优先级越高。作业作业 到达时间到达时间 估计运行时间估计运行时间 优先数优先数1 8：00 40分分 32 8：20 30分分 13 8：30 50分分 24 8：50 20分分 4（1）列出所有作业进）列出所有作业进入内存时间及结束时入内存时间及结束时间。间。（2）计算平
34、均作业周）计算平均作业周转时间。转时间。3.4 实时调度实时调度 实现实时调度的基本条件实现实时调度的基本条件1.1.必要信息必要信息就绪时间、开始截至时间、完成截至时间、处理时间；就绪时间、开始截至时间、完成截至时间、处理时间；资源要求；优先级；资源要求；优先级；2.2.系统处理能力强系统处理能力强3.3.采用抢占式机制采用抢占式机制-硬实时任务；截止时间要求；硬实时任务；截止时间要求；4.4.有快速切换机制有快速切换机制-快速响应外部中断；快速任务分派；快速响应外部中断；快速任务分派；实时调度算法的分类实时调度算法的分类非抢占式非抢占式轮转调度轮转调度(同质任务同质任务)；优先调度优先调度
35、抢占式抢占式时钟中断优先；时钟中断优先；立即抢占优先立即抢占优先非抢占式轮转调度算法非抢占式轮转调度算法非抢占式优先调度算法非抢占式优先调度算法 基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法立即抢占的优先权调度算法立即抢占的优先权调度算法 常用的几种实时调度算法常用的几种实时调度算法最早截止时间优先算法最早截止时间优先算法非抢占式和抢占式非抢占式和抢占式EDFEDF算法用于非抢占调度的调度方式算法用于非抢占调度的调度方式优先级调度优先级调度EDFEDF算法用于抢占调度方式算法用于抢占调度方式最低松弛度优先（最低松弛度优先（LLF LLF）算法）算法松弛度松弛度=必须完成
36、时间必须完成时间-本身运行时间本身运行时间-当前时间当前时间 设有两个周期性实时任务设有两个周期性实时任务A A和和B B，分别每，分别每20ms,50ms20ms,50ms执行一执行一次，每次执行次，每次执行10ms,25ms10ms,25ms。则其须完成的时间为：。则其须完成的时间为：A1,A2,A1,A2,和和B1,B2,B1,B2,，利用利用LLFLLF算法进行调度的情况算法进行调度的情况t t1=01=0时，时，A1A1的松弛度的松弛度=20-10-0=10ms=20-10-0=10ms；B1B1的松弛度的松弛度=50-25-0=25ms;=50-25-0=25ms;利用利用LLFL
37、LF算法进行调度的情况算法进行调度的情况t2t2=10=10时，时，A2A2的松弛度的松弛度=40-10-10=20ms=40-10-10=20ms；B1 B1的松弛度的松弛度=50-25-10=15ms;=50-25-10=15ms;利用利用LLFLLF算法进行调度的情况算法进行调度的情况t3t3=30=30时，时，A2A2的松弛度的松弛度=40-10-30=0ms=40-10-30=0ms；B1 B1的松弛度的松弛度=50-5-30=15ms;=50-5-30=15ms;利用利用LLFLLF算法进行调度的情况算法进行调度的情况t4t4=40=40时，时，A3A3的松弛度的松弛度=60-10
38、-40=10ms=60-10-40=10ms；B1 B1的松弛度的松弛度=50-5-40=5ms;=50-5-40=5ms;利用利用LLFLLF算法进行调度的情况算法进行调度的情况t5t5=45=45时，时，A3A3的松弛度的松弛度=60-10-45=5ms=60-10-45=5ms；B2 B2的松弛度的松弛度=100-25-45=30ms;=100-25-45=30ms;利用利用LLFLLF算法进行调度的情况算法进行调度的情况t6t6=55=55时，时，A4A4未进入第未进入第4 4周期；周期；B2 B2已进入第已进入第2 2周期周期;利用利用LLFLLF算法进行调度的情况算法进行调度的情况
39、t7t7=70=70时，时，A4A4松弛度松弛度=80-10-70=0=80-10-70=0；B2 B2松弛度松弛度=100-10-70=20=100-10-70=20；一个实时系统有四个周期性事件，周期分别为一个实时系统有四个周期性事件，周期分别为50、100、300和和250ms。若假设其处理时间分别需要。若假设其处理时间分别需要35、20、10和和x ms，则该系统可调度允许的，则该系统可调度允许的x值最大为多少？值最大为多少？答：（答：（35/50+20/100+10/200+x/250）1 x16.75ms作业作业对下面的对下面的5个非周期性实时任务，按最早开始截至时间优个非周期性实时任务，按最早开始截至时间优先调度算法应如何进行先调度算法应如何进行CPU调度？调度？进程进程 到达时间到达时间 执行时间执行时间 开始截至时间开始截至时间 A 10 20 110 B 20 20 20 C 40 20 50 D 50 20 90 E 60 20 70