使用确定随机Petri网对Hadoop公平调度的建模和性能分析

doi:10.11772/j.issn.1001-9081.2015.05.1255

计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1255-1261.DOI: 10.11772/j.issn.1001-9081.2015.05.1255

使用确定随机Petri网对Hadoop公平调度的建模和性能分析

何华¹, 林闯², 赵增华¹, 庞善臣³

1. 天津大学计算机科学与技术学院, 天津 300072;
2. 清华大学计算机科学与技术系, 北京 100084;
3. 中国石油大学计算机与通信工程学院, 山东青岛 266510

收稿日期:2014-12-22 修回日期:2015-03-29 出版日期:2015-05-10 发布日期:2015-05-14
通讯作者: 何华
作者简介:何华(1982-),女,山东济宁人,博士研究生,主要研究方向:计算机网络、系统性能模型及评价、随机Petri网; 林闯(1948-),男,辽宁沈阳人,教授,博士生导师,博士,CCF会员,主要研究方向:计算机网络、系统性能模型及评价、随机Petri网、逻辑推演、推理系统;赵增华(1974-),女,河南南乐人,副教授,博士,CCF会员,主要研究方向:无线网状网络、无线多媒体传感器网络、物联网; 庞善臣(1974-),男,山东嘉祥人,教授,博士,CCF会员,主要研究方向:可信计算、服务计算、云计算、Petri网.
基金资助:
国家自然科学基金资助项目(610172063,61272093).

HE Hua¹, LIN Chuang², ZHAO Zenghua¹, PANG Shanchen³

1. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China;
2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
3. College of Computer and Communication Engineering, China University of Petroleum, Qingdao Shandong 266510, China

Received:2014-12-22 Revised:2015-03-29 Online:2015-05-10 Published:2015-05-14

摘要/Abstract

摘要：

由于Hadoop能在同一时间处理多个用户提交的不同作业的多个任务,这使得用传统的方法对其进行建模和性能分析变得十分困难.为了解决这个问题,基于马尔可夫排队模型M/MMDP/C/K建立了一个随机Petri网(SPN)模型和一个确定随机Petri网(DSPN)模型来分别描述Hadoop调度中的数据状态和作业公平调度.通过设置DSPN中的使动谓词和随机开关来建模Hadoop公平调度和YARN公平调度.使用嵌入的马尔可夫链模型来分析单用户情景,而在分析多用户情景时则引入分解和迭代技术来减小模型的状态空间,从而避免产生状态爆炸问题.研究侧重于Hadoop中作业调度的平均性能,仅通过求解提出的分析模型,就可以对比和分析服务质量(QoS)的一些关键指标,如平均吞吐量、平均队列长度和平均时延.采用Matlab进行仿真:当每秒到达任务数大于等于20时,YARN算法的数据积压和平均时延明显少于公平算法;当每秒到达任务数大于等于30时,YARN算法的平均吞吐量明显高于公平算法.实验结果表明,YARN公平算法能够减少平均处理和排队等待时间,在平均吞吐量、平均队列长度和平均时延上明显优于公平算法.

Key words: Hadoop, MapReduce, fair scheduling, Stochastic Petri Net (SPN), Deterministic and Stochastic Petri Net(DSPN), Quality of Service (QoS)

中图分类号:

null

何华, 林闯, 赵增华, 庞善臣. 使用确定随机Petri网对Hadoop公平调度的建模和性能分析[J]. 计算机应用, 2015, 35(5): 1255-1261.

HE Hua, LIN Chuang, ZHAO Zenghua, PANG Shanchen. null[J]. Journal of Computer Applications, 2015, 35(5): 1255-1261.

参考文献

[1] BUYYA R, YEO C S, VENUGOPAL S. Market-oriented cloud computing: vision, hype, and reality for delivering IT services as computing utilities[C]// Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications. Washington, DC: IEEE Computer Society, 2008: 5-13.
[2] VAQUERO L M, RODERO M L, CACERES J, et al. A break in the clouds: towards a cloud definition [J]. ACM SIGCOMM Computer Communication Review, 2009, 39(1): 50-55.
[3] ALI K, CHOWDHARY H S. Cloud computing: the concept and it's applications[J]. The Journal of Research and Scholarly Activity of St Patrick's International College, 2014, 1(1): 28-35.
[4] MURTHY A C. The next generation of Apache Hadoop MapReduce [EB/OL]. [2014-12-01]. http://developer.yahoo.com/ blogs/hadoop/posts/2011/ 02/mapreduce-nextgen, 2011.
[5] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.
[6] LEE H, LEE D, RAMAKRISHNA R S. An enhanced grid scheduling with job priority and equitable interval job distribution[C]// Proceedings of the 1st International Conference on Grid and Pervasive Computing. Berlin: Springer, 2006: 53-62.
[7] PAGE A J, NAUGHTON T J. Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing[C]// Proceedings of the 19th IEEE International on Parallel and Distributed Processing Symposium. Piscataway: IEEE, 2005: 184-189.
[8] ATALLAH M J, LOCK C, MARINESCU D C, et al.Co-scheduling compute-intensive tasks on a network of workstations: model and algorithms[J]. Journal of Parallel and Distributed Computing, 1992, 16(4): 319-327.
[9] ASLANZADEH S, CHACZKO Z, CHIU C. Cloud computing-effect of evolutionary algorithm on load balancing[C]// Computational Intelligence and Efficiency in Engineering Systems, Studies in Computational Intelligence 595. Berlin: Springer, 2015: 217-225.
[10] JIAO J. Research on online task scheduling mechanism in cloud computing[J]. Open Automation and Control Systems Journal, 2014, 6: 927-933.
[11] FLOYD S, JACOBSON V. Link-sharing and resource management models for packet networks [J]. Networking, 1995, 3(4): 365-386.
[12] ROSTI E, SERAZZI G, SMIRNI E, et al.The impact of I/O on program behavior and parallel scheduling[C]// SIGMETRICS'98: Proceedings of the 1998 ACM SIGMETRICS Performance Evaluation Review. New York: ACM, 1998: 56-65.
[13] LEE W, FRANK M, LEE V, et al.Implications of I/O for gang scheduled workloads[C]// JSSPP'97: Proceedings of the Job Scheduling Strategies for Parallel Processing. Berlin: Springer, 1997: 215-237.
[14] WISEMAN Y, FEITELSON D G. Paired gang scheduling [J]. Parallel and Distributed Systems, 2003, 14(6): 581-592.
[15] MARSAN M A, CHIOLA G. On Petri nets with deterministic and exponentially distributed firing times[C]// Proceedings of the 7th European Workshop on Applications and Theory of Petri Net, LNCS 266. Berlin: Springer, 1987: 132-145.
[16] MOLLOY M K. Discrete time stochastic Petri nets[J]. IEEE Transactions on Software Engineering, 1985,SE-11(4): 417-423.
[17] LIN C, MARINESCU D C. Stochastic high-level Petri nets and applications [M]. Berlin: Springer, 1991: 459-469.
[18] MARSAN M A. Stochastic Petri nets: an elementary introduction[C]// Proceedings of the 9th European Workshop on Applications and Theory in Petri Nets. Berlin: Springer, 1990: 1-29.
[19] CIARDO G, TRIVEDI K S. A decomposition approach for stochastic reward net models [J]. Performance Evaluation, 1993, 18(1): 37-59.
[20] MAINKAR V, TRIVEDI K S. Fixed point iteration using stochastic reward nets[C]// PNPM'95: Proceedings of the 6th International Workshop on Petri Nets and Performance Models. Piscataway: IEEE, 1995: 21-30.
[21] BOLCH G, BRUZSA C, SZTRIK J. Modeling and simulation of Markov modulated multiprocessor systems with Petri nets[C]// Proceedings of the 7th European Simulation Symposium. Nuremberg: University of Erlangen, 1995: 1-5.
[22] BORTHAKUR D. The Hadoop distributed file system: Architecture and design[EB/OL].[2014-06-20]. http://hadoop.apache.org/docs/r0.18.0/hdfs_design.pdf.
[23] YANG T, TSANG D H K. A novel approach to estimating the cell loss probability in an ATM multiplexer loaded with homogeneous on-off sources[J]. IEEE Transactions on Communications, 1995, 43(1): 117-126.
[24] LEI L, LIN C, CAI J, et al.Performance analysis of wireless opportunistic schedulers using stochastic Petri nets[J]. IEEE Transactions on Wireless Communications, 2009, 8(4): 2076-2087.

使用确定随机Petri网对Hadoop公平调度的建模和性能分析

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	羌晓清, 景博, 邓森, 焦晓璇, 苏月. 基于模拟退火粒子群算法的不可靠测试点优化[J]. 计算机应用, 2015, 35(4): 1071-1074.
[2]	张斯捷柏青苏旸. null[J]. 计算机应用, 2013, 33(06): 1615-1618.
[3]	胡飞虎张丹丹杨慧媛马玲. 基于网络划分的多实例工作流模式解决方案[J]. 计算机应用, 2011, 31(05): 1420-1422.