分布式环境下基于整体最优的资源分配研究

分布式环境下基于整体最优的资源分配研究

大连理工大学  张丹闯

在科技化和信息化飞速发展的今天,计算机系统已经开始由单机系统向分布式系统方向转变。如何在分布式环境下通过互连网络整合不同资源以提供更高的计算和服务能力已经成为目前关注的焦点。本文设计并实现一种基于资源代理的网格平台,针对两种典型的分布式环境中的资源分配问题进行研究。 用户应用在分布式环境中执行时,往往被分成多个独立或者非独立的任务,非独立的任务之间存在执行顺序和数据传输。本文分别针对独立任务和非独立任务资源分配问题建立问题描述模型,并进行博弈分析,找出纳什均衡状态并证明其存在,分析任务之间博弈对整个系统性能的影响。在独立任务的资源分配模型中,集体利益可以由所有任务的总成本表现出来,是反应系统性能的重要指标。本文通过改变博弈参与人的支付函数提出基于集体利益最大化的资源分配算法(RACGR)在非独立任务的资源分配模型中,任务之间的关系可以用DAG图表示,集体利益体现为调度长度,本文提出一种基于拓扑排序的资源分配算法(TSBS),通过对任务进行排序减少任务之间的静态博弈对系统性能的影响,从而缩短调度长度,提升系统性能。 本文通过仿真实验根据独立和非独立任务的不同性能指标将两种资源分配算法分别与轮询算法、Max-min算法和Min-min算法等进行比较。RACGR算法在系统总成本和资源公平性方面有较好的表现,分析资源花费函数的设置对资源上任务执行数量的影响。而TSBS算法对随机产生的DAG图和现实应用的DAG图都可以有效缩短调度长度,提高资源利用率。

分布式环境下基于整体最优的资源分配研究