随着计算机及网络技术的发展,大规模并行分布式处理系统得到了广泛的应用。对于一个分布式系统而言,多个节点之间如何进行动态的任务分配调度,即动态负载均衡,在很大程度上影响着系统的性能,因而具有较高的理论研究价值和应用前景,受到了人们长期的关注。近年来,各国研究人员对此进行了大量的研究,提出了一系列的动态负载均衡算法。但这些算法并没有完全解决目前存在的问题,因此仍有必要对分布式系统的动态负载均衡进行进一步的研究。本文对负载均衡所涉及的各个方面,包括概念、分类、特点、算法机制、驱动策略、难点、算法步骤等进行了详细的讨论,总结了负载均衡的研究现状,同时还重点分析比较了现有的多个静态和动态负载均衡算法,指出了它们各自的特点和缺陷。在上述讨论的基础之上,本文从网络基础体系结构——拓扑出发,通过对常见的网孔、超立方和网状拓扑进行逻辑上的改造,根据本文中所给法则将物理拓扑划分为多个物理区域并指定每个区域的信息中心节点,必要时对这些信息中心节点组成的二级逻辑分区再指定二级信息中心节点,依此类推,最后使得物理拓扑形成逻辑上的层次结构。通过推导和计算可以证明,网络上的通信经这样的层次处理后,能够从局部区域扩展到整体,确实减少了很多基础的通信开销。基于上述的层次方法,本文提出了一个新的动态负载均衡算法,能够较好解决已有算法的诸如稳定性不够、应用比较单一、通用性不够等缺陷和不足。在此基础之上,本文还提出了一个基于预测的算法机制,该机制能够应用于均衡算法使得节点负载信息能够被准确及时的获取,从而为任务的迁移提供更好的依据;并由此建立了一个基于预测的层次负载均衡模型。算法的主要思想是通过各个局部区域的优化达到系统整体的接近最优化并特别考虑了任务之间的相互关系和系统内节点性能可能存在的差异;算法还通过改进传统的驱动策略,使用新的任务调度规则,在改善底层通信的基础上,使得系统减少了较多的额外开销,提高了算法的效率。该算法的主要特点是:⑴自适应参数可调。算法不是单一的使用某种驱动策略,而是在系统运行过程中动态调整负载阈值和参数,视用户对系统的要求选择参数值,从而获得更好的性能表现。⑵系统稳定,不会出现颠簸。算法中局部区域的使用,使得节点处理机上任务的迁移首先在内部区域上进行,必要时再进行区域之间的迁移;同时算法改进了以往的驱动策略,迁移必须从重载节点到轻载节点,目的性强,避免了一些效率不高的迁移和对节点不必要的打扰。⑶简单实用。算法没有采用基于人工智能理论等耗费较大的调度方法,而是使用局部优化带动全局优化的思想方法和较有针对性的“极端”任务调度方法,除了增加一定空间耗费和任务迁移本身带来的通信路径上的开销外,额外开销比较少。⑷具有较好的通用性。算法可以适用于目前最常见的网孔和超立方拓扑构成的同构、异构分布式系统,也可以推广到最一般的网状拓扑。论文还通过实验比较和实例分析验证了层次策略负载均衡算法的正确性和有效性。因此,本文提出的层次策略负载均衡算法确实能够比较有效和灵活地解决分布式系统的负载均衡问题,从而弥补了现有算法存在的一些缺陷。