Lifang 20111/14操作系统5、实时调度、实时调度1 1） 实时系统实时系统( (real-time system) real-time system) P11P11实时：表示实时：表示“及时及时”，实时系统是系统能及时响应外部事件请求，在规定时间内完实时系统是系统能及时响应外部事件请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。成对该事件的处理，并控制所有实时任务协调一致地运行。用于工业过程、军事、金融等实时控制、实时信息处理领域用于工业过程、军事、金融等实时控制、实时信息处理领域Lifang 20112/14操作系统按任务执行时是否呈现周期性来划分：按任务执行时是否呈现周期性来划分：周期性实时任务：周期性实时任务：每隔一段固定的时间发生每隔一段固定的时间发生非周期性实时任务：非周期性实时任务：在不可预测的时间发生。在不可预测的时间发生。截止时间截止时间( (deadline)deadline)：开始截止时间（最晚开始时间）和完成截止时间（最晚完成时间）开始截止时间（最晚开始时间）和完成截止时间（最晚完成时间）根据对截止时间的要求来划分：根据对截止时间的要求来划分：硬实时任务：存在必须满足的时间限制。硬实时任务：存在必须满足的时间限制。软实时任务软实时任务: :可以容忍偶尔超过时间限制。可以容忍偶尔超过时间限制。实时任务的类型：实时任务的类型：Lifang 20113/14操作系统 2 2）实现实时调度的基本条件）实现实时调度的基本条件 提供必要的信息提供必要的信息( (就绪时间、截止时间、处就绪时间、截止时间、处理时间、资源要求、资源优先级理时间、资源要求、资源优先级) )系统处理能力要足够强系统处理能力要足够强: :单处理机情况下：设有单处理机情况下：设有m个周期性事件，事件个周期性事件，事件i的的周期为周期为Pi，其中每个事件需要其中每个事件需要Ci秒的秒的CPU时间来时间来处理，可调度的的实时系统必须满足：处理，可调度的的实时系统必须满足： C1/P1 + C2/P2 + + Cm/Pm 1采用抢占式调度机制采用抢占式调度机制具有快速切换机制具有快速切换机制Lifang 20114/14操作系统练习：练习：一个实时系统中有一个实时系统中有4 4个周期性事件，周期分别为个周期性事件，周期分别为5050、100100、300300和和250ms250ms。若假设其处理分别需要。若假设其处理分别需要3535、2020、1010和和x x毫秒，则该系统可毫秒，则该系统可调度允许的调度允许的x x值最大为多少？值最大为多少？实时任务可调度应满足如下条件：实时任务可调度应满足如下条件：35/50+20/100+10/300+x/250135/50+20/100+10/300+x/2501x250(1-28/30)=16.67x250(1-28/30)=16.67Lifang 20115/14操作系统3 3）实时调度算法的分类）实时调度算法的分类 1)1)非抢占式调度算法非抢占式调度算法 : :非抢占式轮转调度算法非抢占式轮转调度算法( (实时要求不太严格，实时要求不太严格，s)s)非抢占式优先调度算法非抢占式优先调度算法( (要求比较严格要求比较严格, ,数百数百ms)ms)2)2)抢占式调度算法抢占式调度算法: :基于时钟中断的抢占优先调度算法基于时钟中断的抢占优先调度算法( (要求比较严格要求比较严格, ,数数10ms)10ms)立即抢占优先权调度算法立即抢占优先权调度算法( (紧迫任务紧迫任务, ,几几msms甚至百微秒甚至百微秒) )Lifang 20116/14操作系统图图 3-8 3-8 实时进程调度实时进程调度 Lifang 20117/14操作系统4 4）常用的几种实时调度算法）常用的几种实时调度算法 I.最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 P100图图 3-9 EDF3-9 EDF算法用于非抢占调度方式算法用于非抢占调度方式 1 1）非抢占式调度用于非周期实时任务：最早开始截止时间优先）非抢占式调度用于非周期实时任务：最早开始截止时间优先Lifang 20118/14操作系统Fig. 3-10 Fig. 3-10 2 2）抢占式调度用于周期实时任务：最早完成截止时间优先）抢占式调度用于周期实时任务：最早完成截止时间优先Lifang 20119/14操作系统II. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 P101 该该算算法法是是根根据据任任务务紧紧急急( (或或松松弛弛) )的的程程度度，来来确确定定任任务务的优先级，即的优先级，即选择松弛度最少的进程执行选择松弛度最少的进程执行该算法。该算法。 主要用于可抢占调度方式中。主要用于可抢占调度方式中。松弛度：即各个进程的富裕时间（裕度松弛度：即各个进程的富裕时间（裕度）松弛度松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间Lifang 201110/14操作系统图图 3-12 3-12 利用利用LLFLLF算法进行调度的情况算法进行调度的情况图图 3-11 A3-11 A和和B B任务每次必须完成的时间任务每次必须完成的时间假如在一个实时系统中，有两个周期性实时任务假如在一个实时系统中，有两个周期性实时任务A和和B，任务，任务A要求每要求每 20 ms执行一次，执行时间为执行一次，执行时间为 10 ms；任务；任务B只要求每只要求每50 ms执行一次，执行时间为执行一次，执行时间为 25 ms。 Lifang 201111/14操作系统实时调度问题-习题1对下面的对下面的对下面的对下面的5 5个非周期性实时任务，按最早开始截止时间优个非周期性实时任务，按最早开始截止时间优个非周期性实时任务，按最早开始截止时间优个非周期性实时任务，按最早开始截止时间优先调度算法如何进行先调度算法如何进行先调度算法如何进行先调度算法如何进行CPUCPU调度？调度？调度？调度？( (非抢占式非抢占式非抢占式非抢占式/ /抢占式抢占式抢占式抢占式) )进程进程进程进程到达时间到达时间到达时间到达时间执行时间执行时间执行时间执行时间开始截止时间开始截止时间开始截止时间开始截止时间A A10102020110110B B202020202020C C404020 20 5050D D505020209090E E6060202070700 0101020203030404050506060707080809090100100110110A AB BC CD DE EB BC CE ED DA A到达时间到达时间到达时间到达时间开始截止开始截止开始截止开始截止时间时间时间时间Lifang 201112/14操作系统实时调度问题-习题1对下面的对下面的对下面的对下面的5 5个非周期性实时任务，按最早开始截止时间优个非周期性实时任务，按最早开始截止时间优个非周期性实时任务，按最早开始截止时间优个非周期性实时任务，按最早开始截止时间优先调度算法如何进行先调度算法如何进行先调度算法如何进行先调度算法如何进行CPUCPU调度？调度？调度？调度？( (非抢占式非抢占式非抢占式非抢占式/ /抢占式抢占式抢占式抢占式) )进程进程进程进程到达时间到达时间到达时间到达时间执行时间执行时间执行时间执行时间开始截止时间开始截止时间开始截止时间开始截止时间A A10102020110110B B202020202020C C404020 20 5050D D505020209090E E6060202070700 0101020203030404050506060707080809090100100110110A AB BB BC CC CE EE ED DD DA AA AB BC CD DE EB BC CE ED DA A到达时间到达时间到达时间到达时间开始截止开始截止开始截止开始截止时间时间时间时间Lifang 201113/14操作系统 Lifang 201114/14操作系统实时调度问题-习题2若有若有若有若有3 3个周期性任务，各任务的周期和执行时间如下表所示，个周期性任务，各任务的周期和执行时间如下表所示，个周期性任务，各任务的周期和执行时间如下表所示，个周期性任务，各任务的周期和执行时间如下表所示，考虑应如何按最低松弛度优先算法对它们进行考虑应如何按最低松弛度优先算法对它们进行考虑应如何按最低松弛度优先算法对它们进行考虑应如何按最低松弛度优先算法对它们进行CPUCPU调度？调度？调度？调度？进程进程进程进程周期周期周期周期执行时间执行时间执行时间执行时间A A20201010B B50501010C C505015 15 0 0101020203030404050506060707080809090100100110110A1A1B1B1C1C1A2A2A3A3B2B2C2C2A4A4A5A5A6A6B3B3C3C3A1A1A2A2A3A3A4A4A5A5时间时间时间时间各进程到各进程到各进程到各进程到达时间达时间达时间达时间必须完成必须完成必须完成必须完成时间时间时间时间B1B1C1C1B2B2C2C2Lifang 201115/14操作系统