论文部分内容阅读
异构多核处理器是当前多核发展的主流方向,其实时调度问题成为计算机领域研究的热门课题。本文基于异构多核处理器的调度优化模型来改进调度算法进行实时任务调度研究,其实质是利用异构多核处理器的性能优势来解决异构处理器间的任务合理分配难题,进而提升微内核操作系统的系统性能。本文针对异构多核处理器微内核操作系统实时任务调度问题所做的主要工作有: (1)本文先根据异构多核系统模型,进行任务模型、多核处理器模型、调度模型、约束条件模型的建模设计,为算法的优化实现提供模型目标环境。为了更好解决异构多核处理器面对具有复杂依赖关系的实时任务难以调度的问题,在有向无环任务图模型(DirectedAcyclicGraph,DAG)的基础上,通过任务复制与合并操作,设计了一种利用并行处理的任务树模型(ParallelTaskTree,PTT),其通过分析任务间依赖关系来定义优先级别,确定任务实时响应的需求等级,将任务调度到相应的核执行。该模型主要解决异构多核间的跨核任务通信开销较大的问题,将复杂依赖关系的任务分配转化为方便并行执行的任务树模型。 (2)针对异构多核系统模型选用智能算法中拥有天然并行优势的蚁群算法(antcolonyoptimization,ACO),解决实时调度中的NP难问题,算法设计的步骤包括任务间的选择操作、任务和处理器映射关系、信息量的更新操作、交叉变异的考虑、公式的设计优化等等。其中为提高蚁群算法的搜索效率,发挥异构多核处理器的优势,需要进行适用于异构多核环境下的蚁群算法优化研究。本文中的蚁群算法利用混沌映射来进行混沌扰动,从而使基本蚁群算法跳出局部最优,设计出了改进后的混沌蚁群调度算法(chaoticantswarm,CAS),改进后的算法能充分发挥其异构特性和并行能力。 最后本文对DAG调度模型和PTT调度模型进行多线程下的比较和分析;对改进后的调度算法进行了准确性的验证,对平均运行时间、平均值比较分析;并结合所需调度处理的任务数量,给出了与其他算法在中细粒度规模下的处理结果比较。实验结果证明PTT模型和改进后的CAS算法适合异构多核环境下微内核操作系统的实时任务调度,能够得到更好的调度效果。