Open Access
Issue
JNWPU
Volume 44, Number 2, April 2026
Page(s) 393 - 404
DOI https://doi.org/10.1051/jnwpu/20264420393
Published online 12 June 2026

© 2026 Journal of Northwestern Polytechnical University. All rights reserved.

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

信息技术的快速发展推动飞行器操作系统向高集成、强实时方向演进[1]。多核多分区架构的引入为满足复杂任务负载与严格实时约束提供了硬件基础[2]。在分区实时操作系统中,用户任务被抽象为可调度的任务实体,也称为进程[34],其调度策略直接决定系统资源利用率与任务响应性能[5]。越来越复杂的任务请求,使智能生成调度策略成为操作系统领域亟待解决的关键问题[6]。

在操作系统中可以将进程调度算法分为静态调度算法和动态调度算法。随着机载任务复杂度提升,传统静态调度难以适应动态需求[7]。动态调度分为抢占式调度和非抢占式调度[8],抢占式调度虽灵活性强,却面临调度表生成困难、多约束耦合等挑战。如何实现多分区调度策略的智能化与最优化生成,已成为飞行器机载软件设计的核心问题。

现有调度研究主要沿2条路径展开:①基于形式化建模的抢占行为分析,如Petri网[9]与时间自动机[10];②基于数学优化的可调度性判定与策略设计,Liu等[1113]建立了利用率与最坏响应时间分析框架,后续学者结合分层决策与优化算法实现了动态调度[1416]。针对分区安全隔离需求,两级层次式调度成为工程应用主流[1719],通过固定时间帧分配分区窗口,结合分区内优先级调度保障确定性。然而,现有方法多依赖经验规则或单层优化,难以在多核、多分区、强抢占及复杂时空约束下实现全局调度表的自动寻优,缺乏基于近代优化理论的系统化建模与高效求解框架。

针对上述局限,本文面向多分区操作系统调度表智能生成难题,综合考虑进程周期性、最坏执行时间(WCET)、截止期、动态优先级、分区时空隔离及抢占干扰等多维约束,提出一种基于双层优化模型的智能调度方法。外层确定时间窗口的数量和对应分区,内层处理小规模优化问题,求解分区内进程的最优调度序列。通过构建定量可调度性约束并设计高效求解算法,自动输出满足严格实时性要求的最优调度表,显著提升系统资源利用率与调度确定性。本文主要贡献包括:建立融合多维实时约束的多分区调度双层优化模型;设计兼顾全局可行性与局部最优性的调度表智能生成算法;通过典型机载任务场景验证方法的有效性与工程适用性。

1 多分区智能调度模型

首先从单个分区的可调度性入手,再扩展到多分区的情况。单个分区的可调度性意味着该分区内所有进程都能正常运行,而一个进程可调度的前提是其周期和截止期始终得到满足。在分析单个分区内的进程时,只需关注同一分区内其他进程的影响;但在处理多个分区中的进程时,需要同时考虑所在分区内其他进程以及其他分区的干扰。基于这些基本约束条件,构建一个基于最优化技术的多分区智能调度模型,以确定最优的调度方案。表 1归纳了本文常用符号。

表1

主要符号

依据所研究问题的具体特征, 本文的量化建模基于如下基本假设:

1) 分区内进程按索引i降序排列优先级;

2) 非周期进程的周期大小设为最大运行时间LL;

3) 每个调度表至少包含1个时间窗口, 单窗口仅属1个分区, 可含空闲段;

4) 分区与进程属性预定义, 进程不可跨分区。

1.1 单分区可调度性

首先讨论单个分区的可调度性问题。为此, 引入繁忙区间的概念。

定义1  若时间区间[a, b]内只有第i级以及更高优先级的进程运行, 且区间外无此类进程运行, 则称[a, b]为第i级繁忙区间。

引理1  对于进程tk, i的1次运行, 当tk, i及所有优先级比tk, i高的进程都在0时刻就绪时, 此次运行的响应时间最长。

对于任意的周期进程, 由引理1可得:

引理2  令

Mathematical equation

若对分区k中的任意进程tk, i, i=1, 2, …, nk, 有(1)式成立, 则分区k是可调度的。

Mathematical equation(1)

式中, Mk, i=min{m|Wk, i(m, mTk, i)≤1}。

1.2 多分区可调度性

多分区场景下, 需额外考虑其他分区时间窗口对当前分区的抢占干扰。本文采用虚拟进程法进行建模: 将不属于分区k的时间窗口视为高优先级、不可抢占的虚拟进程, 其周期、截止期与运行时长均对应窗口参数; 将虚拟进程加入分区k的进程集, 即可在单分区框架下统一分析跨分区干扰[13]。

定理1  考虑多分区调度问题中的分区k, 若其满足(2)式,则分区k在最大运行时间LL内是可调度的。

Mathematical equation(2)

式中,1Fjk为示性函数,当Fjk时,它等于1, 当Fj=k时,它等于0;Mathematical equation

证明  分析第k个分区可调度性, 设虚拟进程个数为Mathematical equation。也就是说, 将第k个分区看成是包含Mathematical equation个进程的分区, 各个进程属性如表 2所示。其中, 对Mathematical equation形成对Mathematical equation的一个置换。

表2

各进程属性

对于分区Ak的任意真实进程tk, i,Mathematical equation, 定义

Mathematical equation(3)

由引理2, 该分区可调度需要满足

Mathematical equation(4)

式中,Mathematical equation, (2)式的左端加号右侧项可展开为分区k内的普通进程和其他虚拟进程两部分, 如(5)式所示。

Mathematical equation(5)

由于Mathematical equation, 且g(·)正好是1, 2, …,Mathematical equation的一个置换, 虚拟进程对应的求和部分满足(6)式。

Mathematical equation(6)

将虚拟进程的运行时间和起始时间代入, 截止期约束(4)式可以等价地写成

Mathematical equation(7)

对普通进程对应的求和公式中的下标进行变量代换, (7)式可以转化为

Mathematical equation(8)

注意到, 对每个分区k, 虚拟进程的个数Mathematical equation实际上是k的函数, 即Mathematical equation。当要综合考虑所有分区的约束时, 会出现记号上的混淆。使用示性函数1Fjk描述截止期约束,可将(8)式转换为(9)式。

Mathematical equation(9)

在最大运行时间内, 所有进程的运行总时间一定小于等于L, 因此进程tk, i在主时间框架内的真实运行次数大于等于Mathematical equation。因为分区k未必在开始时刻就绪, 所以Mathematical equation大于等于进程tk, i在主时间框架内的真实运行次数, 进而大于等于Mathematical equation, 即

Mathematical equation

由于虚拟进程和分区k内的普通进程并不都在同一时刻就绪, 为保证所有进程的可调度性, 直接将Nk, i固定取为上界Mathematical equation, 因此有

Mathematical equation(10)

1.3 多分区智能调度优化模型

综合可调度性约束与系统性能指标, 构建一个最优化模型, 满足进程可调度性及时间窗口稠密性约束, 智能确定最佳调度方案。

约束1  进程可调度性

由定理1, 所有K个分区满足可调度性约束

Mathematical equation(11)

式中

Mathematical equation

约束2  时间窗口稠密性

时间窗口在主框架内连续、不交且稠密, 即

Mathematical equation(12)

目标1  最少时间窗口切换次数

用示性函数1FrFr+1表示一次分区切换, 统计所有时间窗口的分区切换总数, 目标函数如(13)式所示。

Mathematical equation(13)

目标2  最大时间窗口利用率

将各个窗口内进程运行总时长和时间窗口长度的比值定义为时间窗口的总利用率, 向上取整取近似, 作为时间窗口利用率目标函数

Mathematical equation(14)

综合上述约束条件和目标函数, 则可构建多分区智能调度优化模型如(15)式所示。

Mathematical equation(15)

1.4 优化模型的等价转化

1.3节建立的多分区智能调度优化模型的第一组约束中包含极小极大运算, 导致优化问题难于求解。为此, 考虑该约束的等价转化。注意到

Mathematical equation(16)

可等价写成

Mathematical equation

使得

Mathematical equation(17)

鉴于取整运算在优化模型中难以处理, 引入(18)式的整值辅助变量。

Mathematical equation(18)

则第一组约束可等价表示为Mathematical equation,有

Mathematical equation

综上, 前述多分区智能调度优化模型可等价写为(19)式。

Mathematical equation

Mathematical equation(19)

2 智能调度优化问题的求解算法

由于优化问题(19)的决策变量维度高, 且表示时间窗口对应分区的变量Fr出现在决策变量Sr的指标上, 优化问题呈强耦合与非凸特性, 无法直接求解。为此, 设计一种新型双层优化算法: 外层确定时间窗口的数量M和对应的分区F; 内层确定时间窗口的其他属性, 包括变量S, Y, τ, y, c。在相邻窗口分区互异性条件下, 目标函数中的切换次数等价于窗口数量M, 外层通过迭代削减低效窗口以逼近最优调度表。

2.1 双层优化算法

双层优化算法的总体框架可描述如下:

算法1  双层优化算法

输入:所有表示进程属性的参数值Tk, i, Dk, i, Ck, i, k=1, 2, …, K, i=1, 2, …, nk,主时间框架长度L,最大运行时长LL,阈值α, β

输出:时间窗口属性Sr, Yr, Fr, r=1, 2, …, M

初始化:l=0,窗口数

Mathematical equation

步骤1  确定窗口分区的排列方法

若存在分区k,使得该分区内Mathematical equationMathematical equation, 则调用算法2;

若存在分区k,使得该分区内Mathematical equationMathematical equation,则调用算法4;

否则,调用算法3;结束若。

输出时间窗口对应的分区排列{F10, F20, …, FM0}, 进入步骤2。

步骤2  求解优化问题(19)

固定{F1, F2, …, FM}={F1l, F2l, …, FMll},调用算法5求解优化问题(19),记最优解为(Fl, Sl, Yl, Ml),相应的最优目标函数值为wl,令l*=l, (Fl*, Sl*, Yl*, Ml*)=(Fl, Sl, Yl, Ml), 进入步骤3。

步骤3  减小窗口数量

计算每个窗口的利用率为wj,若min{v|Fv=Fj, v=1, 2, …, M}=j, 则令Mathematical equation

否则

Mathematical equation

删除窗口利用率最低的第Mathematical equation个窗口,窗口总数变为Ml+1=Ml-1, l=l+1,新的窗口排列变为{F1l, F2l, …, FMll},进入步骤4。

步骤4  终止条件

固定{F1, F2, …, FM}={F1l, F2l, …, FMll},调用算法5求解优化问题(19),若存在可行解,则令l*=l, (Fl*, Sl*, Yl*, Ml*)=(Fl, Sl, Yl, Ml), wl*=wl, 进入步骤3;否则,返回l-1步获得的最优解(Fl*, Sl*, Yl*, Ml*)。

结束若。

结束算法。

2.2 窗口分区排列算法

在给定时间窗口个数且时间窗口长度未知的情况下, 为了给时间窗口分配分区, 考虑各分区中进程的WCET、截止期、周期等属性特点, 针对不同实际情况设计了3种分区排列算法, 分别称为算法2、算法3、算法4, 以便提高整个智能调度算法的总体效率与鲁棒性。

算法2以分区内各个进程的周期大小为判别准则, 优先为周期短的分区分配窗口, 使得各个分区离散地分布于主时间框架内的时间窗口中。

算法2  基于最小周期的分区排列算法

输入: 窗口数Ml, 所有表示进程属性的参数值Tk, i, Dk, i, Ck, i, k=1, 2, …, K, i=1, 2, …, nk, 主时间框架长度L

输出: 窗口对应分区{F1l, F2l, …, FMll}。

步骤1  计算分区特征周期, 即该分区内各个进程周期的最小值, 为Mathematical equation; 按各分区周期从小到大对其进行排序, 即有rank(k)={Tk从小到大排列的次序}, 按rank(k)的值对分区重新进行设置。

步骤2  令每个分区k对应的时间窗口个数为Mathematical equation

步骤3  记已排列的时间窗口集合为F

Mathematical equation

For k=1, 2, …, K

ForMathematical equation

Mathematical equation唯一,则

Mathematical equation

否则

Mathematical equation

结束若。

Mathematical equation

结束For。

结束For。

结束算法

针对实际中可能存在同一分区内各个进程的周期相差较大的情况, 设计算法3。

算法3  分块式分区排列算法

输入: 窗口数Ml, 所有表示进程属性的参数Tk, i, Dk, i, Ck, i, k=1, 2, …, K, i=1, 2, …, nk, 主时间框架长度L

输出: 窗口对应分区{F1l, F2l, …, FMll}。

步骤1  计算所有进程的周期的平均值

Mathematical equation

步骤2  对每个分区k, 计算周期小于Mathematical equation的所有进程的平均周期

Mathematical equation

以及周期大于等于Mathematical equation的所有进程的平均周期

Mathematical equation

步骤3  将Mathematical equation从小到大进行排序。如果相邻的2个数来源于同一个分区, 则删除后一个。将合并后的序列所对应的分区序列记为rank, 则rank(s)表示序列中第s个分量所对应的分区。这里rank中任意相邻分量所对应的分区是不同的, 记rank的长度为r

步骤4  Fil={rank(s)s=i mod r}, i=1, 2, …, Ml

结束算法。

为有效处理WCET和截止期相差较小的情况, 设计算法4, 该算法考虑分区内各个进程的WCET和截止期之间的关系。

算法4  基于截止期及WCET的分区排列算法

输入: 窗口数Ml, 所有表示进程属性的参数Tk, i, Dk, i, Ck, i, k=1, 2, …, K, i=1, 2, …, nk, 主时间框架长度L

输出: 窗口对应分区{F1l, F2l, …, FMll}

步骤1  对每个分区k, 计算Mathematical equation, k=1, 2, …, K, 按该比值降序进行排序, 有rank(k)={Rk从大到小排列的次序}, 按rank(k)的值对分区重新进行设置。

步骤2  将分区k所对应的时间窗口个数设置为Mathematical equation

步骤3  记已排列的时间窗口集合为F

Mathematical equation

For k=1, 2, …, K

For r=0, 1, …, ck-1

Mathematical equation唯一, 则

Mathematical equation

否则

Mathematical equation

结束若。

Mathematical equation

Mathematical equation

结束For。

结束For。

结束算法

2.3 分解算法

在外层按照算法2~4确定了M, F之后, 需要求解内层优化问题(19), 其决策变量仅为S, Y, τ, y, c。考虑到内层优化问题仍存在变量维度高、规模大的挑战, 将内层优化问题(19)分解为一系列较小规模的优化问题来处理。

在给定F时, 优化问题(19)的目标函数变为

Mathematical equation(20)

而问题(19)中相应的约束条件需要对任意的k=1, 2, …, K, i=1, 2, …, nk, m=1, 2, …, Nk, i都成立, 因此可相对于k, i, m, 将优化问题(19)直接分解成相应的子问题。不过, 除相对于k, i, m可分解的约束外, 还有如(21)式所示的耦合约束。

Mathematical equation(21)

这些约束关联着所有的决策变量, 相对k, i, m不具有可分性。为此, 利用增广拉格朗日方法, 通过引入拉格朗日乘子, 将约束(21)式置于放至目标函数中, 将优化问题变为2层。下层需要求解给定拉格朗日乘子λ时对应的子优化问题P(λ),如(22)式所示, 式中其余约束条件和(19)式相同。

Mathematical equation(22)

同时, 上层则需要对拉格朗日乘子寻优, 即求解如(23)式所示优化问题。

Mathematical equation(23)

为提高求解效率, 采用交替迭代法求解下层优化问题。首先, 给定τ, y, c, 求解问题P(λ), 更新S, Y, 即

Mathematical equation(24)

然后, 给定S, Y, 求解问题P(λ), 更新τ, y, c。由于可分性, 最大化问题可相对于k=1, 2, …, K, i=1, 2, …, nk, m=1, 2, …, Mk, i分解成一系列小规模的二次规划问题。分解后的子问题如(25)式所示,式中约束条件与(19)式相同。

Mathematical equation(25)

依次求解子问题Vk, i, m(λ, S, Y), k=1, 2, …, K, i=1, 2, …, nk, m=1, 2, …, Nk, i, 即可获得给定S, Y时问题P(λ)的解。

至此, 可将增广拉格朗日乘子算法的整体流程描述如下:

算法5  分解算法

输入: 外层迭代步数上限B, 内层迭代步数上限Db, 窗口数M, 终止阈值ε1, ε2, 参数α,初始步长s0, 缩减因子ρ∈(0, 1)和c∈(0, 1), 最大运行时长LL, 主时间框架长度L, 所有表示进程属性的参数Tk, i, Dk, i, Ck, i, k=1, 2, …, K, i=1, 2, …, nk

输出: Sr, Yr, r=1, 2, …, M

初始化:

b=0, 选取一组初始可行值λ(0), μ(0), τ(0), y(0), c(0)S(0)

步骤1  求解对应当前乘子λ(b)的优化问题V(λ(b))

步骤1.1  给定Mathematical equation, 求解优化问题(25), 约束为可调度性及非负约束, 得到Mathematical equation;

步骤1.2  给定Mathematical equation, 将原问题解耦为一系列独立的小规模二次规划子问题, 求解Mathematical equation, 得到Mathematical equation

步骤2  乘子的更新

更新二次项惩罚因子

Mathematical equation

更新拉格朗日乘子:

初始化: e=0;se=s0

使用Armijo准则自适应调整步长S(b), 采用梯度上升法更新拉格朗日乘子。

步骤3  终止条件

当目标函数改进量V(λ(b-1))-V(λ(b))<ε2或者达到最大迭代步数B时终止。

结束算法。

3 算法验证

为验证调度表生成与优化算法的有效性,本节基于多核多分区架构及典型航空任务时间属性,构建37组测试算例开展仿真实验。结果表明:当系统存在可行调度策略时,算法可自动寻优并输出全局最优调度表;当系统不可行时,算法能精准定位约束冲突并给出参数修正建议,充分验证了求解机制的可靠性与鲁棒性。

3.1 正例:可调度算例

输入典型任务属性(见表 3),算法经求解自动生成调度表(见表 4)。

表3

进程属性

表4

调度表

可行性校验显示,分区1, 2, 3的主调度周期分别为300, 600与60,各进程响应时间均严格满足截止期约束,系统判定为全局可调度。该结果证实算法在可行域内具备高效的寻优与调度表生成能力。

3.2 反例:不可调度算例

为检验算法的边界诊断能力,将表 3中进程1与2的最坏执行时间(WCET)及截止期调整为表 5参数。求解器判定该配置无可行解,终止调度表生成。诊断模块明确指出分区2累计WCET超出截止期约束, 并定量建议将相关进程截止期放宽至不小于16。该反向验证表明,算法不仅能识别不可行状态,还可提供精确的约束冲突归因与参数调优指引。

表5

进程属性

4 结论

本文研究了具有多属性进程的复杂多分区操作系统的可调度性与最优调度方案的确定。通过构建一个最优化模型,给出确定多分区操作系统中每个分区所分配的时间窗口的开始时间和运行时长,且生成满足各分区内进程可调度性约束的最佳调度表。使用双层优化算法求解所提出的优化模型。外层优化确定各个时间窗口与分区之间的关系,分别由基于最小周期分区排列、分块式分区排列、基于截止期和WCET分区排列3种算法构成。内层优化根据问题可分结构进行解耦分解,并用拉格朗日乘子法求解,以确定时间窗口的开始时间和运行时长。经过正反例验证,表明该算法对于可调度问题能够给出可行且最优的调度表,对于不可调度问题,该算法能给出不可行原因及修改建议。

References

  1. ZHANG Xiao, ZHI Tian. Machine learning inference framework on multi-core processor[J]. Computer Research and Development, 2019, 56(9): 1977–1987 (in Chinese) [Google Scholar]
  2. CHEN Gang, GUAN Nan, LYU Mingsong, et al. State-of-the-art survey of real-time multicore system[J]. Journal of Software, 2018, 29(7): 2152–2176 (in Chinese) [Google Scholar]
  3. LUIZ Andre Barroso, URS Holzle. The datacenter as a computer: an introduction to the design of warehouse-scale machines[M]. San Rafael: Morgan & Claypool Publishers, 2018. [Google Scholar]
  4. RAJKUMAR Buyya, CHEE Shinyeo, SRIKUMAR Venugopal, et al. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009, 25(6): 599–616. [Article] [CrossRef] [Google Scholar]
  5. MOHAMMAD Al-Fares, ALEXANDER Loukissas, AMIN Vahdat. A scalable, commodity data center network architecture[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(4): 63–74. [Article] [Google Scholar]
  6. TAN Jian, MENG Xiaoqiao, ZHANG Li. Coupling task progress for mapreduce resource-aware scheduling[C]//Proceedings of the IEEE International Conference on Computer Communications, 2013: 1618–1626. [Google Scholar]
  7. JIA Mengxin, FAN Yanfang, SONG Zhiwen, et al. Preemptive task scheduling method based on dynamic priority in VEC[J]. Journal of Beijing Information Science & Technology University, 2023, 38(6): 11–20 (in Chinese) [Google Scholar]
  8. 肖利民, 杨锦乾, 王锦权, 等. 一种广域分布式文件系统中的IO任务公平调度算法: CN117492948[P]. 2024-02-02. [Google Scholar]
  9. HE Leifeng, LIU Guanjun. Simulation of the point interval priority time Petri net and TCTL verification of the real-time system[J]. Journal of Software, 2022, 33(8): 2947–2963 (in Chinese) [Google Scholar]
  10. ZUO Zhengkang, ZHAO Shuai, WANG Changjing, et al. PPTA model and verification method for preemptive scheduling problem[J]. Journal of Software, 2024, 35(10): 4533–4554 (in Chinese) [Google Scholar]
  11. LIU Chunglaung, JAMES W Layland. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of the Association for Computing Machinery, 1973, 20(1): 46–61. [Article] [Google Scholar]
  12. OH Yingfeng, SON H Sang. Allocating fixed-priority periodic tasks on multiprocessor systems[J]. Real-Time Systems, 1995, 9(3): 207–239. [Article] [Google Scholar]
  13. LEHOCZKY J. Fixed priority scheduling of periodic task sets with arbitrary deadlines[C]//Proceedings 11th Real-Time Systems Symposium, 1990: 201–209. [Google Scholar]
  14. KIM Daeyoung, LEE Yannhang. Periodic and aperiodic task scheduling in strongly partitioned integrated real-time systems[J]. The Computer Journal, 2002, 45(4): 395–409. [Article] [Google Scholar]
  15. LIU Huai, HU Jifeng. Static optimal scheduling algorithm for periodic task of control system[J]. Computer Engineering, 2002, 28(5): 14–16 (in Chinese) [Google Scholar]
  16. HAO Chunliang, WANG Kai, WU Yanjun. An optimized two-level scheduling strategy in dataos[J]. Network New Media Technology, 2014, 3(1): 39–44 (in Chinese) [Google Scholar]
  17. 赵亮, 徐明道, 曹振兴, 等. 一种面向多核处理器的分区操作系统确定性调度方法: CN117687749[P]. 2024-03-12. [Google Scholar]
  18. 王浩然, 李小坤, 齐志新, 等. 一种操作系统任务分区调度方法、装置、电子设备及介质: CN118484284[P]. 2024-08-13. [Google Scholar]
  19. 王东方, 韩辉, 焦进星, 等. 一种分时分区操作系统的调度方法: CN119046013[P]. 2024-11-29. [Google Scholar]

All Tables

表1

主要符号

表2

各进程属性

表3

进程属性

表4

调度表

表5

进程属性

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.