论文部分内容阅读
嵌入式系统已经越来越多地应用在各个领域中,随着硬件和软件技术的发展,操作系统在嵌入式领域发挥着越来越重要的作用。其中大多数嵌入式系统都是基于单处理器环境,而随着计算机技术的迅速发展,嵌入式系统也开始应用于多处理器环境。从单处理器到多处理器,从串行到并行。多处理器并行系统由于其高性能和可靠性,已成为新一代嵌入式系统发展的趋向。
在嵌入式多处理器系统中,任务调度问题的规模也越来越大,多线程的任务调度成为决定系统性能的关键,但是多处理器系统中任务调度的求解是一个NP完全问题。当系统中的处理器和任务数目较大时,用一般的穷举遍历方法是不现实的。在大多数的情况下,人们寻求的只是次优解。
本文首先研究多处理器并行环境下的各种任务调度计算模型和常用的各种任务调度算法,分析嵌入式系统和多处理器系统的结构特性。采用单芯片多处理器(CMPChipMultiProcessors)硬件架构和对称多处理(SMPSymmetricMultiProcessing)操作系统模式,应用集中式的调度器模型,提高处理器的总体计算能力。结合并行计算的思想,通过将任务进行先划分后组合的方式,减少任务调度中的开销。研究E.B.Fernandez提出的算法模型,改进原有的计算模型和调度模型,应用启发式算法求解最小运行时间。分析单处理器环境下基本的组合分配算法和流量算法,将图论里的深度搜索思想应用到简化任务图上。在流量算法中,应用最大流最小截集算法(MaxFlow/MinCut)求解任务调度问题,并在计算模型中融入叠加开销参数。在此基础上提出一种新的调度策略,即采用逆向有序拓扑序列,通过减少任务的通信开销使得任务的运行时间最小,以此提高任务调度的效率。
在并行程序设计环境下,通过OpenMP编程模拟实验证明,改进后的算法不仅提高了处理器的利用率和任务调度的成功率,而且最大程度地减少了任务的运行时间。