基于多核平台的实时混合任务调度算法研究

发布时间：2018-03-24 17:54

本文选题：多核平台　切入点：混合任务　出处：《武汉理工大学》2013年硕士论文

【摘要】：随着人类对计算机性能需求的不断提高,处理具有严格时间限制的计算密集型实时应用时,单核处理器已经显得力不从心,人们把提高计算机性能的需求通过采用多核处理器来实现。目前,智能手机、平板电脑、笔记本电脑等电子产品基本上都采用了多核处理器。多核处理器因其诸多的优势将取代传统的单核处理器,逐步成为市场的主流。多核处理器的普及为实时系统的应用提供了更广阔的平台,也使实时系统变得更为复杂,系统中同时存在多种类型的任务,其中主要包括硬实时周期任务和软实时非周期任务两种任务类型。这类实时混合任务调度目标是在保证硬实时周期任务满足截止期的前提下,尽量提高软实时非周期任务的平均响应时间,然而,这并不是唯一的目标,为了充分利用多核的性能优势以及维持系统的稳定性,还需要考虑提高多核处理器的利用率和负载均衡。针对以上两个目标,本文对多核平台的实时混合任务调度算法进行了研究,主要工作如下： (1)首先,采用划分方案将所有的硬实时周期任务映射到特定的处理器核上；然后,对每个核上的周期任务进行分析,定义了“超周期空闲时间”和“空闲率”及相关计算方法,提出了分配最小截止期(Assign Minimum Deadline, AMD)算法,该算法为混合任务中的软实时任务选择具有最大空闲率的处理器核,并为其分配最小截止期；最后,将分配最小截止期的软实时任务和硬实时周期任务一起由EDF算法进行调度,可使混合任务中的软实时任务尽可能早得到响应,从而有效缩短了软实时任务的平均响应时间,并且该算法利用的是周期任务集在每个超周期内提供的空闲时间来处理软实时任务,所以不会影响到硬实时周期任务的截止期。 (2)硬实时周期任务的分配策略不仅会影响到软实时任务的调度,还会影响到多核处理器的利用率及负载均衡(Utilization and Load Balance，，ULB),为了综合考虑实时混合任务调度以及多核处理器的利用率和负载均衡,提出了EDF-ULB算法,该算法通过定义“分配因子”对周期任务集的分配策略进行灵活选择,实验结果表明,该算法在提高混合任务中软实时任务平均响应时间的同时,有效的平衡了多核处理器核的高利用率和负载均衡。
[Abstract]:With the increasing demand for computer performance, when dealing with computationally intensive real-time applications with strict time constraints, the single-core processor has become inadequate. The need to improve the performance of computers is achieved through the use of multi-core processors. At present, smartphones, tablets, Notebook computers and other electronic products basically use multi-core processors. Because of its many advantages, multi-core processors will replace the traditional single-core processors and gradually become the mainstream of the market. The popularity of multi-core processors provides a broader platform for the application of real-time systems, and also makes real-time systems more complex, and there are many types of tasks in the system. There are two kinds of tasks: hard real-time periodic task and soft real time aperiodic task. The scheduling goal of this kind of real-time hybrid task is to ensure that hard real-time periodic task meets the deadline. To maximize the average response time of soft real-time aperiodic tasks, however, this is not the only goal, in order to take full advantage of the performance advantages of multi-core and maintain the stability of the system. Consideration should also be given to increasing the utilization and load balancing of multi-core processors. Aiming at the above two objectives, this paper studies the real-time hybrid task scheduling algorithm of multi-core platform. The main work is as follows:. First of all, all hard real-time periodic tasks are mapped to specific processor cores by partitioning scheme, then the periodic tasks on each core are analyzed, and the "super-period idle time", "idle rate" and the related calculation methods are defined. In this paper, an assign Minimum deadline (AMD) algorithm is proposed. The algorithm selects processor cores with maximum idle rate for soft real-time tasks in hybrid tasks, and assigns minimum deadlines to them. The soft real-time task with the minimum deadline is scheduled by EDF algorithm together with the hard real-time periodic task, so that the soft real-time task in the mixed task can be responded as early as possible, and the average response time of the soft real time task can be shortened effectively. Moreover, the algorithm uses the idle time provided by the periodic task set in each super-period to process soft real-time tasks, so it does not affect the deadline of hard real-time periodic tasks. The allocation strategy of hard real-time periodic tasks will not only affect the scheduling of soft real-time tasks. It will also affect the utilization of multi-core processors and load balancing. In order to comprehensively consider the real-time mixed task scheduling, the utilization and load balancing of multi-core processors, a EDF-ULB algorithm is proposed. The algorithm flexibly selects the allocation strategy of periodic task set by defining "assignment factor". The experimental results show that the algorithm not only improves the average response time of soft real-time tasks in hybrid tasks, but also increases the average response time of soft real-time tasks. The high utilization and load balance of multi-core processor core are effectively balanced.
【学位授予单位】：武汉理工大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP301.6

【参考文献】