认知机器人1（2021）214混合关键系统半分区调度算法研究张倩玉，王建国，徐飞，黄淑娟Xi理工大学计算机科学与工程学院aRT i cL e i nf o保留字：混合关键系统多核处理器半分区调度算法a b sTR a cT为了克服在混合关键系统中，一旦系统的关键水平改变，低关键任务可能被放弃以确保高关键任务的可并行性的问题。提出了一种基于异构多处理器混合关键度平台的半分区调度算法SPBRC，该算法综合了全局调度和分区调度的优缺点。该方法首先采用最优装箱算法和最差装箱算法对高、低关键任务分别排序，将所有高关键任务作为固定任务依次分配到不同的处理器上，然后再分配低关键任务。当处理器的关键性改变时，低关键性任务将被允许迁移到与该处理器配对并且处于低关键性模式的处理器，而不是被放弃。因此，提高了系统的整体性能。仿真实验验证了该方法在降低任务丢失率和作业丢失率方面的有效性。1. 介绍混合关键度系统是目前嵌入式系统的重要发展趋势之一，它将不同重要程度的功能集成在一个可共享的计算平台上，如汽车系统中驱动防滑系统的正确性比车载视频功能的正确性更为关键。在一个混合关键级系统中，有两个关键级来表示系统中任务的重要性，一个是高关键级，另一个是低关键级。两者之间的主要区别在于是否会对系统产生严重影响。在没有适当的执行调度的情况下，处于高关键级别的任务对系统的影响更加明显。系统中的所有任务在系统当前所处的临界状态下将具有对应的最差执行时间WCET（最差成本EX延迟时间），当任务的WCET高于当前系统的临界水平下的WCET时，通过改变系统的临界水平来触发混合临界系统的临界水平的转变。此时， 系统的当前临界级别不能被调度为正常执行。混合关键级系统在平台计算能力和提高平台上资源利用率方面发挥着不可或缺的作用，它很好地解决了当今日益复杂的能力与有限的计算资源之间的矛盾随着不同学者对混合关键级调度的研究和探讨，在不同条件下高关键任务的调度分析方法和调度机制方面取得了很大的进展。问题是这些可调度性方法和调度机制通常基于最坏情况。也就是说，为了满足高关键任务的成功调度，总是牺牲低关键任务，将更多的计算资源留给高关键任务。∗ 通讯作者。E-mail：759053211@qq.com（Z. Qian）.https://doi.org/10.1016/j.cogr.2021.12.0012021年12月4日上线2667-2413/© 2021作者。Elsevier B. V.代表KeAi Communications Co. Ltd.提供的出版服务。这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）可在ScienceDirect上获得目录列表认知机器人期刊首页：http://www.keaipublishing.com/en/journals/cognitive-robotics/Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）214215⌈⌉���������表2.1关键任务集的简单混合������������������������������τ1 4 3 3 1τ2 10 5 6 2τ3 3 1 1 1τ4 12 4 5 2τ5 2 1 1 1τ6 5 3 3 1然而，不断的研究表明，在混合关键系统中，低关键任务的可并行性对系统的整体性能也起着非常重要的作用。在某种程度上，低关键任务的执行更好地反映了调度策略的质量。因此，近年来对混合关键调度的研究更多地集中在调度的整体性能上也就是说，尽可能好地完成低关键任务的执行，同时确保高关键任务的正确调度。第一种方法是当系统处于高关键阶段时，增加低关键任务的周期，从而降低低关键任务的优先级，使其能够在不影响高关键任务完成的情况下得到正确执行，以提高系统的整体性能第二种方法是在高关键级别只丢弃部分低关键任务，剩余的低关键任务仍然保证执行，从而尽可能地利用系统的计算资源[1]。文献[2]使用动态执行预算管理，在高关键级别回收冗余执行时间文献[3，4]计算任务错过时限的概率，通过与阈值比较确定关键级别切换的时机，尽可能延迟从低关键级别到高关键级别的切换时间，为低关键级别作业提供更高的服务保障文献[5，6，7]还提出了有效的策略来优化混合关键任务的调度Xu和Burns[8]提出了一种多核平台的半分区模型，用于迁移任务的迁移目的地，如果不超过log2（���），则处理器进入高临界模式（n是处理器的数量），一些低关键任务可能迁移到当前处于低关键模式的核心对，但所有任务继续处于适当的关键级别模式（例如，四核平台上可迁移任务的迁移模型为（c1，c2）、（c1，c3）、（c2，c4）和（c3，c4），其将核划分为四个组，每个组具有两个伙伴核，从而允许可迁移任务在伙伴核可用时迁移过去。例如，c1与c2和c3配对，如果c1进入高临界模式，则c1上的所有迁移任务将迁移到c2和c3）;这种方法是，对于低关键任务的迁移，处理器配对可能导致显著的迁移开销。本文的研究对象是同构多处理器环境下的混合关键系统，在任务调度类型的选择上，传统的全局调度开销大，但调度效率高;分区调度开销小，但资源利用率不能得到充分利用，可能存在负载不平衡和资源浪费等问题。针对上述问题，提出了一种基于核关系的半划分调度算法SPBRC（Semi Partition Based on Relation of Core）。本文基于Xu和Burns提出的半划分模型，在多核平台上为系统中的所有处理器分配了一种新的配对关系，提高了低关键任务的可调度性，减少了低关键任务迁移的开销。该算法不仅充分利用了多处理器的计算资源，而且主动调度低关键任务，避免了系统资源的浪费2. 混合关键任务系统模型集合多处理机平台由m（m≥2）个同构处理机组成，记为{n =1，n =2，，n = 1}，一个混合的临界值。由n个周期性任务组成的典型多任务集，记为Γ = {τ1，τ2，，τn}。 任务在运行时jobs{jobs���，1，jobs���，2，}，其中jobs���，jobs表示任务τi释放的j个作业，作业的实际运行时间记为jobs���，jobs。任务是相互独立的，但允许抢占，并且每个任务都有其对应的最高关键级别。为每个任务，存在与之对应的最高临界级别，系统的临界级别与运行任务。一个任务任务集被表示为一个四元组：任务集、任务集、任务集，其中：������������������(1) τi是任务的周期，它表示任务τi释放相邻的两个作业τi，τi和τi，τ i+1(2) ������在本文所研究的双关键任务系统中，将任务的关键程度表示为低关键任务，将任务的关键程度表示为高关键任务。������������������(3) 分别代表低和高关键级别任务的WCET，且临界值≤临界值。������������������������特别的，当������������������������,���������=���������.������对于混合关键级系统，由于每个任务的WCET随关键级而变化，因此不同关键级任务的处理器利用率不同。将临界值定义为低临界水平的工艺利用率，则临界值=临界闪烁率;因此，���������������������在高临界水平���������下的处理器利用率=���������闪烁������。������������������Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）2142166���������������41031225���= 1Δ表2.1显示了一组混合的关键任务的示例，以及在多核平台下，当系统处于低临界水平，如式（2.1）所示：��� ������=∑���������闪烁������=3+5+1+4+1+3=3。016（2.1）当系统临界水平上升到高临界水平时，由于相对低临界的任务被无限挂起，利用率如式（2.2）所示：������������������6 5��������� 为2+的4 为+= 1。016（2.2）���2���410 12作为上述两种方法的结果，在不同的临界水平的利用率将根据所执行的任务集而变化。 在混合关键级别系统中，没有成功调度的高关键任务可能导致更严重的系统损失。为在本文研究的双关键系统中，允许低关键任务的超时现象（注：超时现象是指一个任务在超过其截止期后开始执行，并在此期间错过了对该任务的调度而释放的作业），因为低关键任务的执行失败不会造成严重的问题，它更多的是为了保证用户能够获得良好的体验感因此，本文将双关键任务调度的正确条件定义如下：(1) 当任务集处于低关键模式时，所有任务释放的作业都允许发生超时，但必须完成;(2) 当任务集处于高关键模式时，所有高关键任务释放作业必须被调度为在其截止日期内完成，而低关键任务释放作业可以尽可能多地完成。3. 算法设计与实现3.1. 相关定义(1) EDF（Earliest Deadline First）算法：一种基于任务的绝对截止日期动态分配优先级的方法。它的优先级由任务的截止日期决定，越(2) 任务分配，任务分配：任务分配在处理器上的份额分配（可能为0），每个任务分配的总份额分配与其利用率匹配，���������i. e. ������=���∑=1������,���,Misthenumberofprocessors;(3)������：处理器上的总共享分配，���������������∑∈������，，和指定的���≤1。0o(4) 迁移（固定）任务：任务在多个（仅一个）处理器上具有非零份额;(5) ��������� ：处理器���������0 −阿维尼翁���图3.13.2. 哲学思想基于同构多处理器执行双关键任务，提出了一种半分区调度算法（一） 高关键任务在任务调度中，必须保证高关键任务的完成。因此，在该算法开始时，所有高关键任务都以最小的升序列出后，它们被分配给不同的处理器作为固定任务。���������(1) 低关键任务为了使最低临界任务尽可能成功，系统资源得到更充分的利用，所有低临界任务的分配是按重要性从高到低的顺序进行的，低重要性任务的分配如下：���������1) 选择利用率最低的低关键任务，以便在第一个处理器上安排高关键任务的分配。a如果处理器上的OPp满足低关键任务，则将该任务作为固定任务分配给处理器b否则，将其移动到第一个不包含高关键任务的处理器进行调度。继续在下一个处理器上选择利用率最低的低关键任务和高关键任务的组合，重复步骤a、b。在将低关键任务分配给具有高关键任务的处理器之后，查询是否存在具有OPp = 1。0。2a）如果存在，则在从未分配的低关键任务中选择最多使用的任务作为固定任务，剩余的未分配任务从不包含高关键任务的第一个处理器开始顺序分配b否则，按利用率降序选择低关键任务，并将其分配给不包含高关键任务的处理器。Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）214217图3.1. 低 关键任务分配和运行的迁移算法流程图。表3.1处理器上每种类型任务的优先级任务类别处理器处于LO_crit模式时任务优先级迁移任务2固定任务1任务类别当处理器处于HI_crit模式时任务优先级在HI_crit 3中固定的任务LO_crit 2中的迁移任务LO_crit 1中的固定任务（一） 低关键任务该算法允许低关键任务在运行时迁移，以使系统性能更好。当处理器迁移率处于低关键级别时，由与高关键任务具有相同处理器提升的低关键迁移任务迁移的处理器是没有高关键任务的第一处理器，并且由另一低关键迁移任务迁移的处理器是其下一处理器迁移率+1。当由高关键任务释放的作业������被执行���������但未被声明完成时，高关键任务所在的处理器上的关键级别从LO_crit切换到HI���_crit，并且该处理器上的低关键任务需要被重新定位到与该处理器配对并处于低关键模式的处理器。3.3. 算法优先级本文中算法指定的任务优先级定义如上表3.1所示(1) 在任务调度中，要保证高关键任务的完成。因此，在任何处理器上，本文始终将高关键任务设置为固定任务，优先级始终为最高;(2) 对于任何低关键性的任务，迁移任务都会消耗系统本身的大量资源利用率，因此，不错过截止日期，尽可能多地完成，设置低关键迁移任务的优先级总是高于低关键固定任务(3) 在低关键模式下，处理器上有两种低关键迁移任务：A从处于高关键模式的处理器迁移的低关键迁移任务B处于低关键模式的处理器上的低关键迁移任务如果处理器上的迁移任务同时包含这两个任务，则由于同一处理器上的低关键性任务比高关键性任务多， 为了尽可能多地完成这些低关键任务，本文为从处于高关键模式的处理器迁移的低关键任务指定了更高的优先级Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）2142186321���104351220145630���= 1表3.2实例任务集。������������������������������τ1 10 9 9 1τ2 4 3 3 1τ3 3 2 2 1τ4 5 2 3 2τ5 12 5 7 2τ6 2 1 1 1图3.2. 所有处理器都处于低临界状态的任务分配过程。否则，如果在处理器上有两个按优先级和优先级+1的顺序调度的迁移任务，则低关键迁移任务优先级被给予高于任务优先级+1的静态优先级[9]。���也就是说，一个迁移任务以最高的优先级在任何不是它的第一个处理器的处理器上执行（注意：迁移任务分配到最低索引处理器分配任务被称为它的第一个处理器），它具有最高的优先级[1]。���如果不是第一个被调度来执行两个迁移任务的处理器是该处理器，则基于EDF算法的优先级来安排两个迁移任务的优先级（注意：在该算法中，即基于迁移任务的WCET，WCET值越小，优先级越高3.4. 算法示例下面给出SPBRC算法的示例。实例任务集如表3.2所示。∑=∑=9+3+2+3+7+1=4（3.1）������������������由公式（3.1）可知，任务集在4个处理器（100-103）上是可行���������������对于所有高关键性任务，按顺序排列，τ4，τ5∶ τ4 τ5。所有低关键性任务τ、τ都是按时间顺序递减的：τ > τ。������1236���1 2 3 6任务分配过程中，所有的处理器都处于低临界状态，如图。3.2：(1)高度关键任务的分配τ4、τ5将从一开始就作为固定任务依次分配给处理器τ0、τ1(1) 低关键任务的分配a 首先选择低关键任务的最低利用率τ6，因为处理器上剩余空间的利用率τ0> τ6的利用率，τ′6，0τ0等于τ′，因此τ6将被分配为第一处理器τ0上的固定任务，������高关键性任务，继续6以选择利用率最低的低关键性任务τ，由于剩余空间利用率最低���1 上处理器τ1，τ3，τ′3，1τ′1的利用率等于τ ′′ 1，因此τ3将被分配为上的迁移任务。���3 3第一个处理器E1和E2 不包含高关键任务;b 在低关键任务被分配给具有高关键任务的处理器之后，由于������3 = 1。0，因此最常用的任务τ1是从从未被分配的低关键任务τ1、τ2中选择的，以被固定地分配给处理器τ3任务由于处理器的剩余空间利用率为100%������τ2 最终被分配给处理器102��� 作为固定的任务。> τ2的利用率，τ2′的利用率等于τ 2，τ 2 ′的利用率等于τ 2，���������������任务分配过程中，所有的处理器都处于高临界状态，如图。3.3：当由高关键任务τ4、τ5释放的作业的执行时间达到预定时间，但未声明完成时，处理器���������������τ和τ的临界水平 从LO_Crit升高到HI_Crit。和低关键任务τ，τ 在处理器上 和���1 需要重新定位到处理器 2003年，2002年 与处理器配对， 2010年，2011年 并且处于低临界模式。然后重新分配低关键任务τ1和τ2因为τ6和τ3被重新分配，导致没有τ2=1.0过程-���由于剩余的空间利用率为������2 的处理器 τ1的利用率，τ 1′的利用率，τ 1′的利用率，τ1 ′的利用率，τ 1 ′的利用率，τ 2′的利用率，τ 1 ′的利用率，τ 2 ′的利用率，τ 1 ′的利用率，������Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）214219τ 2 ′的利用率，τ 1 ′的利用率，τ 2 ′的利用率������ 等于 ���任务，任务τ1将被分配为迁移任务，迁移的处理器将为τ2和τ3。因为剩余的空间利用率仅为100%，Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）2142202⌈⌉图三点三 所有处理器都处于高临界状态的任务分配过程。表4.1任务集生成的主要参数。参数值范围利用率[u][0.3，0.9]HI_crit tasksLO/HI WCET率[λ][0.5，0.9]HI_crit任务任务如果处理器τ3的利用率≥ τ2，τ2′的利用率等于τ 2′，则任务τ2最终将被分配为固定任务，���������������������处理器2003。此时，算法结束。4. 实验结果及分析对于四核平台，本文基于Xu和Burns提出的多核平台上的半划分模型，为系统中的所有处理器分配一种新的配对关系：（c1，c2），（c1，c4），（c2，c3），（c3，c4），以降低迁移成本低关键任务。对两种半分区模型进行了实验比较。4.1. 制作任务集本文采用随机方式生成任务集。主要参数见表4.1。任务集的生成方式如下：• 该算法在四核平台上进行了实验，因此边界数为log2 4 = 2，即每个任务集中的高关键任务数始终不超过2。• 该算法基于双临界系统，因此任务的临界水平在[1，2]内随机取值。• 在[2，29]的范围内随机选择任务在高临界水平下的WCET，根据随机生成的低/高WCET比λ，计算任务在低临界水平下的WCET。���������������������• 因为已经生成了任务的WCET和利用率，所以计算任务的周期������=������scin������。• 任务的利用率在[0.3，0.9]范围内随机取值，所有生成的随机利用率相加，直到利用率之和小于或等于处理器的数量，此时任务集n中的任务数就是最终任务数���此时，任务集生成。4.2. SPBRC算法的仿真与分析生成测试任务集后，统计所有正确调度的任务的截止期错过率和作业错过率（任务的截止期错过率=截止期错过任务数/任务总数），并与模型2的调度结果进行比较。第一章 验证了算法在不同利用率下的平均截止期错过率和平均作业错过率。实验方案：控制实验数据中的临界因子（C（LO）scinC（HI））为0.73，随机抽取100个正确安排的测试任务集进行实验，每个任务集由4-7个独立任务组成图4.1和4.2给出了该算法与模型2的比较，从中可以看出，在截止期错过率方面，当CPU利用率为3.02时，模型2的性能略好于SPBRC，作业错过率总体上优于模型2，但总体上仍优于SPBRC算法。第一章 验证了算法在不同关键度因子下Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）214221图4.1. 不 同利 用 率下 的 平均截止日期错过率。图4.2. 不 同利 用 率下 的 平均作业遗漏率。图四点三不 同关 键 性因 子 下的 平均截止日期错过率。E X实验方案：关键度因子控制在0.5-0.9之间，随机选取100个正确调度的测试任务集进行实验，并对实验数据进行平均。图4.3 4和4.4给出了该算法与模型2的比较，从比较中可以看出SPBRC算法在降低任务截止期错过率和作业错过率方面的能力比Model 2好。在一组随机的成功调度的测试任务中，如果低关键迁移任务被分配给高关键任务所在的最后一个处理器，新的配对将把它迁移到相邻的处理器，如果他们找到一个尚未分配任何任务的处理器，则将分配使用率最高的低关键任务。此时，剩余的低关键任务将依次分配给不包含高关键任务的处理器，新的配对关系将使更多的低关键任务Z. Qian，W. Jianguo，X. Fei等人认知机器人1（2021）214222图四点四 不同关键性因素下的平均作业遗漏率。任务作为固定任务，在一定程度上减少了低关键任务的迁移数量，同时最大限度地利用了将更多的固定任务单独分配到处理器上，降低了任务的截止期错过率和作业错过率。 图 4.1 - 4.4也得到了不同利用率和关键系数实验的很好支持。结论分析了多核处理器上混合关键级系统的研究现状，综合全局调度和分区调度的优缺点，对原有的处理器配对关系进行了改进，提出了一种新的半分区算法SPBRC。通过结合两种装箱算法（First-fit和Worst-fit），并为所有处理器分配配对关系，从而有效地减少迁移开销，以确保高关键 任务，不仅可以提高低关键任务的调度率，而且可以有效地降低低关键任务的截止期错过率和作业错过率，从而减少低关键任务丢弃和迁移的开销，提高系统的整体资源利用率。竞争利益作者声明，他们没有已知的竞争性经济利益或个人关系，可能会影响本文报告的工作引用[1] 号法律公告曾，研究对优化算法doi：10.27135/d.cnki.hudu.2019.004172。混合-关键性调度嵌入式系统[D]，湖南大学，二〇一九年，[2] X. Gu，A. Eastwaran，混合关键系统服务保证的动态预算管理，2016年IEEE实时系统研讨会（RTSS），2016年，pp.47-56，doi：10.1109/RTSS.2016.014。[3] Y. Abdeddaïm，D. Maxim，固定优先级混合关键性实时系统的概率分析，在：欧洲设计，自动化测试会议EX（日期，2017年，pp.596 2017年。[4] Z.郭湖，加-地Santinelli，K. Yang，EDF对具有允许故障概率的混合临界系统的可扩展性分析，2015年IEEE第21届嵌入式和实时计算系统与应用国际会议，2015年，第103页。 187 -196，doi：10.1109/RTCSA.2015.8.[5] 黄立达，李仁发，以截止期为关键参数的混合关键实时任务调度[J]，J. Comput. Res. Dev. 53（07）（2016）1641-1647。[6] 黄立达，李仁发，事件触发关键度转换后实时任务的可并行性分析[J]，J。Comput. Res. Dev. 54（01）（2017）184-191。[7] 黄立达，李龙，李仁发，谢勇.混合关键度调度中低关键度任务的积极处理[J].计算机科学与工程，2001，24（1）：117 - 118. Eng. Sci. 36（01）（2014）6-11。[8] H. Xu，中国春萤叶甲A. 李文，李晓刚，李晓刚，等.混合临界系统的半分块模型[J]. 系统软件。（2019），doi：10.1016/j.jss.2019.01.015.[9] JamesH. 作者：Jeremy P.UmaMaheswari C. Erickson本杰明·德维刘晓波，李晓波，刘晓波，等.软实时系统中的最优半分区调度[J]. 信号处理。84（1）（2016）。
