The Research Of Real-time Hybrid Scheduling Algorithm On Homogeneous Multicore Platform

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.