计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (4): 101-109.doi: 10.11896/jsjkx.241000100

• 智能嵌入式系统 • 上一篇    下一篇

同构多核平台上基于弱硬约束和优先级距离启发的任务划分算法

龚伟强, 韩建军, 张昌安   

  1. 华中科技大学计算机科学与技术学院 武汉 430074
  • 收稿日期:2024-10-21 修回日期:2025-01-30 出版日期:2025-04-15 发布日期:2025-04-14
  • 通讯作者: 韩建军(jasonhan @hust.edu.cn)
  • 作者简介:(m202273807@hust.edu.cn)

Weakly-hard-constraintand Priority-distance Aware Partitioned Scheduling for HomogeneousMulticore Platforms

GONG Weiqiang, HAN Jianjun, ZHANG Chang’an   

  1. College of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China
  • Received:2024-10-21 Revised:2025-01-30 Online:2025-04-15 Published:2025-04-14
  • About author:GONG Weiqiang,born in 2000,postgraduate,is a member of CCF(No.V1042G).His main research interests include real-time systems and scheduling algorithm.
    HAN Jianjun,born in 1972.Ph.D,professor,Ph.D supervisor.His main research interests include AI algorithm and embedded real-time systems.

PDF (PC)

86

摘要： 弱硬实时(Weakly-Hard Real-Time,WHRT)系统由于能够有效地利用计算资源,并且可以同时容忍部分作业的超时来保证系统的稳定性,因此在过去二十年中得到了极大的发展。然而,目前关于多核环境下弱硬实时任务调度的研究却较少,现有的基于全局调度的方案因任务迁移带来的高运行时开销,实际可行性受到了极大的限制;而作业级分区算法则通常忽略了弱硬约束下任务利用率的影响,因此任务集的可调度性性能不高。为了解决这些问题,基于单处理器的全局紧急调度(Global Emergency-Based Scheduling,GEBS),提出了一种弱硬约束启发的任务划分算法(Weakly-Hard-Constraint Aware Task Partition Algorithm,WHCA-TPA)和另一种优先级距离启发的任务划分算法(Priority-Distance-Aware Task Partition Algorithm,PDA-TPA)。WHCA-TPA考虑不同任务之间的干扰,对系统的利用率进行更合理的估计,并以此作为启发对任务进行更合理的分配。PDA-TPA通过减少同一核上不同优先级任务之间的抢占次数,来减少系统上下文切换的次数。将所提算法与现有的传统分区算法进行对比,大量的实验结果表明,WHCA-TPA在不同系统参数下都可以获得更高的可调度比例,并且和PDA-TPA在绝大部分情况下都能有效地降低运行时开销。

关键词: 多核处理器, 实时系统, 弱硬约束, 利用率启发, 分区算法

Abstract: As weakly-hard real-time(WHRT) system enables to effectively exploit computing resources while guaranteeing the system stability by tolerating accidentally temporal violation,it has been broadly developed in some real-life areas over the past two decades.However,there exist rather limited studies on the scheduling of WHRT tasks upon multicores.For the existing global scheduling based schemes,the high runtime overhead caused by task migration greatly restricts their practical viability; while the current job-level partitioned algorithm usually ignores the impacts of the utilizations of tasks under weakly-hard constraints,which may significantly degrade the schedulability performance of task sets.To address such issues,with the focus global emergency-based scheduling(GEBS) for uniprocessors,two task partitioning algorithms have been proposed:the weakly-hard-constraint aware task partitioning algorithm(WHCA-TPA) and the priority-distance aware task partitioning algorithm(PDA-TPA).Firstly,WHCA-TPA considers the interference between different tasks,providing a more reasonable estimate of system utilization,and uses it to allocate tasks more reasonably.In addition,PDA-TPA aims at reducing the number of preemptions between tasks to decrease the number of context switches,thus achieving lower runtime overhead.Ultimately,when compared to the existing conventional mapping schemes,extensive experimental results show that WHCA-TPA can achieve a higher schedulability ratio under various system parameters.Meanwhile,PDA-TPA and WHCA-TPA usually has lower runtime overhead in contrast with other mapping schemes.

Key words: Homogeneous multicores, Real-time systems, Weakly-hard constraints, Utilization Aware, Partitioned scheduling

中图分类号: 

  • TP316
[1]HUANG X,CUI Y,CHEN Q,et al.Joint task offloading and QoS-aware resource allocation in fog-enabled Internet-of-Things networks[J].IEEE Internet of Things Journal,2020,7(8):7194-7206.
[2]TONG E,NIU W,TIAN Y,et al.A hierarchical energy-efficient service selection approach with QoS constraints for Internet of Things[J].IEEE Transactions on Green Communications and Networking,2021,5(2):645-657.
[3]WANG S,ZHOU A,YANG M,et al.Service composition in cyber-physical-social systems[J].IEEE Transactions on Emerging Topics in Computing,2017,8(1):82-91.
[4]WANG Z,LIANG H,HUANG C,et al.Cross-layer design of automotive systems[J].IEEE Design & Test,2020,38(5):8-16.
[5]LIANG H,WANG Z,ROY D,et al.Security-driven codesignwith weakly-hard constraints for real-time embedded systems[C]//2019 IEEE 37th International Conference on Computer Design(ICCD).Piscataway,NJ:IEEE,2019:217-226.
[6]HUANG C,WARDEGA K,LI W,et al.Exploring weakly-hard paradigm for networked systems[C]//Proceedings of the Workshop on Design Automation for CPS and IoT.New York:ACM,2019:51-59.
[7]CHWA H S,SHIN K G,LEE J.Closing the gap between stabil-ity and schedulability:A new task model for cyber-physical systems[C]//2018 IEEE Real-Time and Embedded Technology and Applications Symposium(RTAS).Piscataway,NJ:IEEE,2018:327-337.
[8]WARDEGA K,LI W.Application-aware scheduling of net-worked applications over the low-power wireless bus[C]//2020 Design,Automation & Test in Europe Conference & Exhibition(DATE).Piscataway,NJ:IEEE,2020:222-227.
[9]BERNAT G,BURNS A,LIAMOSI A.Weakly hard real-timesystems[J].IEEE transactions on Computers,2001,50(4):308-321.
[10]CHOI H,KIM H,ZHU Q.Toward practical weakly hard real-time systems:A job-class-level scheduling approach[J].IEEE Internet of Things Journal,2021,8(8):6692-6708.
[11]GONG S,HAN J J.Global emergency-based job-level schedulingfor weakly-hard real-time systems[J].Journal of Systems Architecture,2021,117:102150.
[12]PAZZAGLIA P,SUN Y,NATALE M D.Generalized weaklyhard schedulability analysis for real-time periodic tasks[J].ACM Transactions on Embedded Computing Systems(TECS),2020,20(1):1-26.
[13]GLASER F,TAGLIAVINI G,ROSSI D,et al.Energy-efficient hardware-accelerated synchronization for shared-L1-memory multiprocessor clusters[J].IEEE Transactions on Parallel and Distributed Systems,2020,32(3):633-648.
[14]YOUNESS H,OMAR A,MONESS M.An optimized weighted average makespan in fault-tolerant heterogeneous MPSoCs[J].IEEE Transactions on Parallel and Distributed Systems,2021,32(8):1933-1946.
[15]ANSARI M,SAFARI S,KHDR H,et al.Power-aware checkpointing for multicore embedded systems[J].IEEE Transactions on Parallel and Distributed Systems,2022,33(12):4410-4424.
[16]BOTTARO M,VARDANEGA T.Evaluating a multicoreMixed-Criticality System implementation against a temporal isolation kernel[J].Journal of Systems Architecture,2022,130:102688.
[17]WU T,JIN S.Weakly hard real-time scheduling algorithm for multimedia embedded system on multiprocessor platform[C]//2008 First IEEE International Conference on Ubi-Media Computing.Piscataway,NJ:IEEE,2008:320-325.
[18]KONG Y,CHO H.Guaranteed scheduling for(m,k)-firm deadline-constrained real-time tasks on multiprocessors[C]//2011 12th International Conference on Parallel and Distributed Computing,Applications and Technologies.Piscataway,NJ:IEEE,2011:18-23.
[19]KONG Y,CHO H.Energy-constrained scheduling for weakly-hard real-time tasks on multiprocessors[C]//Computer Science and Convergence:CSA 2011 & WCC 2011 Proceedings.Springer Netherlands,2012:335-347.
[20]GRACIOLI G,FRÖHLICH A A,PELLIZZONI R,et al.Implementation and evaluation of global and partitioned scheduling in a real-time OS[J].Real-Time Systems,2013,49:669-714.
[21]BASTONI A,BRANDENBURG B B,ANDERSON J H.An em-pirical comparison of global,partitioned,and clustered multiprocessor EDF schedulers[C]//2010 31st IEEE Real-Time Systems Symposium.Piscataway,NJ:IEEE,2010:14-24.
[22]HAN J J,WU X,ZHU D,et al.Synchronization-aware energymanagement for VFI-based multicore real-time systems[J].IEEE Transactions on Computers,2012,61(12):1682-1696.
[23]LOPEZ J M,DÍAZ J L,GARCIA D F.Minimum and maximum utilization bounds for multiprocessor RM scheduling[C]//Proceedings 13th Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE,2001:67-75.
[24]HAMDAOUI M,RAMANATHAN P.A dynamic priority as-signment technique for streams with(m,k)-firm deadlines[J].IEEE transactions on Computers,1995,44(12):1443-1451.
[25]LI J,SONG Y Q,SIMONOT-LION F.Providing Real-Time Applications With Graceful Degradation of QoS and Fault Tolerance According to(m,k)-Firm Model[J].IEEE Transactions on Industrial Informatics,2006,2(2):112-119.
[26]HUANG C,LI W,ZHU Q.Formal verification of weakly-hard systems[C]//Proceedings of the 22nd ACM International Conference on Hybrid Systems:Computation and Control.New York:ACM,2019:197-207.
[27]CHOI H,KIM H,ZHU Q.Job-class-level fixed priority scheduling of weakly-hard real-time systems[C]//2019 IEEE Real-Time and Embedded Technology and Applications Symposium(RTAS).Piscataway,NJ:IEEE,2019:241-253.
[28]ISMAIL H,JAWAWI D N A.A Hybrid Multiprocessor Scheduling Approach for Weakly Hard Real-Time Tasks[C]//Mode-ling,Design and Simulation of Systems:17th Asia Simulation Conference.Springer Singapore,2017:666-678.
[29]ISMAIL H,JAWAWI D N A,AHMEDY I,et al.Performance Evaluation of the Weakly Hard Real-Time Tasks for Global Multiprocessor Scheduling Approach[C]//2021 IEEE Asia-Pacific Conference on Computer Science and Data Engineering(CSDE).IEEE,2021:1-6.
[30]ISMAIL H,JAWAWI D N A,AHMEDY I.A Hybrid Real-Time Scheduling Mechanism Based on Multiprocessor for Real-Time Tasks in Weakly Hard Specification[C]//Science and Information Conference.Cham:Springer International Publishing,2022:228-247.
[31]BARUAH S.Partitioned edf scheduling:a closer look[J].Real-Time Systems,2013,49:715-729.
[32]BINI E,BUTTAZZO G C.Measuring the performance of schedulability tests[J].Real-time systems,2005,30(1):129-154.
[33]BRANDENBURG B B,ANDERSON J H.A comparison of the m-pcp,d-pcp,and fmlp on litmusrt[C]//International Confe-rence on Principles of Distributed Systems.Berlin,Heidelberg:Springer Berlin Heidelberg,2008:105-124.
[34]HAN J J,WANG Z,GONG S,et al.Resource-aware scheduling for dependable multicore real-time systems:Utilization bound and partitioning algorithm[J].IEEE Transactions on Parallel and Distributed Systems,2019,30(12):2806-2819.
[35]HAN J J,GONG S,WANG Z,et al.Blocking-aware partitionedreal-time scheduling for uniform heterogeneous multicore platforms[J].ACM Transactions on Embedded Computing Systems(TECS),2020,19(1):1-25.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发