基于多核处理器平台的公平调度算法

doi:10.3785/j.issn.1008-973X.2011.09.009

2011, Vol. 45

Issue (9): 1566-1570 DOI: 10.3785/j.issn.1008-973X.2011.09.009

计算机技术﹑电信技术

基于多核处理器平台的公平调度算法

刘加海1,2,杨茂林2

1.浙江大学城市学院信息与电子工程学系,浙江杭州 310015；2. 浙江大学软件学院,浙江宁波 315103

Fair scheduling algorithm on multi-core platforms based platforms

LIU Jia-hai1,2, YANG Mao-lin2

1. Department of Information Science and Electronic Engineering, Zhejiang University City College,
Hangzhou 310015, China; 2. College of Software Technology , Zhejiang University ,Ningbo 315103, China

全文: PDF HTML

摘要：

为了减少多核处理器系统全局调度算法中共享L2cache抖动,在Pfair调度算法基础上提出一种新的Cache感知的软实时公平调度算法.通过对WSS(work set size)、子任务截止时间和任务负载建立多因素优先级模型,并将此优先级模型应用到改进后的Pfair算法中,该算法的调度决策在系统负载较重的系统中对WSS具有自适应性.模拟实验结果显示:在对称4核和8核处理器系统中,该算法任务丢失率低,且在系统负载重时能够减少共享L2cache抖动,其整体调度性能优于传统的G-EDF(global-earliest deadline first)调度算法和Pfair调度算法.

Abstract:

A new cache-aware scheduling algorithm based on Pfair scheduling algorithm for soft real-time tasks on multi-core platforms was proposed to reduce the shared L2cache thrashing of global scheduling algorithm on multi-core processors. The task priority model of the proposed algorithm which was used in the extended Pfair scheduling algorithm was established by the work set size (WSS), the sub-task deadline, and the task utilization. The scheduling decision of the proposed algorithm is selfadaptive for WSS on heavy-loaded systems. Comparing with the traditional global-earliest deadline first (G-EDF) scheduling algorithm and the Pfair scheduling algorithm, the proposed algorithm can obtain lower task deadline miss rate and the L2-cache thrashing rate on the heavy-loaded multi-core processors. Consequently, the overall performance of the proposed algorithm is better than the other two scheduling algorithms.

出版日期: 2011-09-01

TP 301.6

作者简介: 刘加海(1960-),男,教授,博士,从事计算机应用、信号处理、电子器件等研究.E-mail：Ljhqyyq@yahoo.com.cn

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	作者相关文章

引用本文:

刘加海,杨茂林. 基于多核处理器平台的公平调度算法[J]. J4, 2011, 45(9): 1566-1570.

LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core platforms based platforms. J4, 2011, 45(9): 1566-1570.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2011.09.009 或 https://www.zjujournals.com/eng/CN/Y2011/V45/I9/1566

［1］ FEDOROVA A, SELTZER M, SMALL C, et al. Performance of multithreaded chip multiprocessors and implications for operating system design ［C］ ∥ Proceeding of the USENIX 2005 Annual Technical Conference. Anaheim: IEEE, 2005: 26-26．
［2］ JAIN R, HUGHS C, ADVE S. Soft realtime scheduling on simultaneous multithreaded processors ［C］ ∥ Proceeding of the 23rd RealTime System Symposium. Washington D. C: IEEE, 2002: 134-145．
［3］ SNAVELY A, TULLSEN D, VOELKER G. Symbiotic job scheduling with priorities for a simultaneous multithreading processor ［J］. SIGMETRICS Performance Evaluation Review, 2000, 30(1): 66-76．
［4］成杏梅,刘鹏,顾雄礼,等.支持多线程处理器的实时操作系统实现研究［J］. 浙江大学学报:工学版,2009,43(7)：1177-1181．
CHENG Xingmei, LIU Peng, GU Xiongli, et al. Study on implementation of realtime operating system that supports multithreading processor ［J］. Journal of Zhengjiang University:Engineering Science, 2009, 43(7): 1177-1181．
［5］ BLELLOCH G, GIBBONS P. Effectively sharing a cache among threads ［C］ ∥Proceeding of the 16th ACM Symposium on Parallelism in Algorithms and Architectures. Barcelona: IEEE, 2004: 235-244．
［6］ KIM S, CHANDRA D, SOLIHIN Y. Fair cache sharing and partitioning in a chip multiprocessor architecture ［C］ ∥ Proceeding of the 13rd IEEE International Conference on Parallel Architecture and Compilation Techniques. Washington D. C: IEEE, 2004:111-122．
［7］ ANDERSON J, SRINIVASAN A. Earlyrelease fair scheduling ［C］ ∥ Proceeding of the 12th Euromicro Conference on Realtime Systems. Stockholm: IEEE, 2000: 35-43．
［8］ ANDERSON J, CALANDRINO J M. Parallel realtime task scheduling on multicore platform ［C］ ∥ Proceeding of the 27th IEEE Realtime Systems Symposium. Rio de Janeiro: IEEE, 2006: 89-100．
［9］ ZHOU Benhai, QIAO Jianzhong, LIN Shukuan. Research on synthesis parameter realtime scheduling algorithm on multicore architectures ［C］ ∥ Proceedings of the 21st Annual International Conference on Chinese Control and Decision Conference. Guilin: IEEE, 2009: 5116-5120．
［10］ LIANG Thelee, HUANG Yuanchang, CHAO Shuwei. A hybrid task scheduling for multicore platforms ［C］ ∥ 2008 2nd International Conference on Future Generation Communication and Networking Symposia. Sanya: IEEE, 2008: 44-45．
［11］ LAKSHMANAN K, RAJ R, LEHOCZKY J. Partitioned fixedpriority preemptive scheduling for multicore processors ［C］ ∥ Proceedings of the 21st Euromicro Conference on RealTime Systems. Dublin: IEEE, 2009: 239-248．
［12］ LEONTYEV H, ANDERSON J. Generalized tardiness bounds for global multiprocessor scheduling ［C］∥ Proceeding of the 28th IEEE RealTime Systems Symposium. Tucson: IEEE, 2007: 413-422．
［13］ CALANDRINO J M, ANDERSON J. Cacheaware realtime scheduling on multicore platforms: heuristics and a case study ［C］ ∥ Proceedings of the 20th Euromicro Conference on RealTime Systems. Prague: IEEE, 2008: 299-308．
［14］ CALANDRINO J M, ANDERSON J. On the design and implementation of a cacheaware multicore real time scheduler ［C］ ∥ Proceedings of the 21st Euromicro Conference on RealTime Systems. Dublin: IEEE, 2009:194-204．
［15］ ANDERSON J, CALANDRINO J, DEVI U. Realtime scheduling on multicore platforms ［C］ ∥ Proceeding of the 12th IEEE RealTime and Embedded Technology and Applications Symposium. \
[S.l.\]:IEEE, 2006: 179-190．
［16］ BURCHARD A, LIEBEHERR A, OH Y, et al. New strategies for assigning realtime tasks to multiprocessor systems ［J］. IEEE Transactions on Computers, 1995, 44(12): 1429-1442．

[1]	刘加海,杨茂林,雷航,廖勇. 共享资源约束下多核实时任务分配算法[J]. J4, 2014, 48(1): 113-117.
[2]	赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[3]	张俊超, 岳茂雄, 刘华锋. 结构先验约束的动态PET图像重建[J]. J4, 2012, 46(6): 961-966.
[4]	方水良, 姚嫣菲, 赵诗奎. 柔性车间调度的改进遗传算法[J]. J4, 2012, 46(4): 629-635.

Viewed

Full text

Abstract

Cited

Shared

Discussed