Analysis of automatic generation algorithm for airborne multi-partition operating system scheduling table

机载多分区操作系统调度表自动生成算法分析

¹ School of Software, Northwestern Polytechnical University, Xi'an 710072, China
² Xi'an Aeronautics Computing Technique Research Institute, Aviation Industry Corporation of China, Xi'an 710065, China
³ Innovation Center for Embedded Common Basic Software Technology, Xi'an 710065, China

Received: July 2025

Abstract

With the rapid development of computer technology, airborne operating systems face increasingly complex real-time task challenges. Multi-core multi-partition operating systems have emerged as one of the effective solutions to address these issues. In response to the problem of difficulty in manually configuring scheduling tables for airborne multi-partition operating systems, this paper comprehensively considers factors such as process periodicity, worst-case execution time, deadlines, priorities, partition attributes, and mutual interruption relationships between processes. By integrating optimization theory, the paper conducts a quantitative analysis and modeling of the schedulability of multi-partition operating systems. A two-level optimization scheduling model is established to allocate optimal start times and runtime lengths for each partition, thereby achieving automated scheduling table generation. To solve this model, the structural characteristics of optimization problems are leveraged for decoupling analysis, and efficient iterative solution algorithms are designed by combining the Lagrange multiplier method and alternating direction method. Testing was conducted on the self-generating and optimizing scheduling algorithm. Results demonstrated that the algorithm could intelligently generate optimal schedules for each section, determine schedulability, provide modification suggestions for unschedulable issues, and effectively reduce operational risks during actual flight operations.

摘要

随着计算机技术的飞速发展, 机载操作系统面临日益复杂的实时任务挑战, 多核多分区操作系统成为解决这一问题的有效方法之一。针对机载多分区操作系统调度表难以通过人工有效配置的问题, 综合考虑进程周期性、最坏情况运行时间、截止期、优先级、分区属性及进程间打断关系等复杂因素, 结合最优化理论对多分区操作系统的可调度性进行定量分析和建模。通过建立双层优化调度模型, 为各分区分配最优的时间窗口开始时间和运行时长, 实现调度表智能生成。利用优化问题的结构特征进行解耦分析, 并综合运用拉格朗日乘子法和交替方向法为该模型设计了高效的迭代求解算法。对调度表智能生成及优化算法的有效性进行验证, 结果表明该算法能够智能生成各分区最优调度表及可调度性判断结果, 对于不可调度问题给出修改建议, 可有效降低实际运行时的试飞风险。