论文部分内容阅读
集群系统的关键问题在于如何有效利用系统范围内的资源。负载平衡算法是实现资源高效利用的重要手段,进程迁移机制是负载平衡算法的一种有效实施机制。 本文针对资源异构集群系统中的资源共享和有效利用问题,构建了一个异构集群系统资源共享与负载平衡框架HRSLBF。HRSLBF框架由基于多种资源的负载平衡算法LBMR和抢占式进程迁移机制组成。HRSLBF框架的一个重要特点是能够协调考虑集群系统中多种资源的平衡使用。在HRSLBF框架中,所有调度都是从全局资源共享、协调使用的角度进行的。因此,HRSLBF框架能够从根本上实现系统资源的平衡使用,提高系统的性能。 在HRSLBF框架中,我们提出了一种基于多种资源的负载平衡算法LBMR。LBMR算法的主要思想有三点:第一,基于合理选择和定义的资源负载向量,综合考虑进程迁移对源节点和目标节点资源利用率的影响,通过向量运算协调多种资源的平衡使用;第二,基于最小k子集随机算法,采用信息Cache提供的负载信息作为负载平衡算法位置策略的选择依据;第三,基于进程生命时间的概率分布,根据迁移进程减速(slowdown)数学期望值的改善程度,选择适合于迁移的进程。LBMR算法是一种对称启动算法,它包含两种发送者启动算法:位置优先发送者启动算法LFSILB和选择优先发送者启动算法SFSILB,以及一种接收者启动算法RILB。 进程迁移机制是负载平衡算法的实际执行机制。集群计算都需要某种层次上的通信和同步,因此,进程迁移机制应当提供对网络连接迁移的支持,达到保持进程迁移前的网络连接的目的,实现迁移进程网络连接的透明性。网络连接的透明性要求常常导致进程的源节点剩余相关性,IPC通信源节点剩余相关性对迁移进程的性能有着巨大的负面影响。为此,我们研究并实现了一种基于Socket套接字迁移的TCP连接迁移技术,部分解决了进程迁移机制中TCP网络连接透明性和源节点通信剩余相关性的问题。 为了描述集群系统中负载信息的非精确性和部分性这两个特点,我们提出了信息的弱一致性(Weak Consistency)模型。信息的弱一致性模型是负载平衡算法进行有效调度决策时必须重点考虑的一个问题。为了有效利用系统中的弱一致性信息,使之成为负 国防科学技术大学研究生院学位论文载平衡调度的决策依据,我们提出了一种基于信息弱一致性模型的最小k子集随机算法,并进行了性能模拟分析。模拟结果表明,最小k子集随机算法能够有效地提高负载平衡算法决策的正确性。 基于最小 k子集随机算法,我们设计并实现了一种具有双 Cache结构的信息 Cache机制。信息Cache通过特殊的替换算法,保证两个Cache中的信息分别为系统中负载最大的k个超载节点的信息和负载最小的k个欠载节点的信息。这样,进行负载平衡调度时,无论节点处于哪种状态都能够迅速地使用其中一个与自身状态相反的Cache中的信息,作为负载平衡决定的依据。这种双Cache的信息管理机制非常适合于对称启动算法。 调度算法是一个应用相关的问题,工作负载的特性,尤其是进程生命时间的分布特性,对干调度算法的设计有着重要的影响。大量的研究表明,进程生命时间服从Heavily-Tailed分布。在这种分布形式下,抢占式进程迁移机制是一种非常有效的负载平衡实现机制。基于这些研究,我们得出了异构集群系统中适合于进行迁移的进程的最小年龄,并应用于LBMR算法的选择策略中。 本文采用踪迹驱动的方法进行了大量的模拟和分析。模拟结果表明:在资源异构集群系统中,基于多种资源的负载平衡算法LBMR能够有效地平衡系统负载,提高资源利用率。而且,系统的异构性越强,LBMR算法就越能够体现出比其它算法更好的性能效果。