计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (4): 839-853.doi: 10.1007/s11390-019-1945-5

所属专题： Computer Architecture and Systems

• • 上一篇    下一篇

一种面向资源的划分调度下改进的任务与资源划分方法

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
  • 收稿日期:2018-07-04 修回日期:2019-05-23 出版日期:2019-07-11 发布日期:2019-07-11
  • 通讯作者: Mao-Lin Yang E-mail:maolyang@126.com
  • 作者简介:Ze-Wei Chen is a Ph.D.candidate under the successive postgraduate and doctoral program in the School of Information and Software Engineering,University of Electronic Science and Technology of China (UESTC),Chengdu.He received his B.S.degree in software engineering from UESTC,Chengdu,in 2014.His research interests include the realtime system,real-time scheduling and synchronization,and cyber-physical systems.
  • 基金资助:
    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.

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

补充材料

1

协调划分和资源共享是实时多处理器系统领域中的研究热点。然而，求解最优划分是一个NP-hard问题。最近，学者们提出了一种面向资源的固定优先级划分（ROP）调度，在任务和共享资源的划分下整数加速比因子的可调度性保证，将协调的划分调度的理论研究推至到了新的高度。尽管在理论上实现了突破，但其采用的启发式划分方法仍然限制了其可调度性。本文主要讨论了ROP调度下任务和共享资源的划分问题。首先，提出了一个可调度性测试框架，并在该框架下，提出了一种基于整数线性规划（ILP）的划分方法。实验结果表明，所提出的方法大大提高了ROP调度的可调度性，并且与其他基于ILP的方法相比，显著降低了求解的时间复杂度。

关键词: 多处理器实时调度, 固定优先级划分调度, 共享资源, 整数线性规划

Abstract: 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.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘小惠;. Processing Expertise Systematically[J]. , 1991, 6(2): 121 -134 .
[2] 周建强; 杨立群; 潘世雷; 谈宏;. BSD/I18N—Internationalization of the 4.3BSD U N IX System[J]. , 1993, 8(4): 51 -60 .
[3] 刘群; 刘志勇; 张祥;. Efficient Realization of Frequently Used Bijections on Cube-Connected Cycles[J]. , 1995, 10(4): 298 -309 .
[4] 王显著; 廖恒; 李三立;. DYNAMEM-A Microarchitecture for Improving Memory Disambiguation at Run-Time[J]. , 1996, 11(6): 589 -600 .
[5] 罗军舟; 顾冠群;. CIMS Network Protocol and Its Net Models[J]. , 1997, 12(5): 476 -481 .
[6] 胡伟武; 夏培肃;. Out-of-Order Execution in Sequentially Consistent Shared-Memory Systems:Theory and Experiments[J]. , 1998, 13(2): 125 -140 .
[7] 劳志强; 潘云鹤;. 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] 孟波; 郭磊; 陈世福;. DPAL: Deductive Language for Embroidery Pattern Assembling[J]. , 2000, 15(6): 625 -628 .
[10] . 用于掌纹识别的小波能量特征的提取和匹配[J]. , 2005, 20(3): 411 -418 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：