嵌入式实时系统的任务调度与资源共享模型及算法研究

论文题目: 嵌入式实时系统的任务调度与资源共享模型及算法研究

论文类型: 博士论文

论文专业: 通信与信息系统

作者: 王保进

导师: 王志刚,李明树

关键词: 抢占阈值调度算法,协议,协议,忙周期,伪资源,调度模型,算法,构件模型,调度

文献来源: 中国人民解放军信息工程大学

发表年度: 2005

论文摘要: 嵌入式实时系统要求任务能按时、正确地完成功能操作,这些任务还可能会互斥地访问共享资源。另外,系统的处理能力和内存容量往往是有限的。这需要将调度算法与资源访问控制协议合理地组合到一起使用,从而能恰当地排列任务执行顺序,在保证系统可调度性的同时使用更少的内存资源。实际的嵌入式实时系统提供的优先级是有限的,需要一种适当的优先级映射算法。当前采用构件技术的嵌入式实时系统在开发过程中注重从结构角度利用构件技术的优点,而往往忽视从运行角度充分利用成熟的实时调度理论。 针对上述需求,本文研究了静态优先级实时调度算法和资源访问控制协议,分析了现有调度算法和资源协议结合使用时存在的不足,以及现有优先级映射算法的不足。试图找出一种合理的组合调度算法和资源协议的方案,一种能保证系统实时性的优先级映射算法,一种将构件映射成任务的方式和为底层构件化嵌入式实时操作系统选择适当的调度模型。 首先,本文分析出抢占阈值调度算法与SRP资源访问控制协议更适合嵌入式实时系统,两者具有共同的特点:任务一旦执行就不会被阻塞。据此,用level-i忙周期分析方法重新推导了SRP协议下判定任务可调度性的公式,并基于新公式推导出SRP协议的特性,实现了分配任务优先级的算法。经过进一步分析,推导出抢占阈值调度是应用SRP协议的静态优先级实时系统的一个特例,表明将SRP协议和抢占阈值调度算法相结合是合理的。利用伪资源的概念在SRP协议中实现了抢占阈值调度,提出了SRP-PT调度模型。通过限制使用实资源的任务再次使用伪资源,防止了阈值过限问题。证明了SRP-PT调度模型比现有调度算法和资源协议的结合方式性能更好。通过仿真实验进行性能对比表明:与单独使用SRP协议相比,SRP-PT调度模型能提高任务集合的可调度性。 其次,通过深入分析抢占阈值调度模型生成的非抢占组的特性,证明了组内任务优先级是连续递增的,组间任务优先级值不会相交,并据此提出了阈值段间映射法(TSM)和事件驱动线程框架。能充分利用抢占阈值调度模型的优点,针对没有共享资源的实时系统,在提高任务集合可调度性的同时,使用较少的系统优先级。通过仿真实验与现有优先级映射算法进行性能对比,证明了上述结论。 最后,本文提出一种适合于嵌入式实时系统的软件构件模型以及将构件映射成任务的方式,同时提出一种设计方法。通过仿真实验比较了4种可用调度算法的性能,通过分析说明了抢占阈值调度算法和SRP-PT调度模型最适于构件化嵌入式实时系统。

论文目录:

摘要

Abstract

第一章 绪论

1.1 嵌入式实时系统简介

1.2 嵌入式实时系统的一般需求和特点

1.2.1 最佳的实时性

1.2.2 合适的资源访问控制协议

1.2.3 有限的内存资源

1.2.4 有限的系统优先级

1.3 现有解决方法和存在的不足

1.3.1 实时调度算法

1.3.2 资源访问控制协议

1.3.3 抢占阈值调度算法与 PCP协议结合使用时出现的问题

1.3.4 现有优先级映射算法存在的不足

1.4 构件化嵌入式实时系统的应用现状

1.5 本文主要工作和贡献

1.6 论文结构安排

第二章 算法与协议的研究和分析

2.1 基本概念和定义

2.2 静态优先级实时调度算法

2.2.1 抢占式调度算法-RM算法

2.2.2 非抢占式调度算法

2.2.3 抢占阈值调度算法

2.3 资源访问控制协议

2.3.1 优先级继承协议(PIP)

2.3.2 优先级冲顶协议(PCP)

2.3.3 SRP协议

2.4 level-i忙周期分析方法

2.4.1 在抢占式调度中应用level-i忙周期分析方法

2.4.2 在非抢占式调度中应用level-i忙周期分析方法

2.4.3 在抢占阈值调度中应用level-i忙周期分析方法

2.5 阈值过限问题的分析

2.5.1 PC-PCP协议和 PTC-PCP协议

2.5.2 产生阈值过限问题的原因

2.6 IPA和 DPA优先级映射算法

2.7 现有构件化嵌入式操作系统采用的调度算法

2.8 小结

第三章 SRP协议的新判定公式

3.1 新判定公式的推导

3.1.1 SRP协议的关键时刻

3.1.2 新判定公式的推导过程和结果

3.2 SRP协议的特性

3.3 SRP协议下的优先级分配算法

3.3.1 优先级分配规则

3.3.2 优先级分配算法

3.4 小结

第四章 抢占阈值调度算法与 SRP协议的组合-SRP-PT调度模型

4.1 抢占阈值调度算法与 SRP协议的关系

4.2 SRP-PT调度模型

4.3 SRP-PT调度模型的特性

4.4 SRP-PT调度模型下的优先级分配算法

4.5 SRP-PT调度模型与 PC-PCP协议的比较

4.5.1 阻塞时间的比较

4.5.2 优先级倒置的比较

4.5.3 现场切换次数的比较

4.6 SRP-PT调度模型与 SRP协议的比较

4.7 小结

第五章 抢占阈值调度下的优先级映射-TSM算法

5.1 优先级映射问题

5.2 IPA和 DPA优先级映射算法的特性

5.3 抢占阈值调度下非抢占组的特性

5.3.1 分割非抢占组的方法

5.3.2 分割方法的特点

5.4 TSM优先级映射算法

5.5 事件驱动线程框架

5.6 优先级映射算法的分析

5.6.1 TSM算法使用过程

5.6.2 事件驱动线程的执行过程

5.6.3 IPA和 DPA算法的映射结果

5.7 优先级映射算法的比较

5.7.1 计算复杂度的比较

5.7.2 性能比较

5.8 小结

第六章 调度模型在构件化嵌入式实时操作系统中的应用

6.1 构件模型和映射成任务的方式

6.1.1 构件模型和映射方式

6.1.2 构件化嵌入式实时软件开发过程

6.2 适合构件化嵌入式实时操作系统的调度模型

6.2.1 针对独立任务集合几种调度算法的性能比较和结论

6.2.2 针对有共享资源的任务集合使用 SRP-PT调度模型

6.3 小结

第七章 结束语

参考文献

致谢

作者在攻读博士学位期间参加的科研任务及完成情况

作者在攻读博士学位期间的论文和专利情况

发布时间: 2006-02-20

参考文献

• [1].嵌入式实时系统中关键技术的研究[D]. 毛佳.吉林大学2004
• [2].嵌入式内存管理垃圾搜集器实时算法研究[D]. 张宁.电子科技大学2009

标签：抢占阈值调度算法论文;  协议论文;  忙周期论文;  伪资源论文;  调度模型论文;  算法论文;  构件模型论文;  调度论文;