网格市场中服务质量驱动下的任务调度算法

doi:10.7523/j.issn.2095-6134.2011.1.013

中国科学院大学学报 ›› 2011, Vol. 28 ›› Issue (1): 86-93.DOI: 10.7523/j.issn.2095-6134.2011.1.013

网格市场中服务质量驱动下的任务调度算法

宋浒¹, 杨寿保¹, 刘晓茜¹, 郭良敏^1,2

1. 中国科学技术大学计算机科学与技术学院, 合肥 230027;
2. 安徽师范大学计算机科学与技术系, 芜湖 241000

收稿日期:2010-03-05 修回日期:2010-05-10 发布日期:2011-01-20
基金资助:
国家863项目(2006AA01A110)和国家自然科学基金(60273041)资助 

A quality-driven algorithm for task scheduling in grid market

SONG Hu¹, YANG Shou-Bao¹, LIU Xiao-Qian¹, GUO Liang-Min^1,2

1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China;
2. Department of Computer Science and Technology, Anhui Normal University, Wuhu 241000, China

Received:2010-03-05 Revised:2010-05-10 Published:2011-01-20

摘要/Abstract

摘要：

针对资源提供方不能完成用户所有任务的情况,提出一种服务质量驱动下的任务调度算法,即预算和截止时间限制下的最大任务完成数调度算法(DBCN).这种批调度算法结合了Min-min算法吞吐量较高和线性规划全局优化的优点,不仅考虑了用户的所有任务,同时还考虑了优先级较高的任务.实验结果表明,该算法在任务完成总数方面比经典算法Min-min和DBCT分别提高了约10.6%和22.0%,在优先级高的任务完成总数方面也有大幅度提高,分别约为20%和40%.

关键词: 网格市场, 服务质量, 预算和截止时间, 调度算法

Abstract:

We propose a quality-driven algorithm for task scheduling in grid market, which is deadline- and budget-constrained and maximizes number of completed tasks (DBCN). This algorithm combines the high throughput advantage of Min-min algorithm and the global optimization advantage of linear programming. Meanwhile the algorithm considers not only all the tasks but also those prior ones. Compared with the Min-min and DBCT classical algorithms, DBCN completes about 10.6% and 22.0% more tasks and about 20% and 40% more prior tasks, respectively.

Key words: grid market, QoS, deadline and budget, scheduling algorithm

中图分类号:

TP393

宋浒, 杨寿保, 刘晓茜, 郭良敏. 网格市场中服务质量驱动下的任务调度算法[J]. 中国科学院大学学报, 2011, 28(1): 86-93.

SONG Hu, YANG Shou-Bao, LIU Xiao-Qian, GUO Liang-Min. A quality-driven algorithm for task scheduling in grid market[J]. , 2011, 28(1): 86-93.

参考文献

[1] Buyya R, Abramson D, Giddy J. Economy driven resource management architecture for computational power Grids //PDPTA ’00: Proceedings of the 7th International Conference on Parallel and Distributed Processing Techniques and Applications. 2000.

[2] Ravi B, Sanjukta D, Robert G, et al. A market design for grid computing
[J]. INFORMS Journal on Computing, Forthcoming, 2007, 20(1):100-111.

[3] Stuer G, Vanmechelen K, Broeckhove J. A commodity market algorithm for pricing substitutable grid resources
[J]. Future Generation Computer Systems, 2007, 23(5):688-701.

[4] Buyya R, Murshe M, Abramson D. A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global grids //ICPDP ’02: The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications. Las Vegas, Nevada, USA, 2002.

[5] Buyya R, Abramson D, Giddy J. Nimrod/G: An architecture for a resource management and scheduling System in a Global Computational Grid //HPC ASIA 2000: 4th International Conference and Exhibition on High Performance Computing in Asia-Pacific Region. Beijing, 2000.

[6] Armstrong R, Hensgen D, Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions //HCW ’98: the 7th IEEE Heterogeneous Computing Workshop. 1998:79- 87.

[7] Freund R, Gherrity M, Ambrosius S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet //HCW ’98: the 7th IEEE Heterogeneous Computing Workshop. 1998: 184-199.

[8] Ibarra O, Kim C. Heuristic algorithms for scheduling independent tasks on nonidentical processors
[J]. Journal of the ACM, 1997, 77(2): 280-289.

[9] Buyya R, Giddy J, Abramson D. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications //AMS ’00: The Second Workshop on Active Middleware Services, Pittsburgh, USA, 2000.

[10] Garg S, Konugurthi P, Buyya R. A linear programming driven genetic algorithm for meta-scheduling on utility grids //ADCOM’ 08: The 16th International Conference on Advanced Computing and Communications, Chennai, India, 2008: 19-26.

[11] Wang Z, Cao J W. Committee-based evaluation and selection of grid resources for QoS improvement //Grid’ 09: The 10th IEEE/ACM International Conference on Grid Computing. Canada, 2009: 138-144.

[12] Vanmechelen K, Depoorter W, Broeckhove J. Economic grid resource management for CPU Bound Applications with hard deadlines //CCGrid’ 08: The 8th International Conference on Cluster Computing and the Grid. Lyon, France, 2008.

[13] Sundaram V, Chandra A, Weissman J. Exploring the throughput-fairness tradeoff of deadline scheduling in heterogeneous computing environments //ACM SIGMETRICS’ 08: The 2008 International Conference on Measurement and Modeling of Computer Systems. Annapolis, Maryland, USA, 2008.

[14] Buyya R, Murshed M. GridSim: A Toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing
[J]. The Journal of Concurrency and Computation: Practice and Experience, 2002, 14(13): 1175-1220.

[15] Land A, Doig A. An automatic method of solving discrete programming problems
[J]. Econometrica, 1960, 28: 497-520.

网格市场中服务质量驱动下的任务调度算法

A quality-driven algorithm for task scheduling in grid market

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	曹家燕, 邱玲. 一种基于有效容量的混合业务资源分配算法[J]. 中国科学院大学学报, 2014, 31(5): 685-690.
[2]	程振宇, 张灿, 和智涛, 孙恒. 基于3G网络视频传输的一种QoS控制方法[J]. 中国科学院大学学报, 2014, 31(1): 117-123.
[3]	叶浩, 薛开平, 洪佩琳, 卢汉成. 无线Ad Hoc网络中一种网络无关的 P2P流媒体优化传输方案[J]. 中国科学院大学学报, 2012, 29(4): 555-563.
[4]	黄彦彬, 杨寿保, 滕达, 赫卫卿, 王淑玲. WiMAX Mesh网络下具有QoS保障的动态握手方案[J]. 中国科学院大学学报, 2012, (3): 406-413.
[5]	杜瑞忠, 张焕国, 田俊峰. 基于多服务属性的网格信誉资源选择模型[J]. 中国科学院大学学报, 2011, 28(6): 811-817.
[6]	曾欢, 张灿, 陈德元. 空间通信网中音视频传输的应用层QoS控制与测试方法[J]. 中国科学院大学学报, 2011, 28(1): 108-115.
[7]	李芳, 陈德元, 涂国防, 侯秀红. 基于DiffServ over MPLS的深空通信网络QoS控制方法[J]. 中国科学院大学学报, 2009, 26(6): 803-811.
[8]	林刚, 杨学良. 区分服务模型在Internet2中的研究与发展[J]. 中国科学院大学学报, 2001, 18(1): 76-84.