英语原文共 25 页
实时优先约束任务的到达调度使用遗传算法的多处理器系统
Muhuri,Amit Rauniyar,Rahul Nath
印度新德里南亚大学计算机科学系，邮编：10021
亮点
bull; 一种用于优先约束实时调度问题的新颖公式。
bull;我们将其建模为考虑任务到达时间的动态约束问题。
bull;为实时系统提出动态遗传算法来解决问题。
bull;找到可行的任务计划，最小化完工时间，确保最后期限合规。
bull;它使用可变长度染色体的思想来实现不同数量的任务到达。
bull;与PSO，ABC和SA进行彻底的比较研究，考虑基准任务集。
bull;提供实现方法以解决同步和错过最后期限。
文章信息
文章发展史：
2018年5月26号收稿
2018年9月5号收到修改稿
2018年10月7号稿件被征收
2018年10月29号在线发表
关键词：优先约束；到达时间；任务分配；动态任务调配；实时多处理器系统；遗传算法摘要：本文将基于优先级的实时任务调度问题建模为动态约束问题。它提出了一种新的调度方法，称为“用于实时调度的动态遗传算法”（dGA-RTS）。 dGA-RTS的重要特征是它可以处理实时系统的相互依赖任务的动态和静态调度。在并行或分布式系统中，动态任务调度的最后阶段是将处理器分配给给定的任务集，以在优化的完成时间内执行它们，而不会违反任务依赖性（如果有的话）。当任何新任务到达调度程序时，dGA-RTS调度等待列表中的任务，并最小化任务集的总调度长度，确保最后期限合规性。我们还说明了一种实现技术，以解决多处理器系统中的同步问题。为了展示我们的方法其适用性，我们使用合适的基准测试和合成测试用例进行实验。此外，我们进行广泛的模拟，并将结果与不同的性能指标进行比较。结果与现有方法的比较研究表明，我们提出的方法在产生可行解的方案方面更有效。
1.概要
实时系统（RTS）中的每项任务都需要在特定的时间范围内执行，称为“最后期限”。违反最后期限可能会对系统造成严重损害，并造成对周围环境的影响。 系统被采用的RTS主要有两种类型：硬RTS和软RTS。 硬RTS需要严格遵守任务期限。 也就是说，在硬RTS中，每个任务都必须在截止日期之前处理; 否则，系统故障可能导致重大损失。 在软RTS中，即使在某些范围内违反某些期限，计算输出仍然有用[1]。 因此，任务调度是RTS设计的一个重要模块，它确保系统操作是安全和有针对性的。
实时任务可能具有不同的特征，在这些特征上，它们被称为“强制性”，“先发制人”，“周期性”，“周期性”，“独立性”等。 RTS中的任务调度是静态的还是动态的。基于优先级的“或者独立的”.RTS中的任务调度是静态的或动态的。 静态任务调度通常仅适用于定期任务。 这里，所有必需的任务特征即在调度[2]之前，已知数据依赖性，通信成本，处理时间和同步要求等。 然而，非周期性任务是高度事件生成的，并且它们的特征不是先验已知的。 因此，静态调度方法对于非周期性任务并不是那么有用。 因此，执行并行处理器上的此类任务需要适当的机制，可以动态分配处理器并安排任务。 当新任务到达时，这样的调度程序应该能够动态生成新的可行调度.
为简单起见，研究人员通常认为实时任务是独立的。但是，在实际领域中，任务是非常相互依赖的。为了在拓扑上描绘相互依赖的任务，DAG（有向无环图）是一个非常有用的工具[3]。每个任务都是一个独立的工作单元，可能会从一个或多个任务中获取相关性。前面的任务称为父级，依赖于它的任务称为子任务。此外，实时任务需要在到达系统时立即进行执行。有必要在任务到达时触发调度程序，以便能够以最小延迟进行调度，以确保最后期限符合性并满足等待子任务的输入要求。因此，安排基于到达时间的实时异构系统中的DAG使得环境动态且更复杂。尽管对任务调度问题进行了大量研究，但对于由DAG表示的优先约束任务，RTS中的动态任务调度尚未进行太多探索。在实时并行处理器上动态任务调度的目标是在考虑任务优先级的情况下为一个给定任务分配处理器，并以最小调度时间执行最后期限。
在本文中，提出了一种新的调度方法，我们将其称为“实时调度的动态遗传算法”（dGA-RTS）。 dGA-RTS可以在任务期限内适当地处理RTS中的DAG，以生成动态调度，从而实现最小可能的完工时间并确保最后期限的遵从性。当任何新任务到达调度程序时，它会修改计划。 dGA-RTS的设计基于[4]中考虑的移民计划概念所获得的动机。在这个新算法中，我们引入了一个新的概念，即当新任务到达时，任务数量的变化可变染色长度[5]。 dGA-RTS的主要特点是它可以处理动态以及RTS相互依赖任务的静态调度。此外，该算法可以应用于单处理器系统和多处理器系统。多处理器计算系统可以是同构的也可以是异构的。因此，我们在工作中考虑了两种实验方案。我们使用合适的任务集进行了实验，并证明了所提出的方法在动态和静态调度中的适用性，考虑了不同的性能指标。稍后，我们提出了一种实现技术，该技术能够管理由于在调度算法终止之前某些新任务的存在而可能出现的同步问题。此外，我们还讨论了几种可以处理不可行解决方案和截止日期违规的传统技术的实时系统的异常处理程序。
本文的主要内容如下：
bull;模拟基于优先级的实时任务问题调度作为动态约束问题的基础他们的到来时间。
bull;模型考虑了到达时间表的到达时间并计算每项任务的迟到以检验可行性获得的解决方案。
bull;提出了用于处理动态行为的调度程序模型这个问题。
bull;开发了一个十进制编码的GA，我们将其命名为#39;#39;用于实时系统的动态遗传算法（dGA-RTS）#39;#39;，以找到问题的解决方案。
bull;我们还通过实施几个常用的进化算法即模拟退火（SA），粒子群优化（PSO）和人工蜂殖民地（ABC）来解决这个问题。
bull;我们比较了从PSO，ABC和SA获得的结果使用我们的dGA-RTS技术，使用四种不同的性能不同基准任务集上的指标。
bull;包括可以解决同步问题和截止日期违规的实施方法作为例外处理。
本文的其余部分安排如下：在第2节，简要介绍对现有文献进行了回顾。第3节讨论了该问题的制定，并提出了基于GA的动态任务调度解决方案的细节RTS，它还说明了拟议方法的运作用一个简单的例子。第4节介绍了一项比较研究结果讨论了几项绩效指标以及静态和静态的较大任务集的模拟结果动态案例。第5节第6节描述了一种处理同步问题的方法和实现过程中的异常处理并总结了论文和讨论了结果，它还强调了未来的研究方向解决问题的背景。
2.文献综述
遗传算法（GA）被广泛用于优化和搜索问题包括任务调度问题[6-8]。报告了一系列关于静态任务调度的研究工作使用GA的RTS。然而，报道的研究报道并不多使用GA在RTS中进行动态任务分配和调度。一些众所周知的方法，使用GA进行任务调度现在简要讨论问题。
在其早期应用于调度问题之一，Monnier等人。[9]实现了一个GA来解决复杂的实时周期性任务调度问题，以便在分布式环境中获得最优的调度。在[10]中，Choe等人提出了一种基于GA的迭代重新调度方法来提升实时约束下的性能，据报道这种方法的表现优于基于模拟退火的方法。在[11]中，Oh等人提出了一种基于GA的解决方案技术，用于在多处理器系统上查找任务执行的最佳调度，旨在最大限度地减少所需的处理器数量任务的迟到。几种杂交形式的GA也是开发用于改进多处理器任务调度的形成时间表。在[12]中，Omara等人发展了两个混合GAs，。即CPGA（关键路径遗传算法）和TDGA（任务复制遗传算法）用于通用计算系统中的任务调度问题。 CPGA可以最小化执行长度并平衡负载，而TDGA使用了任务复制的想法，以优化通信开销任务之间。最近，Zhang等人 [13]设计了基于GA的负载感知资源分配和DAG的解决方案技术云计算系统的任务调度（LA-RATS）策略。他们的实验结果表明该方法已经完成以及最小化货币成本，总周转时间和提高延迟容忍和敏感的最后期限满意度应用。一种用于容错调度的新型混合遗传算法保证Samal等人开发了实时任务截止日期的合规性 [14]。他们设计了一个调度程序模型和主要备份容错方法，考虑任务的实时属性来处理故障。这种方法实现了解决方案经过几个任务集的实验证明了他们的技术能够产生改进的解决方案。阿克巴里等。 [15]提出了一种基于GA的新技术遗传算子的调整和初始种群的调整以进行优化计划长度较低的重复解决方案。它们在异构系统中的随机图上进行了模拟并测量了几个性能指标。他们的结果的比较研究表明在这方面有显着的提高到其他调度算法。
Zomya等人提出了GA动态负载平衡和调度的一个非常早期和重要的考虑因素。 [16]，投影比第一次拟合启发式方法更好。[17]，Cheng等。提出了一种基于遗传算法的动态实时多处理器调度问题的方法，该方法考虑了具有可行能量函数的资源和时间约束。等。 [18]实施了改进的动态版GA解决云计算中的动态任务调度问题，以提高其性能。他们的云环境模型可以通过减少产生有效的吞吐量在执行时间。基于GA的动态调度方案是由Page等人提出的。 [19]说明了分布式异构处理器上执行时间的最小化在任务到来时考虑系统资源。同样的，Page等。 [20]提出了一种动态调度方法将GA与异构的八种常见启发式结合起来
多处理器系统，以最大限度地减少执行时间。他们的算法是为安排批量任务而设计的被抢先重新映射到处理器。 Nayak等人。 [21]提出了一种带有BFO的混合GA用于多处理器任务调度并报告了其他方法的重大改进。纳特等人。提出了基于GA的节能方法[22-24]在不确定情况和静态情景下的调度。 Wen等人提出了一种不同处理器的调度方案。 [25]考虑了GA的杂交与邻居搜索技术。在[4]中，Cheng等人。解决了一个动态负载平衡问题，其中有许多GA连续执行。郑等人。 [26]提出了一个问题安排DAG工作流程来处理云上的大数据旨在最大限度地降低货币成本并满足最后期限限制。通过广泛的模拟，作者展示了他们的提出具有成本效益的调度算法优于其他算法现有解决方案Li等人提出了一种称为多阶段复合GA的GA的改进版本。 [27]解决随机问题解决缓慢的资源分配问题考虑进化技术的早熟收敛。他们甚至发现该方法可能适合于调度在制造过程，数据挖掘和其他复杂的数值优化[28]系统。李等人。 [29]，研究了其中之一经典优化问题，随机分配问题制造和管理过程中的资源分配。考虑到这一点，他们开发了基于GA的解决方案复合效应的均值和方差作出决定。该他们的实验结果表明效率的提高和收敛。一种基于DAG的静态调度算法在[30]中提出了使用混合GA的分布式系统。对于Suresh等人在异构环境中对任务调度和数据划分进行了分析。在[31]中提出了一种实数编码的混合遗传算法。同样，Biswas等人。 [32]报告了基于DAG的实时任务基于贝叶斯优化算法的调度方法最小化计划的总完工时间和延迟。 Chaudhary等[33]研究了理论，概念和理论的背景系统科学中的进化策略原理，整合GA作为人工智能工具。通过，他们的研究也为广泛的业务应用程序提供了GA的范围和商业软件。 GA，作为流行的和有效的进化算法（EA）之一，被应用于许多其他任务分配和研究的重要着作[28,34-38]近期的资源配置问题。
3.问题的制定和拟议的遗传算法解决方案的工作
在本节中，我们首先描述有向无环图的模型，它在我们的问题公式中用于表示任务特征。 然后，我们描述了生成任务期限所遵循的程序。 此外，我们简要介绍传统GA的步骤。 接下来解释用于有向无环图的GA的元素。 最后，我们已经解释了所提算法的工作原理。表1中提到了用于解释的符号和缩写以及问题的数学公式。
3.1 有向无环图的模型
Kwok等人 [3]提出了一个DAG模型，并进行了比较，以对任务调度算法的几个图进行基准测试。新到达的任务可以是依赖的或独立的已安排的任务。如果新到的任务是依赖，然后它形成一个任务图G =（V，E），它可以是由加权DAG表示，其中V为节点集，E为有向边的集合。节点是一组称为的指令任务。边从父节点开始并在子节点处下沉。没有父节点的节点称为入口节点，而节点没有任何子节点称为退出节点。图1显示了典型的DAG。
子节点在形成时可以具有一个或多个父节点节点之间的子父关系。孩子的话在所有父母完成执行之前不执行，如可以为子节点输入父母的处理数据。节点ni的计算成本由（ni）时间表示。从父到子的优先级可以表示为ni→nj，在哪里你是nj孩子的父母。边缘上的重量称为通信成本，用C（ni，nj）表示[3,30]。这个当安排ni和nj时，计算通信成本不同处理器;否则，考虑通信费用为零。如果节点ni计划在处理器Pj上那么节点ni的开始时间和结束时间由ST（ni，Pj）表示和FT（ni，Pj）。在安排所有节点之后，在所有处理器上定义为maxi {FT（ni，Pj）}的调度长度计算。 DAG调度的目标是找到不同处理器的任务分配及其开始时间考虑到，总执行长度最小化保留优先约束并遵守最后期限。
3.2 基于优先级的任务调度：动态约束问题
将基于优先级的任务图作为动态约束问题进行调度更加实用和实用。 这里，预先不知道诸如到达时间，开始时间，执行时间和期限之类的任务特性。 我们将问题定义为适应[39]中描述的类似策略的一系列实例，用于动态约束问题[40,41]。设计了一个集中式框架，其中中央计划器具有关于要分配的所有处理器和任务的知识。 中央调度程序评估特定实例中所有可用任务的调度。 问题（在那个例子）是安排 n基于优先级的任务{T1，T2 ,.。。 ，Tn}对m的数量分布式处理器{P1，P2 , ... ,Pm}。 每个任务Ti具有到达时间AT（Ti）le;0，处理器Pj上的开始时间ST（Ti，Pj），执行时间ET（Ti）gt; 0和截止日期，截止日期（Ti）le;AT（Ti） ET（Ti）。
参考文献lt;
资料编号：[5604]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
