Partitioned DM Scheduling for Sporadic Real-time Tasks Based on Interference Time in Parallel Machine
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [33]
  • |
  • Related [2]
  • | | |
  • Comments
    Abstract:

    Partitioned DM (deadline-monotonic) scheduling of sporadic real-time tasks is a classic research problem. This study proposes a partitioned scheduling algorithm PDM-FFD (partitioned deadline-monotonic first-fit decrease) with higher processor utilization for constrained-deadline sporadic tasks. In PDM-FFD, firstly tasks are sorted in non-decreasing order according to the relative deadline, then the first-fit strategy is utilized to select the processor core to allocate tasks, and each core adopts DM scheduling policy. Finally, a tighter schedulability determination method is obtained by analyzing the task interference time to determine the task schedulability. This study proves that the speedup factor of PDM-FFD is 3 - (3 + 1)/(m + ) and the time complexity is O(n2) + O(nm). = ∑τjτCj×uj/Dmax where τj belongs to the task set τ, Cj is the worst-case execution time, uj is the utilization, Dmax is the maximum relative deadline, n is the task number, and m is the processor core number. The speedup factor of PDM-FFD is strictly less than 3 - 1/m, which outperforms the existing multi-core partitioned scheduling algorithm FBB-FFD. Experiments show that PDM-FFD improves processor utilization by 18.5% compared to other available algorithms on a four-core processor. The PDM-FFD performance improves with the increasing processor core number, task set utilization, and task number. Due to high performance, PDM-FFD can be widely utilized in typical real-time systems such as resource-constrained spacecraft, autonomous vehicles, and industrial robots.

    Reference
    [1] Akesson B, Nasri M, Nelissen G, Altmeyer S, Davis RI. An empirical survey-based study into industry practice in real-time systems. In: Proc. of the 2020 IEEE Real-time Systems Symp. Houston: IEEE, 2020. 3–11.
    [2] Buttazzo GC. Hard Real-time Computing Systems: Predictable Scheduling Algorithms and Applications. New York: Springer, 2011.
    [3] Leung JYT, Whitehead J. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 1982, 2(4): 237–250.
    [4] Burmyakov A, Nikolić B. An exact comparison of global, partitioned, and semi-partitioned fixed-priority real-time multiprocessor schedulers. Journal of Systems Architecture, 2021, 121: 102313.
    [5] Hagens F, Chen KH. Assessment of efficient dispatching in FreeRTOS. In: Proc. of the 17th Annual Workshop on Operating Systems Platforms for Embedded Real-time Applications. Vienna, 2023. 7–9.
    [6] Liu JX, Zhao KB, Du HY, Li M, Wang ZC. Application of uCOS-II and LabVIEW in stirling engine fuel supply control system. Applied Mechanics and Materials, 2011, 143–144: 381–385.
    [7] Wang W, Xia S, Wang LY. Research of interrupt processing in motion control system based on VxWorks. In: Proc. of the 5th Int’l Conf. on Telecommunications and Communication Engineering. Chengdu: Association for Computing Machinery, 2022. 277–280.
    [8] Li SF, Qiao L, Yang MF. Memory state verification based on inductive and deductive reasoning. IEEE Trans. on Reliability, 2021, 70(3): 1026–1039.
    [9] 陈熙, 乔磊, 杨孟飞, 刘洪标. 基于避让阻塞的优先级天花板协议. 软件学报, 2023, 34(7): 3422–3437. http://www.jos.org.cn/1000-9825/6534.htm
    Chen X, Qiao L, Yang MF, Liu HB. Priority ceiling protocol based on avoidance blocking. Ruan Jian Xue Bao/Journal of Software, 2023, 34(7): 3422–3437 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6534.htm
    [10] Liu HB, Xi C, Qiao L, Zhang JK, Yang MF. A schedulability test for sporadic task DM scheduling based on density upper bound. IEEE Access, 2022, 10: 12475–12486.
    [11] 刘洪标, 乔磊, 杨孟飞, 陈熙, 马智, 李少峰. 基于周期虚拟缩减的实时任务调度和分析方法. 软件学报, 2022, 33(9): 3512–3528. http://www.jos.org.cn/1000-9825/6394.htm
    Liu HB, Qiao L, Yang MF, Chen X, Ma Z, Li SF. Real-time task scheduling and analysis method based on virtual zoom out period. Ruan Jian Xue Bao/Journal of Software, 2022, 33(9): 3512–3528 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6394.htm
    [12] Baruah S, Bertogna M, Buttazzo G. Multiprocessor Scheduling for Real-time Systems. Cham: Springer, 2015.
    [13] Sun ZY, Guo MY, Liu XW. A survey of real-time scheduling on multiprocessor systems. In: Proc. of the 39th National Conf. of Theoretical Computer Science. Yinchuan: Springer, 2021. 89–118.
    [14] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 1973, 20(1): 46–61.
    [15] Joseph M, Pandya P. Finding response times in a real-time system. The Computer Journal, 1986, 29(5): 390–395.
    [16] Chen JJ, Huang WH, Liu C. K2U: A general framework from k-point effective schedulability analysis to utilization-based tests. In: Proc. of the 2015 IEEE Real-time Systems Symp. San Antonio: IEEE, 2015. 107–118.
    [17] Bertogna M, Cirinei M, Lipari G. Improved schedulability analysis of EDF on multiprocessor platforms. In: Proc. of the 17th Euromicro Conf. on Real-time Systems. Balearic Islands: IEEE, 2005. 209–218.
    [18] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman & Co., 1979.
    [19] Dhall SK, Liu CL. On a real-time scheduling problem. Operations Research, 1978, 26(1): 127–140.
    [20] Oh Y, Son SH. Tight Performance Bounds of Heuristics for a Real-time Scheduling Problem. Charlottesville: University of Virginia, 1993.
    [21] Sprunt B, Sha L, Lehoczky J. Aperiodic task scheduling for hard-real-time systems. Real-time Systems, 1989, 1(1): 27–60.
    [22] Burchard A, Liebeherr J, Oh Y, Son SH. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. on Computers, 1995, 44(12): 1429–1442.
    [23] Rothvoss T. On the computational complexity of periodic scheduling. Lausanne: EPFL, 2009.
    [24] Lopez JM, Díaz JL, Garcia DF. Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling. IEEE Trans. on Parallel and Distributed Systems, 2004, 15(7): 642–653.
    [25] Fisher N, Baruah S, Baker TP. The partitioned scheduling of sporadic tasks according to static-priorities. In: Proc. of the 18th Euromicro Conf. on Real-time Systems. Dresden: IEEE, 2006. 118–127.
    [26] Chen JJ. Partitioned multiprocessor fixed-priority scheduling of sporadic real-time tasks. In: Proc. of the 28th Euromicro Conf. on Real-time Systems. Toulouse: IEEE, 2016. 251–261.
    [27] Baruah SK, Mok AK, Rosier LE. Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proc. of the 11th Real-time Systems Symp. Lake Buena Vista: IEEE, 1990. 182–190.
    [28] Fisher N, Baruah S. A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines. In: Proc. of the 17th Euromicro Conf. on Real-time Systems. Balearic Islands: IEEE, 2005. 117–126.
    [29] Hoare CAR. Algorithm 64: Quicksort. Communications of the ACM, 1961, 4(7): 321.
    [30] Bini E, Nguyen THC, Richard P, Baruah SK. A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans. on Computers, 2009, 58(2): 279–286.
    [31] Bini E, Buttazzo GC. Measuring the performance of schedulability tests. Real-time Systems, 2005, 30(1): 129–154.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

刘洪标,宋程昊,王婷煜,姜菁菁,乔磊,杨孟飞.并行机器中基于干扰时间的间歇实时任务分区DM调度.软件学报,2024,35(11):5306-5318

Copy
Share
Article Metrics
  • Abstract:347
  • PDF: 1827
  • HTML: 488
  • Cited by: 0
History
  • Received:January 16,2023
  • Revised:April 10,2023
  • Online: December 27,2023
  • Published: November 06,2024
You are the first2044391Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063