合肥网站搭建,著名的网站建设公司,宁夏建设银行发行寄念币网站,互联网营销培训课程动态优先级模式与静态优先级模式类似#xff0c;但动态优先级模式会随着任务运行时条件的改变自动调整任务优先级。调整任务优先级的策略有很多种#xff0c;最常见的是“最早截止期优先”(Earliest Deadline First)#xff0c;即优先级最高的任务是离截止时间最近的任务。动…动态优先级模式与静态优先级模式类似但动态优先级模式会随着任务运行时条件的改变自动调整任务优先级。调整任务优先级的策略有很多种最常见的是“最早截止期优先”(Earliest Deadline First)即优先级最高的任务是离截止时间最近的任务。动态优先级模式明确强调了任务的紧迫性高于其关键性。
5.10.1 摘要
正如上一节提到的可调度性最重要的两个概念是紧急性和关键性但操作系统通常只提供一个单一数值优先级来管理两者。静态优先级模式中优先级是在设计时确定的通常反映了紧急性和关键性的组合。动态优先级模式则根据任务的紧迫性在运行时动态设定任务优先级。
动态优先级模式将每个任务的优先级设定为一个与剩余时间相关的函数越接近截止时间优先级升高。这种调度策略通常被称为最早截止期优先 (Earliest Deadline First简称 EDF)。该策略已被证明是可验证的最佳策略即如果任务集合可以用任何方法调度那么它也一定可以用 EDF 方法调度。然而动态优先级模式并不稳定这意味着在设计时无法预测过载情况下哪些任务会失败。
动态优先级模式最适用于关键性大致相等的任务集合因为在这种情况下紧迫性成为首要考虑因素。它也非常适合高度复杂的情况例如无法预测同时运行的任务集合。在如此复杂的情况下为任务构建最佳静态优先级往往困难甚至不可能。
动态优先级模式通过协作的系统对象根据任务的紧迫性动态调整优先级从而实现高效的实时任务调度。
优点
对紧迫性要求高的任务更有效。适用于任务集关键性大致相等的情况。
缺点
不稳定无法预测过载情况下哪些任务会失败。实现比静态优先级模式复杂。 5.10.2 问题
在小型实时系统中任务的排列组合是已知的任务本身是稳定的它们的截止日期从任务调用到任务调用是一致的执行时间大致相同。但在复杂系统中如完全对称的多任务系统任务分配到处理器直到执行时才知道这使得分析变得困难或不可能。
对于小型实时系统来说待运行任务的排列组合是已知的任务本身也是稳定的它们的截止时间从上一个任务调用到下一个任务调用是一致的执行时间大致相同。这极大地简化了分析允许以绝对值精确计算系统的可调度性。
然而在复杂系统中例如完全对称的多任务系统任务被分配到哪一个处理器需要等到执行时才知道这种分析变得困难或不可能。此外即使能够进行分析这也是一项复杂的工作添加单个任务就需要完全重新进行分析。 5.10.3 模式结构
如图 5-19 所示动态优先级模式的结构与静态优先级模式非常相似但抽象线程类中额外包含了一个名为截止时间(Deadline) 的属性。该属性通常是指从任务被调用到截截止时间点之间的时间段。虽然指定为持续时间但调度器会根据此信息计算出任务的绝对截止时间 (存放在任务控制块中)并根据“最接近截止时间最优先”的策略安排任务执行。当一个新任务准备就绪时它会根据其下一个截止时间插入就绪队列。 5.10.4 协作角色 抽象线程 (Abstract Thread) 抽象类不可直接实例化。与调度器关联保证接口一致性。拥有一个“截止时间”属性表示任务执行完成的期限。 阻塞队列 (Blocked Queue) 一个按优先级排序的任务控制块引用队列。任务被阻塞时其引用会放入该队列。任务解除阻塞时其引用会从该队列移除并放入就绪队列。 具体线程 (Concrete Thread) 可实例化的抽象线程子类。用于包含执行系统实际工作的“语义对象”。提供将这些语义对象纳入并发架构的直接方式。 互斥锁 (Mutex) 一次只允许一个调用者通过的互斥信号量对象。共享资源的服务调用会锁定它完成后解锁。尝试调用已锁定的服务则会被阻塞直到互斥锁解锁。 就绪队列 (Ready Queue) 存放当前准备运行的任务控制块引用的队列。就绪队列中最高优先级的任务比当前运行任务优先级高时将其移出并执行。高优先级任务加入就绪队列时会抢占当前运行任务使其重新排入就绪队列。 调度器 (Scheduler) 与静态优先级模式类似但动态计算任务优先级。根据任务截止时间与当前时间的距离计算优先级离截止日期越近优先级越高。 共享资源 (Shared Resource) 由一个或多个线程共享的对象。必须是可重入的或通过互斥锁保护以免并发访问导致错误。 栈 (Stack) 每个抽象线程都有一个用于返回地址和传递参数的栈。这是调度基础设施的重要组成部分。 任务控制块 (Task Control BlockTCB) 包含线程的调度信息包括优先级、默认启动地址和当前入口地址等。保存任务下一个截止时间的属性“绝对截止日期”。 5.10.5 结果
动态优先级调度算法虽然是最优的但并不稳定。所谓“最优”是指如果任务集可以用任何算法调度成功那么它也一定可以用动态优先级算法调度成功。所谓“不稳定”是指我们无法预先预测在过载情况下哪些任务会失败。
在无法进行静态分析的复杂情况下动态优先级模式可以很好地扩展到大量线程。静态优先级模式适用于相对静态的场景在这种情况下我们可以预知并为最坏的情况做好规划。但在高度复杂的系统中尤其是完全对称的多任务架构情况可能并非如此。 5.10.6 实施策略 实施这种模式比静态优先级模式稍微复杂一些。在静态优先级模式中具体线程必须包含一个常量值的优先级。而在动态优先级模式中具体线程必须包含相对于任务开始的截止日期。 实现难度略高于静态优先级模式
动态优先级模式的实现复杂度仅略高于静态优先级模式。两者的主要区别在于
静态优先级模式 具体线程Concrete Thread内存储固定的优先级值调度器Scheduler用它来安排任务控制块TCB的优先级队列。动态优先级模式 具体线程存储的是任务相对于开始时间的截止时间Deadline 属性。当具体线程准备就绪时调度器会计算出下一个绝对截止时间AbsoluteDeadline并将该值存储在 TCB 中。调度器正是根据这个属性对优先级队列进行排序。
关键实现步骤
具体线程中设置 Deadline 属性 表示任务相对于开始时间的截止时间。调度器计算 AbsoluteDeadline 当具体线程准备就绪时调度器从 Deadline 属性计算出下一个绝对截止时间。存储 AbsoluteDeadline 于 TCB 计算出的绝对截止时间存储在任务控制块中。基于 AbsoluteDeadline 排序 调度器使用 AbsoluteDeadline 属性作为优先级队列的排序依据。 5.10.7 相关模式
虽然存在动态优先级模式但并不像静态优先级模式那样常见。与静态优先级模式一样动态优先级模式通常会与其他多种模式结合使用例如资源管理模式。
就像静态调度模式一样当资源需要共享时调度就变得格外棘手。优先级继承、最高锁持有者和优先级上限协议等资源共享模式专门解决无界优先级反转可能引发的问题。 5.10.8 示例模型
图片 5-20 展示了与上一节静态优先级模式相同的模型不同之处在于图中标注了每个线程的截止时间属性值这些值会产生等效但未必完全相同的任务调度结果。
例如如果数据采集线程 (DataAcqThread) 准备就绪运行在静态优先级模式下它会抢占其他任何线程而不考虑任务距离截止时间有多近。然而在动态优先级模式下数据采集线程只有在它的下一个截止时间确实比其他线程的截止时间更近时才会抢占它们。在这两种情况下任务都是可调度完成的。
在静态优先级模式下当系统过载时我们可以预测哪个线程会延迟优先级最低的线程过滤线程。然而如果使用动态优先级模式则无法预测哪个线程会在过载情况下延迟。
