实时调度.ppt

《实时调度.ppt》由会员分享，可在线阅读，更多相关《实时调度.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、处理机调度处理机调度 处理机调度的基本概念处理机调度的基本概念 调度算法调度算法 1.高响应比调度算法高响应比调度算法动态优先权动态优先权响应比响应比=（等待时间（等待时间+要求服务时间）要求服务时间）/服务时间服务时间2.多级反馈队列调度算法：多级反馈队列调度算法：抢占式调度抢占式调度多级队列：多级队列：队列时间片长递增；新进程进入最上级队列队列时间片长递增；新进程进入最上级队列每级队列：先进先出，时间片机制每级队列：先进先出，时间片机制时间片完，自动降级时间片完，自动降级上级队列未空，下级队列不能调度上级队列未空，下级队列不能调度抢占条件：下级队列进程运行时，上级队列有新进程进入，发生抢占

2、抢占条件：下级队列进程运行时，上级队列有新进程进入，发生抢占抢占处理：被抢进程不降级，排到队列末尾，等待剩余时间的完成抢占处理：被抢进程不降级，排到队列末尾，等待剩余时间的完成 实实 时时 调调 度度 实时调度实时调度 实现实时调度的基本条件实现实时调度的基本条件 2.系统处理能力强系统处理能力强 在在实实时时系系统统中中，通通常常都都有有着着多多个个实实时时任任务务。若若处处理理机机的的处处理理能能力力不不够够强强，则则有有可可能能因因处处理理机机忙忙不不过过来来而而使使某某些些实实时时任任务务不不能能得得到到及及时时处处理理，从从而而导导致致发发生生难难以以预预料料的的后后果果。假假定定系

3、系统统中中有有m个个周周期期性性的的硬硬实实时时任任务务，它它们们的的处处理理时时间间可可表表示示为为Ci，周周期期时时间间表表示示为为Pi，则则在在单单处处理理机机情情况况下下，必必须须满满足足下下面面的限制条件：的限制条件：假如系统中有假如系统中有6个硬实时任务，它们个硬实时任务，它们的周期时间都是的周期时间都是 50 ms，而每次的，而每次的处理时间为处理时间为 10 ms，则不难算出，则不难算出，此时是不能满足上式的，因而系统此时是不能满足上式的，因而系统是不可调度的。是不可调度的。解决的方法是提高系统的处理能力，其途径有二：解决的方法是提高系统的处理能力，其途径有二：其其一一仍仍是是

4、采采用用单单处处理理机机系系统统，但但须须增增强强其其处处理理能能力力，以以显显著地减少对每一个任务的处理时间；著地减少对每一个任务的处理时间；其其二二是是采采用用多多处处理理机机系系统统。假假定定系系统统中中的的处处理理机机数数为为N，则则应将上述的限制条件改为：应将上述的限制条件改为：3.采用抢占式调度机制采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度

5、时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务。4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：(1)对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2)快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。实时

6、调度算法的分类实时调度算法的分类 1.非抢占式调度算法非抢占式调度算法(1)非抢占式轮转调度算法。非抢占式轮转调度算法。(2)非抢占式优先调度算法。非抢占式优先调度算法。2.抢占式调度算法抢占式调度算法(1)基于时钟中断的抢占式优先权调度算法。(2)立即抢占(Immediate Preemption)的优先权调度算法。常用的几种实时调度算法常用的几种实时调度算法 1.最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 EDF算法用于非抢占调度方式 2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 该算法

7、是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。一一个个任任务务在在200ms时时必必须须完完成成，它它本本身身所所需需的的运运行行时时间间有有100ms，因因此此，调调度度程程序必须在序必须在100 ms之前调度执行，该任务的紧急程度之前调度执行，该任务的紧急程度(松弛程度松弛程度)为为100 ms。任务在任务在400 ms时必须完成，它本身需要运行时必须完成，它本身需要运行 150 ms，则其松弛程度为，则其松弛程度为 250 ms。2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算

8、法 算法要求算法要求1、系统中有一个按松弛度排序的实时任务就绪队列，、系统中有一个按松弛度排序的实时任务就绪队列，2、松弛度最低的任务排在队列最前面、松弛度最低的任务排在队列最前面3、调度程序总是选择就绪队列中的队首任务执行。、调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。该算法主要用于可抢占调度方式中。周期内任务只执行一次周期内任务只执行一次松弛度为松弛度为0时发生抢占时发生抢占 该假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。2.2.最低松弛度

9、优先即最低松弛度优先即最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法算法算法 周期性实时任务周期性实时任务周期性实时任务周期性实时任务A A、B B，A A要求每要求每要求每要求每20ms20ms执行一次，执行时执行一次，执行时执行一次，执行时执行一次，执行时间间间间10ms10ms；B B要求每要求每要求每要求每50ms50ms执行一次，执行时间执行一次，执行时间执行一次，执行时间执行一次，执行时间25ms25ms 在刚开始时在刚开始时在刚开始时在刚开始时(t1=0)(t1=0)，A1A1必须在必须在必须在

10、必须在20ms20ms时完成，而它本身运时完成，而它本身运时完成，而它本身运时完成，而它本身运行又需行又需行又需行又需 10 ms10 ms，可算出，可算出，可算出，可算出A1A1的松弛度为的松弛度为的松弛度为的松弛度为10ms10ms；B1B1必须在必须在必须在必须在50ms50ms时完成，时完成，时完成，时完成，而它本身运行就需而它本身运行就需而它本身运行就需而它本身运行就需25 ms25 ms，可算出，可算出，可算出，可算出B1B1的松弛度为的松弛度为的松弛度为的松弛度为25 25 msms，故调度程序应先调度，故调度程序应先调度，故调度程序应先调度，故调度程序应先调度A1A1执行。执行

11、。执行。执行。在在在在t2=10 mst2=10 ms时，时，时，时，A2A2的松弛度可按下式算出：的松弛度可按下式算出：的松弛度可按下式算出：的松弛度可按下式算出：A2A2的松弛度的松弛度的松弛度的松弛度=必须完成时间必须完成时间必须完成时间必须完成时间-其本身的运行时间其本身的运行时间其本身的运行时间其本身的运行时间-当前时间当前时间当前时间当前时间 =40 ms-10 ms-10 ms=20 ms=40 ms-10 ms-10 ms=20 ms 类似地，可算出类似地，可算出类似地，可算出类似地，可算出B1B1的松弛度为的松弛度为的松弛度为的松弛度为15ms15ms故调度程序应选择故调度程

12、序应选择故调度程序应选择故调度程序应选择B1B1运行。运行。运行。运行。在在在在t3=30 mst3=30 ms时，时，时，时，A2A2的松弛度为（的松弛度为（的松弛度为（的松弛度为（40-10-30)=0ms40-10-30)=0ms，而，而，而，而B1B1的松的松的松的松弛度为弛度为弛度为弛度为15ms15ms。故抢占。故抢占。故抢占。故抢占B1B1处理机而调度处理机而调度处理机而调度处理机而调度A2A2运行运行运行运行依次计算下去依次计算下去依次计算下去依次计算下去 在在刚刚开开始始时时(t1=0)，A1必必须须在在20ms时时完完成成，而而它它本本身身运运行行又又需需 10 ms，可可

13、算算出出A1的的松松弛弛度度为为10ms；B1必必须须在在50ms时时完完成成，而而它它本本身身运运行行就就需需25 ms，可可算算出出B1的的松松弛弛度度为为25 ms，故调度程序应先调度故调度程序应先调度A1执行。执行。t2=10 ms，A1完成，完成，A2无需计算无需计算t2=20 ms，A2的松弛度的松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间 =40 ms-10 ms-20 ms=10 ms B1=50 25 20=5ms，调度调度B1调度程序选择调度程序选择B1运行。运行。t3=30 ms时，时，A2抢占抢占B1。t4=40 ms时，重新调度时，重新调度B1。t5=45 ms时，调度时，调度A3执行。执行。t6=55ms时，调度时，调度B2执行执行t7=70 ms时，时，A4抢占抢占B2利用LLF算法进行调度的情况