Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (07): 1910-1912.DOI: 10.3724/SP.J.1087.2012.01910

• Network and distributed techno • Previous Articles     Next Articles

DPST: a scheduling algorithm of preventing slow task thrashing in heterogeneous environment

DUAN Han-cong,LI Jun-jie,CHEN Cheng,LI Lin   

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China
  • Received:2012-01-29 Revised:2012-03-29 Online:2012-07-05 Published:2012-07-01
  • Contact: LI Jun-jie
  • Supported by:

    A new generation of broadband wireless mobile communication network

异构环境下降低慢任务抖动的调度算法——DPST

段翰聪,李俊杰,陈宬,李林   

  1. 电子科技大学 计算机科学与工程学院,成都611731
  • 通讯作者: 李俊杰
  • 作者简介:段翰聪(1973-),男,重庆人,副教授,博士,主要研究方向:云计算、内容分发网络;李俊杰(1985-),男,四川宜宾人,硕士研究生,主要研究方向:分布式存储与分布式计算;陈宬(1985-),男,四川成都人,硕士研究生,主要研究方向:分布式存储与分布式计算;李林(1981-),男,四川成都人,副教授,博士,主要研究方向:网络安全、分布式计算。
  • 基金资助:

    国家“新一代宽带无线移动通信网”科技重大专项(2010ZX03004-001-02; 2011ZX03002-003-02; 20122012ZX03002-004-004);广东省部产学研重大基金资助项目(2010A090200082)

Abstract: With regard to the thrashing problem of load-balancing algorithm in heterogeneous environments, a new scheduling algorithm called Dynamic Predetermination of Slow Task (DPST) was designed to reduce the probability in slow task scheduling and improve load-balancing. Through defining capability measure of heterogeneous task in heterogeneous nodes, the capacity of nodes which performed heterogeneous tasks was normalized. With the introduction of predetermination, thrashing result from heterogeneous environments was reduced. By using double queues of slow task and slow node, the efficiency of scheduling was improved. The experimental results show that the thrashing times in heterogeneous environments fell by more than 40% compared with Hadoop. Because thrashing times have been reduced effectively, DPST algorithm has better performance in reducing average response time and increasing system throughput in heterogeneous environments.

Key words: cloud computing, load-balancing, slow task, heterogeneity, thrashing

摘要: 为解决在异构计算环境中现有的云计算负载均衡算法存在的慢任务频繁抖动的问题,提出了一种能减低慢任务调度抖动概率的算法——DPST算法。首先通过定义一种异构计算节点中异构任务的能力度量,对执行异构任务的节点处理能力进行了归一化;然后通过引入节点能力预判机制,降低慢任务无效调度的次数;并且利用慢任务和慢节点双队列机制,提高了调度效率。实验结果表明,DPST相对于Hadoop平台在异构环境下任务调度的抖动次数下降了40%以上。由于有效降低了任务调度的抖动次数,在异构环境中DPST算法能明显地缩短任务的平均响应时间并提高系统的吞吐量。

关键词: 云计算, 负载均衡, 慢任务, 异构, 抖动

CLC Number: