Please wait a minute...
J4  2011, Vol. 45 Issue (9): 1566-1570    DOI: 10.3785/j.issn.1008-973X.2011.09.009
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
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      


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.

Published: 01 September 2011
CLC:  TP 301.6  
Cite this article:

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

URL:     OR


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

[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] LIU Jia-hai, YANG Mao-lin, LEI Hang, LIAO Yong. Multicore real-time task allocation algorithms with shared resource constraints[J]. J4, 2014, 48(1): 113-117.
[2] ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. J4, 2013, 47(6): 1022-1030.
[3] ZHANG Jun-chao, YUE Mao-xiong, LIU Hua-feng. Dynamic PET image reconstruction with Geometrical structure
prior constraints
[J]. J4, 2012, 46(6): 961-966.
[4] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. J4, 2012, 46(4): 629-635.