| Citation: | SHANG Lihong, TAN Te, ZHOU Miet al. Time windows distribution algorithm for real-time harmonic-period partition system on uniprocessor platform[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(1): 43-49. doi: 10.13700/j.bh.1001-5965.2016.0980(in Chinese)
|
Recently the avionics system is quickly transferring to integrated modular architecture. To prevent the mutual interference between different applications, IMA software usually adopts partition mechanism. Due to the "time partition", the traditional real-time schedulability analytical method is not applicable. This paper researches a class of special partition system, which is called harmonic-period partition system on uniprocessor platform. This paper gives the formalized definition of harmonic-period partition system and the necessary and sufficient condition of schedulability of tasks in harmonic-period partition system. On this basis, this paper proposes an algorithm, which is called time windows distribution algorithm. This algorithm distributes multiple time windows for each partition in the main time frame. This algorithm must be able to find a feasible schedule table for a harmonic-period partition system if this system is schedulable theoretically, and all tasks in partitions will not timeout if the global scheduler schedules partitions according to this schedule table. The algorithm proposed in this paper can be applied to practical engineering.
| [1] |
WATKINS C B, WALTER R. Transitioning from federated avionics architectures to integrated modular avionics[C]//Digital Avionics Systems Conference, 2007. Piscataway, NJ: IEEE Press, 2007: 2. A. 1-1-2. A. 1-10.
|
| [2] |
周强, 熊华钢.新一代民机航空电子互连技术发展[J].电光与控制, 2009, 16(4):1-6. https://www.wenkuxiazai.com/doc/28d17de59b89680203d8254f.html
ZHOU Q, XIONG H G.Development of the new generation civil avionic interconnection technology[J].Electronics Optics & Control, 2009, 16(4):1-6(in Chinese). https://www.wenkuxiazai.com/doc/28d17de59b89680203d8254f.html
|
| [3] |
沈玉龙, 崔西宁, 马建峰, 等.综合化航空电子系统可信软件技术[J].航空学报, 2009, 30(5):938-945. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hkxb200905030&dbname=CJFD&dbcode=CJFQ
SHEN Y L, CUI X N, MA J F, et al.Trust software technology in integrated avionics systems[J].Acta Aeronautica et Astronautica Sinica, 2009, 30(5):938-945(in Chinese). http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hkxb200905030&dbname=CJFD&dbcode=CJFQ
|
| [4] |
ARINC. avionics application software standards interface: ARINC 653[S]. Annapolis: AEEC, 2003.
|
| [5] |
杨霞, 桑楠, 雷剑, 等.嵌入式高可信架构中基于静态模型的调度研究[J].航空学报, 2009, 30(12):2387-2394. doi: 10.3321/j.issn:1000-6893.2009.12.022
YANG X, SANG N, LEI J, et al.Scheduling based on static model in trusted architecture for embedded systems[J].Acta Aeronautica et Astronautica Sinica, 2009, 30(12):2387-2394(in Chinese). doi: 10.3321/j.issn:1000-6893.2009.12.022
|
| [6] |
LIU J W S.Real-time sytem[M].Upper Saddle River:Prentice Hall, 2003:130-140.
|
| [7] |
MOK A K, FENG X, CHEN D. Resource partition for real-time systems[C]//7th IEEE Proceedings of Real-time Technology and Applications Symposium. Piscataway, NJ: IEEE Press, 2001: 75-84.
|
| [8] |
谭龙华, 杜承烈, 雷鑫.ARINC 653分区实时系统的可调度分析[J].航空学报, 2015, 36(11):3698-3705. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hkxb201511020&dbname=CJFD&dbcode=CJFQ
TAN L H, DU C L, LEI X.Schedulability analysis for ARINC 653 partitioned real-time systems[J].Acta Aeronautica et Astronautica Sinica, 2015, 36(11):3698-3705(in Chinese). http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hkxb201511020&dbname=CJFD&dbcode=CJFQ
|
| [9] |
CARNEVALI L, PINZUTI A, VICARIO E.Compositional verification for hierarchical scheduling of real-time systems[J].IEEE Transactions on Software Engineering, 2013, 39(5):638-657. doi: 10.1109/TSE.2012.54
|
| [10] |
陈平, 魏峰, 李蜀瑜.ARINC 653调度算法研究[J].现代电子技术, 2015, 38(15):29-32. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=xddj201512009&dbname=CJFD&dbcode=CJFQ
CHEN P, WEI F, LI S Y.Study on ARINC 653 scheduling algorithm[J].Modern Electronics Technique, 2015, 38(15):29-32(in Chinese). http://kns.cnki.net/KCMS/detail/detail.aspx?filename=xddj201512009&dbname=CJFD&dbcode=CJFQ
|
| [11] |
李昕颖, 顾健, 何锋, 等.硬实时系统在强分区约束下的双层分区调度[J].计算机学报, 2010, 33(6):1032-1039. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx201006008&dbname=CJFD&dbcode=CJFQ
LI X Y, GU J, HE F, et al.Two-level partition scheduling in hard real time system under strong partition constraints[J].Chinese Journal of Computers, 2010, 33(6):1032-1039(in Chinese). http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx201006008&dbname=CJFD&dbcode=CJFQ
|
| [12] |
周天然, 熊华钢.航空电子系统混合实时任务的双层调度[J].航空学报, 2011, 32(6):1067-1074. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hkxb201106014&dbname=CJFD&dbcode=CJFQ
ZHOU T R, XIONG H G.Two-level hierarchical scheduling for hybrid real-time tasks in avionics systems[J].Acta Aeronautica et Astronautica Sinica, 2011, 32(6):1067-1074(in Chinese). http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hkxb201106014&dbname=CJFD&dbcode=CJFQ
|
| [13] |
LIPARI G, BINI E, NGUYEN C, et al.A methodology for designing hierarchical scheduling system[J].Journal of Embedded Computing-Real-time System, 2005, 1(2):257-269. http://portal.acm.org/citation.cfm?id=1233768
|
| [14] |
WAN M, TIAN S. Research on schedulability of partition scheduling for IMA[C]//20114th International Symposium on Computational Intellingence and Design. Piscataway, NJ: IEEE Press, 2011, 2: 322-325.
|
| [15] |
NASRI M, FOHLER G. An efficient method for assigning harmonic periods to hard real-time tasks with period ranges[C]//201527th Euromicro Conference on Real-Time Systems. Piscataway, NJ: IEEE Press, 2015: 149-159.
|
| [16] |
桥乃强, 徐涛, 谷青范.ARINC 653分区调度算法的研究与改进[J].计算机工程, 2011, 37(20):249-251. doi: 10.3969/j.issn.1000-3428.2011.20.085
QIAO N Q, XU T, GU Q F.Research and improvement of ARINC 653 partition schedule algorithm[J].Computer Engineering, 2011, 37(20):249-251(in Chinese). doi: 10.3969/j.issn.1000-3428.2011.20.085
|
Figures(5) / Tables(3)
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:
