论文部分内容阅读
现今,实时嵌入式系统在许多领域都得到了广泛应用,包括但不限于,通信系统、消费电子、车辆电子、医疗图像和航天航空等等。显而易见,这些领域最为关键的核心问题在于任务的调度,亦即计算资源的管理,因此实时调度一直是人们研究的重点。随着信息科学和电子技术的高速发展,面向应用的嵌入式专用多处理机系统正越来越普及,人们拥有了质量和数量都远超从前的计算资源。然而,传统的单处理机实时任务调度已开始逐渐不能适应当前多处理机强劲的发展趋势。所以,大力研究多处理机的调度技术以便更加高效地利用计算资源在理论上和实际上都具有重要意义。
本文的研究目的在于,根据各种实时应用的复杂性和多样性建立更加通用的多处理机实时任务模型并且提供一种新的调度算法,通过批处理和并行的方式尽量提高实时任务的调度成功率。本文的主要工作体现在如下几个方面。
(1)研究实时系统的主要特点,给出调度算法常见的分类以及相关的性能度量和最优准则。
(2)全面总结近半个世纪以来单处理机实时任务调度的研究。文章渐进地分析了常用的任务模型,并详细讨论四种经典的调度算法,指出各自的适用范围、优缺点以及计算复杂度。多处理机的实时任务调度问题哪怕是使用简化的任务模型在绝大部分情况下都是NP完全的。本文从静态调度和动态调度两个方面仔细研究多处理机实时任务的多种调度策略。
(3)既然不存在最优的动态调度算法来为多处理机安排事先并不知晓相关参数的实时任务,本文提出一种时间复杂度是线性的新型多处理机实时任务启发式调度算法,它能利用任务的并行性为动态的实时系统提供较优的解。
(4)开发用于仿真和实验的软件框架,它能够产生大量存在可行调度的任务集合。使用大量的任务集合测试多种多处理机实时任务调度算法的性能,分析数种主要参数对调度成功率的影响。实验表明新的调度算法具有更高的调度成功率。