【作者】 王艳；

【导师】 李仁发；

【作者基本信息】 湖南大学 ， 计算机科学与技术， 2012， 硕士

【摘要】 近年来,多核处理器因其高性能、低功耗的特点在实时系统中得到了广泛应用。处理器架构的转变,给实时操作系统中任务调度的研究带来了新的挑战。本文对多核混合调度算法进行了深入研究。纯局部调度不能充分利用核的剩余处理能力,同时全局调度因为频繁迁移造成开销过大,针对上述的问题,提出了一种改进的混合调度算法,并对其利用率进行了分析。另一方面,考虑到共享高速缓存对调度的影响,在软实时应用的背景下,提出了一种面向共享缓存改进的多核混合调度算法。本文的具体研究如下：首先,本文在典型全局调度算法EDF-US[1/2]的基础上提出了采用分簇策略的混合调度算法。该算法对同构多核处理器中的多个核平均分组,令同一个分组中的处理器核为一个处理器簇集。将待调度的任务按利用率从大到小排列,基于最差适应算法将任务分配到各个处理器簇集,并保证每个簇集内利用率大于1/2的任务不超过簇集内的核数。任务分配后在各个簇集内使用全局EDF-US[1/2]调度算法,调度过程中,任务不允许在各个簇集间迁移。本文给出了采用分簇策略的混合调度算法的利用率下界,并分析比较了该混合调度算法与全局调度算法和局部调度算法的性能。其次,为了减小调度过程中共享高速缓存的抖动次数,提出了一种改进的混合调度算法。通过建立有任务依赖的任务模型,采用启发式算法将存在依赖的任务分配到同一个共享二级缓存的处理器簇集；并在处理器簇集内鼓励这些任务共同调度。仿真研究表明改进算法相比于原算法可以使共享二级缓存的命中率得到提高,从而提高调度的效率。更多还原

【Abstract】 In recent years, Multicore architecture has been widely adopted in real-time system due to the higher processor performance and lower power consumption. Multicore architecture is different from the single-core architecture, so how to effectively exploit the parallelism in multicore platform brings new changes to real-time scheduling.In this paper we made a deep research on hybrid approaches which combines elements of both partitioned and global scheduling. Fully partitioned approaches suffer from the drawback that the available processing capacity can become fragmented, such that although in total a large amount of capacity is unused. Meanwhile, the overheads incurred by global scheduling can potentially be very high. Neither partitioned nor global strategies could dominate over the other, so we presented an improved hybrid scheduling algorithm, and given a lower bound on the utilization bound of this algorithm. Then we analysed the hybrid scheduling through the utilization bound. To effectively use the available shared cache on multicore platforms, scheduling methods must be aware of it. Considering this problem in the context of soft real-time application, we presented an improved hybrid scheduling algorithm on multicore platform. Therefore, we proposed two new agorithms in this research work:First, based on the EDF-US[1/2] scheduling algorithm, we presented an cluster-based hybrid scheduling algorithm. In this approach, the homogenous multicore is averagely partitioned into clusters. Based on worst fit heuristic algorithm tasks are statically assigned to these clusters after sorting the tasks by descresing order, and in each cluster the number of the heavy task which utilization is greater than1/2must not more than the number of the core in the cluster. Tasks are scheduled within each cluster using global EDF-US[1/2] scheduling algorithm and not allowed to migration. Our work gives the lower bound on the utilization bound of the improved algorithm. Then compared to global scheduling and partitioned scheduling, we analyses the performance of the hybrid scheduling algorithm.Second, in order to reduce the hierarchically shared cache contention and effectively use the available shared cache, based on the classical task model we introduced a new task model considering the resourcing constraints of tasks, and then proposed an improved hybrid approach for scheduling real-time tasks on multicore platforms. The multicore platform is divided into clusters of cores according to whether the cores share a common L2cache, and then tasks which access the same memory region are statically assigned to the same cluster using heristic algorihm. Devising mechanisms encourage those tasks to be co-scheduled within each cluster. Our simulation results show the effectiveness of the proposed algorithm can improve the cache performance and increase the cache hit rate.更多还原