摘  要

        近年来，多核处理器因其高性能、低功耗的特点在实时系统中得到了广泛应用。处理器架构的转变，给实时操作系统中任务调度的研究带来了新的挑战。

本文对多核混合调度算法进行了深入研究。纯局部调度不能充分利用核的剩余处理能力，同时全局调度因为频繁迁移造成开销过大，针对上述的问题，提出了一种改进的混合调度算法，并对其利用率进行了分析。另一方面，考虑到共享高速缓存对调度的影响，在软实时应用的背景下，提出了一种面向共享缓存改进的多核混合调度算法。本文的具体研究如下：

        首先，本文在典型全局调度算法EDF-US[1/2]的基础上提出了采用分簇策略的混合调度算法。该算法对同构多核处理器中的多个核平均分组，令同一个分组中的处理器核为一个处理器簇集。将待调度的任务按利用率从大到小排列，基于最差适应算法将任务分配到各个处理器簇集，并保证每个簇集内利用率大于1/2的任务不超过簇集内的核数。任务分配后在各个簇集内使用全局EDF-US[1/2]调度算法，调度过程中，任务不允许在各个簇集间迁移。本文给出了采用分簇策略的混合调度算法的利用率下界，并分析比较了该混合调度算法与全局调度算法和局部调度算法的性能。

        其次，为了减小调度过程中共享高速缓存的抖动次数，提出了一种改进的混合调度算法。通过建立有任务依赖的任务模型，采用启发式算法将存在依赖的任务分配到同一个共享二级缓存的处理器簇集；并在处理器簇集内鼓励这些任务共同调度。仿真研究表明改进算法相比于原算法可以使共享二级缓存的命中率得到提高，从而提高调度的效率。

关键词：同构多核处理器；实时调度；混合调度；算法利用率；共享高速缓存

研究报告