文档介绍：基于计算机动态任务分配表的负载均衡新算法
摘 要:计算机技术飞速发展的今天,在并行计算机系统之中,任务调度依旧是解决多资源配置的最有效方法之一,但是当前的任务调度依然存在着一些困境,其中的一个难题是NP-Hard问题,即和任随机地完成分配的任务。
任务窃取算法的任务数量策略
在任务数量的选择策略方面,传统的任务窃取算法有3种进行数量计算的策略可供选择,分别是乘数级别算法。二分法级数算法以及加法级数算法。第一,乘数级别算法。当已经明确窃取任务的数量的时候,乘数级别的算法对当前进行策略分析相关的任务数进行计算,对处理机不断进行改变,任务的数量会呈现出乘数级别的增长。第二,二分级数方法。如果需要窃取的任务数量是特定的,遇到紧急的情况需要根据队列统计的任务获取处理机的工作量,对工作量进行简单的计算,之后选择总处理队列之中的1/2的任务。第三,加法级数的方法。当确定需要窃取的任务数量之后,采用加法级数的策略会针对当前正在执行的工作进行分析,随后会根据加法技术的改变对任务机进行处理,所处理的任务数量根据加法级数逐步增加。上述3种方法在不同的场合均有所使用。 工作窃取算法的时机选择
工作窃取算法在窃取的时间的选择特点方面可以归纳成两种策略分类,即对于空闲节点的窃取和对即将处于闲置状态的节点的窃取。
与空闲节点有关的窃取
如果遇到和任务窃取相关的任务,第一步是服务器向处理机发出指令,命令任务机开始执行任务窃取的动作,任务调度中心首先提出任务窃取的请求。和中心调度有关的服务器就会开始对各种机器的状态进行调查,根据运行状态下的机器的动态,给服务器反馈信息。这样就选择出了可以进行任务处理的处理机,任务窃取的处理机就可以进行任务的操作,实现任务的窃取。还有一些处于满负荷运行状态的任务处理机的工作状态就会有所改变。
和空闲节点有关的任务窃取
如果某个正在执行任务的节点执行完了整个任务,这个时候就会接收到任务处理的请求,那么任务处理过程当中的空闲节点就会进行任务回程。
在实践中运用的情况是,上述两种选择的策略都既有优点又有缺点,还是会根据不同的算法对任务执行的策略有所选择。
3 改进型Work-Stealing算法
之前已经论述过的工作窃取算法只是停留在比较原始的阶段当中,与任务窃取算法有关的任务数量和任务的策略一般是比较传统的类型,尽管这些策略在执行方面已经有可能实现负载均衡的部分问题,但是到目前为止,很多算法的研究依然停留在与策略组合有关的阶段,均是进行静态的研究,这样就无法实现和并行计算相关的时序性要求。
相关算法的流程
该文所研究的窃取算法的第一步需要确定一个处理机,同时将其称为窃取机,窃取机在工作的时候,通过窃取所获得的任务调度中心的请求不一样,服务器主动根据负载的情况,将负载的运算结果报告给主机,服务器会根据负载的不同做出选择,根据负载最优的那个实现负载均衡。候选机的选择有如下几个步骤。
第一,任务调度中心对服务器之中已经开始进行轮候的各个处理机的状态进行问询,了解每一个可以处理的任务的最大队列可能性,通过对队列任务进行比较选择一个最为适当的处理机种类,将这种类型的处理机中的一个选择为轮候的