多核处理器容错实时调度算法

doi:10.16180/j.cnki.issn1007-7820.2025.01.010

Abstract

Abstract:

In view of the problems such as too many times of rejected tasks and waste of resources in fault-tolerant fair scheduling FT-FS(Fault Tolerate Fair Scheduler) algorithm, a new fair scheduling algorithm PA-FTFS(Primary-Alternate and Fault Tolerant Fair Scheduling) is proposed based on FT-FS algorithm by integrating the main/alternative PA(Primary Alternate) fault-tolerant strategy. This algorithm can reduce the number of rejected tasks in multi-core processor system and reduce the waste of resources. MATLAB simulation software is used to verify the above algorithms. The experimental results show that PA-FTFS algorithm using proportional replacement task strategy has significantly reduced the number of task rejection times compared with FT-FS algorithm after permanent kernel failure. Data analysis shows that PA-FTFS algorithm has better failure rate and scheduling rate than FT-FS algorithm.

Key words: multi-core processor, failure, fault tolerance, fair dispatch, main/alternative version, reject tasks, alternative tasks, MATLAB simulation

CLC Number:

TP316

ZHU Yangshuo, LÜ Haiyu, LI Yichen, ZHANG Fengdeng. Fault-Tolerant Real-Time Scheduling Algorithm in Multi-Core Processor[J].Electronic Science and Technology, 2025, 38(1): 73-80.

Figures/Tables 10

算法2 PA-FTFS-Faulty算法
输入任务集F_l和替代任务集A_l
输出系统恢复期间的任务调度队列
1.t=F_DT
2.while t<F_RT do
3. for each task τ_i in F_l do
4. calculaterw_i and ew_i;
5. end for
6. while system is in unsafe do
7. partition task set F_l into three disjoint subsets
8. calculate G^f and H^f
9. if H^f<G^f then
10. if task in L₁are alternate tasks then
11. reject a_i,the least critical task from L₁;
12. t=PT=max $A T i, F D T$ ;
13. updata F_l back to its contents at timet
14. remove τ_i from F_l;
15. else
16. remove τ_i from F_l;
17. add a_i to F_l;
18. end if
19. else
20. call the Weight-Donation algorithm;
21. end if
22. end while
23. if system is in safe state then
24. call the PA-FTFS-Normal algorithm;
25. t=t+tsl_l
26. end if
27.end while

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

References 19

[1]	张凤登. 分布式实时系统[M]. 北京: 科学出版社, 2014:198-258.
	Zhang Fengdeng. Distributed real-time system[M]. Beijing: Science Press, 2014:198-258.
[2]	黄国睿, 张平, 魏广博. 多核处理器的关键技术及其发展趋势[J]. 计算机工程与设计, 2009, 30(10):80-84.
	Huang Guorui, Zhang Ping, Wei Guangbo. Key technologies of multi-core processors and its development trends[J]. Computer Engineering and Design, 2009, 30(10):80-84.
[3]	Moulik S, Sarkar A, Kapoor H K. Energy aware frame based fair scheduling[J]. Sustainable Computing: Informatics and Systems, 2018, 21(2):66-77.
[4]	Zhu D, Xuan Q, Daniel Mossé, et al. An optimal boundary fair scheduling algorithm for multiprocessor real-time systems[J]. Journal of Parallel and Distributed Computing, 2011, 71(10):1411-1425.
[5]	Samala A K, Mallb R, Tripathy C. Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm[J]. Swarm and Evolutionary Computation, 2014, 14(1):92-105.
[6]	Nair P P, Sarkar A. Fault-tolerant real-time fair scheduling on multiprocessor systems with cold-standby[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(4):1718-1732.
[7]	Pathan R M. Real-time scheduling algorithm for safety-critical systems on faulty multicore environments[J]. Real Time Systems, 2017, 53(1):45-81.
[8]	Bhat A, Samii S, Rajkumar R. Recovery time considerations in real-time systems employing software fault tolerance[C]. Barcelona: Proceedings of the Thirtieth Euromicro Conference on Real-Time Systems, 2018:231-252.
[9]	Kang S H, Park H W. Optimal checkpoint selection with dual-modular redundancy hardening[J]. IEEE Transactions on Computers, 2015, 64(7):2036-2048.
[10]	Samala A K, Mallb R, Tripathy C. Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm[J]. Swarm and Evolutionary Computation, 2014, 14(1):92-105.
[11]	Mottaghi M H, Zarandi H R. DFTS:A dynamic fault-tolerant scheduling for real time tasks in multicore processors[J]. Microprocessors and Microsystems, 2014, 38(1):88-97.
[12]	Powell M D, Biswas A, Gupta S, et al. Architectural core salvaging in a multi-core processor for hard-error tolerance[J]. ACM SIGARCH Computer Architecture News, 2009, 37(3):93-104.
[13]	Pop P, Izosimov V, Eles P, et al. Design optimization of time and costconstrained fault-tolerant embedded systems with checkpointing and replication[J]. IEEE Transactions on Very Large Scale Integration Systems, 2009, 17(3):389-402.
[14]	Levinet G, Funk S, Sadowski C, et al. DP-FAIR:A simple model for understanding optimal multiprocessor scheduling[C]. Belgium: Proceedings of the Twenty-second Euromicro Conference on Real-Time Systems,IEEE, 2010:3-13.
[15]	彭浩, 韩江洪, 魏振春. 副版本优先级可提升的全局容错调度算法[J]. 计算机研究与发展, 2016, 53(2):354-361.
	Peng Hao, Han Jianghong, Wei Zhenchun. Fault tolerant global scheduling with backup priority promotion[J]. Journal of Computer Research and Development, 2016, 53(2):354-361.
[16]	黄迎春, 邓庆绪. 基于副版本零调整策略的实时任务主副版本容错调度[J]. 东南大学学报(自然科学版), 2018, 48(2):260-264.
	Huang Yingchun, Deng Qingxu. Fault-tolerant scheduling for real-time tasks based on non-adjusting strategy of alternate[J]. Journal of Southeast University(Natural Science Edition), 2018, 48(2):260-264.
[17]	陈刚, 关楠. 实时多核嵌入式系统研究综述[J]. 软件学报, 2018, 29(7):14-23.
	Chen Gang, Guan Nan. State-of the-art survey of real-time multicore system[J]. Journal of Software, 2018, 29(7):14-23.
[18]	曹营. 嵌入式系统任务调度机制的研究与实现[D]. 大连: 大连理工大学, 2010:8-14.
	Cao Ying. Research and implementation of task scheduling mechanism based on embedded system[D]. Dalian: Dalian University of Technology, 2010:8-14.
[19]	何忠政. 分布式实时系统任务容错调度优化算法算法研究[D]. 哈尔滨: 哈尔滨工程大学, 2016:73-83.
	He Zhongzheng. Research on the task fault-tolerate scheduling optimization algorithms for the distributed real-time system[D]. Harbin: Harbin Engineering University, 2016:73-83.

Fault-Tolerant Real-Time Scheduling Algorithm in Multi-Core Processor

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 19

Related Articles 15

Metrics

Comments

Recommended 0

[1]	LUO Guang, MAO Hang, ZHU Yangshuo, ZHANG Fengdeng. Real-Time Hybrid Task Scheduling Algorithm in Embedded Multicore System [J]. Electronic Science and Technology, 2024, 37(8): 84-91.
[2]	ZHANG Yang, LIU Jin. Character Enhancement Based on Named Entity Recognition for Industrial Equipment Faults [J]. Electronic Science and Technology, 2024, 37(10): 48-54.
[3]	WANG Lihua,CHENG Xiang,YANG Ningbin,GONG Biyao,HUANG Zeyu,CHEN Meiyan. Distributed-Based Decentralized Federated Machine Learning [J]. Electronic Science and Technology, 2023, 36(8): 29-34.
[4]	LU Yu,ZHANG Li,ZHANG Fengdeng. Fault-Tolerant Clock Synchronization Algorithm Based on Grey Prediction [J]. Electronic Science and Technology, 2023, 36(3): 29-35.
[5]	BAI Xingyu,GOU Yutao,JIANG Yu,LIU Mingyu. An Acoustic Treatment Method for On-Line Fault Monitoring of Electromechanical Systems in Complex Noise Environment [J]. Electronic Science and Technology, 2023, 36(3): 55-61.
[6]	SUN Sinan,HAO Zhenghang. Research on Battery Grid Connection Based on Voltage and Current Double Loop Control [J]. Electronic Science and Technology, 2023, 36(2): 13-21.
[7]	XU Lili,YANG Chao,ZENG Haoran. Fault Section Location of Distribution Network with DG Based on Improved Whale Algorithm [J]. Electronic Science and Technology, 2023, 36(1): 15-20.
[8]	ZHANG Yuhui,ZHANG Fengdeng,ZHANG Haitao. Research on Improved FTA Clock Synchronization Algorithm in RTEthernet [J]. Electronic Science and Technology, 2023, 36(1): 67-74.
[9]	SUN Sinan,HAO Zhenghang. Photovoltaic Grid-Connected System Based on Adaptive VSG Control [J]. Electronic Science and Technology, 2022, 35(9): 22-29.
[10]	LIU Jianlong,HAO Zhenghang. Comparative Study of Wind Power System Simulation Based on Back-to-Back Converters [J]. Electronic Science and Technology, 2022, 35(2): 67-73.
[11]	WANG Yang,WANG Yagang. Identification Method Based on Step Response and Genetic Algorithm to Optimize Higher-Order Plus Time-Delay Model [J]. Electronic Science and Technology, 2021, 34(9): 41-46.
[12]	YAN Zhenbin,ZHENG Bochao,ZHOU Zhiyong. Research on Grid Connection of Photovoltaic Power Generation Systems Based on a New Robust Droop Control Method [J]. Electronic Science and Technology, 2021, 34(8): 79-86.
[13]	WANG Jialiang,JIANG Kejian,ZHU Fangfu. Magnetic Field Analysis of Magnetic Bearing Pole Fault under Fault-Tolerant Control [J]. Electronic Science and Technology, 2021, 34(11): 81-87.
[14]	WANG Jiaren,WANG Yagang. Research on Complex Control Algorithms for Non-Minimum Phase Systems [J]. Electronic Science and Technology, 2021, 34(1): 55-59.
[15]	XIANG Yang,SUN Xiaoxia,SONG Yukun. A Fault-tolerant Scheme for Data Flow Driven Computing Channels [J]. Electronic Science and Technology, 2020, 33(7): 6-11.

算法1 Weight-Donation算法
输入贫缺任务集L₁、富余任务集L₂和平衡任务集L₃
输出更新任务集L₁、L₂和L₃
1.while L₁≠∅ do
2. select needy task τ_i and affluent task τ_j from L₁ and L₂,respectively
3. if oa_j≥ua_i then
4. ew_j=ew_j-ua_i,ew_i=rw_i;
5. oa_j=oa_j-ua_i,ua_i=0;
6. remove τ_i from L₁and add to L₃;
7. ifoa_j =0 then
8. remove τ_j from L₂and add to L₃;
9. end if
10. else
11. ew_j=ew_j-oa_j,ew_i=ew_i+oa_j;
12. ua_i=ua_i-oa_j,oa_j=0;
13. remove τ_j from L₂and add to L₃;
14. end if
15.end while