论文部分内容阅读
目前,多处理器系统已成为计算机领域中的研究热点,随着它的应用领域越来越广泛,其复杂性也在不断增加,所处理的任务也越来越复杂,在这样的环境下,对任务调度提出了更高的要求。
多处理器系统任务调度是NP完全问题,改进算法的效率并构建任务调度实现机制成为研究重点。大多数实时多处理器系统的动态调度算法都是针对同构系统提出的,对实时异构系统的动态调度算法研究的比较少。
本文研究了最初用于处理组合优化问题的蚁群算法(Ant Colony Optimization Algorithm,ACO),并用其解决多处理器系统的任务调度问题。在基本蚁群算法的基础上,考虑了带截止期的多处理器实时异构系统的特点,结合任务和处理器各个属性,设计新的任务选择和处理器分配策略,以及信息素更新策略。该算法能够满足任务间的优先约束关系以及截止期的限制,取得较短的调度长度,并且具有较好的收敛性。
为了验证该蚁群算法解决调度问题的优点,本文用Microsoft Visual C++6.0对任务模型进行实验,将得到的数据同其它的调度算法进行比较,实验证明本文的算法是一种求解多处理器系统任务调度问题的有效算法。