三维调度器模型及其调度算法

摘要

本发明公开了一种三维调度器模型及其调度算法，对各种类型的实时任务的时间确定性、安全性、可靠性进行分析之后，将各类实时任务模型转换为统一的三维立体层次关系模型，再根据任务所在的层次进行调度策略的调整，最后将其映射到与核对应的二维时空图中。该策略不仅要考虑负载均衡以提升多核的并行执行效率而且要能满足任务执行过程中的实时性、可靠性和安全性需求。此外，该模型和算法还对各种实时任务的共享资源同步机制进行研究，研究出一种新的共享资源管理方案，以减少死锁的发生和防止出现CPU饥饿现象。

说明书

技术领域

本发明涉及嵌入式系统领域，具体涉及一种三维调度器模型及其调度算法。

背景技术

自从2004年ARM公司与英国剑桥推出了世界上第一块嵌入式多核处理ARM11 MPcore以来，片上多核处理器CMP(ChipMulti-Processors)凭借体积小、通信延迟低、设计 和验证周期短、高频、低功耗以及低成本等特点很快就成为嵌入式应用领域强劲的驱动力。

目前，多核已经被广泛地应用到各种设备中，但软件的发展却远远落后于硬件的 发展，尤其是在嵌入式系统中任务的调度和分解直接影响到系统软件的正常使用，当前支 持多核的嵌入式操作系统都是针对单一类型的实时任务，要么只是考虑周期性执行的实时 任务，要么只是考虑一次性执行的非周期实时任务。目前还没有针对多种混合类型的实时 任务的研究。这种情况下的多核系统，要么会存在系统利用率不高，要么会存在系统安全性 无法保障等问题。因此在当前多核芯片核数迅猛增长的情况下，如何尽快提高软件并行效 率，加速实现多核计算在嵌入式系统中的应用是最为紧要的、迫切的问题。本项目紧跟多核 计算研究的热点问题，研究嵌入式系统中多种类型的实时任务的调度、分解以及同步机制 问题。这不仅可以提高系统效率，加速多核在嵌入式系统中的应用，而且也是符合当前国内 国防、军事科技发展的需要。

然而多核处理器性能的提高主要来自于片上处理器核数的增加，其潜在并行性能 的发挥将主要依赖于多核软件的发展。而当前的嵌入式软件大都是基于单核系统开发的， 并且都以单一类型的实时任务(如周期任务或非周期任务)作为设计思想，执行过程是串行 的。随着嵌入式系统处理的任务类型越来越复杂，采用原有类型的软件，无论在实时性、可 靠性，还是在安全方面都存在很多问题。例如，在同一时刻不同种类的实时任务申请同一资 源，由于原系统任务调度方案的唯一性，会导致因为按规则等待而超过了预期时间，无法满 足任务实时性的要求，更无法保证安全关键任务的完成，从而降低系统的可靠性，造成重大 事故的发生，导致无可挽回的损失。那么研究提高软件可靠性和安全性、有效降低软件错误 出现概率、提出更为先进的调度方案和同步机制就成为嵌入式软件多核计算研究的焦点。

那么，在嵌入式多核平台下，如何使多种类型的串行任务划分为并行任务并映射 到数量有限的核上去执行以提高系统整体性能；如何在任务并行执行条件下满足实时性、 高可靠性以及高安全性的需求，都是有待解决的问题。例如在单核系统中，优先级抢占调度 是一种常见的实时任务调度策略，但在多核系统中，低优先级任务会与高优先级任务同时 在不同的核上执行，很有可能导致低优先级的任务先执行完而高优先级任务未能满足实时 性需求。而一旦混合关键任务出现这种情况，则高可靠性和高安全性都不能得到保障。其 次，对于共享资源的竞争问题。单核采用锁机制对共享数据进行访问，一旦一个线程取得了 锁，那么其他线程进行锁操作时必须等待，而在多核体系结构下，由于核数增加，将导致核 之间对共享资源的竞争加剧。如果采用大量锁机制对共享资源进行访问，就容易导致死锁 和优先级反转现象，也会导致某些CPU处于饥饿状态，从而大大降低多核并行执行的效率。 这必将成为影响多核并行计算性能发挥和软件扩展的一个关键性问题。要解决这个问题， 一种方法是要减少共享数据的访问，将同步计算转化为线程私有计算。这种方法开销较大 且还是不能避免死锁现象。另一种方法则是使用原子操作的“无锁(Lock-Free)编程”。然 而，无锁编程的难度和复杂度又非常高，因此对共享资源的竞争问题是嵌入式系统软件面 临的又一个巨大的挑战。

在嵌入式领域中，实时性、可靠性是整个系统的灵魂，而系统软件正是保障这些特 性的强有力的支柱。在多核和嵌入式相结合的领域，要想充分发挥多核的优势，不但在调度 时需要考虑负载均衡、同步机制等细节，更重要的还要同时考虑实时性、可靠性以及关键任 务的保障机制。这对于目前串行调度的实时嵌入式系统软件来说，无疑是一个巨大的挑战。 目前国内外就上述问题的研究正处在激烈讨论当中，各种方法层出不穷，但大都是针对单 一实时任务类型进行的，并没有一个统一的、完整的、系统的整体解决方案。因此，针对嵌入 式多种实时任务的特点，研究出一种高可靠的、高安全的调度模型和调度算法势在必行。

当前嵌入式多核平台下的实时调度模型，主要是针对相互独立的实时周期任务。 该模型下的调度算法有两大类：全局调度算法和任务划分调度算法。全局调度算法的优点 是核利用率高，缺点是要想达到负载均衡必须进行线程迁移，而迁移的开销很大。任务划分 调度算法的优点是能够达到负载均衡，但却使核利用率较低。于是，采用何种方法使得既能 提高核利用率又能达到负载均衡便成为业界研究的焦点问题。为此，当前的研究者采用两 种方法：一种方法是将任务划分看成装箱问题，通过采用启发式方法设立各种任务划分条 件以提高核利用率。但如何设立任务划分条件，使核利用率达到最优则成为难点问题；另一 种是将任务划分和全局进行结合，以减少迁移开销。但如何结合才既能提高核利用率，又使 负载均衡且开销又小便成为了难点。

当前混合关键任务调度算法有三大类：(1)基于优先级的任务调度方法。该方法系 统利用率不高，且并不能防止关键级别反转现象；(2)基于资源任务划分的调度算法。该算 法实现起来比较繁琐，且在满足任务时限不丢失的情况下，对核处理速度要求很高；(3)基 于slack-aware的调度算法，该算法要求对每一个任务的slack时间进行多次推算，计算过 程很繁琐，时间复杂度高且zero-slack方法只能调度一小部分的任务集。

在传统的实时任务调度过程中，任务对共享数据的访问通常采用锁机制，这种机 制可能会引起死锁和优先级翻转现象。如果应用在混合关键系统中，还可能会导致关键级 别翻转现象。

所研究的多核任务分配和调度以及同步机制等问题是多核计算在嵌入式系统中 存在的很重要的问题之一。虽然目前国内外有些研究，但都没有进行综合考虑，达到理想状 况。由于嵌入式系统中存在各种各样的实时任务，如有安全关键任务，有混合关键任务，有 周期任务也有非周期任务，有零星任务也有管道任务，所有的这些任务都有可能会同时存 在于同一个复杂系统中。而目前大多数的研究都是针对其中一项或者两项进行的研究、并 没有整体进行规划，也没有将这些不同类型的实时任务的调度方法统一应用到综合平台 中。另外，随着任务类型的增加，共享资源的管理也是很棘手，因为多核会加剧资源竞争，多 种类型的任务特点不一，如何解决好资源分配和同步也是需要仔细研究的。如果这些问题 解决的很好，那么多核在嵌入式系统中的效率就会得到很大的提升，这将大大加速我国在 国防、航空、航天等众多实时领域的技术发展而且对嵌入式领域中的发展起到巨大的推动 作用，对我国现在和未来科技发展具有重要的技术推动作用。

发明内容

为解决上述问题，本发明提供了一种三维调度器模型及其调度算法。

为实现上述目的，本发明采取的技术方案为：

三维调度器模型及其调度算法，三维调度器模型及其调度算法，其特征在于，三维 调度器模型采用三维坐标空间(x，y，z)，其中x轴代表实时周期任务的job执行完毕所需要 的时间，y轴代表实时周期任务的job开始执行的时间值，z轴代表实时周期任务可能被分配 到的CPU号，具体包括Sporadic任务模型，PPTT模型、混合关键任务模型。

Sporadic任务模型，PPTT模型、混合关键任务模型通过最基本的实时周期任务模 型节点组合在一起，该模型具有如下特征：

a.每个周期任务都是一个三元组τ_i＝(Φ_i，E_i，D_i)。其中，Φ_i是任务到达时刻，E_i表 示最差执行时间WCET，D_i表示任务时限；

b.每个周期任务τ_i都包含一个无限的作业(job)，而τ_ik表示τ_i的第k次作业。r_ik和 d_ik分别表示τ_ik的发布时刻和第k次作业的绝对时限时间；

c.U(τ_i)＝E_i/D_i表示τ_i任务的利用率因子。于是对于一个周期任务，系统的总利用 率为设σ为任务最大可达利用率，σ＝max{U(τ_i)}，显然σ∈(0，1]；

Sporadic任务模型所采用的负载均衡的调度算法为：

定理A给定由n个周期任务组成的集合，τ＝{τ₁，τ₂...，τ_n}，其中τ_i＝(E_i，D_i)，利用 时限驱动DD算法是可以调度的充分必要条件是

$\underset{i=1}{\overset{k}{\Sigma }}U\left({\tau }_i\right)=\frac{E_1}{D_1}+\frac{E_2}{D_2}+...+\frac{E_3}{D_3}\le 1---(2-3)$

定理B互补的周期任务在同一个处理器核上一定是可调度的，并且该处理器核的 利用率为1。

证明设存在k个互补的周期任务τ₁＝(Φ₁，E₁，D₁)，τ₂＝(Φ₂，E₂，D₂)，...，τ_k＝ (Φ_k，E_k，D_k)，则由定义2-7可知那么根据定理2-1可知，这 些任务在同一个处理器核上，通过时限驱动DD(DeadlineDriver)的调度算法进行调度，一 定是可以满足的，且该处理器核一直处于执行状态，故其利用率为1。

定理C设在一个核上分配了k个周期任务，且这k个周期任务满足提出的假设条 件，如果这k个周期任务处理器核总利用率小于等于1，则必定存在一个时间段[0，T]，其中T 为k个周期任务时限的最小公倍数。如果k个任务在这个时间段内可被调度，则这k个任务在 系统上一定可以被调度。

证明由于T为k个周期任务时限的最小公倍数。如果k个任务在这个时间段[0，T] 内可被调度，则在以后的[i*T，(i+1)*T](i＝1，2，LL，n)等的时间段里可以重复地执行这 种调度方法，那么这k个周期任务就可以周期性地循环被调度。因为所以在该时 间段内由定理A可知，必定可以被调度。

定理D对于任何一个Sporadic任务τ′＝(Φ′，E′，D′)其中Φ′为其到达的时刻、E′ 为其必须执行的时间单元，D′为该Sporadic任务的时限，令Δ＝D′-Φ′，则该Sporadic任务 在Δ间隔内可以被调度的充分必要条件是Space(Δ)≥E′。

证明先证充分条件：当Space(Δ)≥E′时，说明在Δ＝D′-Φ′时间间隔内，存在满 足该Sporadic任务执行的时间单元E′，因此在时限D′之前能够执行完毕，故可以被调度。

次证必要条件：若任务要在Δ＝D′-Φ′时间间隔内执行完毕，则必须要有空余的时间 单元来执行该Sporadic任务，且在这个间隔内的空余时间单元要大于或等于E′，故Space(Δ)≥E′。

S11、对于输入的一个周期任务集判断其是否为超满利用率系统，如果是，则输出 不可调用；否则，执行第二步；

S12、根据任务利用率，将任务集划分为两大子集合——高利用率集合S^H和低利用 率集合S^L，其中这里i，j都为正整数；

S13、从对应的S^H集合中选择利用率最高的M-1个任务τ₁，τ₂...τ_M-1分别分配到M-1 个核上，然后从S^L集合中选择与τ₁，τ₂...τ_M-1互补或近似互补(选择ε最小)的任务集合s₁， s₂...s_M-1相应地分别分配到M-1个核的队列当中；如果S^H集合中的任务少于M-1，则在S^L集合 中找出互补的或近似互补的任务组分别分配到剩余的核当中；

S14、根据定理B和定理C可以知道在M-1个核上运用定理A的DD调度算法将各自的 调度队列中的任务进行调度；

S15、根据定理D计算Sporadic任务τ′＝(Φ′，E′，D′)从到达时刻到其死限这段时 间Δ内的M-1个核剩余可利用空间Space_i(Δ)，i＝1，2，...，M-1。如果该Sporadic任务的执 行时间Space_i(Δ)≥E′则可以将它分配到第i个核上。如果都不能满足，则该任务无法被调 度；

针对该模型中的M个核分别对应z轴的M个平面，其中M-1个平面上会有s₁，s₂...s_M-1M-1个集合，将每个集合中的任务周期性发起的job的执行的开始时间和执行的结束时间 分别映射到三维调度器模型的x轴和y轴上。阴影部分为每个job的执行期。如果两个job之 间还有非阴影区域则就表示剩余可利用空间Space_i(Δ)，i＝1，2，...，M-1。分配给 Sporadic任务的job。

PPTT模型采用处理器预分配算法，具体步骤为：假设处理器核的个数为m，处理器 预分配算法可描述如下：

S21、首先对任务系统中n个ST树分别生成相应的扩展图，并将每个扩展图中的第 一个作业放入就绪队列中，根据优先级判定，选择m个高优先级的作业分配到m个核上去执 行，如果作业个数n小于m个，则选择n个核来执行；

S22、当一个作业执行完毕之后，将其后斜对角线上的可并行执行的作业放入就绪 队列中，计算当前核上每个任务的作业所执行的时间值，如果则表明该作业已 执行完毕，此时在所对应的任务扩展图和就绪队列中将其删除。如果说明该作业 没有执行完毕，则更改该作业需要执行的时间片为并把该作业重新放到就绪队 列中等待和其他作业一起调度；

S23、重新计算就绪队列中的每个任务的优先级，选取m个任务分别分配到m个核上 运行。如果作业数n小于m，则选择n个核去执行；

S24、重复步骤S22、S23，直到所有的作业都能分配到核上去执行；

针对PPTT模型中每个ST树的节点按照上述调度算法将形成m个平面，将任务扩展 图中的作业按照调度顺序分别映射到m个平面上影射方法仍然是将每个job的开始执行时 间和结束时间分别映射为x轴和y轴。

混合关键任务模型，包括job模型、task模型以及系统模型，其采用的算法如下：

定理E假设在同一个核上进行调度，且不考虑上下文切换和中断等额外开销的情 况下，某种调度方案对于同时刻到达的任务集，作业J_i可以被调度成功的充分必要条件是 该作业的周期应大于或等于其前面已经执行过的任务的执行时间与该任务需要执行的时 间值之和。

证明1)必要性令某作业集J的执行顺序为J₁，J₂，L，J_n设每个任务执行完毕的时刻 依次为a₁，a₂，L，a_n，若所有任务都能满足时限，由于不计算额外开销那么前面作业的发布时 刻就是后面任务的开始执行时刻。故有

a₁＝r₁+c₁≤d₁

a₂＝a₁+c₂＝r₁+c₁+c₂≤d₂

a₃＝a₂+c₃＝r₁+c₁+c₂+c₃≤d₃

......

a_n＝a_n-1+c_n＝r₁+c₁+c₂+...+c_n≤d_n

d_n＝p_n+r_n

因为是同时刻到达，因此r_n＝r₁，再结合上面式子，可以得到

$r_1+c_1+c_2+...+c_n\le r_n+p_n\Rightarrow \underset{i=1}{\overset{n}{\Sigma }}{c}_i\le p_n$

由此得证。

2)充分性如果每个作业的周期都大于其前面执行任务的执行时间之和，那么任 何一个作业周期大于该作业的执行时间与其前面执行过的作业的执行时间之和，则有

$p_i\ge c_i+c_{i-1}+c_{i-2}+\mathrm{....}+c_1\Rightarrow d_i=r_i+p_i\ge r_i+c_i+c_{i-1}+c_{i-2}+\mathrm{....}+c_1$

这表明任何一个任务的执行都没有超过时限，所以是可以被调度的。此定理得证。

对于非同时到达的作业，判定其是否可被调度的条件分为两种情况：

第一种情况：当满足r_i＜a_i-1，i＝2，L，n，时，有

a₁＝r₁+c₁≤d₁＝r₁+p₁

a₂＝a₁+c₂≤d₂＝r₂+p₂

......

a_n＝a_n-1+c_n＝r₁+c₁+c₂+...+c_n≤d_n＝r_n+p_n

当满足时，可被成功调度。

第二种情况：当r_i≥a_i-1，i＝2，....，n，时，则

a₁＝r₁+c₁≤d₁＝r₁+p₁

a₂＝r₂+c₂≤d₂＝r₂+p₂

......

a_n＝r_n+c_n≤d_n＝r_n+p_n

当c_i≤p_i时，即可被成功调度。

S31、计算不同级别下每个job的关键因子，根据关键因子的大小进行优先级排序， 并根据定理E判定是否可以在同一个核上调度；

S32、检查是否有关键级别转化，如果有则根据已经转化的当前级别计算每个job 的关键因子，决定新的优先级顺序，并与转化前的优先级顺序相比较，记录那些优先级推后 的job，以及该job优先级未推后时后面的job顺序；

S33、针对优先级未推后的job其后作业的调度顺序，根据定理E判定这些job是否 能够在同一个核上调度。如果可以，根据这些job的释放时间和各个级别下的最坏执行时间 计算最早执行窗口(正向时间分割函数)和最迟执行时间窗口(反向时间分割函数)， 并求出他们的公共空闲时间窗口，利用公共空闲时间窗口来调度推后的job，如果不可以， 则只能另外分配处理器核；

S34、如果没有关键级别转化，或者关键级别转化后没有优先级推后的job，则继续 按照该调度顺序执行。

其中，所述定理E为假设在同一个核上进行调度，且不考虑上下文切换和中断等额 外开销的情况下，某种调度方案对于同时刻到达的任务集，作业J_i可以被调度成功的充分 必要条件是该作业的周期应大于或等于其前面已经执行过的任务的执行时间与该任务需 要执行的时间值之和。

混合关键任务模型针对不同的系统关键值，如果job能够在同一个核上调度则放 在同一个平面上，否则放在不同平面上，同样将每个job的开始执行时间和结束时间分别映 射为该平面的x轴和y轴。

在所有的任务模型中的job被映射到三维模型中之后，将所有的阴影区域下移，并 将多个平面合并的同一个平面上，纵坐标表示为CPU号，横坐标为时间值，则三维模型就可 以转化为二维平面执行图，所有的执行顺序就可以在二维图中显示。如图3所示。

本发明具有以下有益效果：

对各种类型的实时任务的时间确定性、安全性、可靠性进行分析之后，将各类实时 任务模型转换为统一的三维立体层次关系模型，再根据任务所在的层次进行调度策略的调 整，最后将其映射到与核对应的二维时空图中。该策略不仅要考虑负载均衡以提升多核的 并行执行效率而且要能满足任务执行过程中的实时性、可靠性和安全性需求。此外，该模型 和算法还对各种实时任务的共享资源同步机制进行研究，研究出一种新的共享资源管理方 案，以减少死锁的发生和防止出现CPU饥饿现象。

附图说明

图1为本发明实施例三维调度器模型及其调度算法中的三维立体模型图。

图2为本发明实施例中CPU号为4的job的执行时间与x轴形成阴影覆盖方法图。

图3为本发明实施例中三维模型转化为二维执行顺序图。

图4为本发明实施例中调度器模型设计示意图。

图5为本发明实施例中ST树实时周期任务扩展图。

图6为本发明实施例中系统调度主流程图。

图7为本发明实施例中共享优先级队列的调度方案。

图8为本发明实施例中二层BloomFilter设计。

图9为本发明实施例中算法执行总体流程图。

图10为本发明实施例中BloomFilter加锁过程。

具体实施方式

为了使本发明的目的及优点更加清楚明白，以下结合实施例对本发明进行进一步 详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发 明。

如图1所示，本发明实施例提供了一种三维调度器模型及其调度算法，三维调度器 模型及其调度算法，其特征在于，三维调度器模型采用三维坐标空间(x，y，z)，其中x轴代表 实时周期任务的job执行完毕所需要的时间，y轴代表实时周期任务的job开始执行的时间 值，z轴代表实时周期任务可能被分配到的CPU号，如图1所示。

将上述三种不同的调度模型和调度算法形成的调度顺序影射为三维空间模型进 行调度，方法如下：将安排好的调度顺序中的每个job的开始执行的时间以及执行完毕所需 要的时间分别映射到z＝1的平面的x轴和y轴，如果出现重合的部分则移动到下一个z平面。 并将同一个job的开始执行时间和执行完毕所需要的时间以及x轴作为平面阴影部分。该部 分表明是该job的执行期。如图2所示CPU号为4的平面映射图。

实施例

实时周期任务模型

假设一个有M个核(M＞1)的系统，且核是同构的。下面以n个周期任务τ＝{τ₁，τ₂，L L，τ_n}和k个Sporadic任务τ′＝{τ′₁，τ′₂，LL，τ′_k}在同构多核处理器上的可抢占调度问题 为例进行论述。

周期任务具有以下特性：

1)每个任务都可用一个三元组τ_i＝(Φ_i，E_i，D_i)表示。其中，Φ_i是任务到达时刻，E_i表示最差执行时间WCET，D_i表示任务死限。

2)任务之间是可抢占的，且相互独立，不考虑同一个核上任务切换带来的开销，以 及其他一些资源如变量及缓冲区等访问开销。

3)每个周期任务τ_i都包含一个无限的作业job，而τ_ik表示τ_i的第k次作业。r_ik和d_ik分别表示τ_ik的发布时刻和第k次作业的绝对死限时间。

4)U(τ_i)＝E_i/D_i表示τ_i任务的利用率因子。于是对于一个周期任务，系统的总利用 率为设σ为任务最大可达利用率，σ＝max{U(τ_i)}，显然σ∈(0，1]。

假定任何一个Sporadic任务优先级都低于周期任务，且都是一个三元组τ′_i＝ (Φ′_i，E′_i，D′_i)其中，Φ′_i是到达的时刻，E′_i表示最坏的计算时间，D′_i表示相应的死限。定 义Sporadic任务瞬时利用率为U(τ′_i)＝E′_i/D′_i，U′_i∈(0，1]。

多核模型描述如下：P＝{P₁，P₂LL，P_M}为含有M个具有相同处理能力的处理器核 集；η_i为第i个核P_i的利用率，即分配给该核的任务的总利用率U_i。另外，假定任务调度是以 可抢占的方式进行，并且中断后可立即恢复执行。

Sporadic实时周期任务调度器模型，采用一个中心调度器和边缘处理器核模型， 即有一个核作为专门的调度器。所有任务都要先到达这个中心调度器，然后通过调度算法 将其分配到系统中的边缘处理器核上去执行，如图4所示。而每个边缘处理器核都有自己的 一个调度队列(DispatchQueues)。这样，在它执行完当前任务之后，就从其调度队列中取 出一个任务来执行。当边缘处理器核的调度队列执行完毕之后，它就会通知中心调度器，中 心调度器会再次根据算法将新到的任务分配给该边缘处理器核的调度队列中，同时对自己 的调度队列进行修改。

PPTT模型

为了定义PPTT模型，首先定义DAG图中结点之间的关系。

定义3-3(执行顺序关系)对于DAG图中任意两个不同任务的结点A和B，如果A存在 于B的前驱结点集合中，则称A和B之间有先后执行顺序关系，即A必须在B开始之前执行完。

定义3-4(复制关系)对于DAG图中任何一个有后继的结点(也称fork结点)A，假设 A的后继结点有n个，则可以通过将A结点复制n-1次，形成A₁，A₂，...，A_n-1，A，这n个结点分别 对应n个不同的后继结点，从而可消除fork结点。此时，称这n个结点A₁，A₂，...，A_n-1，A之间存 在复制关系。

定义3-5(合并关系)对于DAG图中任何一个有前驱的结点(也称为join结点)A，如 果A的前驱结点有m个，则可将该结点拆分为不相同的结点A₁，A₂，...，A_m分别对应不同的前 驱结点。此时称这m个结点A₁，A₂，...，A_m之间存在合并关系。

定义3-6(独立关系)如果A和B两个结点之间不存在上述三种关系，则称此两个结 点相互独立。

定义3-7在STF中，只有处于同一层上的结点之间具有复制关系和合并关系。将具 有复制关系和合并关系的不同ST树称为具有复制关联关系或合并关联关系的单树。

定义3-8如果k棵ST树既没有合并关联关系也没有复制关联关系，则称这k棵树之 间具有相互独立关系。具有相互独立关系的不同ST树上的结点均相互独立。

定义3-9并行优先级任务树PPTT模型可用一个二元组PPTT＝(STF，R)表示。其中 STF是ST的集合；R用来定义该ST中任意两个结点之间存在的关系，包括执行顺序关系，复制 关系，合并关系和相互独立关系。

处理器预分配算法

在进行处理器预分配之前，首先将STF模型中的每个ST的任务结点按照周期任务 的作业形式展开，如图5所示。

从图5中可以看出该扩展图中任务之间的依赖关系，斜对角线上虚线连接的任务 之间不存在依赖关系，且其前驱执行完毕时可以并行执行。假设处理器核的个数为m，处理 器预分配算法可描述如下：

本申请假定在进行处理器预分配算法时，忽略了由于任务复制带来的开销。在分 配核时，尽量将具有合并关系的结点任务所在的单树分配到同一个核上执行，以减少同步 通信开销。在处理器核数和任务数相同情况下，处理器按照如下原则进行预分配：

(1)将STF中的每棵ST树分别分配到不同的核上去执行。

(2)为了依次减少合并次数，将具有合并关系的结点尽量分配到同一核上执行。

(3)在调度时按照优先执行关系进行调度。

系统调度主流程图如图6所示。

混合关键任务模型

包括job模型、task模型以及系统模型。

job模型

混合关键系统中的关键级别具有两层含义：第一，整个系统本身在不同的时刻有 一个关键级别；第二，在不同的时刻，每个job也有一个相应的关键级别。在一个共有k个级 别的混合关键系统中，一个job可以用一个4维向量来表示：J_i＝(r_j，d_j，x_j，c_j)，其中，r_j表示 该job的到达时刻，也就是发布时刻；d_j表示job的死限，显然，d_j＞r_j；x_j∈{1，2，......，k} 是指该job在某一时刻的关键级别，在某一确定的时刻，它的值也是确定的；c_j则代表一个k 维向量：c_j＝{c_j(1)，c_j(2)，......，c_j(k)}，用来表示该job在每个级别对应的最坏执行时 间，在这里假设c_j(1)≤c_j(2)≤...≤c_j(k)。对一个任务集合中的每一个job，要确保实时系 统的特性，必须在死限到来之前执行完毕，也就是说，实际执行完毕的时刻要小于死限。

对于具有n个job的集合而言，必定有一个相应的实际执行时间向量：(c₁，c₂，...， c_n)，其中c_j表示第j个job的实际执行时间。针对这个特定的向量，此系统的关键级别是指这 样的一个最小整数值l(l∈{1，2，...，k}))，它能保证针对系统当前的每一个job，均有如下 关系式成立：c_j≤c_j(l)，(j∈{1，2，...，n})。在这里，只研究那些能够找到这样的一个/值的 系统job集合。

结合上述的job的4维定义以及系统关键级别的确定，不难发现，如果当前系统处 于/关键级别，那么整个系统在运行过程中，处于/级别或大于/级别的所有job都必须在死 限时刻到来之前执行完毕。即首先要保证/级别或大于/级别任务的执行，其次考虑小于/级 别的任务的执行。

task模型

在具有k个级别的混和关键任务系统中，每一个任务(task)可以用一个3维向量来 表示：T_i＝(c_i，p_i，x_i)。其中，c_i与job模型中的一样，是一个k维向量，用来分别表示该任务处 于各个级别下所对应的最坏执行时间，即c_i＝{c_i(1)，c_i(2)，......，c_i(k)}；p_i则表示该 task的执行周期，也是连续两次job被发布的最短时间间隔；x_i(x_i∈{1，2，...，k})与job模 型一样，表示该task所处的级别，在某一确定的时刻，它的值也是确定的。同样，在task模型 中，针对c_i，假设c_i(1)≤c_i(2)≤...≤c_i(k)。

在混和安全关键任务模型中，每一个任务T_i可以隐含无数个job，这些job每隔p_i个 时间间隔发布并执行一次。在此模型中，每次job发布之后，它的发布时刻r_i就确定了，其死 限规定为该job发布之时经过p_i之后的时刻，即d_i＝r_i+p_i。至于关键级别，该job的关键级别 与该任务的关键级别相同，即为x_i。这些job的c_i与该任务的c_i同样保持一致。因此，根据 task这个3维向量，便能够确定所有已发布job的4维向量，进而全面确定这些job的参数，根 据后文介绍的调度算法即可对这些job进行调度。

系统模型

在具有k个级别的混合关键任务系统中，设T＝{T₁，T₂，...，T_n}表示该系统中的任 务集合。由于本文主要研究循环任务系统，因此后文假定该混合关键任务系统中一次循环 中共有n个任务：T_i＝(c_i，p_i，x_i)，(i＝1，2，...，n)，其中，c_i表示该任务的最坏执行时间；p_i表示该任务的执行周期；x_i表示该任务在此混合关键任务系统中的关键级别。设J＝{J₁， J₂，...，J_m}表示该系统中的job集合，即该混合关键任务系统一次循环作业过程中共需执行 m个job。每个job亦可表示为J_j＝(r_j，d_j，x_j，c_j)，(1≤j≤n)。其中，r_j表示该job的发布时刻； d_j表示该job的死限，可以通过其发布时间以及最坏执行时间计算得到；x_j表示该job所处的 关键级别，与其所属任务当前关键级别保持一致。c_j是一个k维向量，表示该job在不同关键 级别下的最差执行时间，它由该job所属关键任务的最坏执行时间得到。

混合关键调度算法设计与实现

定义4-1最早可以开始执行时刻----是指J_i允许最早获得空闲处理器核的时 刻。

定义4-2最晚开始执行时刻------是指J_i的绝对死限减去其所需要执行的最 坏执行时间所得到的时刻值，即

定义4-3最晚执行窗口------是指J_i从最晚开始执行时刻，到绝对死限这一段 时间为其最迟执行窗口，即

定义4-4最早执行完毕时刻O_i------是指J_i最早可以执行时刻加上其所需要的最 大执行时间所得到的值，即

定义4-5最早执行窗口------是指J_i从最早允许执行时刻到最早执行完毕时 刻这一段时间，即

定义4-6空闲可执行窗口------是指如果J_i的最早可以执行完毕时刻O_i小于 最晚开始执行时刻那么这段时间就称为空闲可执行窗口，即$W_i^I=[O_i,S_i^l].$

定义4-7相对关键度ρ_i------是指一个jobJ_i相对于其他job的关键级别重要程 度。用来表示。

定义4-8关键额度δ_i------是指一个jobJ_i在k个关键级别下所能具有的关键份 数。用来表示。

定义4-9关键因子------是指一个jobJ_i在某个级别下的一次执行相对于其 他任务的一次执行所处关键级别重要程度以及利用率的一种度量。用来表 示，且其中，为J_i在k级别下的利用率。

将上述三种模型的调度算法按照job执行的最晚开始时间或者最早开始时间为纵 坐标，job的时限为横坐标，对应的CPU号为第三个坐标都可以映射到对应的三维调度模型 当中，并且通过下移阴影部分以及合并不同的平面图就可以映射到CPU和时间节点的二维 平面图中。

三维调度模型在实时系统调度过程中的具体实现方法以及同步机制的整体设计

本申请采用lock与free-lock相结合的机制来实现实时周期任务在执行过程中的 调度以及同步。具体方法是采用基于锁的BloomFilter来判断被选择的job的运行状态和 采用基于无锁算法实现改进的Skip-list数据结构，用以存放将要被调度的任务及阻塞的 job。系统设计方案如图7所示。

在此方案中，Skip-list的纵向列表针对不同模型，意义不同。如针对Sporadic任 务模型的Skip-list的纵向列表可以看成是不同类型的周期任务如定周期和不定周期， PPTT任务模型的Skip-list的2级纵向列表可以看成不同的ST树，混合关键任务模型中 Skip-list的2级纵向列表可以看成为不同关键级别。当某周期任务的性质发生变化时，比 如Sporadic模型中固定周期任务转化为Sporadic周期任务，PPTT模型中周期任务从一个ST 树转化为另外一个ST树上的任务，混合关键模型中关键级别由低级转化为高级别时，该任 务将在不同的纵向列表中进行转换，如从低关键级别层次的链表升级为高关键级别层次的 链表。将Skip-list中的结点增加为两种：一种是周期任务结点，另一种是某任务被挂起的 job结点。

当某个处理器核上发生高优先级任务抢占低优先级任务时，正在执行的低优先级 job被挂起，被挂起的job根据其转化性质和优先级顺序被放入到Skip-list当中相应的位 置上，所有核对Skip-list的访问采用无锁算法。第二种是查询任务状态的BloomFilter， 用以查询某个周期任务的某个时刻的job是否处于就绪、执行、挂起、执行完毕四种状态。下 面就混合关键任务模型举例说明：

对于一个具有k个关键级别的n个混合关键任务的系统，采用全局调度算法将关键 任务调度到m个核上执行。在系统整体调度过程中，首先利用Skip-list数据结构的创建、插 入等操作，将需要调度的n个混合关键任务，按照不同关键级别，插入到Skip-list数据结构 中。其次，空闲核从Skip-list队列中选择当前关键级别中优先级最高的任务，或者是被挂 起的job准备执行。如果是挂起的job，先判断是否已经发生死限丢失，如果是则删除该job， 并选择下一个任务。否则，通过BloomFilter来查询将要被调度的任务或者job所处的状 态，如果是未执行状态，则取出执行；否则从Skip-list中选择当前关键级别中下一个任务 对应的job准备执行。第三，在运行过程中，如果有高关键级别任务(高优先级任务)被发布， 则抢占正在处理低关键级别(低优先级任务)的处理器核，将低关键级别的job插入到Skip- list链表中，并将BloomFilter中相应的job状态设定为未执行状态。最后，不同的核可以 同时访问Skip-list数据结构。

本申请中同步算法按照以下途径实现。在基于全局优先级调度算法的基础上，对 优先级队列Skip-list采用无锁访问方法以及BloomFilter状态查询法，而在Bloom Filter中，最为关键的技术是位数选择和哈希函数的设置。位数选择的目的是使大范围的 元素通过哈希函数映射到小范围的位数中。假设某个集合有u个元素，BloomFilter有m位， 必须定义相应的哈希函数使得这u个元素能够对应给定范围m内的某些可能的位置。本章中 BloomFilter位数的选择，以及哈希函数的选择，都和混合关键系统中任务数量有关，且将 BloomFilter改进为多层结构。

实时系统中，使用BloomFilter的目的有两个：

第一，通过BloomFilter判断某个任务的job是否属于被调度范围，以避免多个核 执行相同的job。

第二，通过BloomFilter判断当前job所处的状态：执行还是未执行，根据该状态 可以判断被访问的job是被放弃还是被执行。改进的BloomFilter如图8所示。

图9显示了整体的调度流程。当多个处理器核同时访问Skip-list时，只有一个核 会获得哈希函数对应的BloomFilter状态位的修改权。当其他处理器核获知该job已经执 行时，则会选择下一个任务。由于对Skip-list的插入、删除以及修改操作都依据无锁同步 机制，因此可以提高多核对共享优先级队列的并行操作效率。

当开始创建Skip-list优先级队列时，需要更新当前任务的发布时间，创建完成之 后，即可从Skip-list中提取任务，算法如下：

1)选取Skip-list中已发布的任务或阻塞job；

2)通过BloomFilter判断该任务或阻塞job是否正在执行，如果正在执行，则从 Skip-list任务链表中重新选取任务结点；

3)如果任务或阻塞job未执行，则继续判断该任务或阻塞job是否超过死限时间， 如果发现超过死限时间，则输出该任务或阻塞job的丢失死限时间，更新任务的发布时间， 将任务重新发布，如果是阻塞job就将该job删除。返回第一步在Skip-list任务链表中重新 选取任务或阻塞job；

4)将Skip-list链表中已发布，状态为未执行，且未超过死限时间的任务或阻塞 job返回。

在BloomFilter上，将该任务或阻塞job标识为未运行。在整个调度过程中，对 BloomFilter进行操作主要有如下几个方面：

1)根据任务对应的job，计算二级hash函数值，BloomFilter根据任务数量来确定 哈希函数。当查询状态是读的过程，并行读内存是不需要加锁机制。

2)当可以调度该job时，根据二级hash函数值的计算，找到BloomFilter上相应的 位置，如果是0，则需要对该位置进行加锁并直接写入1，然后解锁。如果该位置已经是1，则 表明是该job已经被执行，需要重新找到一个新的可以调用的job。

3)当要job完成时，根据二级hash函数值的计算，在BloomFilter上将其标识为未 运行值0；然后解锁。BloomFilter细粒度加锁过程的流程如图10所示。

三维模型在对各种类型的实时任务的时间确定性、安全性、可靠性进行分析之后， 将各类实时任务模型转换为统一的三维立体层次关系模型，再根据任务所在的层次进行调 度策略的调整，最后将其映射到与核对应的二维时空图中。该策略不仅要考虑负载均衡以 提升多核的并行执行效率而且要能满足任务执行过程中的实时性、可靠性和安全性需求。 此外，该模型和算法还对各种实时任务的共享资源同步机制进行研究，研究出一种新的共 享资源管理方案，以减少死锁的发生和防止出现CPU饥饿现象。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人 员来说，在不脱离本发明原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应 视为本发明的保护范围。