Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (4): 839-853.doi: 10.1007/s11390-019-1945-5

Special Issue: Computer Architecture and Systems

• Computer Architecture and Systems • Previous Articles     Next Articles

Improved Task and Resource Partitioning Under the Resource-Oriented Partitioned Scheduling

Ze-Wei Chen1, Hang Lei1, Member, CCF, Mao-Lin Yang1,*, Yong Liao1, Member, CCF, Jia-Li Yu2   

  1. 1 School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 610054, China;
    2 School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 610054, China
  • Received:2018-07-04 Revised:2019-05-23 Online:2019-07-11 Published:2019-07-11
  • Contact: Mao-Lin Yang E-mail:maolyang@126.com
  • Supported by:
    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61572112 and 61802052, and the Applied Basic Research Programs of Science and Technology Department in Sichuan Province of China under Grant No. 2019YJ0185.

PDF (PC)

157

Supplement

1

Coordinated partitioning and resource sharing have attracted considerable research interest in the field of real-time multiprocessor systems. However, finding an optimal partition is widely known as NP-hard, even for independent tasks. A recently proposed resource-oriented partitioned (ROP) fixed-priority scheduling that partitions tasks and shared resources respectively has been shown to achieve a non-trivial speedup factor guarantee, which promotes the research of coordinated scheduling to a new level. Despite the theoretical elegance, the schedulability performance of ROP scheduling is restricted by the heuristic partitioning methods used in the original study. In this paper, we address the partitioning problem for tasks and shared resources under the ROP scheduling. A unified schedulability analysis framework for the ROP scheduling is proposed in the first place. A sophisticated partitioning approach based on integer linear programming (ILP) is then proposed based on the unified analysis. Empirical results show that the proposed methods improve the schedulability of ROP scheduling significantly, and the runtime complexity for searching a solution is reduced prominently compared with other ILP-based approaches as well.

Key words: multiprocessor real-time scheduling; partitioned fixed-priority scheduling; shared resource; integer linear programming;

[1] Sha L, Rajkumar R, Lehoczky J P. Priority inheritance protocols:An approach to real-time synchronization. IEEE Trans. Computers, 1990, 39(9):1175-1185.
[2] Baker T P. Stack-based scheduling of realtime processes. Real-Time Systems, 1991, 3(1):67-99.
[3] Brandenburg B B, Gul M. Global scheduling not required:Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations. In Proc. the 2016 IEEE Real-Time Systems Symposium, November 2016, pp.99-110.
[4] Biondi A, Sun Y. On the ineffectiveness of 1/m-based interference bounds in the analysis of global EDF and FIFO scheduling. Real-Time Systems, 2018, 54(3):515-536.
[5] Han G, Zeng H, Natale M D, Liu X, Dou W. Experimental evaluation and selection of data consistency mechanisms for hard real-time applications on multicore platforms. IEEE Trans. Industrial Informatics, 2014, 10(2):903-918.
[6] Brandenburg B B, Anderson J H. Optimality results for multiprocessor real-time locking. In Proc. the 31st IEEE Real-Time Systems Symposium, November 2010, pp.49-60.
[7] Yang M, Wieder A, Brandenburg B B. Global real-time semaphore protocols:A survey, unified analysis, and comparison. In Proc. the 2015 IEEE Real-Time Systems Symposium, December 2015, pp.1-12.
[8] Huang W, Yang M, Chen J. Resource-oriented partitioned scheduling in multiprocessor systems:How to partition and how to share? In Proc. the 2016 IEEE Real-Time Systems Symposium, November 2016, pp.111-122.
[9] Yang M, Huang W, Chen J. Resource-oriented partitioning for multiprocessor systems with shared resources. IEEE Transactions on Computers, 2019, 68(6):882-898.
[10] Joseph M, Pandya P K. Finding response times in a realtime system. Comput. J., 1986, 29(5):390-395.
[11] Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 1973, 20(1):46-61.
[12] Guan N, Yi W. Fixed-priority multiprocessor scheduling:Critical instant, response time and utilization bound. In Proc. the 26th IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum, May 2012, pp.2470-2473.
[13] Bletsas K, Audsley N, Huang W H, Chen J J, Nelissen G. Errata for three papers (2004-05) on fixed-priority scheduling with self-suspensions. Technical Report, CISTER Research Center, 2015. http://193.136.60.49/docs/errata_for_three_papers_(200405)_on_fixed_priority_scheduling_with_self_suspensions/1440/view.pdf, March 2019.
[14] Chen J, Nelissen G, Huang W. A unifying response time analysis framework for dynamic self-suspending tasks. In Proc. the 28th Euromicro Conference on Real-Time Systems, July 2016, pp.61-71.
[15] Huang W, Chen J, Zhou H, Liu C. PASS:Priority assignment of real-time tasks with dynamic suspending behavior under fixed-priority scheduling. In Proc. the 52nd Annual Design Automation Conference, June 2015, Article No. 154.
[16] Liu C, Chen J. Bursty-interference analysis techniques for analyzing complex real-time task models. In Proc. the 35th IEEE Real-Time Systems Symposium, December 2014, pp.173-183.
[17] Chen J, Nelissen G, Huang W, Yang M, Brandenburg B, Bletsas K. Many suspensions, many problems:A review of self-suspending tasks in real-time systems. Real-Time Systems, 2019, 55(1):144-207.
[18] Baruah S, Bini E. Partitioned scheduling of sporadic task systems:An ILP-based approach. In Proc. the 2008 Conference on Design and Architectures for Signal and Image Processing, November 2008, pp.100-105.
[19] Wieder A, Brandenburg B B. Efficient partitioning of sporadic real-time tasks with shared resources and spin locks. In Proc. the 8th IEEE International Symposium on Industrial Embedded Systems, June 2013, pp.49-58.
[20] Davis R I, Burns A. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor realtime systems. Real-Time Systems, 2011, 47(1):1-40.
[21] Chen Z, Yang M, Lei H, Liao Y, Xie W. SET-MRTS:Schedulability experiment toolkit for multiprocessor realtime systems. Journal of Computer Applications, 2017, 37(5):1270-1275. (in Chinese)
[22] Block A, Leontyev H, Brandenburg B B, Anderson J H. A flexible real-time locking protocol for multiprocessors. In Proc. the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 2007, pp.47-56.
[23] Rajkumar R, Sha L, Lehoczky J P. Real-time synchronization protocols for multiprocessors. In Proc. the 9th RealTime Systems Symposium, December 1988, pp.259-269.
[24] Brandenburg B B. Improved analysis and evaluation of realtime semaphore protocols for P-FP scheduling. In Proc. the 19th IEEE Real-Time and Embedded Technology and Applications Symposium, April 2013, pp.141-152.
[25] Rajkumar R. Real-time synchronization protocols for shared memory multiprocessors. In Proc. the 10th International Conference on Distributed Computing Systems, May 1990, pp.116-123.
[26] Gai P, Lipari G, Natale M D. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In Proc. the 22nd IEEE Real-Time Systems Symposium, December 2001, pp.73-83.
[27] Lakshmanan K, de Niz D, Rajkumar R. Coordinated task scheduling, allocation and synchronization on multiprocessors. In Proc. the 30th IEEE Real-Time Systems Symposium, December 2009, pp.469-478.
[28] Nemati F, Nolte T, Behnam M. Partitioning real-time systems on multiprocessors with shared resources. In Proc. the 14th International Conference on Principles of Distributed Systems, December 2010, pp.253-269.
[29] Yang M, Chen J, Huang W. A misconception in blocking time analyses under multiprocessor synchronization protocols. Real-Time Systems, 2017, 53(2):187-195.
[30] Brandenburg B B. Blocking optimality in distributed realtime locking protocols. Leibniz Transactions on Embedded Systems, 2014, 1(2):Article No. 01.
[31] Brandenburg B B. The FMLP+:An asymptotically optimal real-time locking protocol for suspension-aware analysis. In Proc. the 26th Euromicro Conference on Real-Time Systems, July 2014, pp.61-71.
[32] Elliott G A, Anderson J H. An optimal k-exclusion real-time locking protocol motivated by multi-GPU systems. RealTime Systems, 2013, 49(2):140-170.
[33] Audsley N C. On priority assignment in fixed priority scheduling. Inf. Process. Lett., 2001, 79(1):39-44.
[34] Han J, Zhu D, Wu X, Yang L T, Jin H. Multiprocessor realtime systems with shared resources:Utilization bound and mapping. IEEE Trans. Parallel Distrib. Syst., 2014, 25(11):2981-2991.
[35] Han J, Tao X, Zhu D, Yang L T. Resource sharing in multicore mixed-criticality systems:Utilization bound and blocking overhead. IEEE Trans. Parallel Distrib. Syst., 2017, 28(12):3626-3641.
[36] Andersson B, Easwaran A. Provably good multiprocessor scheduling with resource sharing. Real-Time Systems, 2010, 46(2):153-159.
[37] von der Brüggen G, Chen J, Huang W, Yang M. Release enforcement in resource-oriented partitioned scheduling for multiprocessor systems. In Proc. the 25th International Conference on Real-Time Networks and Systems, October 2017, pp.287-296.
[38] Wieder A, Brandenburg B B. On spin locks in AUTOSAR:Blocking analysis of FIFO, unordered, and priority-ordered spin locks. In Proc. the 34th IEEE Real-Time Systems Symposium, December 2013, pp.45-56.
[39] Yang M, Lei H, Liao Y, Rabee F. Improved blocking time analysis and evaluation for the multiprocessor priority ceiling protocol. J. Comput. Sci. Technol., 2014, 29(6):1003-1013.
[40] Schliecker S, Negrean M, Ernst R. Response time analysis on multicore ECUs with shared resources. IEEE Transactions on Industrial Informatics, 2009, 5(4):402-413.
[41] Baruah S K, Bonifaci V, Bruni R, Marchetti-Spaccamela A. ILP-based approaches to partitioning recurrent workloads upon heterogeneous multiprocessors. In Proc. the 28th Euromicro Conference on Real-Time Systems, July 2016, pp.215-225.
[1] Ning Xu, Yu-Chun Ma, Jia Liu and Shou-Chun Tao. Thermal-Aware Post Layout Voltage-Island Generation for 3D ICs [J]. , 2013, 28(4): 671-681.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Liu Xiaohui;. Processing Expertise Systematically[J]. , 1991, 6(2): 121 -134 .
[2] Zhou Jianqiang; Yang Liqun; Pan Shilei; Tan Hong;. BSD/I18N—Internationalization of the 4.3BSD U N IX System[J]. , 1993, 8(4): 51 -60 .
[3] Liu Zhipong; Liu Qun; Zhang Xiang;. Efficient Realization of Frequently Used Bijections on Cube-Connected Cycles[J]. , 1995, 10(4): 298 -309 .
[4] Wang Xianzhu; Liao Heng; Li Sanli;. DYNAMEM-A Microarchitecture for Improving Memory Disambiguation at Run-Time[J]. , 1996, 11(6): 589 -600 .
[5] Luo Junzhou; Gu Guanqun;. CIMS Network Protocol and Its Net Models[J]. , 1997, 12(5): 476 -481 .
[6] Hu Weiwu; Xia Peisu;. Out-of-Order Execution in Sequentially Consistent Shared-Memory Systems:Theory and Experiments[J]. , 1998, 13(2): 125 -140 .
[7] Lao Zhiqiang; Pan Yunhe;. A Knowledge Representation Model for Video-Based Animation[J]. , 1998, 13(3): 228 -237 .
[8] G.Huet;. A Crash Course in λ-Calculus[J]. , 1998, 13(6): 546 .
[9] MENG Bo; GUO Lei; CHEN Shifu;. DPAL: Deductive Language for Embroidery Pattern Assembling[J]. , 2000, 15(6): 625 -628 .
[10] Xiang-Qian Wu, Kuan-Quan Wang, and David Zhang. Wavelet Energy Feature Extraction and Matching for Palmprint Recognition[J]. , 2005, 20(3): 411 -418 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved