车联网中基于数据相关性任务调度算法研究

大连理工大学本科毕业设计（论文）车联网中基于数据相关性任务调度算法研究A Data Interrelation Aware Task Scheduling Algorithm in VANET学部（学院）：电子信息与电气工程学部专 业： 计算机科学与技术 学 生 姓 名： 何兵兵 学 号： 201181075 指 导 教 师： 丁男 评 阅 教 师： 完 成 日 期： 大连理工大学Dalian University of Technology车联网中基于数据相关性任务调度算法研究摘 要 随着车联网概念的出现，各大研究机构和相关企业均投入了大量的关注。车联网丰富的应用引爆大数据，面对复杂的任务、数据，作为单位节点的车辆，拥有一个强大的计算机系统就显得尤为关键，车辆中配置多核处理器已成必要。多核处理器的产生为计算机性能的进一步提高带来了很大的契机。然而对于多核处理器，很难仅仅通过提高硬件水平来提升计算机性能，而高效适应多核处理器的任务调度算法的研究就显得十分重要。 多核处理器的任务调度算法，初衷在于使得各内核负载均衡。而本文针对基于负载任务调度算法的不足，着重考虑了多核处理器的通信时间，基于车联网任务数据参数特点，设计了基于数据相关性的任务调度算法。算法设计了关联多任务模型，适应三类车联网任务，即交通安全类、交通效率类和娱乐应用类。算法旨在利用数据关联性增加核内通信、减少核间通信，从而降低通信开销，提高任务完成效率。 为了验证算法的性能，本文采用C语言编程模拟任务调度环境对本算法进行测试。主要以通信时延作为衡量标准，与基于负载均衡的随机任务调度算法比较分析，验证算法的调度性能。通过实验证明，本文算法缩短了通信时间，优化了调度性能。关键词：多核处理器；任务调度；数据相关性；车联网任务- -车联网中基于数据相关性任务调度算法研究A Data Interrelation Aware Task Scheduling Algorithm in VANETAbstract With the emergence of VANET, so many research institutions and related businesses have invested a great deal of attention. The rich applications have led to Big Data. Faced with the complex tasks and data, it is particularly critical for a car, as a node of VANET, to have a powerful computer system where that multicore processors are necessary. Multicore processors brings a great opportunity for the further improvement of computer performance. But foe multicore processors ,it can not improve computer performance merely by raising the level of hardware. Therefore the research on scheduling algorithm for multicore processors become more and more important.For the scheduling algorithm of Multicores processor, the original intention is to make each core load balancing. The deficiency of scheduling algorithm based on load in this paper is considered, and the communication cost of multicores processor is also emphatically concerned about .So we design a scheduling algorithm based on data interrelation and the characteristic of VANET tasks parameters. The algorithm design association multitasking model, which corresponds to the three types of VANET tasks, including traffic safety, transport efficiency and entertainment applications. The algorithm is designed to increase the use of data interrelation to increase the frequency of internal communications and decrease the frequency of external communications, so that it can reduce communication costs and improve work efficiency.In order to verify the performance of the algorithm, we program simulate task scheduling environment by C language in this paper. Then we test the algorithm majorly by comparison of the communication delay with random task scheduling algorithm based load balancing. Experiments show that the proposed algorithm reduces the communication time and optimize the scheduling performance.Key Words：Multicore Processors；Scheduling；Data Interrelation；VANET Tasks- III -目 录摘 要IAbstractII1 绪论11.1 研究背景11.2 研究现状分析11.3 论文主要研究工作及组织结构22 车联网任务及任务调度概述42.1 车联网概述42.1.1 车联网的现状分析与挑战42.1.2 车联网主要技术62.2 车联网中的任务及其分类72.2.1 车联网中数据参数及其来源72.2.2 车联网中任务及其分类82.3 任务调度概述82.4 任务调度的分类92.5 任务调度的系统结构103 基于数据相关性的关联多任务模型设计133.1 关联多任务概述133.1.1 关联多任务的提出133.1.2 关联多任务的定义133.2 任务的数据关联性模型133.2.1 基于车联网任务的分类及其参数集合133.2.2 数据关联性任务的关联性表达154 基于数据相关性的任务调度算法设计184.1 任务调度算法的任务模型184.2 任务调度算法的处理器模型194.3 基于数据相关性的任务调度算法设计205 任务调度算法性能测试245.1 任务调度性能测试标准245.2 实验测试方案255.2.1 实验环境255.2.2 测试方案设计255.2.3 实验程序设计275.3 算法性能测试结果与分析29结 论31参 考 文 献32致 谢331 绪论1.1 研究背景车联网VANET（Vehicular Ad-hoc Network）是由运行在交通道路上的拥有感知、计算、存储、和无线通信能力的移动车辆及其周边的基础通信单元而组成的新型自组织网络。1作为新型无线通信技术和现代智能交通的产物，持续受到了各界的广泛关注，被认为是建设道路高安全性和高效率性交通系统的关键技术。对于车联网系统，通过车辆间的通信能力、云计算、大数据等新兴互联网的综合，许多潜在应用就应运而生。当前的车联网应用类型按照功能主要分为三类，即面向交通安全的、面向交通运输管理和效率的、面向用户娱乐和互联网服务的。2随着社会的发展，汽车保有量持续增长，汽车已经成为人类的重要空间。堵车、交通事故一些列的社会问题相继出现，这就需要车联网在其中扮演十分重要的角色，车联网中的应用将会越来越丰富。车联网引爆大数据，面对复杂的任务、数据，作为单位节点的车辆，拥有一个强大的计算机系统就显得尤为关键，车辆中配置多核处理器已成必要。多核处理器的产生为计算机性能的进一步提高带来了很大的契机。然而对于多核处理器，很难仅仅通过提高主频来提升计算机性能,即通过提高主频来提高单个处理器核的计算性能己经无法适用，且主频提高的同时也带来芯片能耗和发热量的巨大开销。3即硬件水平上，多核处理器的性能的提升将变的很困难。在应用程序的进程、线程比过去多得多的情况下，充分利用多处理核是一个很大的挑战。因此需要重点考虑的是，任务的分配调度问题。为车联网多核处理器选择一个好的任务调度算法能够提高整体的性能，最大化利用系统资源，从而获得最优的参考标准，例如使得调度长度最小，通信代价最低及CPU的利用效率最大化等，能够为车联网应用的高效率运行提供很重要的技术保证。1.2 研究现状分析计算机任务调度的研究开始于上世纪60年代,由Manacher G.K第一次提出了“任务”的概念,并通过列表法进行基本的调度研究工作。任务调度一直是经典NP难问题。4 其含义是指系统为执行一系列任务集合分配到处理器上所釆用的调度策略和方法，任务调度算法是任务调度核心部分。多核处理器系统的任务调度一般分为，任务全局分配以及任务在各处理核的的本地调度。先按照一般的过程，全局调度器从待调度任务队列中挑选任务分配调度给与之相应的处理内核，这称之为任务全局分配，然后当任务进入到处理内核的本地队列之后，由本地处理内核根据一定的单核调度算法执行并完成该任务,这一过程称为本地调度。本文的研究重点在于全局分配，而目前的调度算法技术已经有很多研究著作对多核处理器下提出了一些性能比较好的任务调度算法或者是在已有算法上的改进。目前多核处理器任务调度目标是充分利用每一个处理核，使得处理器上执行总体程序的时间最短，提高了系统处理程序的吞吐率。为了充分利用这些处理核心，更好地发挥出多核的优势，必须保证分配到各个处理核心上的任务具有一个较好的负载平衡。否则如果一些核心在运行，而同时另一些核心却处于空闲状态，这使得多核处理器的并行优势无法发挥出来。如今多核调度算法，多数在设计调度算法时考虑了有关负载均衡问题。本文主要提到一种基于随机调度算法,它是任务负载均衡中比较经典的算法，在算法操作中利用处理器空闲时间并结合随机算法可得到较好的负载均衡效果。5多核处理器任务全局调度的初衷在于使的负载均衡，而任务执行时间是由两个重要的影响因素，一个是计算代价，另外一个是处理器之间的通信代价。通信代价中，不仅仅需要考虑核内通信，而且还要考虑到核间通信。任务调度后，处理器中每个内核都有复杂应用的多个功能不一的任务构成，而现如今的多核处理器任务调度由于调度过程没有考虑到任务之间的数据相互依赖性，忽略数据之间的“生产-消费”依赖关系，导致数据相互依赖的任务之间的核间通信增加，并且每个任务处理的数据量很大时，数据访问模式的更加多样化、复杂，使得关联的任务之间对数据系统的并发访问传输行为的规律性和可预测性显著减弱，因此多核系统效率的稳定性和可控性也难以得到保障。因此多核处理器的任务调度算法需要基于数据相关性进行有效的优化。1.3 论文主要研究工作及组织结构 本文的主要研究目的是设计在车联网中的多核处理器基于数据关联性的任务调度算法，优化多核处理器核之间的通信代价。本文主要工作内容包括以下几个方面：（1）对车联网的任务基于数据关联性进行分类；（2）根据车联网的任务特点，为本文提出的任务调度算法设计任务模型；（3）设计出基于车联网数据关联性进行任务调度算法的设计；（4）使用Windows操作系统搭建一个符合算法要求的环境，并将本文提出的算法在模拟的环境下进行性能测试。本文大致分为五章进行论述，各部分的组织结构如下：第1章 介绍了车联网和任务调度的研究背景，并提出了基于数据相关性的任务调度算法及其研究方向，为论文做了一个简要的概述。第2章 对车联网进行概述和任务调度技术，主要讨论车联网中的任务参数使用情况及其分类，为数据相关性任务调度提供一个应用背景。从而对任务调度技术进行较全面概述，引出本文所需要设计的任务调度算法。第3章 给出任务调度技术的中使用到的任务调度模型进行简要的介绍，并结合车联网的分类任务设计关联多任务模型。第4章 根据结合车联网的任务，设计基于关联多任务模型的数据相关性的任务调度算法，对算法主要思想进行详细地讨论。第5章 给出了本人所设计的任务调度算法的性能测试方案，与基于负载均衡的随机任务调度进行比较，并对测试结果做出分析，证明算法的优越性。2 车联网任务及任务调度概述2.1 车联网概述2.1.1 车联网的现状分析与挑战车联网，指的是运用高水平的传感、GPS、无线通信等技术技术，用来实现车路、车车、车人、车与城市网络的相互连接，而后在对应的信息平台上实现对所有车辆自身属性以及道路、人、环境等车辆外在属性的采集和高效使用，并且在这些基础上提供了安全、监控、定位、跟踪、管理以及娱乐等综合性服务，实现和谐统一的“人、车、道路、环境”一体化网络。车联网的发展和应用改变了人们在未来的出行交通模式，道路交通系统在运输方面、安全方面、智能化方面及环保方面的效率均得到了提升，为建成一种适应现代道路交通网络运输发展的建设、运营、管理模式、移动互联等新思维提供突破口。 车联网具有三大特性，包括移动特性、节点特性和数据流特性。6其移动特性表现为网络拓扑变化快、节点移动速度快以及移动轨迹可预测。其节点特性表现为具有强大的计算能力、存储能力以及几乎没有能量限制。其数据流特性表现为实时的路况信息以及突然增大的通讯负载。 近年来，国际上的学术界和产业界在车联网领域上十分得关注，并且投入大量的技术研发，国内外对于车联网的研究阶段不一样。国外方面，车联网目前还处于研究和测试阶段7，欧洲较早地开展了车联网研究工作，2004年启动的NoW（Network on Wheel）项目研究了两个方面的内容，包括路径导航和车载无线通信技术，在第六框架计划中，车辆厂商、道路管理和交通管理部门等部门为主要参与单位设立了多个车联网项目，包括COOPERS、SAFESPOT和SeVeCOM等，研究了车联网相关的各种关键技术。从2006年欧盟就开始从事车路协同系统CVIS的研究，该项目的初衷在于提高交通的效率，缓解交通堵塞问题，在传感探测、无线通信等技术的基础上，从车车通信和车辆与周边环境通信两方面开始研究。美国交通部在2009年发布了美国智能交通五年战略规划（2010-2014），从应用开发、技术支持、政策支撑三个方面重点支持IntelliDrive项目。美国七大汽车生产商组织建立了车辆安全通信协会，并相继启动了三期项目，包括VSC（Vehicle Safety Communication）、VSC-A、VSC3。同时美国学术领域就车联网通信机制、安全机制和商业应用等方面进行了相关的研究工作。日本车联网的研究项目主要有Smartway、ETC、DSSS、VICS等。日本截止2007年11月就有了约2000万车辆安装了车辆信息通信系统，到2008年5月已经完成了将近2000万辆车辆的ETC安装。日本信息科技战略总部在2010年发布了“新IT战略”，包括“绿色智能交通”和“安全支持协作系统”。前者主要研究的是交通的运输模式和验证检测数据的方法，后者主要研究的是道路安全问题及国际智能交通系统的兼容问题，总而言之二者的目的都是为日本智能交通大规模部署制定蓝图。国内对车联网的研究才刚刚起步，高校、研究机构、企业对车联网的研究仍局限在理论研究阶段。我国十分重视车联网的发展，2011年车联网项目就被确定为国家重大专项，一期就获得了百亿资金的拨款扶持。近年来我国 3G、4G移动通信网络的大规模完善，基本覆盖了全国大部分地区的路网，为提供全方位、高质量的无线通信提供了扎实的物质基础，使得车辆在行驶环境下稳定可靠地接收以图片格式或者地图文件格式的道路状态信息、诱导信息甚至是娱乐音频文件的需求得以实现，也最大化的实现了车联网下无时无刻的信息交换。车联网也对各部门的协调提出了新的挑战，在我国则表现为移动运营商与交通指挥中心、气象中心等各部门的合作问题，可以参考美国和日本已经形成的良好车联网体系，促进政企合作的协调性以及相关产业的均衡合理发展。 而在技术和经济方面，车联网的设计和部署都存在着诸多挑战。技术方面的挑战主要包括了：（1）缺乏在线集中管理和协调的实体；（2）无线信道的固定特性；（3）高移动性和可扩展性的需求已经各种不同的环境条件；（4）隐私和安全的关注和需求；（5）灵活性与标准化。而从社会经济、应用的角度来看，车联网主要挑战如下：（1）分析和量化车联网的成本效益关系；（2）车联网的部署策略的设计；（3）分析和量化车联网在行车安全和交通效率方面的效益；（4）将车联网嵌入到智能交通系统中。从技术、社会经济和应用等方面的挑战可以得到，车间通信技术和车辆应用领域建立在对跨学科的努力和研究之上，这些学科包括了通信、网络、车辆工程、交通运输等方面，所以，车联网可以视为智能交通系统的重要组成部分。未来车联网的发展将利用传感器、无线通信以及GPS技术的相互融合，组成多层次、全立体的网络拓扑，逐步建立一个车-车内部之间、车-路的移动自组织网络。未来车联网时代，主要整合车辆、通信交流、传感和通信技术。未来车辆之间能够通过这些技术进行通信并感知周边环境，拥有智能导航、自动泊车、行人探测、无人驾驶以及紧急停车等智能功能。2.1.2 车联网主要技术车联网是一种全新的物联网应用，是新一代的智能交通、智慧城市的核心基础，在其发展过程当中，需要的关键技术涉及到如下几个方面，包括射频识别技术、传感器技术、智能开放车载终端系统平台数据处理技术、通信技术、协议研发等8，具体介绍如下：（1）射频识别技术（Radio Frequency Identification，RFID）。射频识别技术是一种无线射频识别技术，主要由读写器、天线和标签组成。目前车联网中主要采用的还是这种可以实现更远读写的RFID技术，而其中中间件技术是目前研究的核心技术。RFID是一种非接触式自动识别技术，无须人工干预，通过射频信号自动识别对象并获取相关信息，在各种恶劣环境中均能工作。（2）传感器技术。传感器技术是车联网发展宽度的体现，也直接或者间接了车联网应用的数据基础。车联网是基于车、人、路、互联网之间的网络，而获得车、人、路的数据信息是车联网发展的基础和关键。通过各种各样的传感器来获取数字化信息，提供给车联网，将这些数据信息传输到处理中心，实现了传感器数据信息的融合。其研究的内容主要包括了人工智能、信息融合、智能控制、信号处理识别等。（3）智能开放车载终端系统平台数据处理技术。开放智能的车载终端系统平台数据处理技术是车联网之所以能体现自身价值的媒介，是车联网中的重要节点。大量的数据、大量的需求，便需要一个具有较强处理能力的平台作为技术支持，车联网中的整个应用服务才能够提升整体的服务水平，当然这也有赖于平台营运数据处理的能力以及前端传感器技术的共同提升。（4）通信技术。车联网应用的通信技术主要分为两种，一种是无线通信技术，另外一种是移动无线通信技术。无线通信技术指的是近距离的通信技术，主要采用的是RFID技术以及WIFI技术。移动无线通信主要包括3G、4G、GPRS、蜂窝数据网络等移动通信技术。二者相辅相成。（5）协议研发。车联网是一种全新的网络系统，因此需要研发一种使用与车联网的网络协议。传统的TCP/IP采用的是分层的思想，而车联网也可以借鉴这种思想，再加上车联网本身的特性对分层思想进行改进，采用类分层模型进行进行研究和分析。而车联网是需要与互联网进行通信的，因此也需要考虑到协议转换的问题。2.2 车联网中的任务及其分类2.2.1 车联网中数据参数及其来源 数据信息在车联网应用的分发十分重要，车联网信息分发系统的基本架构的设计是关键。车辆内部和外部信息源收集的信息存储在本地知识库中；该知识库中的信息可以被车联网的应用获取，还可以进一步通过通信手段与汽车之间进行交换和共享；通过对知识库的数据应用汇总和融合技术，可以对数据进行融合，避免重复冗余。基于分发的车联网应用在开始传输和处理数据前，必须首先获取车辆及车辆附近的局部观测数据，一个或者局部参数的观测数据。车联网使用的局部数据信息很大程度上取决于具体用途，如VANET应用的目标，并且与协议和融合机制中的其他设计参数精密相关。参数来源主要包括车内传感器、导航系统、外部传感器、VANET设备、参数预测等。9具体说明如下：（1）车内传感器。车联网中车辆的内置传感器提供了数据，是最为简单的获取信息的方式。例如，车内速度器和转速计数器能提供一些重要的车辆信息，能对当前的交通状况做出总结。一些车内传感器用于车内的电子子系统，为车辆提供一些环境参数信息，如温度、光强、速度、位置或路面情况等。（2）导航系统信息。多数车联网应用都会直接或者间接与导航系统相关。例如路线规划和停车导航系统，路线规划根据当前的交通状况、所在地与目的地来确定最合适的行驶路径，停车导航系统帮助车辆寻找最佳的空闲停车位。导航系统信息中拥有非常精确的定位、速度信息、还有驾驶方向的详细地图数据和信息等。（3）外部传感器。外部传感器作为车辆外部信息源来补充车辆的内部传感器。典型的例子就是外部传感器可以部署在人行道上并记录行驶过的车辆，从而生成用来分析当前交通情况的原始数据。通常，外部设备通过无线网络，将数据信息传输给车联网设备，如驶过的车辆与它们通信，从而获取相应的信息。（4）VANET设备。从VANET自身的观测数据得出的有关交通状况结论作为信息来源，来补充车内车外的信息源，在车联网中进行传播。许多VANET安全应用都是基于周期性信标帧的，包含了车辆的位置、速度、方向等信息。并通过VANET节点在本地周期性地广播。（5）参数预测。上面所有提到的感知参数都仅仅考虑了当前的情况。由于车联网信息广播的速度有限，因此把测量的数据传输到目的节点有很大的时延，而导致行为决策失效。根据现有数据信息以及过往的统计数据，预测数据参数，使得VANET中的数据信息更加全面。2.2.2 车联网中任务及其分类车联网最大的作用在于对信息的处理，并且能够以及其高效地解决道路堵塞问题。根据统计信息预计，VANET在交通道路上的应用可以减缓交通拥堵约，提高短途运输效率，提高使现有道路网的能力。除了这方面，更重要的是，通过车载传感器以及车联网中传播信息，还可以感知周围环境和驾驶员驾驶习惯，做出迅速的调整，从而实现“零交通事故”，也是车联网的一大作用。根据美国车辆安全通信项目组的总结报告和欧洲电信标准化协会的技术报告。车联网主要应用在安全驾驶辅助、交通效率管理以及提高车载娱乐与互联网应用服务等方面。三类车联网应用介绍如下：（1）交通安全类。交通安全类应用有车辆换道辅助、交通事故广播、交叉路口碰撞避免、紧急情况或者事件警告、追尾警告等安全类应用，所含的参数主要包括了速度、加速度、雷达距离、预警信息、驾驶员习惯等微观类交通参数。（2）交通效率类。交通效率管理应用主要包括了交叉路口管理、线路导航控制、堵塞提醒等改善道路交通状况并且有利益单个车辆节点的运行效率，所含的参数主要包括导航信息、交通密度、停车信息、实时路况等宏观类交通参数。（3）娱乐应用类。车载娱乐应用类包括通信软件、游戏、为用户提供生活资讯的多媒体等，所含的参数主要是来源于互联网数据中的图文信息、音频视频信息等。2.3 任务调度概述随着多核处理器的大面积普及使用，对能够高效适应多核处理器的任务调度算法的研究就显得十分重要。多核处理器对传统编译技术提出了挑战。到目前为止很多程序都是通过串行模式而编写的，如果直接在多核处理器运行，不能高效地发挥好多核处理器的并行处理能力。为此，并行编译技术引入多核处理器中。而任务调度算法尤为关键，如果调度算法不能够和调度对象进行很好地匹配的话，这势必会造成调度效率的低下，甚至将多核处理器该有的特性抹杀掉。任务调度算法是指针对一定的任务模型的一种明确具体的方法和步骤，根据一定的调度规则和调度策略把复杂程序的所有任务按照特定的执行时序分配到不同的计算节点上，使得任务能够执行。任务调度算法设计的设计过程包括：（1）任务的划分；（2）通信时间、参数分析；（3）任务组合；（4）处理节点映射。任务调度旨在合理调度任务到相应的处理节点上使得最终任务执行时间综合尽可能得短。任务的最终执行效率直接取决于任务调度算法的优良。虽然任务调度也生成了额外的开销，但即使是随机地将某些任务调度到相应的计算节点上也会明显提高系统的性能。因此，一个任务调度算法对于计算机系统来说是至关重要的。2.4 任务调度的分类多处理器系统的任务调度也分为，任务全局分配以及任务各个处理器上的本地调度。10任务全局分配是根据一定的算法，任务调度器从调度队列中选择合适的任务分配给对应的处理内核。而本地调度是指任务由分配队列到达本地队列后，由对应的处理器根据一定的策略执行并完成分配好的任务。上述调度情况如图2.1。图2.1 多核处理器的任务调度模型 根据任务数据和多核处理器的结构特点是否能在任务调度算法程序执行前获知，和已分配任务能不能随时改变内核等因数，将任务调度问题分为以下两种，静态任务调度和动态任务调度： （1）静态任务调度。在编译过程中能够利用静态估算方法获得待分配任务的运行时间、通信时间和任务间的相互依赖等参数，各个计算单元间的拓扑结构和计算性能均是已知的，任务调度算法程序按照以上已知的数据把任务调度到相应计算节点上运行。（2）动态任务调度。任务运行时，任务调度算法程序随时捕获任务运行时的参数，接着依据这些信息，实时地将任务转移到对应的计算节点。操作系统的任务调度就是动态地达到各处理单元的负载平均，实时地将任务从计算负担大的处理单元移动给负担轻的处理单元。这种调度算法的系统资源消耗较大，还需要考虑到任务转移时数据传递的问题。 本文设计的任务调度算法属于静态任务调度，并且主要研究的是任务全局调度。而在静态任务调度中可以按照调度方法分为以下四种类型：（1）有向无环图（DAG,Directed Acyclic Graph）12。根据DAG来代表应用程序的结构特征，节点表示的是任务，而有向边表示的是不同任务间的联系和依赖。处理器系统也使用无向图来表示，抽象成处理器模型。节点表示是处理节点，而边的是代表节点间的通信通道和结构。（2）分级任务图（HTG,Hierarchical Task Graph）13。HTG可以有冗余节点，其是由其他分级任务图组成。HTG需要编译器以显式的方式插入驱动代码。（3）任务交互图（TIG,Task Interaction Graph）。节点表示的是可以并行发生的应用任务，而其边表示的是任务之间的通信。通常是用在静态调度算法中的一种松散的通信处理方式，也就是任务均单独执行，时间上先后。（4）Peric网。作为经典的数学模型，Peric被用于展示并行系统。在控制数据流图方面，Prtic图为高层任务并行信息提供支持。Peric被广泛应用于硬件，并且也被用来建模解决对多处理器的任务分配问题。由于过度复杂，很少真正用来解决多处理器的调度问题。2.5 任务调度的系统结构任务调度系统是由三大模型部分构成，包括任务、处理器和算法。11任务模型是通过形式化的方式来表达等待调度的任务集合，并且包括调度过程中需要的所有有关数据，例如数据参数、任务间的通信开销和任务的计算时间等，本文献中的任务模型着重考虑的是数据参数。处理器模型是用来表示多核处理器中CPU处理器中各个计算内核节点的拓扑结构和运算能力等信息。最后，调度算法是采用某种规则和策略把任务模型中的任务集合按照一定执行次序分配到处理器系统模型的各个计算内核上，即生成任务映射图，使任务能够并行执行。以上所述如图2.2。图2.2 任务调度系统结构任务调度系统中的任务模型通常使用经典图论当中的有向无环图DAG来表示。整个任务图由多个节点和边组合而成，结构清晰，很好地表示了任务之间的优先约束关系。如图2.3，表示的是一个并行程序，或者是优先级互相约束的任务簇，矩形框所表征的节点表示的是程序的单一任务，也可以是子功能函数，矩形框数值表示的是任务运行时间。矩形框之间的有向线段表示两个节点任务间存在依赖关系，有控制信息或者计算数据进行传递，箭头方向就是控制信息或者计算数据传递的方向，有向线段上的数值则表示通信所花费的时间代价。 这种任务模型是基于消息传递的方式，任务图从开始节点到终止节点。任务之间以前驱节点的计算数据或者控制信息，来启动开始后继节点。在多核处理器中，同一个处理内核节点任务间的通信是可以忽略不计的，而不同内核节点之间的通信要有一定的通信时间。而在本文献中，我们提出的另外一种相近似的任务模型，将在下一章节中介绍，任务图主要是以参数作为任务图数据。图2.3 DAG任务图 多核处理器采用的是同构多核模型，即传统的对称多处理结构，内核和内核之间无差别，运算能力、通信能力相同。本文献采用的多核处理器中，采用的是一个任务调度内核，和多个执行内核的结构，即整个多核处理器中，由其中一个处理内核负责处理任务的调度、而所有其他的内核负责执行分配后的任务。该结构如图2.4所示，由处理内核0充当任务调度内核，将所有任务分配给其他所有执行内核，而后各个执行内核根据自己的单核任务调度算法执行任务。另外，核内通信通过核内cache进行，由于处于同一核内的这些任务的相关信息存储在同一本地缓存中，数据交换延迟时间很短，所以核内通信时间可以近似忽略不计。而核间通信间接通过核间cache通信开销不可忽略，这是因为核间通信中间的通信渠道增加，势必会造成时延。图2.4 多核处理器结构图3 基于数据相关性的关联多任务模型设计3.1 关联多任务概述3.1.1 关联多任务的提出在计算机科学与技术领域，任务指的是在处理器中完成的的一个基本工作单元，是由程序需要处理的一个或者多个指令的序列。在本文第三章中提到的任务调度的处理器模型，即本文献采用的多核处理器中，采用的是一个任务调度内核，和多个执行内核的结构，即整个多核处理器中，由其中一个处理内核负责处理任务的调度、而所有其他的内核负责执行分配后的任务。每个任务表示的是通过一个程序或者一组程序执行的单一线索，而主程序是每个任务下执行的第一个程序，其他的都是辅程序。例如“RISC主控处理器核+多个运算处理器核”在内的多种多核处理器体系结构都符合这一经典的任务描述，其中，RISC主控处理器主要负责执行主程序，而多个运算处理器核则承担辅程序的执行，并且运算负荷基本都分布在辅程序上14。而这样的结构势必造成了同一个应用中的多个任务元被分散开，而这些任务元必然会存在着通信，导致任务元之间的通信时延加大，导致运行效率不高。在本文的研究过程中，在对应用程序划分子任务后，进行任务关联性分析，保证关联性强，即通信次数多的任务尽可能多地在同一内核处理器中执行，保证通信代价的低廉。处理器核对数据系统访问传输效率的稳定性和可控性是具有重大意义的15。3.1.2 关联多任务的定义关联多任务是由两方面内容组成，包括任务和任务关系。任务根据本文介绍是不可再分的基本单元，直接对应于应用的完整独立的功能、函数；而任务关系指的是关联多任务中任务间数据的依赖关系，包括数据的“生产-消费”和数据的共享等。3.2 任务的数据关联性模型3.2.1 基于车联网任务的分类及其参数集合关联多任务定义的提出，任务之间的关系变得清晰，本文主要以数据参数作为中间量，通过与任务数据参数相关的数据来计算量化得到两个任务之间的关联性强弱。本文以车联网的任务作为实例说明并且设计基于数据相关性的任务调度算法，首先引入的是车联网任务的分类，而后将分类参数的频次权重进行计算，为任务的关联性的量化打下基础。而任务关联性包括两方面，一个是类关联性，而另外一个是任务关联性。类关联性是指相关联任务之间存在着数据的分享关系，即任务所使用到的参数与某种类型中所有的参数都有比较大的重合部分；任务关联性：相关联任务之间存在着“生产-消费者”关系。而根据关联性量化后得到关联因子，于是就有类关联因子、任务关联因子。由第二章可知，车联网主要应用在安全驾驶辅助、交通效率管理以及提高车载娱乐与互联网应用服务等方面。因此本文把车联网应用任务分为三类，分别是交通安全类、交通效率类、娱乐应用类，具体的任务实例和参数在表3.1中列举。表3.1 车联网任务分类分类实例主要涉及参数交通安全类并线协助，提前感知碰撞，违反交通信息警告 ，弯道速度警告，紧急制动警告，碰撞预警，左转协助，车道变换警告，“停车”标志协助等车辆特征，速度，加速度，温度，方向，位置，预警信息，车辆路径预测信息，公路几何机构等交通效率类旅途规划，路径选择，避免堵车，自动巡航，查找停车位，避免交通事故发生点等导航信息，全局公用时钟，交通密度，行程时间，停车位信息，城市实时交通状况，指示灯状况，驾驶员偏好等娱乐应用类通信交流、服务公告、信息娱乐、支付服务、互联网应用等文字信息，图片信息，语音信息，视频信息，网页文件等 根据表3.1中所示，三类车联网任务的主要设计参数，表示的是一类任务中较集中使用的数据参数，我们把一类任务对应的参数称之为相对应类的参数，相对应地，就有交通安全类参数、交通效率类参数和娱乐应用类参数。 本文把三类任务的数据参数用三个参数集合来表示，如下：, , 其中，N、M、C为常数且近似相等，xi，yj，zk（其中1iN，1jM，1kC）其中表示对应类参数集合中的各个参数，。3.2.2 数据关联性任务的关联性表达 在车联网任务中，并不是每个参数使用的情况即使用频次都相同。因此根据参数计算关联性之前，必须在调度内核中记录每个参数的使用情况。本文以参数使用频次计算使用情况。假设经过一定量车联网任务的执行，对每个参数的使用频次进行统计，可以得出每个参数在同类参数中占有的频次权重。本文用F表示参数的使用次数，则每个参数的使用次数分别为Fx1,Fx2,.,Fy1,Fy2,.,Fz1,Fz2,.。每个参数的使用次数在同类参数总使用次数中所占的比例称之为频次权重w，则有如下计算公式： (3.1) (3.2) (3.3)由如上易得，本文根据所得的频次权重得到3个N1的矩阵Wx,Wy,Wz，表示三类车联网任务的参数频次权重矩阵，表示方法如下： (3.4) 得到参数频次权重矩阵之后，接着就可以根据任务之前的参数量化任务之间的类关联性和任务关联性，得到类关联因子和任务关联因子。 假设有两个任务P,Q，且P,Q任务中所涵盖的参数均包含在X,Y,Z中的参数，即P,QXYZ。并且分别为P,Q定义三个1N的参数矩阵Ex,Ey,Ez，即 (3.5) 其中eg=1或者eg=0，表示的任务P中是否涵盖X类参数集合第g个参数，在参数矩阵相应位置中用1表示相应参数共有，0表示相应参数不共有。同理可得Ey,Ez。 因此可以通过类关联性分析、任务关联性分析，得到类关联因子和任务关联因子。由于车联网任务的三个类别，我们把相应的类关联因子和任务关联因子同时分为三类，其中类关联因子分为x,y,z。则对任务P来说，其类关联因子的计算过程16如下： (3.6) (3.7) (3.8)由公式（3.6）、（3.7）、（3.8）可得x,y,z0,1,表示的是该任务所有参数在三类任务参数集合中所占有的使用频次比重，并且值越大，类关联性越强。而任务关联性是两个任务之间的数据关联程度，用任务关联因子来表示，则x(P,Q),y(P,Q),z(P,Q)相对应地表示了在三类参数集合基础上两个任务的任务关联因子。任务P,Q的参数集合的交集PQ的参数矩阵分别对应于Ex,Ey,Ez,表示的是任务P与Q共同涵盖的参数在三类任务参数中是否涵盖。任务P,Q的参数集合的并集PQ的参数矩阵分别对应于Ex,Ey,Ez,表示的是任务P或Q所涵盖的参数在三类任务参数中是否涵盖。而则P与Q的任务关联因子计算过程如下： (3.9) (3.10) (3.11)由公式（3.9）、（3.10）、（3.11）可得(P,Q),y(P,Q),z(P,Q)0,1,表示的是P与Q参数集合交集的部分在P或者Q所涵盖的参数中占有的比重，并且值越大，二者的任务关联性越强。根据上文所述，任务关联性主要由两个指标量化，包括类关联性、任务关联性。其中类关联性更关心的是数据共享的相关性，与各类任务参数的历史数据比较，主要指的是任务之间使用的参数的一致性，在多核处理器中，基于Cache的数据缓存系统对于类关联性强的任务来说，同类任务在同一处理器核中运行，对于数据的采集和存储将会很有效率，避免了更多的核间通信；而任务关联性更注重的数据之间的“生产-消费”关系，与各类任务参数的最新数据比较，保证任务之间的通信数据在当下的Cache数据缓存系统中拥有并且保持一段时间，使得在任务关联性强的任务之间的通信代价变低。本文献在算法设计时分别考虑了类关联性和任务关联性，而在算法验证性能的时候综合考虑了类关联性和任务关联性，由于二者产生影响调度结果的相似性。4 基于数据相关性的任务调度算法设计 任务调度系统是由三大模型部分构成，包括任务、处理器和算法。如第三章所述，本章将在如今研究的基础上进行修改，对这三大模型的设计进行阐述。4.1 任务调度算法的任务模型任务模型是通过形式化的方式来表达等待调度的任务集合，并且包括调度过程中需要的所有有关数据，例如数据参数、任务间的通信开销和任务的计算时间等，本文献中的任务模型着重考虑的是数据参数。本文采用类似有向无环图DAG模型的无向无环图UAG来表示本文献任务调度算法的任务模型，如图4.1所示。图4.1主要阐述任务之间的数据关联性，整个任务图由多个节点和边组合而成，结构清晰，很好地表示了任务之间的数据相关联关系。图4.1 基于数据相关性的UAG任务图上图所示的是基于数据相关性的UAG任务图，表示的是车联网任务中的部分应用程序。方框节点表示的是一个任务P，根据第三章基于数据相关性的关联多任务的关联性量化计算方法，每个任务都有相对应的类关联因子集合A=x,y,z，基于三类车联网任务参数集合的类关联因子均含在其中。三个类关联因子的大小就能反馈出任务节点与哪一类的类关联性任务最强，从而更多地与该类任务参数进行计算和通信。节点任务之间的无向曲线表示是任务之间存在的数据相关性，无向曲线上的值表示的是任务之间的任务关联因子集合B(P,Q)=x(P,Q),y(P,Q),z(P,Q)，基于三类车联网任务参数集合的任务关联因子均含在其中。三个任务关联因子表示的是该任务与其他任务的数据关联性，数值越大，表示两个任务之间就该类任务参数的通信、数据传递就越频繁。基于该描述，建立任务关系表，如表4.1所示。当有新任务动态加载或删除，将其任务关系在表内动态添加或删除。表4.1 任务关联性因子表任务X/Y/ZP1P2PnX/Y/Z-A1A2AnP1A1B(P1,P1)B(P1,P2)B(P1,Pn)P2A2B(P2,P1)B(P2,P2)B(P2,Pn)PnAnB(Pn,P1)B(Pn,P2)B(Pn,Pn)这种任务模型是基于数据相关性的，任务图的节点信息、无向边信息反应了在三类车联网任务参数分类中，与每类参数集合的类关联性和任务关联性。利用数据量化后的任务关联性因子表