Time windows distribution algorithm for real-time harmonic-period partition system on uniprocessor platform
-
摘要:
目前航空电子系统正快速朝着综合模块化方向发展。为了防止同一计算平台上的应用相互干扰，IMA软件普遍采用分区机制。由于时间分区的引入，传统的实时周期任务可调度性分析已经不再适用。为此研究了一类特殊的分区系统——和谐周期分区系统在单处理器下的可调度性。给出了和谐周期分区系统的形式化定义以及系统中任务可调度性的充分必要条件，并基于此提出了一种分区时间窗口分配算法。该算法为每个分区在主时间帧内分配多个时间窗口，并且保证只要和谐周期分区系统在理论上可调度，该算法就一定能生成一个可行的调度表，使得当全局调度器按照此调度表周期地调度分区时，各个分区中的任务不会超时。本文提出的算法可以运用在实际的工程中。
Abstract: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.
-
Key words:
- partition /
- real-time /
- harmonic-period /
- schedulability /
- time window
-
表 1 用于案例分析的分区系统的任务参数
Table 1. Parameters of tasks of partitioning systems for case analysis
任务 分区 周期 截止时间 最坏执行时间 优先级 task1 A 8 8 1 H task2 A 2 2 1 L task3 B 4 4 1 H 
下载: 导出CSV
表 2 任务的工作实例的响应时间
Table 2. Response time of jobs instances of tasks
任务 最大响应时间 最小响应时间 平均响应时间 task1 0 0 0 task2 1 0 0.25 task3 3 1 2
下载: 导出CSV
表 3 用于算法对比的分区系统的任务参数
Table 3. Parameters of tasks of partitioning systems for algorithms comparison
任务 分区 周期 截止时间 最坏执行时间 优先级 task1 A 8 8 1 L task2 A 2 2 1 H task3 B 4 4 1 H
下载: 导出CSV
-
[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.htmlZHOU 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=CJFQSHEN 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.022YANG 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=CJFQTAN 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=CJFQCHEN 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=CJFQLI 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=CJFQZHOU 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.085QIAO 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 -
下载:
点击查看大图
计量
- 文章访问数: 604
- HTML全文浏览量: 43
- PDF下载量: 363
- 被引次数: 0
