操作系统课件 第3章(必威体育精装版最完整的课件).ppt

3.4 实时调度 3.4.1 实现实时调度的基本条件 3.采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。 4. 具有快速切换机制 该机制应具有如下两方面的能力： (1) 对外部中断的快速响应能力。 (2) 快速的任务分派能力。 3.4 实时调度 3.4.2 实时调度算法的分类 (1)按实时任务性质分 硬实时任务调度算法和软实时任务调度算法 (2)按调度方式分 非抢占调度算法和抢占调度算法 (3)按调度时间 静态调度算法和动态调度算法 3.4 实时调度 3.4.2 实时调度算法的分类 1.非抢占调度算法 (1) 非抢占式轮转调度算法。 由一台计算机控制若干个相同(或类似)的对象，为每个被控对象建立一个实时任务，并将它们排成一个轮转队列。 (2) 非抢占式优先调度算法。 赋予要求较为严格的实时任务较高的优先级，在Ready队列中作为队首，等待当前任务自我终止或运行完成后被调度执行。 3.4 实时调度 3.4.2 实时调度算法的分类 2.抢占调度算法 (1)基于时钟中断的抢占式优先权调度算法。 优先级高于当前任务的实时任务到达后，并不立即抢占当前任务的处理机，而是等到时钟中断到来时才“抢占”。 (2)立即抢占的优先权调度算法。 只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。 图 3-6 实时进程调度 3.4 实时调度 3.4.3 常用的几种实时调度算法 1. 最早截止时间优先即EDF(Earliest Deadline First)算法 根据开始截止时间的早晚来确定优先级。 2. 最低松弛度优先即LLF(Least Laxity First)算法 根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高(松弛度越低)，为该任务所赋予的优先级就愈高， 以使之优先执行。 3.4 实时调度 3.4.3 常用的几种实时调度算法 2. 最低松弛度优先即LLF(Least Laxity First)算法 进程的松弛度=|t-最迟开始时间| 其中，t为当前时刻； 最迟开始时间为(完成截止时间-处理时间) 说明： (1)松弛度越低，当前时间距最迟开始时间就越近 (2)松弛度越低，任务就越紧急，优先级越高 2. 最低松弛度优先即LLF(Least Laxity First)算法 例：在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50 ms执行一次，执行时间为25ms。 3.4 实时调度 3.4.3 常用的几种实时调度算法 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 20 40 60 80 100 120 140 160 B 1 B 2 B 3 t 0 周期性任务A和B的完成截止时间 2. 最低松弛度优先即LLF(Least Laxity First)算法 解: (1)找已到达但未完成的任务(已完成的划去) (2)找上述任务中松弛度最低(当前时间距最迟开始时 间最近)的执行 (3) 保证每个周期任务都能执行完成。 3.4 实时调度 3.4.3 常用的几种实时调度算法 2. 最低松弛度优先即LLF(Least Laxity First)算法 3.4 实时调度 3.4.3 常用的几种实时调度算法 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 20 40 60 80 100 120 140 B 1 B 3 t 0 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 B 1 B 2 B 3 A1(10) 10 40 30 45 90 130 80 t 0 70 B1(20) B 2 30 A2(10) B1(5) 55 A3(10) B2(15) A4(10) B2(10) 100 A5(10) 110 A6(10) 155 B3(20) 140 A7(10) 145 B3(5) A8(10) 解: A、B每次到达的时间如下，并计算出它们的最迟开始时间。 150 10 50 70 25 75 90 110 130 125 到达时间 最晚开始时间 练习： 在一个实时系统中，有三个周期性实时任务A、B和C。 任务A要求每20ms执行一次，执行时间为10ms； 任务B要求每50ms执行一次，执行时间为10ms； 任务C要求每50ms执行一次，执行时间为15ms。 请按最低松弛度优先算法画出0~100ms的任务调度顺序。