面向复杂任务集的任务调度算法
|
摘要
基于测控地检设备的显控软件需要同时处理测量解算、遥测帧解析、网络通信和遥测数据存储等多项任务。针对常规的任务调度算法无法适应设备显控软件复杂的任务集,提出了一种动态双优先级任务调度算法。算法在时间片轮转技术的基础上,综合考虑任务周期、相对截止期和剩余空闲时间3方面因素,对于硬实时和软实时周期任务提出不同的动态优先级计算策略,并针对引入剩余空闲时间导致的"颠簸"现象,提出一种抢占阈值的计算方法。理论分析和实测数据均证明该算法的优越性。
Display control software based on test equipment in TT&C needs to deal with measurement solution,telemetry frame resolution,network communication and telemetry data store,and many other missions parallel. Aiming at the problem that the conventional algorithms lose pace with complex task set,a dynamic dual priority scheduling algorithm is put forward. Based on time slice rotation technology,the algorithm takes duty cycle,relative deadline and remaining idle time synthetically. Respective dynamic priority computing strategies are proposed in terms of hard real time and soft real time task. The preemption threshold computing method is presented towards the jolt from the remaining idle time. Both theoretical analysis and measured data authenticate the benefits of the dynamic dual priority scheduling algorithm.
Display control software based on test equipment in TT&C needs to deal with measurement solution,telemetry frame resolution,network communication and telemetry data store,and many other missions parallel. Aiming at the problem that the conventional algorithms lose pace with complex task set,a dynamic dual priority scheduling algorithm is put forward. Based on time slice rotation technology,the algorithm takes duty cycle,relative deadline and remaining idle time synthetically. Respective dynamic priority computing strategies are proposed in terms of hard real time and soft real time task. The preemption threshold computing method is presented towards the jolt from the remaining idle time. Both theoretical analysis and measured data authenticate the benefits of the dynamic dual priority scheduling algorithm.
引文
[1]吴美金,王秉臣,卢逸斌.基于PLC的航天器地面测控系统通用化设计研究[J].计算机测量与控制,2016,24(7):14-16,20.WU Mei-jin,WANG Bing-chen,LU Yi-bin. Generalized Design of Spacecraft Ground Test and Control System Based on PLC[J]. Computer Measurement and Control,2016,24(7):14-16,20.
[2]袁铁山.便携多模式测控地检设备的设计与实现[D].杭州:浙江大学,2013.YUAN Tie-shan. Design and Implementation of Portable and Multi-Mode TT&C Earth Equipment[D]. Hang zhou:Zhejiang University,2013.
[3] WU Zhi-lu,ZHAO Nan,LI Shu-ying,et al. A Novel PCM/FM Multi-Symbol Detection Algorithm for FPGA Implementation[J]. Information Technology Journal,2009,8(4):583-588.
[4] Hongya Wang,Yingyuan Xiao,Lih Chyun Shu. Scheduling Periodic Continuous Queries in Real-Time Data Broadcast Environments[J]. IEEE Transactions on Computers,2012,61(9):1325-1340.
[5] Jinkyu Lee. Preempt a Job or Not in EDF Scheduling of Uniprocessor Systems[J]. IEEE Transactions on Computers,2014,63(5):1197-1206.
[6]史婷娜,陈正伟,方红伟.网络控制系统任务属性不确定的模糊EDF调度[J].天津大学学报,2011,44(8):690-694.SHI Ting-na,CHEN Zheng-wei,FANG Hong-wei. Fuzzy EDF Scheduling with Uncertain Task Attributes of Network Control System[J]. Journal of Tianjin University,2011,44(8):690-694.
[7]程禹,赵宏伟,龙曼丽.最早截止期优先调度算法的改进[J].吉林大学学报,2013,43(5):1338-1342.CHENG Yu,ZHAO Hong-wei,LONG Man-li. Improvement of the First Deadline Scheduling Algorithm[J].Journal of Jilin University,2013,43(5):1338-1342.
[8] RIVAS J M,HARBOUR M G. Deadline Assignment in EDF Schedulers for Real-Time Distributed Systems[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(10):2671-2684.
[9]任小西,赵公怡.基于动态抢占阈值的LSF调度算法[J].计算机工程,2012,38(4):275-277,280.REN Xiao-xi,ZHAO Gong-yi. LSF Scheduling Algorithm Based on Dynamic Preemption Threshold[J]. Computer Engineering,2012,38(4):275-277,280.
[10]巴巍.实时系统动态优先级任务调度算法的研究[D].大连:大连理工大学,2010.BA Wei. Research on Real-time System Dynamic Priority Task Scheduling Algorithm[D]. Dalian:Dalian University of Technology,2010.
[11]郑志,冯全源.低复杂度的阈值优化实时调度算法[J].计算机工程与设计,2008,19(17):4411-4413,4422.ZHENG Zhi,FENG Quan-yuan. Low Complexity Preemption Threshold Optimization Real-Time Scheduling Algorithm[J]. Computer Engineering and Design,2008,19(17):4411-4413,4422.
[12]徐文清,杨红雨.一种基于动态优先级的实时混合任务调度算法[J].四川大学学报,2006,11(3):544-548.XU Wen-qing,YANG Hong-yu. A Real-Time Hybrid Task Scheduling Algorithm Based on Dynamic Priority[J]. Journal of Sichuan University,2006,11(3):544-548.
[13]巴巍,张大波,李琦.一种新的组优先级动态实时调度算法[J].计算机科学,2009,36(7):230-233,239.BA Wei,ZHANG Da-bo,LI Qi. New Group Priority Dynamic Real-Time Scheduling Algorithm[J]. Computer Science,2009,36(7):230-233,239.
[14] SHARMA R,NITIN. Task Migration with EDF-RM Scheduling Algorithms in Distributed System[C]∥Advances in Computing and Communications,2012:182-185.
[15] Myunggwon Hwang,Dongjin Choi,Pan Koo Kim. Least Slack Time Rate First:An Efficient Scheduling Algorithm for Pervasive Computing Environment[J]. Journal of Universal Computer Science,2011,17(6):912-925.
[2]袁铁山.便携多模式测控地检设备的设计与实现[D].杭州:浙江大学,2013.YUAN Tie-shan. Design and Implementation of Portable and Multi-Mode TT&C Earth Equipment[D]. Hang zhou:Zhejiang University,2013.
[3] WU Zhi-lu,ZHAO Nan,LI Shu-ying,et al. A Novel PCM/FM Multi-Symbol Detection Algorithm for FPGA Implementation[J]. Information Technology Journal,2009,8(4):583-588.
[4] Hongya Wang,Yingyuan Xiao,Lih Chyun Shu. Scheduling Periodic Continuous Queries in Real-Time Data Broadcast Environments[J]. IEEE Transactions on Computers,2012,61(9):1325-1340.
[5] Jinkyu Lee. Preempt a Job or Not in EDF Scheduling of Uniprocessor Systems[J]. IEEE Transactions on Computers,2014,63(5):1197-1206.
[6]史婷娜,陈正伟,方红伟.网络控制系统任务属性不确定的模糊EDF调度[J].天津大学学报,2011,44(8):690-694.SHI Ting-na,CHEN Zheng-wei,FANG Hong-wei. Fuzzy EDF Scheduling with Uncertain Task Attributes of Network Control System[J]. Journal of Tianjin University,2011,44(8):690-694.
[7]程禹,赵宏伟,龙曼丽.最早截止期优先调度算法的改进[J].吉林大学学报,2013,43(5):1338-1342.CHENG Yu,ZHAO Hong-wei,LONG Man-li. Improvement of the First Deadline Scheduling Algorithm[J].Journal of Jilin University,2013,43(5):1338-1342.
[8] RIVAS J M,HARBOUR M G. Deadline Assignment in EDF Schedulers for Real-Time Distributed Systems[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(10):2671-2684.
[9]任小西,赵公怡.基于动态抢占阈值的LSF调度算法[J].计算机工程,2012,38(4):275-277,280.REN Xiao-xi,ZHAO Gong-yi. LSF Scheduling Algorithm Based on Dynamic Preemption Threshold[J]. Computer Engineering,2012,38(4):275-277,280.
[10]巴巍.实时系统动态优先级任务调度算法的研究[D].大连:大连理工大学,2010.BA Wei. Research on Real-time System Dynamic Priority Task Scheduling Algorithm[D]. Dalian:Dalian University of Technology,2010.
[11]郑志,冯全源.低复杂度的阈值优化实时调度算法[J].计算机工程与设计,2008,19(17):4411-4413,4422.ZHENG Zhi,FENG Quan-yuan. Low Complexity Preemption Threshold Optimization Real-Time Scheduling Algorithm[J]. Computer Engineering and Design,2008,19(17):4411-4413,4422.
[12]徐文清,杨红雨.一种基于动态优先级的实时混合任务调度算法[J].四川大学学报,2006,11(3):544-548.XU Wen-qing,YANG Hong-yu. A Real-Time Hybrid Task Scheduling Algorithm Based on Dynamic Priority[J]. Journal of Sichuan University,2006,11(3):544-548.
[13]巴巍,张大波,李琦.一种新的组优先级动态实时调度算法[J].计算机科学,2009,36(7):230-233,239.BA Wei,ZHANG Da-bo,LI Qi. New Group Priority Dynamic Real-Time Scheduling Algorithm[J]. Computer Science,2009,36(7):230-233,239.
[14] SHARMA R,NITIN. Task Migration with EDF-RM Scheduling Algorithms in Distributed System[C]∥Advances in Computing and Communications,2012:182-185.
[15] Myunggwon Hwang,Dongjin Choi,Pan Koo Kim. Least Slack Time Rate First:An Efficient Scheduling Algorithm for Pervasive Computing Environment[J]. Journal of Universal Computer Science,2011,17(6):912-925.