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

doi:10.16180/j.cnki.issn1007-7820.2025.01.010

电子科技 ›› 2025, Vol. 38 ›› Issue (1): 73-80.doi: 10.16180/j.cnki.issn1007-7820.2025.01.010

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

朱扬烁, 吕海玉, 李奕晨, 张凤登()

上海理工大学光电信息与计算机工程学院,上海 200093

收稿日期:2023-05-28 修回日期:2023-06-30 出版日期:2025-01-15 发布日期:2025-01-06
通讯作者: 张凤登(1963-),男, E-mail:1148452262@qq.com,博士,教授。研究方向:汽车电子与现场总线、分布式实时系统。
作者简介:朱扬烁(1997-),男,硕士研究生。研究方向:分布式实时系统、容错实时调度。
基金资助:
国家自然科学基金(71840003);上海市自然科学基金(15ZR1429300)

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

ZHU Yangshuo, LÜ Haiyu, LI Yichen, ZHANG Fengdeng()

School of Optical Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China

Received:2023-05-28 Revised:2023-06-30 Online:2025-01-15 Published:2025-01-06
Supported by:
National Natural Science Foundation of China(71840003);Natural Science Foundation of Shanghai(15ZR1429300)

摘要/Abstract

摘要：

针对系统故障模式下容错公平调度FT-FS(Fault Tolerate Fair Scheduler)算法存在拒绝任务次数较多和资源浪费等问题,文中在FT-FS算法的基础上融入了主/替代版本PA(Primary Alternate)容错策略,提出了新的公平调度算法PA-FTFS(Primary-Alternate and Fault Tolerant Fair Scheduling)。该算法能够在多核处理器系统中减少资源浪费的同时更好地减少拒绝任务的次数。利用MATLAB仿真软件对上述算法进行了仿真验证,实验结果表明在内核发生永久性故障后,采用比例替代任务策略的PA-FTFS算法相较于FT-FS算法拒绝任务的次数明显减少。通过数据分析表明,PA-FTFS算法相较于FT-FS算法在故障率和调度率上具有较大改进。

关键词: 多核处理器, 故障, 容错, 公平调度, 主/替代版本, 拒绝任务, 替代任务, MATLAB仿真

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

中图分类号:

TP316

朱扬烁, 吕海玉, 李奕晨, 张凤登. 多核处理器容错实时调度算法[J]. 电子科技, 2025, 38(1): 73-80.

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.

图/表 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

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 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)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 19

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	傅僈喃, 陈苏婷, 解维坤, 林晓会. 基于改进EK算法的FPGA内部互联自动化测试方法[J]. 电子科技, 2025, 38(2): 10-16.
[2]	黄泽华, 毕贵红, 张梓睿. 基于深度学习的复杂模拟电路故障识别[J]. 电子科技, 2025, 38(2): 23-34.
[3]	吕海玉, 罗广, 朱嘉炜, 张凤登. 多核处理器共享Cache的划分算法[J]. 电子科技, 2024, 37(9): 27-33.
[4]	仝兆景, 荆利菲, 兰孟月. 一种用于变压器故障诊断的贝叶斯网络优化方法[J]. 电子科技, 2024, 37(8): 34-39.
[5]	罗广, 冒航, 朱扬烁, 张凤登. 嵌入式多核系统中的实时混合任务调度算法[J]. 电子科技, 2024, 37(8): 84-91.
[6]	马啸宇, 陈卓, 杨超, 李庆生, 郝正航. 基于RTLAB虚实结合的馈线自动化测试[J]. 电子科技, 2024, 37(5): 25-31.
[7]	仝兆景, 兰孟月, 荆利菲. 改进贝叶斯网络在变压器故障诊断中的应用[J]. 电子科技, 2024, 37(5): 47-53.
[8]	葛晓伟, 周颖. 基于事件触发的Delta算子网络控制系统故障检测[J]. 电子科技, 2024, 37(5): 79-87.
[9]	满延露,刘敏,王锴. 主动配电网态势感知技术研究综述与展望[J]. 电子科技, 2024, 37(2): 6-13.
[10]	张阳, 刘瑾. 基于字符增强的工业设备故障命名实体识别[J]. 电子科技, 2024, 37(10): 48-54.
[11]	张彦喆,胡定玉,师蔚,廖爱华. 基于空-频域联合滤波的列车轴承轨旁声学诊断[J]. 电子科技, 2024, 37(1): 55-60.
[12]	王丽华,程翔,杨宁彬,宫碧瑶,黄泽宇,陈美燕. 基于分布式存储框架的无中心联邦学习[J]. 电子科技, 2023, 36(8): 29-34.
[13]	欧敬逸,田颖,向鑫,宋启哲. 基于迁移BN-CNN框架的小样本工业过程故障诊断[J]. 电子科技, 2023, 36(7): 49-55.
[14]	仝兆景,乔征瑞,李金香,兰孟月,荆利菲. 基于改进麻雀搜索算法优化BN的变压器故障诊断研究[J]. 电子科技, 2023, 36(4): 52-58.
[15]	陆禹,张力,张凤登. 基于灰色预测容错时钟同步算法[J]. 电子科技, 2023, 36(3): 29-35.

算法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