| 本文已被：浏览 1823次 下载 3468次 |
码上扫一扫！ |
|
|
| 基于周期虚拟缩减的实时任务调度和分析方法 |
|
刘洪标1,2, 乔磊2, 杨孟飞3, 陈熙2, 马智2, 李少峰1,2
|
|
1.西安电子科技大学 计算机科学与技术学院, 陕西 西安 710071;2.北京控制工程研究所, 北京 100190;3.中国空间技术研究院, 北京 100094
|
|
| 摘要: |
| 针对航天器等安全关键系统中实时任务调度和可调度性分析的实际问题, 提出基于任务周期虚拟缩减的可调度性判定方法, 构建SHT (strong-hard task)任务模型对强硬实时任务进行精确描述, 并根据任务时间特性分配优先级. 虚拟化所有强实时任务为一个硬实时任务, 对此硬实时任务周期虚拟缩减并计算出其最差虚拟执行时间, 然后按RMS可调度性判定公式判定. 给出了判定方法的严格证明, 可对包含n个SHT任务的任务集进行快速可调度性判定, 此算法时间复杂度仅为O(n2). 在我国空间站计算机进行了对比验证, 实验表明判定效率优于现有可调度性判定方法, 平均运行时间开销降低了41.8%, 可调度率提高了5.7%. |
| 关键词: 动态扩展 实时任务 周期虚拟缩减 优先级分配 可调度性 |
| DOI：10.13328/j.cnki.jos.006394 |
| 分类号:TP316 |
| 基金项目:国家自然科学基金(61632005, 62032004) |
|
| Real-time Task Scheduling and Analysis Method Based on Virtual Zoom Out Period |
|
LIU Hong-Biao1,2, QIAO Lei2, YANG Meng-Fei3, CHEN Xi2, MA Zhi2, LI Shao-Feng1,2
|
|
1.School of Computer Science and Technology, Xidian University, Xian 710071, China;2.Beijing Institute of Control Engineering, Beijing 100190, China;3.China Academy of Space Technology, Beijing 100094, China
|
| Abstract: |
| Regarding the practical problems of the real-time task scheduling and analysis in safety-critical systems such as spacecraft, this study proposes a schedulability determination method based on virtual zoom out period, constructing a strong-hard task (SHT) model to accurately describe real-time tasks, and allocates priority based on task’s time characteristics. Virtualizing all strong real-time task as a hard real-time task, virtually reduces the period of the hard real-time task and calculates the worst virtual execution time, and then determines the schedulability according to the RMS schedulability judgment formula. This paper presents a rigorous proof of the method, which can make a fast schedulability determination on an SHT task set containing n tasks, and the time complexity of this algorithm is only O(n2). Comparative verification was carried out on the China space station computer, and the experiments show that the schedulability determination efficiency is better than the existing methods. The average running time overhead is reduced by 41.8%, and the schedulable ratio is increased by 5.7%. |
| Key words: dynamic expansion real-time task virtual zoom out period priority assignment schedulability |
