留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

实时单核和谐周期分区系统时间窗口分配算法

尚利宏 谭特 周密

尚利宏, 谭特, 周密等 . 实时单核和谐周期分区系统时间窗口分配算法[J]. 北京航空航天大学学报, 2018, 44(1): 43-49. doi: 10.13700/j.bh.1001-5965.2016.0980
引用本文: 尚利宏, 谭特, 周密等 . 实时单核和谐周期分区系统时间窗口分配算法[J]. 北京航空航天大学学报, 2018, 44(1): 43-49. doi: 10.13700/j.bh.1001-5965.2016.0980
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)
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)

实时单核和谐周期分区系统时间窗口分配算法

doi: 10.13700/j.bh.1001-5965.2016.0980
详细信息
    作者简介:

    尚利宏  男, 博士, 副教授, 硕士生导师。主要研究方向:嵌入式系统、容错技术

    谭特  男, 硕士研究生。主要研究方向:嵌入式系统

    周密  男, 博士。主要研究方向:嵌入式系统、容错技术

    通讯作者:

    尚利宏, E-mail: shanglh@buaa.edu.cn

  • 中图分类号: V247;TP316.2

Time windows distribution algorithm for real-time harmonic-period partition system on uniprocessor platform

More Information
  • 摘要:

    目前航空电子系统正快速朝着综合模块化方向发展。为了防止同一计算平台上的应用相互干扰,IMA软件普遍采用分区机制。由于时间分区的引入,传统的实时周期任务可调度性分析已经不再适用。为此研究了一类特殊的分区系统——和谐周期分区系统在单处理器下的可调度性。给出了和谐周期分区系统的形式化定义以及系统中任务可调度性的充分必要条件,并基于此提出了一种分区时间窗口分配算法。该算法为每个分区在主时间帧内分配多个时间窗口,并且保证只要和谐周期分区系统在理论上可调度,该算法就一定能生成一个可行的调度表,使得当全局调度器按照此调度表周期地调度分区时,各个分区中的任务不会超时。本文提出的算法可以运用在实际的工程中。

     

  • 图 1  引理1证明示意图

    Figure 1.  Schematic for proving Lemma 1

    图 2  第1轮分配结果

    Figure 2.  Distribution results of the first iteration

    图 3  第2轮分配结果

    Figure 3.  Distribution results of the second iteration

    图 4  主时间帧内分区时间窗口布局

    Figure 4.  Layout of partition time windows in main time frame

    图 5  本文算法生成的调度表

    Figure 5.  Schedule table of proposed algorithm

    表  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.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
  • 加载中
图(5) / 表(3)
计量
  • 文章访问数:  394
  • HTML全文浏览量:  2
  • PDF下载量:  355
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-12-29
  • 录用日期:  2017-03-24
  • 刊出日期:  2018-01-20

目录

    /

    返回文章
    返回
    常见问答