基于偶发性任务模型的混合关键性实时调度算法研究

摘要

近年来随着信息技术产业的飞速发展，嵌入式系统集成的功能日益复杂，应用也愈发广泛，但同时受到系统体积、成本、能耗、利用率等约束。为了克服这些问题，在现代嵌入式系统设计中采用在一个共享处理器平台中集合多种不同关键性级别功能应用的方案成为流行趋势。这种混合关键性系统为现代嵌入式实时系统的设计提供了有效的方案，但其中实时调度算法的设计，以该系统正确性的验证都颇具挑战性，并成为当今学术界和工业界研究的热点和难点。
　　在已有的混合关键性调度策略中，适用于有限作业系统的OCBP算法具有很多优秀的性质并被学术界广泛关注。LB算法将OCBP扩展到更为通用的混合关键性偶发性任务模型中，但其伪多项式级别的时间复杂度对嵌入式系统而言难以接受。后来的PLRS算是利用在离线计算的优先级计划表和运行时抽象数据结构将系统的时间复杂度降为平方级别，但对于嵌入式系统来说依然过高。
　　针对上述不足，本文提出新调度算法LPA，该算法核心思想:当系统运行中发生抢占时，LPA调度算法不是立刻对各个任务的所有作业进行优先级调整，相反，仅仅让各个任务记录抢占发生时被抢占任务的优先级值，在后续作业释放并需要设定优先级时才通过相关判断来决定是否需要对当前任务进行优先级调整。这就将集中而繁重的优先级调整工作分散到各个作业释放时刻进行，不但降低了单次优先级调整的复杂度，也避免了大量冗余的计算量进而显著提升了运行时调度的性能。
　　另外，LB、PLRS算法在将无限作业数转化为有限作业数时采用了忙碌周期概念，但是在计算其上界时采用的算法比较悲观，求得结果过于松弛，导致系统空间开销过大。本文提出一种改进的忙碌周期上界计算方法，利用该方法可以得到一个更加精确的忙碌周期上界，在相同的任务周期情况下每个忙碌周期内作业数减少，从而使得系统空间复杂度得到有效降低，最后通过实验还发现，通过改进的忙碌周期上界还能提高系统的随机任务集可调度比率。

目录

声明

摘要

第1章 绪论

1．1 课题背景

1．2 研究目标和意义

1．3 研究现状

1．4 论文的组织结构

第2章 相关工作

2．1 实时系统相关理论

2．1．1 传统实时系统

2．1．2 任务模型

2．1．3 混合关键性

2．2 混合关键性调度算法分析

2．2．1 OCBP

2．2．2 LB

2．2．3 PLRS

2．3 本章小结

第3章 LPA算法设计

3．1 混合关键性系统模型

3．1．1 任务与作业

3．1．2 系统运行时行为

3．1．3 任务可调度性

3．2 LPA算法设计

3．2．1 离线优先级分配

3．2．2 运行时调度

3．3 LPA算法应用实例

3．4 本章小结

第4章 LPA算法分析

4．1 LPA算法可调度性证明

4．1．1 相关定义及引理

4．1．2 可调度性证明

4．2 LPA算法时间复杂度分析

4．3 本章小结

第5章 忙碌周期上界计算方法

5．1 忙碌周期

5．1．1 负载定义

5．1．2 忙碌周期计算

5．2 改进的忙碌周期

5．2．1 改进的忙碌周期计算

5．2．2 忙碌周期实例

5．3 本章小结

第6章 实验设计及结果分析

6．1 随机任务集生成

6．2 结果分析

6．2．1 时间效率

6．2．2 空间效率

6．2．3 可接受率

6．3 本章小结

第7章 结论与展望

7．1 结论

7．2 未来工作与展望

参考文献

致谢

科研项目和论文发表情况