面向车联网应用的数据关联性任务调度算法

摘要

The extensive application of multi-core system improves the concurrency of tasks, however, brings the extra cost of inter-core communication.Inter-core communication will significant affect the schedule length and real-time of data related tasks.Aiming at the problem of real-time task response in multi-core processor system, this paper proposes a data related task scheduling algorithm (DTSV) for Vehicular Ad Hoc Networks (VANETs), with considering the multi-task concurrency mechanism in VANETs.Firstly, three types of data in Vehicular Ad Hoc Networks applications and their features are described and analyzed according to the vehicular networks protocol standards.In vehicular networks protocol standards, tasks of vehicular networks applications are divided into three types, Critical Safety, Traffic Efficiency and Non-Safety.Every type of task consists of a lot of parameters.In these parameters, some of them are not included in only one task, but included in several tasks.So it can be inferred that tasks of vehicular networks applications are related by data correlation.Based on the common data related task model and the task characteristics in vehicle networks, a related task model based on data correlation of vehicular networks applications is defined.Secondly, an evaluation function is proposed according to the related task model.The evaluation function is mainly constructed by the communicating tasks of computing task.And then a multidimensional vector is gotten from the evaluation function, to characterize the strong and weak correlation between tasks.Furthermore, a data related task scheduling algorithm based on the related task model and evaluation function is designed to reduce the inter-core communications during task execution by assigning tasks which have deep correlation in data into a same core.There are two phases for the algorithm, initialization phase and running phase.The initialization phase of the algorithm works at the start time of VANET system, to assign periodic tasks which generated at the start time.And the initialization phase can significantly reduce the schedule length of periodic tasks.The running phase of the algorithm works at the running time of VANET system, to assign aperiodic tasks which generated at the running time.It can marginally improve the real-time of aperiodic tasks with considering features of aperiodic tasks.Meanwhile, the data correlation of aperiodic tasks is pre-processed at the running time.After that, the real-time of aperiodic tasks can be further improved.Finally, the experimental and simulation is conducted to compare DTSV with other multi-core task scheduling algorithm.According to the result of the experimental, DTSV can reduce the schedule length by 10.6%.It is a considerable optimization for tasks which are continuously executing.The response time of aperiodic tasks can be reduced by 33.5% averagely.Aperiodic tasks generally require high real-time in vehicular networks.And the decrease of response time can significantly improve the safety of vehicular networks.The results of the experimental show that DTSV can effectively reduce the inter-core communication delay, shorten the task schedule length, reduce response time of tasks and improve the real-time of task response to data related periodic tasks and aperiodic tasks.%多核系统的广泛应用提高了任务的并发性,同时也带来了任务核间通信这一额外开销.对于具有数据关联性的任务,核间通信会极大地影响任务的调度长度和实时性.结合车联网多任务混合并发的应用特点,针对多核系统中任务响应实时性问题,该文提出了一种面向车联网应用的数据关联性任务调度算法(DTSV).首先,根据车联网协议标准中针对车联网应用相关的三类数据及其特性进行了描述与分析.车联网应用中任务被分为安全关键类、交通效率类和安全无关类,每类任务都包含大量参数.有些参数并不仅存在于一个任务中,而会同时被多个任务所应用.因此,在车联网中,任务之间存在着大量的数据关联性.基于常用关联性任务模型以及车联网中任务特性,定义了一种基于车联网应用的数据关联性模型.其次,根据任务相关性模型给出了任务关联性评价函数,该评价函数的建立主要依据与计算型任务有关的所有通信型任务,生成一个多维的向量,以表示任务与内核中任务之间的强弱关联关系.再次,根据上述关联性模型和评价函数设计了基于此评价函数的关联性任务调度算法,通过将数据关联性较强的任务分配到同一个内核,以减少任务执行过程中核间通信量.算法分为初始化阶段和运行阶段.算法的初始化阶段主要解决了车联网系统启动时大量周期性任务的分配问题,能够明显地减少周期性任务的周期调度长度.算法的运行阶段主要解决了车联网系统运行中随机产生的非周期性任务的分配问题,考虑到非周期性任务的特性,算法能够在一定程度上提高其实时性.同时,在算法的运行阶段,通过对非周期性任务的数据关联的预处理,更进一步提高了非周期性任务的实时性.最后,通过实验将DTSV与传统多核任务调度算法做出了比较,结果显示DTSV平均能够缩短10.6%整体任务调度长度,同时非周期性任务的响应时间平均能够减少33.5%.实验证明,DTSV相对于传统多核调度算法,针对具有数据关联性的周期性任务以及非周期性任务都能有效地降低其核间通信延时,缩短任务调度长度,提高任务响应实时性.