CN103885826A - 一种多核嵌入式系统实时任务调度实现方法 - Google Patents

Abstract

本发明公开了一种多核嵌入式系统实时任务调度实现方法，包括如下步骤：建立实时任务集合，计算任务依赖关系序列，建立以完成时限要求排序的任务序列，处理起始调度任务，建立调度序列。本发明的技术方案适用于多核嵌入式系统任务实时调度，充分利用了多核处理器的多个处理器核，既加快了多核嵌入式系统中任务的处理速度，又保证了实时任务的实时性。

Description

一种多核嵌入式系统实时任务调度实现方法

技术领域

本发明属于多核嵌入式系统任务资源调度技术领域，特别是涉及一种多核嵌入式系统实时任务调度实现方法。

背景技术

随着半导体技术的不断进步，VLSI(Very Large-Scale Integrated，超大规模集成电路)的集成密度在大幅度增加。单一芯片上的集成度不断提高，使得SoC(System on Chip，片上系统)技术得到了发展和应用。SoC技术是将一个系统的全部功能模块集成到单一的芯片上，从而实现在单个芯片上集成完备的系统功能，其处理器核也简称为核。

集成在SoC芯片上的通常是IP(Intellectual Property，知识产权)核。这些可重用的IP核包括嵌入式处理器，、存储模块、接口模块和面向应用定制的处理构件。在SoC上集成的IP核可以分为三类：软核(Soft IP)，是指使用RTL(RegisterTransfer Level，寄存器传送级别)或者更高级别进行描述的IP核；硬核(Hard IP)，是指具有固定的层结构，并且针对特定过程中的特定应用进行了定制的优化过的IP核；固化核(Firm IP)是指已经做了描述但是提供了参数供设计人员进行应用定制的IP核。

SoC不仅集成的晶体管数量多，而且由于集成了不同种类的功能和技术，并且由于软硬件的协同工作，使得SoC具有复杂的体系结构和逻辑接口。SoC的高集成度也使得SoC的功能极为丰富，提高了对片上面积的有效利用，缩短了片上连线的长度，从而提高了整个系统的性能。

多核嵌入式系统(MPSoC)是对SoC技术的进一步发展，是指具有多个嵌入式指令集处理器的SoC。MPSoC结合SoC技术与多核技术的特点。多核技术是指在一个芯片上集成多核处理器核，以提高处理器的处理能力；如果芯片上所集成的多个处理器核相同，核问地位相同，则称为同构多核处理器；如果芯片上所集成的处理器核不同，有主处理器和协处理器之分，则称为异构多核处理器。MPSoC片上既有多核处理器核，又集成了不同种类的软硬件，兼具了SoC和多核的优点。在SoC与MPSoC芯片上，往往会集成存储器，为处理器核提供存储服务，从而提高处理器的效率。

实时操作系统(RTOS)是指能对外部事件在限定的时间内作出并完成响应的多任务操作系统，它是嵌入式计算机中的重要的系统资源，与通用平台的操作系统不同，它往往嵌入到目标机硬件设备内部运行，一般用户无法看到它的运行界面，因而又被称为嵌入式操作系统。它往往采用微内核结构，具有实时性、可靠性和可裁减性的特点，非常适合于嵌入式系统和要求实时处理的应用场合。

实时的特征有两点，那就是系统不仅需要给出合乎逻辑的计算结果，而且其处理时间还需要满足一定的要求，比如说不能超过某个截止时间等等。因此可以把实时系统分为两类，一类是硬实时(Hard Real-Time)；另外一类则是软实时(Soft Real-Time)。所谓硬实时是指如果系统对某个实时任务的处理未能在某个截止时间开始或者结束的话，最终的结果将是灾难性的，这就意味着即便是处理结果合乎逻辑但是仍然毫无意义；而在软实时系统中，处理任务启动或者结束的截止时间只是一个期望值，并不见得必须满足；即便是处理时间超过了截止时间，也是有意义的。

而随着对于计算机处理器的研究开始转向多处理核心的方向，多核嵌入式系统成为操作系统新的挑战，而任务调度则是其中的要点。如何对多核嵌入式系统中的任务在确保实时性的条件约束下能够进行高效的任务调度，是当前的一个重要问题。同时这也涉及到如何利用多个处理器核的问题。而目前现有的任务调度方法往往强调实时性，但对于多核上如何进行调度缺少深入的分析，因而不能实现高效的调度；同时，由于现有调度方法需要一个较为严格的假设条件，因此在实际使用时往往受到很大的限制。

发明内容

本发明旨在克服现有技术缺陷，提供一种多核嵌入式系统任务实时调度实现方法。

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

一种多核嵌入式系统实时任务调度实现方法，包括以下步骤：

S10，建立包含多核嵌入式系统中全部任务的实时任务集合T；

S20，从任务集合T中选择不依赖其他任务的s个任务建立集合B；以这s个任务为起点，建立分别以任务B1，B2，…，Bs为起点的任务依赖关系序列的集合L；

S30，对任务集合T中的所有任务按照完成时限要求从短到长进行排序，形成任务序列U；

S40，处理起始调度任务：从U中选择m个排序在前的任务，作为起始调度任务；

S50，建立调度序列，包括：

S501：如果U中的任务数量小于或等于m，则将序列U作为调度序列，调度工作完成，其中m为多核嵌入式系统的处理器核数，否则执行步骤S502；

S502：计算U中排序在前的m个任务的完成时间并按完成时间从短到长排序形成序列R，如果没有任何任务完成时间超过其完成时限要求，则以依赖关系为顺序，对于第i个处理器核C_i，从处理器核C_i上的任务T_ci对应的任务依赖关系序列集合选择任务T_ci的后继任务中第一个没有被分配且不受任务依赖关系影响的任务分配到处理器核C_i上；如果受到任务依赖关系影响，则依照R中的序列关系进行分配；

如果有q个任务的完成时间超过其完成时限要求则对于这q个任务，按照其完成时限要求进行从短到长进行排序，然后将q个任务依次分配到前q个处理器核上；

S503，将这m个任务从U中转移到调度序列K中；

S504，如果U中仍有任务，重复步骤S402～S403，直到U中不再有任务，调度序列K即为最终的调度序列。

进一步的，所述步骤S10还包括：

为T中的每个任务分别建立属性集合，所述属性集合包括所述任务的执行时间长度和完成时限。

进一步的，所述步骤S10还包括：

对于T中的N个不同任务，建立集合厂{(Ti，Tj)}，其中任务Tj的执行依赖于任务Ti的执行结果。

进一步的，步骤S40包括：

如果U中的任务数量小于或者等于m，按照U中的排序将U中的所有任务分配到处理器核上，调度工作完成；否则将选中的m个任务分配到m个处理器核上，并将这m个任务从U中转移到调度序列K中。

由于采用上述技术方案，本发明减少了复杂的理论化的实时调度假设，改进对于实时性调度过程中过多的约束条件所造成的实用性问题，为多核嵌入式系统任务的实时调度提供了更为简化的方法，从而提高了多核嵌入式系统任务实时调度的效率。本发明与现有技术相比，具有如下积极效果：

(1)高效性。多核嵌入式系统上具有多个处理器核，可以同时处理多个任务。在本发明中，对任务集合中的多个任务进行依赖关系的分析，使得多个任务能够顺利的在多个处理器核上进行分配，完成多任务的同时调度，达到更高的调度效率；

(2)实用性。在本发明中，简化了对多核嵌入式系统中任务的多重约束条件，在相对较少的约束条件下，对任务的分析从实际运行的角度出发，使得任务的分配能够更加灵活，并使得调度方法能够满足实际需要，从而使得本发明所提供的方法能够具有更强的实用性。

因此，本发明适用于多核嵌入式系统任务实时调度，充分利用了多核处理器的多个处理器核，既加快了多核嵌入式系统中任务的处理速度，又保证了实时任务的实时性。

附图说明

图1是本发明实施例的方法示意图。

具体实施方式

下面结合附图和具体实施方式对本发明做进一步的描述，并非对其保护范围的限制。

一种多核嵌入式系统实时任务调度实现方法，该实现方法的步骤如图1所不：

S10，建立包含多核嵌入式系统中全部任务的实时任务集合T。

对于多核嵌入式系统中的全部任务，建立一个任务的集合T，T由系统中的n个任务构成，可以表示为：

T={T_o,T₁，…，T_n-1}；

例如，对于具有15个任务的多核嵌入式系统，其集合T为：

T={T₀,T₁,T₂,T₃,T₄,T_s,T₆,T₇,T₈,T₉,T₁₀,T₁₁，T₁₂，T₁₃，T₁₄}；

对于T中的任务Ti(0_q<N)，为其建立属性集合Ai，包括执行时间长度Ei和完成时限要求Di；

对于上述具有15个任务的集合T，每个任务的属性集合Ai如下表所示：

对于T中的N个不同任务，建立集合Γ{(Ti，Tj)}，O<i<N，O≤j<N，其中任务Tj的执行依赖于任务Ti的执行结果。即当任务Tj的执行依赖于任务Ti的执行结果时，Tj的执行不早于Ti。

对于上述具有15个任务的集合T，集合厂如下所示：

Γ={(T₂，T₉)，(T₅，T₄)，(T₁₀，T₁)，(T₉，T₀)，(T₄，T₃)，(T₁，T₁₃)，(T₀，T₁₁)，(T₁₂，T₁₄)，(T₃，T₇)，(T₁₃，T₈)，(T₇，T₆)}。

S20，从任务集合T中选择不依赖其他任务的s个任务建立集合B；以这s个任务为起点，建立分别以任务B1，B2，…，Bs为起点的任务依赖关系序列的集合L。

各任务之间存在着相互关系，在此对其中所述任务依赖关系进行说明：任务依赖关系是指一个任务的执行需要以另一任务的完成为条件而产生的任务先后执行的顺序关系。例如，对于任务T₁和任务T₂，如果完成任务T₂的一个必要条件是任务T₁执行过程中所产生的一个计算结果；则若要完成任务T₂，必须等待任务T₁提供这个计算结果。因此，称任务T₁和任务T₂之间具有任务依赖关系，任务T₂依赖于任务T₁。

从T中选择不依赖其他任务的s个任务，B1，B2，…，Bs，记为集合B；以这s个任务为起点，根据集合厂分别计算出以任务B1，B2，…，Bs为起点的任务依赖关系序列集合L，其中Li对应以任务Bi为起点的任务依赖关系序列；

对于上述具有15个任务的集合T，不依赖其他任务的任务为：

T₂，T₅，T_lo；

其中，T₂被标记为B1，T₅被标记为B2，T₁₀被标记为B3，则对应的Li如下所示：

对于B1即T₂，L1为T₂，T₉，T₀，T₁₁，T₁₂，T₁₄；

对于B2即T₅，L2为T₅，T₄，T₃，T₇，T₆；

对于B3即T_lo，L3为T_lo，T₁，T₁₃，T₈。

S30，对任务集合T中的所有任务按照完成时限要求从短到长进行排序，建立任务序列U。

对于具有m个处理器核的多核嵌入式系统，对T中的所有任务按照完成时限要求从短到长进行排序，形成序列U；

对于上述具有15个任务的集合T，而多核处理器上的核数量m=4，其序列U如下：

T₂，T₅，T₁₀，T₁，T₉，T₄，T₀，T₃，T₁₁，T₇，T_i2，T₁₃，T₆，T₈，T_i4

降序排序时，完成时限要求小的任务排在序列的前端。

S40，处理起始调度任务：从U中选择m个排序在前的任务，作为起始调度任务。

对于上述具有15个任务的集合T，从中选择排序前4的任务，则调度的起始任务为：T₂，T₅，T_lo，T₁；

这4个任务被分配到处理器核C₁，处理器核C₂，处理器核C₃和处理器核C₄，对应如下：

任务	对应的处理器核
		T2	C1
T5	C2
		T10	C3
T1	C4

S50，建立调度序列，包括：

S501：如果U中的任务数量小于或等于m，则将序列U作为调度序列，调度工作完成，其中m为多核嵌入式系统的处理器核数，否则执行步骤S502。

S502：计算U中排序在前的m个任务的完成时间并按完成时间从短到长排序形成序列R，如果没有任何任务完成时间超过其完成时限要求，则以依赖关系为顺序，对于第i个处理器核C_i，从处理器核C_i上的任务T_ci对应的任务依赖关系序列集合选择任务T_ci的后继任务中第一个没有被分配且不受任务依赖关系影响的任务分配到处理器核C_i上；如果受到任务依赖关系影响，则依照R中的序列关系进行分配；

如果有q个任务的完成时间超过其完成时限要求则对于这q个任务，按照其完成时限要求进行从短到长进行排序，然后将q个任务依次分配到前q个处理器核上。

S503，将这m个任务从U中转移到调度序列K中；

S504，如果U中仍有任务，重复步骤S402～S403，直到U中不再有任务，调度序列K即为最终的调度序列。

从U中余下的11个任务中选择排序在前的4个，分别计算它们分配到这四个处理器核上时的任务完成时间，分别如下表所示：

	C1	C2	C3	C4
					To	14	19	18	16
T4	10	15	14	12
					T0	9	14	13	11
T3	7	12	11	9

则后续4个任务在4个处理器核上的任意分配均不会产生任何超出完成时限要求的情况。

但是由于受到依赖关系约束，即T₈依赖于T₁₃，T₁₃应比T₈先分配。因此，对于处理器核C₁，选择C₁上的任务T₂的后续任务T₉分配到C₁上；对于处理器核C₂，选择C₂上的任务T₅的后续任务T₄分配到C₂上；对于处理器核C₃，选择C₃上的任务T₁₀的后续任务T₈分配到C₃上；对于处理器核C₄，选择C₄上的任务T₁的后续任务T₁₃分配到C₄上。

任务	对应的处理器核
		T0	C1
T4	C2
		T13	C3
T8	C4

这4个任务从U中去除，此时U中的序列为：

T₀，T₃，T₁₁，T₇，T₁₂，T₆，T₁₄；

而调度序列K为：

T₂，T₅，T₁₀，T₁，T₉，T₁₃，T₈，T₄；

T₉，T₄，T₁₃和T₈的开始执行时间分别为：

T₉在时刻4，T₄在时刻9，T₈在时刻8，T₁₃在时刻6；

则4个任务的运行结束时间分别为：

T₉在时刻14，T₄在时刻15，T₈在时刻16，T₁₃在时刻15；

则序列R为：

T₉，T₄，T₁₃，T₈；

接下来从U中后续7个任务中选择排序在前的4个，分别计算它们分配到这四个处理器核上时的任务完成时间，分别如下表所示：

	C1	C2	C3	C4
					T0	19	20	21	20
T3	26	27	28	27
					T11	21	22	23	22
T7	20	21	22	21

则后续4个任务中，T₃可能由于分配到C₂和C₃上导致T₃的运行时间超过完成时限要求。为保证T_s能够满足完成时限要求，采用如下分配方法：对于处理器核C₁，选择将T₃分配到C₁上；对于处理器核C₂，选择任务T₀分配到C₂上；对于处理器核C₃，选择任务T₁₁分配到C₃上；对于处理器核C₄，选择C₄任务T₇分配到C₄上。

任务	对应的处理器核
		T3	C1
T0	C2
		T11	C3
T7	C4

这4个任务从U中去除，此时U中的序列为：

T₁₂，T₆，T₁₄；

而调度序列K为：

T₂，T₅，T₁₀，T₁，T₉，T₁₃，T₈，T₄，T₃，T₀，T₁₁，T₇；

T₃，T₀，T₁₁和T₇的开始执行时间分别为：

T₃在时刻14，T₀在时刻15，T₁₁在时刻16，T₇在时刻15；

则4个任务的运行结束时间分别为：

T₃在时刻26，T₀在时刻20，T₁₁在时刻23，T₇在时刻21；

则序列R为：

T₀，T₇，T₁₁，T₃；

接下来对U中3个任务，分别计算它们分配到这四个处理器核上时的任务完成时间，分别如下表所示：

	C1	C2	C3	C4
					T12	34	28	31	29
T6	35	29	32	30
					T14	36	30	33	31

则3个任务在4个处理器核上的任意分配均不会产生任何超出完成时限要求的情况。

但是由于受到依赖关系约束，即T₁₄依赖于T₁₂，T₁₂应比T₁₄先分配。因此，对于处理器核C₁，选择C₁上的任务T₃的后续任务T₆分配到C₁上；对于处理器核C₂，选择C₂上的任务T₀的后续任务T₁₂分配到C₂上；对于处理器核C₃，选择C₃上的任务T₁₁的后续任务T₁₄分配到C₃上；对于处理器核C₄，该处理器核空闲。

任务	对应的处理器核
		T6	C1
T12	C2
		T14	C3

这4个任务从U中去除，此时U中的序列为空。

而最终的调度序列K为：

T₂，T₅，T₁₀，T₁，T₉，T₁₃，T₈，T₄，T₃，T₀，T₁₁，T₇，T₁₂，T₆，T₁₄。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，任何不超过本发明实质精神范围的发明创造、修改，均落入本发明的保护范围。

Claims (4)

1.一种多核嵌入式系统实时任务调度实现方法，其特征在于，包括：

S10，建立包含多核嵌入式系统中全部任务的实时任务集合T；

S20，从任务集合T中选择不依赖其他任务的s个任务建立集合B；以这s个任务为起点，建立分别以任务B1，B2，…，Bs为起点的任务依赖关系序列的集合L；

S30，对任务集合T中的所有任务按照完成时限要求从短到长进行排序，形成任务序列U；

S40，处理起始调度任务：从U中选择m个排序在前的任务，作为起始调度任务；

S50，建立调度序列，包括：

S501：如果U中的任务数量小于或等于m，则将序列U作为调度序列，调度工作完成，其中m为多核嵌入式系统的处理器核数，否则执行步骤S502；

S502：计算U中排序在前的m个任务的完成时间并按完成时间从短到长排序形成序列R，如果没有任何任务完成时间超过其完成时限要求，则以依赖关系为顺序，对于第i个处理器核C_i，从处理器核C_i上的任务T_ci对应的任务依赖关系序列集合选择任务T_ci的后继任务中第一个没有被分配且不受任务依赖关系影响的任务分配到处理器核C_i上；如果受到任务依赖关系影响，则依照R中的序列关系进行分配；

如果有q个任务的完成时间超过其完成时限要求则对于这q个任务，按照其完成时限要求进行从短到长进行排序，然后将q个任务依次分配到前q个处理器核上；

S503，将这m个任务从U中转移到调度序列K中；

S504，如果U中仍有任务，重复步骤S402～S403，直到U中不再有任务，调度序列K即为最终的调度序列。

2.根据权利要求1所述的多核嵌入式系统实时任务调度实现方法，其特征在于，所述步骤S10还包括：

为T中的每个任务分别建立属性集合，所述属性集合包括所述任务的执行时间长度和完成时限。

3.根据权利要求1或2所述的多核嵌入式系统实时任务调度实现方法，其特征在于，所述步骤S10还包括：

对于T中的N个不同任务，建立集合Γ{(Ti，Tj)}，其中任务Tj的执行依赖于任务Ti的执行结果。

4.根据权利要求3所述的多核嵌入式系统实时任务调度实现方法，其特征在于，步骤S40包括：

如果U中的任务数量小于或者等于m，按照U中的排序将U中的所有任务分配到处理器核上，调度工作完成；否则将选中的m个任务分配到m个处理器核上，并将这m个任务从U中转移到调度序列K中。