北京航空航天大学学报 ›› 2018, Vol. 44 ›› Issue (1): 43-49.doi: 10.13700/j.bh.1001-5965.2016.0980

• 论文 • 上一篇    下一篇

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

尚利宏1, 谭特1, 周密2   

  1. 1. 北京航空航天大学 计算机学院, 北京 100083;
    2. 北京中航瑞博航空电子技术有限公司, 北京 100192
  • 收稿日期:2016-12-29 修回日期:2017-03-24 出版日期:2018-01-20 发布日期:2017-04-27
  • 通讯作者: 尚利宏 E-mail:shanglh@buaa.edu.cn
  • 作者简介:尚利宏,男,博士,副教授,硕士生导师。主要研究方向:嵌入式系统、容错技术;谭特,男,硕士研究生。主要研究方向:嵌入式系统;周密,男,博士。主要研究方向:嵌入式系统、容错技术。

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

SHANG Lihong1, TAN Te1, ZHOU Mi2   

  1. 1. School of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China;
    2. Reliable Avionics Technology Co., Ltd., Beijing 100192, China
  • Received:2016-12-29 Revised:2017-03-24 Online:2018-01-20 Published:2017-04-27

摘要: 目前航空电子系统正快速朝着综合模块化方向发展。为了防止同一计算平台上的应用相互干扰,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

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发