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

doi:10.11896/jsjkx.241000100

Abstract

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

CLC Number:

TP316

GONG Weiqiang, HAN Jianjun, ZHANG Chang’an. Weakly-hard-constraintand Priority-distance Aware Partitioned Scheduling for HomogeneousMulticore Platforms[J].Computer Science, 2025, 52(4): 101-109.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

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

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 7

Metrics

Comments

Recommended 0

[1]	ZHANG Tian-yu, GUAN Nan and DENG Qing-xu. Analysis of Real-time Performance of Algorithm Credit in Xen Virtual Machine [J]. Computer Science, 2015, 42(12): 115-119.
[2]	ZHAI Zheng-li and DING Zhi-jun. Schedulability Analysis of Time Petri Net and its Application in FMS [J]. Computer Science, 2015, 42(1): 12-18.
[3]	ZHOU Zheng-yong,YANG Fu-min,LI Jun,HU Guan-rong,TU Gang and ZHANG Jie. Priority Assignment Strategy for Real-time System under Fault Bursts [J]. Computer Science, 2014, 41(Z11): 1-6.
[4]	WANG Ying-feng , LIU Zhi-jing. Energy-efficient Task Scheduling Approach for Homogeneous Multi-core Processors [J]. Computer Science, 2011, 38(9): 294-297.
[5]	ZHU Xu-dong,CHANG Hui-you,YI Yang,TAO Qian. Constraint Specification of Weakly Hard Real-time Systems Based on Smooth Scheduling [J]. Computer Science, 2010, 37(3): 205-207291.
[6]	NIU Yun, DAI Guan-zhong, LIANG Ya-lin （College of Automation, Northwesten Polyteehnical University, Xi ＇ an 710072, China）. [J]. Computer Science, 2009, 36(1): 121-125.
[7]	. [J]. Computer Science, 2006, 33(3): 287-290.