| Citation: | SONG Zixu, LI Qiao, WANG Jingjing, et al. Time-triggered scheduling table generation method based on schedulability ranking[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(11): 2388-2395. doi: 10.13700/j.bh.1001-5965.2018.0043(in Chinese)
|
The time-triggered Ethernet (TTE) static scheduling table is generated based on the satisfiability modulo theories (SMT). If the time-triggered (TT) traffic set is of a large scale, the subsets of traffic need to be selected in batches into the incremental scheduling table generation, where the order of selection has a significant impact on the calculation time consumption. An incremental time-triggered scheduling table generation method based on schedulability ranking is proposed and formed:strict-periodic utilization (SPU) is used to measure the schedulability of TT traffic; TT traffic subsets are selected in batches according to scheduling difficulty descending order, and solved by SMT subset by subset in turn; meanwhile, schedulability check and contention-free constraints reduction are involved. During the solving process, a back-track operation is performed in the case of partly-non-schedulable situation; meanwhile, the interference time is used as the joint constraint condition of the scheduled set on the unscheduled set, and the number of constraints between the two sets is reduced on a large scale, which further improves the solving efficiency. Case study shows that this method's growth rate of the backtracking times with the scale of the problem is lowered down significantly, compared with incremental scheduling method using random order, period ascending order, or scheduling difficulty ascending order.
| [1] |
STEINER W, BAUER G, HALL B, et al.TTEthernet dataflow concept[C]//Proceedings of 8th IEEE International Symposium on Network Computing and Applications.Piscataway, NJ: IEEE Press, 2009: 319-322.
|
| [2] |
SAE AS-2 Committee.Time-triggered Ethernet: SAE AS6802[S].Warrendale, PA: SAE International, 2011.
|
| [3] |
张英静, 熊华钢, 刘志丹, 等.可用于航空电子系统的时间触发以太网[J].电光与控制, 2015, 22(5):49-53. doi: 10.3969/j.issn.1671-637X.2015.05.012
ZHANG Y J, XIONG H G, LIU Z D, et al.Application of TTE communication technology in avionics system[J].Electronics Optics & Control, 2015, 22(5):49-53(in Chinese). doi: 10.3969/j.issn.1671-637X.2015.05.012
|
| [4] |
STEINBACH T, LIM H T, KORF F, et al.Tomorrow's in-car interconnect A competitive evaluation of IEEE 802.1 AVB and Time-Triggered Ethernet (AS6802)[C]//Proceedings of IEEE Conference on Vehicular Technology.Piscataway, NJ: IEEE Press, 2012: 1-5.
|
| [5] |
STEINER W.An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of 31st IEEE Real-Time Systems Symposium (RTSS).Piscataway, NJ: IEEE Press, 2010: 375-384. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks
|
| [6] |
DE MOURA L, BJORNER N.Satisfiability modulo theories:Introduction and applications[J].Communications of the ACM, 2011, 54(9):69-77. doi: 10.1145/1995376
|
| [7] |
POZO F, RODRIGUEZNAVAS G, STEINER W, et al.Period-aware segmented synthesis of schedules for multi-hop time-triggered networks[C]//Proceedings of IEEE, International Conference on Embedded and Real-Time Computing Systems and Applications.Piscataway, NJ: IEEE Press, 2016: 170-175. http://ieeexplore.ieee.org/document/7579952/
|
| [8] |
陈进朝, 杜承烈.单处理器平台下的严格周期任务可调度性判定[J].计算机工程, 2016, 42(5):288-291. doi: 10.3969/j.issn.1000-3428.2016.05.050
CHEN J C, DU C L.Schedulability test for strictly periodic tasks on uniprocessor platform[J].Computer Engineering, 2016, 42(5):288-291(in Chinese). doi: 10.3969/j.issn.1000-3428.2016.05.050
|
| [9] |
CHEN J, DU C, XIE F, et al.Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems[J].Real-Time Systems, 2016, 52(3):239-271. doi: 10.1007/s11241-015-9226-z
|
| [10] |
KORST J, AARTS E H L, LENSTRA J K, et al.Periodic multiprocessor scheduling[C]//Parallel Architectures and Languages Europe(PARLE).Berlin: Springer-Verlag, 1991, LNCS505: 166-178.
|
| [11] |
KERMIA O.Timing analysis of TTEthernet traffic[J].Journal of Circuits Systems & Computers, 2015, 24(9):1550140. doi: 10.1142/S0218126615501406
|
| [12] |
POZO F, STEINER W, RODRIGUEZ-NAVAS G, et al.A decomposition approach for SMT-based schedule synthesis for time-triggered networks[C]//Emerging Technologies & Factory Automation.Piscataway, NJ: IEEE Press, 2015: 1-8. https://www.researchgate.net/publication/308853509_A_decomposition_approach_for_SMT-based_schedule_synthesis_for_time-triggered_networks
|
| [13] |
张英静, 何锋, 卢广山, 等.基于TTE的改进加权轮询调度算法[J].北京航空航天大学学报, 2017, 43(8):1577-1584. http://bhxb.buaa.edu.cn/CN/abstract/abstract14152.shtml
ZHANG Y J, HE F, LU G S, et al.A modified weighted round robin scheduling algorithm in TTE[J].Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(8):1577-1584(in Chinese). http://bhxb.buaa.edu.cn/CN/abstract/abstract14152.shtml
|
| [14] |
POZO F, RODRIGUEZ-NAVAS G, HANSSON H, et al.SMT-based synthesis of TTEthernet schedules: A performance study[C]//IEEE International Symposium on Industrial Embedded Systems.Piscataway, NJ: IEEE Press, 2015: 1-4. https://www.researchgate.net/publication/314921079_SMT-based_synthesis_of_TTEthernet_schedules_A_performance_study
|
| [15] |
SHEIKH A A.Strictly periodic scheduling in IMA-based architectures[J].Real-Time Systems, 2012, 48(4):359-386. doi: 10.1007/s11241-012-9148-y
|
Figures(4) / Tables(2)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
