基于计算机动态任务分配表的负载均衡新算法

摘  要：计算机技术飞速发展的今天，在并行计算机系统之中，任务调度依旧是解决多资源配置的最有效方法之一，但是当前的任务调度依然存在着一些困境，其中的一个难题是NP-Hard问题，即和任务负载均衡相关的分配方法还存在调度方面的问题。该文提出了一个新的负载均衡的动态Work-Stealing新算法，通过这个新算法可以加强动态计算机集群之中任务分配的效率，帮助各种任务进行得更加顺畅，以此帮助整个计算机系统提升资源的利用效率，并提升计算机系统的整体性能。该文首先对常见的任务调度模型进行分析，分析了任务调取算法的计算机制，着重对工作窃取算法的计算策略进行探讨，通过快速地选择窃取的时机和窃取的工作任务数量，可以实现复杂维度的算法，提升负载的实际均衡能力。

关键词：任务分配  负载均衡  Work-Stealing算法

中图分类号：TP391                                 文献标识码：A                         文章编号：1672-3791（2019）04（b）-0013-02

1  和任务调度的动态化相关的概念

动态调度相关问题对于计算机的性能产生非常大的影响，特别是在云计算的框架之中。大量的学者在这个领域投入了研发，他们的研究结果表明，在并行计算和云计算的任务当中，进行调度和分配的时候，会遇到一些负载的问题，其中很多问题甚至属于复杂的NP-Hard问题。负载均衡的算法和任务调度的算法有很大的关联性，效果也是比较好的。负载均衡是一种提升并行计算之中计算机资源利用效率的最重要的技术。在对计算机资源进行调度和对计算任务进行分配的过程中，最关键的技术领域则是调度算法和调度模型。选择最为恰当的调度模型和调度算法进行搭配，可以最大程度地實现任务调度的负载均衡处置。

1.1 调度模型

分布式模型和集中式模型是动态任务调度分配表中最为常见的两种，动态任务管理器是在分布式原理的基础上设计出来的，在实际调度操作的实收，投入到应用之中的调度方法有Gearman、Falkon等方法，这些方法都有很多的实际应用的例子。上述几种调度模型均可以与其对应的基础调度算法互相之间达到调和的效果，以此来保证系统运行方面的负载可以达到均衡，在这之中，尤其突出的是名为Gearman的调度模式。和这种模型有关的负载均衡运算可以得到良好的运用。

1.2 调度算法

和负载均衡有关的调度算法可以分为两个大类：第一，静态渐变的交流算法动态的传播模式，动态的模式和静态渐变的模式有细微的差异，突出表现在互相连接的节点方面，这些节点之间大都是运用均衡的方法实现系统负载的均衡。第二，动态共享均衡和均衡算法之间也有不同，常见的方法是通过几个随机分布的动态节点之间的均衡实现良好状态的最终效果的动态负载均衡，为了达到这种状态，各个负载节点之间通常不是链接紧密的。该文所研究的主要是动态均衡算法，现阶段学术界议论比较多的是随机轮训算法、负载均衡算法、任务窃取算法等，任务窃取算法就是Work-Stealing算法。

2  任务窃取算法

2.1 实现任务窃取有关的过程

任务窃取算法的实现基础是在任务窃取的基础方法之中，实现整个系统的负载均衡。任务窃取算法所要实现的价值，是均衡的任务分配，在进行任务分配的负载均衡的过程中，激发一些没有被利用的空闲节点，从而使得一些并非处于繁忙工作状态的节点可以解放出来部分空间，给那些空闲节点分配过去。从这种任务架构的内容上看，上述策略最终实现了任务之间的负载均衡。在进行任务截取的过程当中，相同的处理器之间可能有一些同样的双端队列，通过这些队列可以实现调用栈的随机调用，可以尝试在这些栈的底部插入部分栈程，如果遇到这样的栈程，在任务窃取器工作的时候，底端的栈程就可以实现恢复，然后进行删除，这样队列就会被认定为一个任务调度相关的栈。

当工作端发现负载出现不均的情况之时，需要运用任务窃取算法进行任务的窃取，并将窃取到的任务从窃取的栈之中弹出，将该栈给窃取端使用。这个步骤的基本操作为：第一，一个负载不均衡的服务器被设置为窃取端，并且设置其为想要窃取任务。第二，等待窃取请求的窃取端服务器等待接收窃取任务，等待中心调度器发来的可以窃取调度任务的信息，窃取端根据任务处理器发过来的信息询问每一个处理器所控制的窃取栈，如果这个栈不是空的，那么就设置窃取栈之中的元素当作窃取的服务器。第三，如果窃取的栈是空的，窃取端就会随机选择另外一个处理器进行窃取，经过不断地寻找迭代，最终选到可以窃取任务的处理器，之后对该处理器进行访问，处理机所窃取的任务就会自动地加入到自身的队列任务之中，任务队列之间就可以随机地完成分配的任务。

2.2 任务窃取算法的任务数量策略

在任务数量的选择策略方面，传统的任务窃取算法有3种进行数量计算的策略可供选择，分别是乘数级别算法。二分法级数算法以及加法级数算法。第一，乘数级别算法。当已经明确窃取任务的数量的时候，乘数级别的算法对当前进行策略分析相关的任务数进行计算，对处理机不断进行改变，任务的数量会呈现出乘数级别的增长。第二，二分级数方法。如果需要窃取的任务数量是特定的，遇到紧急的情况需要根据队列统计的任务获取处理机的工作量，对工作量进行简单的计算，之后选择总处理队列之中的1/2的任务。第三，加法级数的方法。当确定需要窃取的任务数量之后，采用加法级数的策略会针对当前正在执行的工作进行分析，随后会根据加法技术的改变对任务机进行处理，所处理的任务数量根据加法级数逐步增加。上述3种方法在不同的场合均有所使用。

2.3 工作窃取算法的时机选择

工作窃取算法在窃取的时间的选择特点方面可以归纳成两种策略分类，即对于空闲节点的窃取和对即将处于闲置状态的节点的窃取。

2.3.1 与空闲节点有关的窃取

如果遇到和任务窃取相关的任务，第一步是服务器向处理机发出指令，命令任务机开始执行任务窃取的动作，任务调度中心首先提出任务窃取的请求。和中心调度有关的服务器就会开始对各种机器的状态进行调查，根据运行状态下的机器的动态，给服务器反馈信息。这样就选择出了可以进行任务处理的处理机，任务窃取的处理机就可以进行任务的操作，实现任务的窃取。还有一些处于满负荷运行状态的任务处理机的工作状态就会有所改变。

2.3.2 和空闲节点有关的任务窃取

如果某个正在执行任务的节点执行完了整个任务，这个时候就会接收到任务处理的请求，那么任务处理过程当中的空闲节点就会进行任务回程。

在实践中运用的情况是，上述两种选择的策略都既有优点又有缺点，还是会根据不同的算法对任务执行的策略有所选择。

3  改进型Work-Stealing算法

之前已经论述过的工作窃取算法只是停留在比较原始的阶段当中，与任务窃取算法有关的任务数量和任务的策略一般是比较传统的类型，尽管这些策略在执行方面已经有可能实现负载均衡的部分问题，但是到目前为止，很多算法的研究依然停留在与策略组合有关的阶段，均是进行静态的研究，这样就无法实现和并行计算相关的时序性要求。

3.1 相关算法的流程

该文所研究的窃取算法的第一步需要确定一个处理机，同时将其称为窃取机，窃取机在工作的时候，通过窃取所获得的任务调度中心的请求不一样，服务器主动根据负载的情况，将负载的运算结果报告给主机，服务器会根据负载的不同做出选择，根据负载最优的那个实现负载均衡。候选机的选择有如下几个步骤。

第一，任务调度中心对服务器之中已经开始进行轮候的各个处理机的状态进行问询，了解每一个可以处理的任务的最大队列可能性，通过对队列任务进行比较选择一个最为适当的处理机种类，将这种类型的处理机中的一个选择为轮候的处理机，在此之后将窃取的相关信息通过进程信息系统反馈给窃取机。

第二，经过上述步骤之后，窃取机可以收获任务的授权，在处于进程之中的任务机器进行选择，对于任务进程的调度而言有可能出现延迟的问题，如果窃取的任务和获取信号的强弱有关，这些进程的信息获取会在经过一定的时点时有适当延迟，经过一段时间之后才能够转播出现。窃取機会进行简单的选择操作，根据窃取的任务的数量进行分配选择确定完成之后，到被窃取的数量最终达到最大的数量级别为止。

3.2 如何对算法进行改进

在笔者的研究过程中，改进型算法一般都是和工作窃取方法的任务匹配相关的，根据任务机的实际巡行状态，可以对任务实现合理分配，上文论述过分配的步骤如何实现，和该文的流程处理有关联。

窃取时机的算法细节为：第一步遍历所有的处理机，选取数个初始化的处理机，将其设置为窃取处理机。在任务流程方面，第一步开始计算待窃取的任务数量，第二步对这些任务实现窃取并开始执行。

3.3 实验数据方面的对比

通过搭建原型系统对改进型工作窃取算法的实验表明，原型系统当中的十天服务器客户端，实现的任务负载最高纪录为10台，实现的负载任务量为10个，与传统的计算方法相比，在传统的计算方法当中，有3种和任务窃取密切关联的任务组合策略，3种任务组合策略和2种随机组合策略都有实验对照组。对比的结果发现，改进型算法的优势特别大，其优异表现在，可以进行不断的动态改变，使得可以获得的动态窃取的任务数量出现变动，和该文有关的动态窃取平衡算法实现了动态的均衡，负载的方面非常均衡，和该文研究有关的窃取数量和时机的选择不算复杂。

4  结语

计算机科学技术的飞速发展要求在并行计算的信息系统当中，通过任务调度的方法实现资源的有效配置，但是目前的技术在任务的均衡分配方面还存有不足。该文通过改进和设计一种动态均衡的工作窃取算法，实现任务分配的效率。该文通过对日常比较常见的窃取算法和任务调度模型进行分析，着重分析了任务窃取算法的工作策略，通过最大负载优势的传统工作窃取算法的改进，可以完善这种算法对于动态变化系统的数据处理的改进要求，实现较强的实时均衡负载。

参考文献

[1] 李坤.基于动态反馈机制的服务器负载均衡算法研究[J].电子科技，2015，28（9）：45-49.

[2] 向建军，白欣，左继章.一种用于实时集群的多任务负载均衡算法[J].计算机工程，2003（12）：36-38.

①作者简介：王涛（1996，2—），男，汉族，湖北黄冈人，本科，研究方向：计算机科学与技术。