基于μC/OS-Ⅱ的实时分层调度算法研究

0引言

嵌入式实时系统由于自身CPU计算能力较弱和内存容量较低的原因，希望采用复杂度低、系统开销小的调度算法。目前的实时系统通常采用单优先级驱动的抢占式调度算法，根据任务的某一时间特性参数如任务周期或最后截止期等为各个任务分配系统资源[1][2]。这种抢占式调度策略具有灵活性和动态性等优点。但在，实际应用系统中也有一些由不相交的周期任务子集组成，每个子集是系统的一个主要部分，称之为子系统。例如，飞行管理系统包含飞行控制，电子设备和导航式三个子系统。这三个子系统的任务如果按照以前的静态、动态算法实现需要系统开发人员设计很复杂的调度算法，实时控制也相对困难[3][4]。本文按照分层思想在实时操作系统层面上设计调度算法，减轻了解决此类问题系统开发人员的负担，算法的主要思想是：修改内核的任务控制块，增加一个子模块标识来控制分层调度，采用固

定时间轮转算法调度各子系统模块，子系统中的任务按照速率单调算法调度，从而实现两层的调度策略。本文首先定义了分层调度系统的模型，并对分层调度算法的可调度性进行了理论分析；其次，以实时内核μC/OS-Ⅱ为背景，实现了具有分层调度功能的调度器，最后通过实验验证分层调度算法的可行性和正确性。

1 分层调度系统模型的定义

定义1 在不考虑释放抖动的情况下，一个任务集Τ={τ1,τ2,…, τn}中的任务τi 的属性可以用一个五元组（Mi， ,Pi,Di, Ei）来表示。其中，Mi 表示任务属于的模块； 是相位；Pi 表示任务周期，对于非周期任务，取其最小时间间隔作为周期；Di 表示任务完成

的最后期限；Ei 表示任务的最大请求运行时间。

在定义任务属性时，扩展以前任务描述的四元组到五元组[5]，增加了任务所属模块的属性，这一点是为了给子模块的索引表提供一个标志，以便实现任务集按子模块分层调度管理。

定义2 对于任务τi，其各实例从到达时刻至执行完成时刻之间的时间间隔称为该实例的响应时间,各实例响应时间的最大值称为任务τi的最大响应时间 Ri，若 Ri≤Di，则称任务τi可调度。

2 分层调度算法模型的实现

2．1分层模型的可调度性分析

假定：系统中具有n个独立的，可抢占的任务，并且任务的相对时限等于各自的周期。如果系统的总利用率U满足下式：