一种面向非对称多核处理器的综合性调度算法

Comprehensive Scheduling Algorithm for Asymmetric Multi-Core Processors

在非对称多核处理器上进行任务调度时，现有的操作系统调度器没有考虑其非对称性．针对单一指令集非对称多核处理器上的操作系统调度问题，首先建立线性规划模型，分析各种因素，得出行为匹配、减少迁移和负载均衡的调度原则．然后，基于调度原则提出一种综合性调度算法．该算法包括两个部分：1）集成负载表征，提出集成行为的概念，全面衡量任务的整体性和阶段性行为；2）基于集成行为的调度算法，有效开发非对称多核处理器的特性，能够保证各核心负载均衡，同时可以避免不必要的任务迁移．另外，该算法通过参数调整机制实现了算法的通用性．该算法是一种综合处理任务的整体性和阶段性行为，并具备通用性的调度算法．实际平台上的实验结果表明，该算法可通用于多种环境，且性能比其他对应算法提高6％-22％．

This research focuses on the problem of operating system （OS） scheduling on asymmetric multi-core processors （AMP）. A task scheduling model based on linear programming is proposed. Several attributes of AMP factors are taken into account in this model. Scheduling principles of behavior matching, migration avoiding, and load balancing are adhered as well. A comprehensive scheduling algorithm is also proposed based on the model. The algorithm has two parts： an integrated workload characterization, which proposes integrated behavior to measure the global and local behaviors of tasks comprehensively, and an integrated behavior- based scheduling algorithm, which efficiently utilizes the asymmetric multi-core processors without frequent task migration. This guarantees the load balance between cores. In addition, the algorithm achieves universality with a flexible parameter adjustment mechanism. It is an algorithm to achieve universality as well as the first to handle the global and local behaviors of tasks comprehensively. The evaluation on real platform demonstrates that the algorithm is universal for different conditions, and it always outperforms other scheduling algorithms on asymmetric multi-core processors （by 6%-22%）.