关键实时系统中执行任务的方法

摘要

本发明涉及用于执行由一组连续并备选的处理操作组成的任务的方法。方法包括以下步骤：a)为每个处理操作分配硬件资源需求和时间约束；b)将时隙与每个具有对应于处理操作的时间约束的持续时间的处理操作相关联；c)识别在该处决定两个备选处理操作(a，b)中的一个或另一个处理操作的执行的分支点；d)将公共时隙(+2)与两个备选处理操作相关联；e)为公共时隙分配等于两个备选处理操作中的需求的较大者的需求(max(a,b))；f)针对每一个分支点重复步骤c)；g)组合所生成的时隙到与任务相关联的执行模板中；以及h)基于向执行模板的时隙分配的需求，配置实时多任务系统以便约束任务的执行。

说明书

技术领域

本发明涉及设计为采用通过时基设定的强制时间线来执行进程的关键实时系统。本发明特别涉及在它们的实施中要求高等级性能的实时系统，并且涉及其中在向系统中的每个任务所分配的硬件执行资源的使用中要求高等级安全性的关键系统。

本发明特别适用于诸如在运输(汽车，铁路，海运，航空航天)，工业自动化，能源的领域中使用的进程控制系统，以及如通信网络的对于其受控资源分配很重要的其它系统。

背景技术

在关键实时系统中，任务通常被建模为周期性活动，导致基于任务调度的固定优先级规则的多任务系统的实现，提供性能成绩的保障。例如，在文章["SchedulingalgorithmsforMultiprogramminginahardreal-timeenvironment",C.Liu,J.Layland,JournaloftheACM,vol.20,no.1,pp.46-61]中描述过这样的系统。

然而，当非常简单的周期性任务的模型通过任意分割使多任务系统的设计成为不是周期性的先验的特定实时活动的周期性任务，从而使该多任务系统的设计复杂化或对其约束时，该方法缺乏灵活性。实际上，当非周期性实时活动以周期性活动的形式实施时，这会导致增加任务数量或提高执行速度以便分别地满足时间约束。然后每个任务可能对于每个周期性的执行不再有用，其将负面地影响多任务系统的性能。

其它方法，诸如在文章“[“Giotto:ATime-TriggeredLanguageforEmbeddedProgramming”,ThomasA.Henzinger,BenjaminHorowitz,andChristophMeyerKirsch,EMSOFT2001,pp.166-184,2001,Springer-Verlag]和[“Amethodandatechniquetomodelandensuretimelinessinsafetycriticalreal-timesystems”,C.Aussaguès,V.David,FourthIEEEInternationalConferenceonEngineeringofComplexComputerSystems,1998]中描述的这些内容，提出更灵活的任务模型以便描述每一个任务为时间活动的序列。然后使任务形式化为具有时间约束的进程的图的形式，其中如美国专利No.7,299,383中所提议的，如果有需要，则进程可以是有条件的。

那么可能实现多任务系统的高灵活性和高等级性能，并且甚至正式保证任务可被调度，但这种保证一般要求系统中的动态调度。这导致其中针对调度竞争的任务或任务进程中的任务之间的时间干涉，并且因此可能在并发任务之前或之后执行任务。

在关键系统中，其中执行的安全性是最重要的，因为耗尽一切地测试所有可能的调度组合或证明故障状态的不存在是不可能的，所以避免动态调度系统。于是优选采用简化的测试组合的系统，因此限制任务之间的时间干扰的系统。这通常导致使用缺乏灵活性的静态方法。

发明内容

存在用于配置基于灵活性任务模型的实时系统，但是提供限制时间干涉的实施方式的需求。

本发明涉及用于执行由一组连序并备选的进程组成的任务的方法。方法包括步骤：

a)为每个进程指派硬件资源需求和时间约束；

b)为每个进程分配具有对应于进程的时间约束的持续时间的时隙；

c)识别在该处决定两个备选进程中的一个或另一个进程的执行的分支点；

d)为两个备选进程分配公共时隙；

e)为公共时隙指派等于两个备选进程中的资源需求的较大者的资源需求；

f)针对每一个分支点，迭代步骤c)；

g)组合在与任务相关联的执行模板中生成的时隙；以及

h)根据向执行模板的时隙指派的资源需求，配置实时多任务系统以便约束任务的执行。

方法可包括以定义由转换节点连接的一组进程的图的形式来表示任务的步骤，其中每一个转换节点在任务在多任务系统上的执行期间根据时基定义同步点；从进程的源转换节点和目的地转换节点中，定义向每一个进程分配的时隙的极限；对于具有公共源节点和两个相应目标节点的两个备选进程，合并两个目标节点为合并的目标节点；并且由公共源节点和所合并的目标节点，定义备选进程两者的公共时隙。

针对在步骤c)具有不同的时间约束的两个备选进程，方法可包括以下步骤：在具有最长时间约束的两个备选进程中的第一备选进程中生成中间转换节点，产生在源节点与中间节点之间的第一部分备选进程，和在中间节点和第一备选进程的目标节点之间的第二部分进程；为第一部分备选进程指派第一资源需求和等于第二备选进程的时间约束的时间约束；为第二部分进程指派第二资源需求，和等于两个备选进程的时间约束之差的时间约束，其中该第二资源需求使第一和第二资源需求之和等于第一备选进程的资源需求；根据步骤d)进行第一部分备选进程和第二备选进程。

方法可包括以下步骤：在每个时隙，通过监视器检查进行中的进程的执行遵守向时隙指派的资源需求；并且如果进行中的进程的执行超过资源需求并且进行中的进程是第一部分备选进程，则忽略通过监视器发出故障信号。

方法可包括以下步骤：根据第一部分备选进程的执行，设定状态变量；如果进行中的进程的执行超过资源需求并且设定了状态变量，则忽略通过监视器发出故障信号；并且对应于合并的目标节点的同步点清除状态变量。

方法可包括针对图的循环部分的下列步骤：将每个具有更长时间约束的进程分成一组具有更短时间约束的部分进程，该更短时间约束为循环部分中时间约束的最大公约数，从而将图的循环部分转变成为归一化的子图，该子图定义一系列全部具有相同归一化时间约束的完整或部分进程；以及在对应的部分进程之间为每个具有更长时间约束的进程分配资源需求，从而部分进程的资源需求之和等于具有更长时间约束的进程的资源需求。

方法可包括以下步骤：将子图的第一部分的末端与子图的第二部分的始端重叠，使得子图的第一部分的末端的转换节点与子图的第二部分的始端的相应的节点重合，从而通过两对连续的重合节点定义与具有第一对的两个节点作为相应起源的进程公用的时隙；以及指派共有时隙，因此限定资源需求等于与第一对节点相关的进程中最大的资源需求，并且时间约束等于归一化的时间约束。

附图说明

从仅出于示例性目的提供并在附图中表示的本发明的特定实施例的以下描述中，其它优点和特征将变得更显而易见，在附图中：

图1是符合具有采用相同时间约束的分支备选的灵活性任务模型的实时任务图的示例；

图2A和2B示出图1中的图的可能处理序列中的一种处理序列的部分执行轨迹，以及并行任务的执行轨迹；

图3A到3C示出图1中的图的转化以及生成的静态执行模板；

图4是符合具有采用不同时间约束的分支备选的灵活性任务模型的实时任务图的示例；

图5A到5C示出针对时间约束的第一备选的图4的图的转化，以及生成的静态执行模板；

图6A到6C示出针对时间约束的第二备选的图4的图的转化；以及

图7A和7B说明地示出用于图5C的执行模板的优化步骤。

具体实施方式

图1是符合灵活性任务模型的示例性实时任务图。在这个图中，如同以下陈述的其它图，通过在源节点和目标节点的两个转换节点之间的定向的弧线，表示组成任务的每个进程。节点是在执行任务期间由操作系统使用以便组织进程启动的同步点。向每个进程指派用于识别对应同步点之间的持续时间的时间约束。

另外，对于在其时间约束的限制内将要执行的进程，它也具有物理的资源需求(CPU占用，内存印记)。

采用信息x+N注释图中的每条弧线(或进程)，其中x是资源需求标识并且N是时间约束标识。可将资源需求x表示为时间，即假设进程具有所有的硬件资源时完成进程所需要的时间。时间约束可以是定义时间单位的整数。因此，以相同的时间单位表示x和N，选择值x和N使x≤N。如果x＝N，则进程要求贯通由时间约束定义的时隙的所有硬件资源，从而没有其它进程可在同一间隙中被并行执行。(资源需求和时间约束的计算不是本发明的主题，并且将不会详细描述)

在下文中，用于指定资源需求的字母同样识别进程。

图或任务被称为依据其中包括任意组织的分支和环路的“灵活性模型”。因为每条分支是在运行时动态地，并且以不可预测的方式确定的，所以进程的执行顺序一般是非周期性的。将在下文中理解该结论。

图2A示出图1的图的示例性执行轨迹。在通过进程的时间约束而定义的步的时间轴上示出在执行期间交叉的节点。因此，将节点定位于其中操作系统启动对应进程的固定的同步点处。

每个进程可根据它的需要和实际可用资源来采取可变的时间。操作系统也执行被配置成通过每个进程计算执行中所花费的时间的监视器进程。如果进程超过向其指派的时间需求，则监视器发出异常信号。因此可认为时间需求是执行时间限额。

图1中的图的任务的执行从节点1开始，其中第一分支发生在两个备选进程a和b之间。选择进程b用于执行，则导向节点2。进程d在节点2和4之间执行。在节点4，新的分支发生在进程f和进程g之间；选择进程g用于执行，则导向节点3。进程c在节点3和5之间执行。在节点5，新的分支发生在进程e和进程h之间；选择进程h用于执行，则导向节点2…

总之，针对进程设定的资源需求可以显著小于时间约束，意味着任务执行留出可用资源以便并行地实施其它任务。

图2B示出与图2A的任务并行执行的任务的执行轨迹。该并行任务包括具有采用相同标记定义的资源需求的一系列进程m，n，p，q和r。为了帮助理解，该任务采用与图2A中的这些任务对齐但时间约束有变化的同步点示出。对于这个将要与图2A中的任务并行调度的任务，在同步点之间的任意间隔内，可期望进程的资源需求之和与时间约束兼容。在时间轴下说明地示出满足示例的一组可能的不等式。

因此，并行调度两个任务涉及导出必要参数的一系列进程的知识。如果可离线确定该系列，则同样可离线地进行调度，即静态调度。当任务符合灵活性模型，即特别是当它包括分支时，一般不可能离线地得知序列。那么当可识别分支状态时，传统上动态地实现调度，即在运行时实现。

在关键实时系统中，此外期望验证系统对于任何调度组合都是安全的。这在传统上是通过测试所有组合而实现的。当动态地实现调度时，测试的组合数量在实际中可能是禁止性的。

本文中公开了用于实施符合灵活性模型的任务的静态或者离线调度的方法。该方法的目的在于限制调度组合的数量，从而可使用常规工具来耗尽一切地验证。寻求为每个任务建立通过离线调度工具可开发的所谓静态的“执行模板”。

为了这个目的，在执行模板中向可跟随分支发展的两个备选进程指派单独的时隙。将指派给单独间隙的资源需求定义为等于两个备选进程中的较大资源需求。指派给间隙的时间约束，即间隙的边界留待定义。

在第一方法中，将解决其中备选进程具有相同时间约束的情况。在更通用情况下，如以下进一步讨论的，可以找到将任意情况变为其中两个备选进程具有相同时间约束的情况的转化。

在图1的图中，跟随每条分支(节点1，4和5)发展的备选进程刚好具有相同的时间约束。

图3A说明地示出转换图1的图的第一步。两个备选进程a和b的两个目标节点2和3合并为单独节点2_3。连接节点2和3到节点4和5的弧线都连接到节点2_3。从节点1到节点2和3的两条弧线合并为单独的弧线。这个唯一的弧线与表示进程a和b中任何一个的“矛盾”进程相关联，并且被标注为a|b+2。如通过这个注释所指示的，进程a和b的公共时间约束(+2)为矛盾进程的时间约束。矛盾进程的资源需求被定义为等于进程a和b中资源需求的最大值max(a,b)。

可注意到不是分支备选的进程c和d，变成在合并的节点2_3处起始的备选。还可以注意到由于节点2和3被合并的事实，将从节点4和5行进到节点2和3的备选f，g和e，h组合在一起。在这个阶段，这些备选已可以通过单独弧线来表示，像弧线a|b+2。

图3B说明地示出图1的任务图的转换的最终步骤。将备选进程c和d的目标节点4和5合并为节点4_5。存在从节点2_3行进到节点4_5的具有相同时间约束(+4)的两个进程c和d，和以相反方向行进的具有相同时间约束(+2)的四个进程e，f，g和h。根据应用于备选进程a和b的规则，将从同一源节点到同一目标节点并具有相同时间约束的所有弧线合并为指派给保持时间约束的矛盾进程的单独弧线，并且将其资源需求设定为等于被合并的弧线中的资源需求的最大者。因此获得从节点2_3到节点4_5的具有资源需求max(c,d)的单独的矛盾进程c|d+4，以及反向的具有资源需求max(e,f,g,h)的单独的矛盾进程e|f|g|h+2。因此移除图中的所有备选来产生具有由环路中执行的循环部分终结的线性路径的图是可能的。

图3C说明地示出从图3B的转换图中确定的执行模板，与图2A的执行轨迹具有相同的格式。模板和轨迹之间的显著差异在于，可使用图3B的所转换的图离线确定模板。

在时间t＝0，在节点1决定备选进程a和b中的一个备选进程的执行。无论什么进程，都在节点1和2_3之间限定的单独间隙中执行，其持续时间与两个备选都兼容。因此在节点2_3和4_5之间限定的下一间隙中执行进程c和d中的任意一个进程。最后，在节点4_5和2_3之间限定的间隙中执行进程e，f，g和h。然后执行从节点2_3继续新循环R。

指派给节点1，2_3，4_5和2_3之间的间隙的资源需求相应地为max(a,b)，max(c,d)和max(e,f,g,h)。

该执行模板可以是处理定义任务的图的源代码的编译工具链的中间产品。模板提供允许操作系统运行任务并检查其安全操作的参数，特别是指派给时隙的资源需求，该需求可用于配置监视器以确保对应进程按时完成。

将注意的是这种方法并不影响任务的执行，而是修正进程的执行约束，因为监视器被配置成考虑最大化的资源需求，而不是准确的资源需求。

此外模板允许在任何时刻预测任务在资源需求和时间约束方面是如何发展的。实际上，无论什么备选在分支之后执行，图3C的模板的循环部分R可从图2A的第一节点2随意地重复，从而预测执行轨迹的任意点的资源需求和时间约束。唯一缺点是资源需求的值被最大化，而不是准确值。

针对在系统上运行的每个任务生成类似的模板。限定在这些模板中的时隙的持续时间和对应的资源需求通过可生成操作系统的静态调度参数的离线调度工具是可用的。

图4是包括具有不同时间约束的备选进程的示例性图，其对应于比图1的图更普遍的情况。沿着导向节点2的进程，执行在节点1开始。在节点2，分支在时间约束+1的进程b，或时间约束+4的进程c之间发生。进程b导向节点3，而进程c导向节点4。时间约束+3的进程d从节点3行进到节点4。最终，进程e从节点4行进到节点1。

试图修正该图，使其可像图1的图一样被转化，从而定义静态执行模板。图5A到图5C说明地示出针对其的方法。

图5A图示地说明了图4的图的第一转化步骤。在具有最长时间约束的备选进程，即进程c中，插入中间节点3b。据知连接节点2和3b的弧线代表进程c的一部分c1，并且对其指派与备选进程b相同的时间约束+1。连接节点3b和4的弧线代表进程c的剩余部分c2，并且对其指派进程c的时间约束的补足部分+3。部分进程c1和c2的资源需求满足c1+c2＝c。资源需求c在需求c1和c2之间的分配可以是任意的。可以优化该分配，例如以便减小在备选进程的资源需求和它们的最大值之间的偏差。例如，如果c＝2，b＝0.8以及d＝1，则值c1＝0.9且c2＝1.1产生0.1的最大偏差。

在此可注意到增加资源需求(c1)的事实对应于增加由监视器检测的执行约束，约束不要求先验的。如果不采取特定的测量，监视器将从点2检查部分进程c1的执行满足资源需求c1，然而最初的约束是进程c的执行满足资源需求c。

满足这些约束的第一种方法是开发者或工具链负责将进程c分成适合的部分进程c1和c2。作为任务的所修正的执行特性的回报，这允许使用现有的未修正的操作系统。

优选的方法涉及操作系统的简单修正。如图5A所示，为节点2的分支的两个备选进程指派状态变量或标记B以便识别在运行时所采取的备选。当所执行的备选对应于未修正的弧线(b)时，标记B保持预置的清空的值(例如0)。当备选对应于所修正的弧线(c1)时，通过进程本身或通过操作系统设定标记B。将结合图5C的更多细节描述这个标记的使用。

图5B说明地示出图5A的图的最终转换。由于节点3b的插入，生成两个具有相同时间约束的备选进程，根据关于图3A所描述的方法可将这些备选进程的目标节点3和3b进行合并。这在节点2和所合并的节点3_3b之间生成具有时间约束+1和资源需求max(b,c1)的矛盾进程b|c1。

利用标记B，矛盾进程表示为b(B＝0)|c1(B＝1)。

从节点3和3b行进到节点4的具有相同的时间约束+3的进程d和c2，可被合并到具有时间约束+3和资源需求max(c2,d)的单独的矛盾进程c2|d。

图5C说明地示出从图5B的转化图确定的执行模板。这个模板可根据节点1，2，3_3b，4的顺序重复。

如果不使用标记B，并且部分进程c1在其对应的时隙中执行，监视器从点2检查进程c1符合它的资源需求c1。这涉及指定部分进程c1设计成满足该约束，尽管这在最初并不是强制性的。

在这种情况下标记B被用于禁用监视器，从而可放松对该部分进程的约束。

如果执行备选进程b，则标记B保持其原始的清空状态。这向监视器发出应当正常地监测进程的执行的信号。

如果执行备选部分进程c1，则(通过进程本身或通过操作系统)设定标记B。在这种情况下，即使超过资源需求c1，监视器报告无故障。标记B在节点3_3b被清除，这样从节点3_3b起监视器正常操作。

因此通过使用标记B，将进程c实际上分成两个部分进程变得没必要。原始进程c可在节点2发起，并且它的执行可持续超出节点3_3b而无需发送故障信号。只有进程c的执行超过资源需求c1+c2时，将发出故障信号，其对应于原始图的约束。出于调度的目的，仍然认为进程c的资源需求在两个值c1和c2之间分配。

如上面所注意的，在插入中间节点3b之后，进程c2和d具有相同的时间约束。选择这些值以便简化说明。在通常情况下，时间约束将是不同的。在这个例子中，通过以下示例所示，重复用于进程c的技术是充分的。

图6A-6C说明地示出针对进程d的不同时间约束值的图4的图的转换步骤，在此采用+6代替+3。

图6A对应于图5A的步骤。唯一不同的是进程d的时间约束值。

在图6B中，已将节点3和3b合并。节点3_3b和4通过具有不同时间约束的两条弧线c2+3和d+6连接。

在图6C中，节点4被分成两个节点，形成进程c2+3的目标的4'的一个节点，以及形成进程d+6的目标的4”的另一节点。节点4'和4”每个通过进程e+1连接到节点1。

从该步骤，通过在具有最长时间约束的进程d+6中插入中间节点，重复图6A或5A的步骤的流程，以便生成具有相同时间约束的两个备选进程c2+3和d1+3，以此类推，将该图转化为循环图或由循环部分终结的图。

从任意的图，这个方法产生包括循环部分的，由不同持续时间的有限数量的时隙形成的执行模板。为了并行调度若干任务，专门的工具将使用资源需求和包含在模板中的间隙持续时间，从而找到可并行执行的模板的组合，以及因此可并行执行的任务。因此，将调度简化为匹配模板(每个任务一个)而不是进程的匹配序列(每个任务多个)。

为了进一步简化系统验证测试，可期望采用具有相同时隙的短执行模板。

图7A和7B说明地示出将时隙的长度归一化和缩短模板的方法。

图7A说明地示出图5C的模板的处理步骤，作为示例。在模板的循环部分，寻求将更长的间隙分成其长度为循环部分的间隙的最大公约数的若干更短的间隙。在图7A的模板中，节点3_3b和4之间长度为3的时隙，被分为3个长度为1的间隙。这相当于在图的弧线c2|d中插入中间转换节点4a和4b。

矛盾进程c2|d因此被分为具有相同时间约束1的3个部分矛盾进程[c2|d]0到[c2|d]2。进程c2|d的初始资源需求max(c2,d)在权重为使p0+p1+p2＝1的p0，p1和p2的三个部分进程之间分配。

至于图5A的中间节点3b，中间节点4a和4b变成从中监视器监测进程的执行时间的同步点。为了避免在实际上拆分进程c2|d，优选使用像标记B的标记S，该标记S指示如果进程超过它的资源需求，则监视器忽略报告故障。从进程c2|d的始端(所以基本上从进程c和d中任意进程的始端)无条件地设定标记S，并且然后在最后的中间同步点(4b)清除。

这个技术因此将时隙的持续时间归一化，这是简化验证测试的第一种改进。

图7B说明地示出缩短图7A的标准化执行模板的步骤。模板的第二半段与其第一半段重叠，从而节点4a，4b和4相应地与节点1，2和3_3b合并。因此仅保留持续时间为1的三个时隙。在第一时隙，可执行进程a和[c2|d]1中的任意进程，因此事实上当使用标记B和S时，是进程a，c和d中的任意进程。在第二时隙，可执行进程b，c1和[c2|d]2中的任意进程，因此在事实上是进程b，c和d中的任意进程。在最后的时隙中，可执行进程e和[c2|d]0中的任意进程，因此事实上是进程e，c和d中的任意进程。

这些时隙的资源需求遵循与备选进程相同的确定规则。它们相应地等于max{a,p1·max(c2,d)}，max{b,c1,p2·max(c2,d)}和max{e,p0·max(c2,d)}。

针对所考虑的示例模板，其是采用偶数间隙完全循环的，该模板的尺寸可被减半。在任何情况下，模板包括由可包括奇数间隙的循环部分(图3B，3C)跟随的线性部分。重叠方法应用于标准化的循环部分。即使归一化的循环部分具有奇数个间隙时仍可适用，实际上重叠可以是局部的，其稍微牺牲模板的尺寸简化。