法律状态公告日
法律状态信息
法律状态
2020-02-11
未缴年费专利权终止 IPC(主分类):G06F9/48 授权公告日:20160601 终止日期:20190218 申请日:20130218
专利权的终止
2016-06-01
授权
授权
2013-07-24
实质审查的生效 IPC(主分类):G06F9/48 申请日:20130218
实质审查的生效
2013-06-19
公开
公开
技术领域
本发明涉及多处理器实时系统的调度技术,尤其涉及一种基于温度约束的固定优先级实时任务静态调度方法。
背景技术
所谓的实时系统是指能够在指定或者确定的时间内完成系统功能并做出响应的系统。它具有一定的时间约束,即任务要在指定的时限之前完成操作。近年来,嵌入式实时系统,因其具有较高的可靠性,被广泛应用于航空航天、军事、核工业、信息采集以及环境勘测等领域。为了使储能相对低的嵌入式系统能提供更优质的服务,学术界以及产业界在嵌入式实时系统能耗以及温度方面进行了深入的研究。
在嵌入式实时系统的能量管理方面,普遍被采用和研究方法主要包括动态电压调节技术以及动态电源管理技术。而在温度管理上则主要应用动态的温度管理技术。虽然这些技术都被广泛研究也行之有效,但它们都对嵌入式系统的硬件配置有较高的要求。一方面,动态的能量管理要求系统的处理器支持多种执行频率,并且支持动态的频率切换功能;另一方面,动态的温度管理还需要系统有内置的温度传感器来实时的获取当前的温度情况。
本发明针对更加普遍的嵌入式多处理器的提出静态的任务调度方法,不仅能够静态的保证系统的温度安全,还能最小化系统的能耗。本发明所提出的方法并不需要处理器支持动态的频率调节功能,亦不需要增置额外的温度监控设备。
Gang Quan等人提出了温度约束下的可行性检测技术,该技术可以应用于固定优先级实时任务的温度安全检测。这项技术推进了温度约束下静态实时任务调度的研究进步。然而,该方法需要通过对一个超周期内所有的非安全区间进行温度可行性检查,计算复杂度很高。此外,在温度可感知的静态调度方面,有一些研究通过安排任务执行的顺序来降低处理器的温度峰值。这些研究提出的冷热间隔执行任务的策略来降低处理器峰值的目的。但现有研究大多是基于等周期任务模型。对于普通的非等周期模型还没有深入的研究应用。
发明内容
本发明克服了现有技术中对于超周期的检测计算复杂和温度感知的静态调度未涉及非等周期模型等缺陷,提出了一种基于温度约束的固定优先级实时任务静态调度方法。
本发明提出了一种基于温度约束的固定优先级实时任务静态调度方法,包括以下步骤:
步骤一:获取所有待分配的任务和所有待分配任务的处理器,并获取所述任务的能耗贡献值Metric与所述处理器的能耗贡献值PeMetric;
步骤二:对于一个处理器,选取一个任务进行模糊温度约束检测;若不通过,则不分配所述任务至所述处理器上并选取下一个任务重新执行步骤二;若通过,则将所述任务分配至所述处理器上,并选取下一个待分配的任务重新执行步骤二;直至检测所有待分配的任务后,执行步骤三;
步骤三:对所述处理器上的任务进行精确温度约束检测;若通过,则执行步骤四;否则,删除所述处理器中能耗贡献值Metric最小的任务并重新执行步骤三;
步骤四:若所有待分配的任务均已分配至处理器,则执行步骤五;若还存在待分配的任务未分配至处理器,判断当前分配任务的处理器是否为最后一个处理器;若不是,则选用下一个处理器并重新执行所述步骤二;否则,终止所述静态调度;
步骤五:保存所述静态调度的方案,并根据所述方案实施调度。
其中,步骤一中进一步包括:将所述按处理器的能耗贡献值PeMetric从低至高排序。
其中,执行所述步骤二前进一步包括:将所述任务根据任务的能耗贡献值Metric从高至低排序;选取第一个处理器并开始执行所述步骤二。
其中,步骤二中所述模糊温度约束检测包括以下步骤:
步骤A1:将一个任务预分配至当前的处理器的任务集中;
步骤A2:对所述处理器的任务集进行实时约束检测,测量所述任务集中每个任务的响应时间;若所述响应时间小于延迟阈值,则执行步骤A3;否则,所述模糊温度约束检测结果为不通过;
步骤A3:构造一个调度序列,对所述处理器上第一个超周期内的调度序列进行模糊温度约束下的温度可行性检测,所述超周期表示所述处理器中所有任务的周期的最小公倍数;若所述调度序列满足所述温度可行性检测,则所述模糊温度约束检测结果为通过;否则,所述模糊温度约束检测结果为不通过。
其中,步骤三中所述精确温度约束检测包括以下步骤:
步骤B1:对所述处理器的任务集进行空闲时间分配;
步骤B2:构造一个调度序列,对所述处理器上第一个超周期内的调度序列进行精确温度约束下的温度可行性检测,所述超周期表示所述处理器中所有任务的周期的最小公倍数;若所述调度序列满足所述温度可行性检测,则所述精确温度约束检测结果为通过;否则,所述精确温度约束检测结果为不通过。
其中,所述调度序列如以下公式表示:
>
式中,
其中,对所述调度序列进行的所述温度可行性检测包括以下检测过程:
B(edi-sti)=Bi=(b-a*cfi*v(r))
Kj=exp(-B(ed0-sto)-…-B(edj-stj);
K=exp(-B(ed0-sto)-…-B(ed1-st1)
式中,B(edi-sti)表示第i个调度区间[sti,edi]的温度变化速度因子,Kj表示从第0个调度区间到第j个调度区间内的温度变化因子,st表示执行区间的起始端,ed表示执行区间的截止端,cfi表示执行任务的电路活动因子,0表示第一个超周期的起始端,l表示第一个超周期的截止端。
其中,所述调度序列经所述温度可行性检测后,当且仅当满足以下条件时,通过所述模糊温度约束检测:
0<K<1;T(L)≤Tmax(1-K);
且,在第一个超周期[0,L]内,区间[sti,edi]满足:
>
其中,>有T(edi)≥T(edj);
式中,Tmax表示系统温度阈值,K表示一个超周期结束点的温度变化因子,j表示一个超周期内的温度峰值点所在的调度区间,st表示执行区间的起始端,ed表示执行区间的截止端,l表示第一个超周期的截止端。
其中,所述调度序列经所述温度可行性检测后,当且仅当满足以下条件时,满足所述精确温度约束检测:
0<K<1
T(L)≤Tmax(1-K)
在第一个超周期[0,L]内,对于任意区间[sti,edi]有:
>
式中,Tmax表示系统温度阈值,K表示一个超周期结束点的温度变化因子,j表示在一个超级周期内的任意执行区间的下标号,st表示执行区间的起始端,ed表示执行区间的截止端,L表示第一个超周期的截止端。
其中,所述空闲时间分配用于构造混合任务集,降低处理器执行任务的温度峰值,其包括以下步骤:
步骤C1:根据所述处理器和所述处理器上分配的任务,构成所述混合任务集;
步骤C2:计算所述混合任务集中各每一个混合任务的稳定温度,并根据稳定温度判断所述每一个混合任务属于热任务或冷任务;
步骤C3:计算所述混合任务集的理想均衡温度,选取所述混合任务集中周期最长的任务,判断所述任务是否为热任务;若是,执行步骤C4,否则执行步骤C8;
步骤C4:计算当前混合任务集的理想空闲时间;
步骤C5:计算当前混合任务的最大可用空闲时间;
步骤C6:计算所述当前混合任务的实际空闲时间;
步骤C7:更新所述当前混合任务的执行长度;
步骤C8:判断当前混合任务是否为所述混合任务集中最后一个混合任务;若是,则结束所述空闲时间分配,否则选取下一个混合任务并重新执行所述步骤C4。
本发明中提出一种模糊稳定检测机制。它只对一个超周期内温度最高的不安全区间做温度安全检查。通过这种模糊温度约束下的检测可以检测出大部分不符合温度要求的任务集,大大加快的任务的分配过程。与此同时,本发明考虑到优先级固定的实时系统固有的约束,提出一个温度可感知的空闲时间分配技术,将冷热间隔的优越性应用与普通周期任务调度。更具普遍应用价值。
附图说明
图1为基于温度约束的固定优先级实时任务静态调度方法的流程图。
图2为模糊温度约束下的静态调度的流程图。
图3为精确温度约束下的静态调度的流程图。
图4为空闲时间分配的流程图。
具体实施方式
结合以下具体实施例和附图,对本发明作进一步的详细说明。实施本发明的过程、条件、实验方法等,除以下专门提及的内容之外,均为本领域的普遍知识和公知常识,本发明没有特别限制内容。
实时系统任务是一种具有固定优先级的实时周期任务。任务一般可以表示为一个三元组,如τi=(ai,ci,pi).其中pi是周期,di是时限,ci是τi最坏情况下执行的时钟周期(cycles)数。假设所有的任务的周期等于时限,即pi=di,
本发明应用于一种多处理器模型,在该模型下,每个处理器只支持一种工作频率,不同的处理器的工作频率可以相同也可以不同。假设,系统有R个处理器:PE1,PE2,...,PER,每个处理器支持的频率记作:f(1),f(2),...,f(R);每个处理器支持的工作电压记作:v(1),v(2),...,v(R)。
本发明基于一种被广泛采用的能量模型。处理器PEr的能耗由两部分构成,一部分是系统的漏电功耗Pst(r)=C1*v(r)+C2Tamb;另一部分是系统的动态功耗Pdy=C0*v(r)3。系统的总功耗可以表示为:P(r)=Pdy(r)+Pst(r)=C0*v(r)3+C1*v(r)+C2Tamb (1)。
当任务τi在处理器PEr上运行是,产生的能耗还与任务本身的一个属性相关,一般被称作电路活动因子cfi(circuit activity factor)。任务的活动特性与能耗的关系可表述为:
P(i,r)=cfi*P(r) (2)。
本发明基于标准的RC温度模型。该模型可表述为如下等式:
>
其中,T(t)是在时刻t,处理器芯片的温度。Tamb是外部环境温度。P(t)是时刻t,处理器功耗。R,C是芯片的热阻和热容。
本发明的目标是设计静态的实时任务分配方法,在满足系统温度约束的前提下,最小化系统功耗。的系统功耗是指在一个超级周期L内系统平均功耗。所谓的超级周期实际上是分配在同一个处理器上的所有任务周期的最小公倍数(Lowest Common Multiple,LCM)。
L=LCM(p1,p2,...,pK) (4)
本发明为目标问题作建模工作,假设有任务集Γ={τ1,τ2,...,τN}要分配到处理器PE1,PE2,...,PER上。分配后将产生静态映射矩阵MR×N:
设:Ptot为所有处理器的总功耗,那么它可以表示为:
>
PLCM(r)表示处理器r上,一个超级周期内,任务的平均功耗为,那么:
>
那么,目标函数可以表示为,
>
为了寻求可行的任务分配方案,使得在满足任务实时约束条件下,所有处理器总能耗最小,本发明为目标问题建立如下模型:
求解最优的映射矩阵M,使得在满足条件一、二的情况下,目标式>具有最小值。
条件一、对于任意的τi,1≤i≤N,必须满足Rt(i)<Di且
其中,Rt(i)是τi的响应时间:
条件二、保证处理器在运行过程中的任意时刻温度均小于系统阈值Tmax。
当完成系统任务、能耗、温度模型的建立以及目标问题的建模之后,本发明通过以下步骤解决,如图1所示:
步骤一:获取所有待分配的任务和所有待分配任务的处理器,并获取任务的能耗贡献值Metric与处理器的能耗贡献值PeMetric。其中,进一步包括:将按处理器的能耗贡献值PeMetric从低至高排序。
计算任务的能耗贡献值Metric值:>
其中,Metrick表示τk的对能耗的贡献值。cfk是任务τk的电路活动因子(0<cfk≤1)。pk是任务的释放周期。ck是τk在每个周期需要完成的时钟周期(cycles)个数。
计算所有处理器的能耗贡献值PeMetricr:
>
其中,PeMetricr是处理器PEr对能耗的贡献值。C0,C1,C2是与处理器功耗相关的常系数。v(r)表示PEr所支持的工作电压,而f(r)是PEr所支持的工作频率。Tamb是系统工作的外部环境温度(室温)。根据目标公式(5)可得:
>
本发明中提出静态任务分配方法,其主要思想如下:在满足温度和实时约束的条件下,尽可能将能耗贡献值Metrici大的任务分配到能耗贡献值PeMetricr小的处理器上。因此,首先需要对处理器按照其能耗贡献值PeMetricr进行从小到大的排序。将处理器按照其能耗贡献值PeMetricr从低到高排序,PE1,PE2,...,PER,使得:PeMetric1≤PeMetric2≤…≤PeMetricR。
初始化相关标记量:处理器下标r初始化为1;待分配任务集合Γ={τ1,...,τN}为系统待分配的所有任务。例如,待分配任务集Γ={τ1,τ2,...τN},N=29。任务属性如表1所示:
表1待分配任务集的任务属性表
待分配的处理器集PE1,...,PER。处理器参数如表2所示:
表2处理器参数
其中,R=6;处理器的电容值C=8.415mJ/K;热阻值;R=1.83℃/W;Tmax=85℃,Tamb=25℃
计算任务能耗贡献值Metric:>其中,Metrick表示τk的对能耗的贡献值。cfk是任务τk的电路活动因子(0<cfk≤1)。Pk是任务的释放周期。ck是τk在每个周期需要完成的时钟周期(cycles)个数。计算后各任务的能耗贡献值Metric及属性如表3所示:
表3任务的能耗贡献值及属性表
计算所有处理器的能耗贡献值PeMetricr:
>
其中,PeMetricr是处理器PEr对能耗的贡献值。C0,C1,C2是与处理器功耗相关的常系数。v(r)表示PEr所支持的工作电压,而f(r)是PEr所支持的工作频率。Tamb是系统工作的外部环境温度(室温)。
将处理器按照其能耗贡献值从低到高排序,PE1,PE2,...,PER,使得PeMetric1≤PeMetric2≤…≤PeMetricR。
在本实施例中,处理器的能耗贡献值以及顺序如表4所示:
表4处理器的能耗贡献值与顺序表
初始化相关标记量:处理器下标初始化为r=1;待分配任务集合Γ={τ1,...,τ20}为系统待分配的所有任务。
步骤二:对于一个处理器,选取一个任务进行模糊温度约束检测;若不通过,则不分配任务并选取下一个任务重新执行步骤二;若通过,则将任务分配至处理器上,并选取下一个待分配的任务重新执行步骤二;直至检测所有待分配的任务后,执行步骤三。
在执行步骤二之前先对待分配的任务进行排序处理,对待分配任务集Γ按照任务的Metrlc从大到小排序。置
表5排序后的任务集顺序表
如图2所示,选取第一个处理器及第一个任务执行模糊温度约束检测。先将该任务预分配至该处理器上的任务集中,即Γr=Γr+τi。之后对该处理器上的任务集进行实施约束下的检测,假设处理器PEr上有任务集Γr={γ1,γ2,..,γK}。所有任务都在时刻0释放。根据公式(6)来计算每个任务的响应时间,并检查响应时间是否小于延迟阈值,即Rt(i)<Di是否成立。若任务集中所有任务都满足上式,那么Γr在处理器PEr上运行可以满足实时性;否则,当前的任务不分配至当前的处理器中,并选取下一个任务重新进行模糊温度约束测试。
若任务满足实时性时,进行模糊温度约束下的温度可行性测检测。构造一个调度序列
对处理器r上第一个超周期[0,L]内的调度序列,其中st0=0,ed1=L;进行如下温度可行性检测,令:
B(edi-sti)=Bi=(b-a*cfi*v(r))
Kj=exp(-B(ed0-sto)-…-B(edj-stj);
K=exp(-B(ed0-sto)-…-B(ed1-st1)
0<K<1
T(L)≤Tmax(1-K)
且,在第一个超周期[0,L]内,存在区间[sti,edi]满足:
>
其中,>有T(edi)≥T(edj)。令>>
若不满足,当前的任务不分配至当前的处理器中,并选取下一个任务重新进行模糊温度约束测试。
若任务通过上述模糊温度约束测试,表示任务τi可以分配到PEr上,则更新系统待分配任务集Γ=Γ-τi;否则,更新处理器r上的任务集Γr=Γr-τi。检查当前所处理任务是否为最后一个任务,若是则结束模糊静态调度工作;否则,可选择下一个任务(i=i+1),并跳回步骤二中重新进行处理。
在本实施例中,对任务集Γ进行模糊温度约束下的静态调度:一开始,已分配给处理器PE1的任务集Γ1为空。接着,从下标最小的任务τ1到下标最大的任务τ29逐一进行实时检测以及温度检测。假设当前检测任务为τi。当实时约束检测结果为TRUE且温度检测结果也为TURE时,
分配所检测任务到处理器上。并更新Γ1=Γ1+τi。具体实施过程如下表6所示:
表6任务进行模糊温度约束下的静态调度结果表
步骤三:对处理器上的任务进行精确温度约束检测;若通过,则执行步骤四;否则,删除处理器中能耗贡献值Metric最小的任务并重新执行步骤三。
步骤四,若所有待分配的任务均已分配至处理器,则执行步骤五;若还存在待分配的任务未分配至处理器,判断当前分配任务的处理器是否为最后一个处理器;若不是,则选用下一个处理器并重新执行步骤二;否则,终止静态调度。
步骤五:保存静态调度的方案,并根据方案实施调度。调度结束时,若任务集Γ非空,那么宣布静态调度失败。否则,保存静态调度将产生满足实时性和温度约束的调度方案。
如图3所示,步骤三中先对已分配任务集Γr进性空闲时间分配(SLACK分配),然后检测任务集是否能通过精确温度检测条件;若无法通过,则移除Metric最小的任务,否则结束精确温度条件下的任务调度。
图4描述了本发明的Slack分配方法。本发明Slack分配方法的具体流程如下:先计算要构造的混合任务集的理想温度。然后从下标最低的任务开始,依次判断每一个任务是否是热任务,若是,那么依次计算任务的理想SALCK以及计算当前任务的最大可用slack长度,最终可以计算出任务的实际slack长度。若不是热任务,则不为该任务作SLACK分配。当前任务处理结束后,查看当前任务是否是最后一个任务。若不是,则继续选择下一个任务执行同上的slack分配流程,直到最后一个任务被处理完毕。SLACK方法的具体步骤为:
A.初始化工作:
令
B.计算理想的均衡温度,并计算每个任务的理想slack长度。
B.1计算任务的稳定温度Tss(i,γ),将Γr中的任务分为冷任务和热任务两类。
B.2计算理想的均衡温度Tideal:
>
根据RC模型可以求解对于混合任务ψi={τi,sli},τi=(ai,ci,pi),其稳定温度可以由如下式子表示:
>
B.3根据公式(10,11)可以求解ψi理想的slack长度的slideal,i.
>
C.若i>N,结束SLACK分配。否则进入D。
D.选取:ψi.若ψi是冷任务。那么,跳入H。否则,进入E。
E.计算ψi的最大可分配的slack长度sli,max。
E.1初始化:设定一个slack的下界,sllow=0;设定一个slack的上界,slhigh=Di-Rt′i;设置变量slmid=0;设定变量δ=slhigh-sllow
E.2检查δ≤0.1是否成立,若成立则结束搜索过程,跳至步骤E.7;否则进入下一步。
E.3计算:>
E.4设定混合任务ψi={τi,slmid}。
E.5使用公式(9)来验证混合任务集Ψ是否满足实时性。若满足,则置sllow=slmid;否则,置slhigh=slmid。
E.6置δ=slhigh-sllow。跳转至E.2
E.7置sli,max=slmid
在本实施例中,以ψi为例,它的最大空闲时间的求解方法如下:
ψ1=(τ1,sl1);τ1=(4000,20,20);eti=4.994,cf=0.97;
根据E.1可以设定sllow=0;slhigh=20-4.994=15.006;
根据E.2-E.6可以二分搜索检查最大可用空闲长度,搜索过程如下表7所示:
表7二分搜索检查最大可用空闲长度结果表
当δ=0.0586181时,跳出循环搜索过程。
根据E.7,sli,max=slmid=0.293091。
F.计算ψi实际可用的空闲时sli=MIN{sli,max,sli,ideal}。
G.更新混合任务ψi=(τi,sli)。
选取下一个任务i=i+1。跳转至C。
在本实施例中,经过模糊温度约束下的静态调度,PE1上分配的任务集为:
Γ1={γ1,γ2,γ3,γ4,γ5,γ6}={τ1,τ2,τ3,τ9,τ28,τ29}。
按照步骤A,构建混合任务Ψ1={ψ1,ψ2,ψ3,ψ4,ψ5,ψ6}。其中,ψ1=(γ1,0)=(τ1,0),ψ2=(γ卜,0)=(τ2,0),ψ3=(γ3,0)=(τ3,0),ψ4=(γ4,0)=(τ9,0),ψ5=(γ5,0)=(τ28,0),ψ6=(γ6,0)=(τ29,0)
按照步骤B,先将任务划分为冷热两类,划分结果如表8所示:
表8冷任务与热任务划分结果表
然后,求解理想稳定温度:Tideal=83.5091。
最后,对热任务进行slack分配,构造混合任务的结果如下表9所示:
表9构造后混合任务的结果表
经过SLACK分配后,应用精确温度检测条件对任务集Γr进行检测。
对处理器r上第一个超周期[0,L]内的调度序列,其中st0=0,ed1=L;进行如下温度可行性检测,令:
B(edi-sti)=Bi=(b-a*cfi*v(r))
Kj=exp(-B(ed0-sto)-…-B(edj-stj);
K=exp(--B(ed0-sto)-…-B(ed1-st1)
0<K<1
T(L)≤Tmax(1-K)
且,在第一个超周期[0,L]内,区间[sti,edi]满足:
>
根据检测结果,调整处理器的任务分配或者结束该处理器的分配工作。若未通过检测,那么从Γr中选择一个贡献值最小的任务τm移除,令Γr=Γr-τm,Γ=Γ+τm。然后转向重新执行步骤三,对Γr作精确温度约束下的静态调度工作。若通过检测,则结束PEr的任务分配工作,执行步骤四。
在本实施例中,所构建的任务集Ψ1的温度峰值为81.69。应用精确温度检测条件对任务集其进行检测。结果满足精确温度约束条件,则执行步骤四。步骤四中,还检查未分配的任务集Γ是否为空,对剩余任务进行处理。若Γ为空,则结束静态调度工作,执行步骤五。否则,检查是否当前处理器是否是最后一个处理器,若不是,则选择下一个处理器,并跳转至步骤二继续进行调度。
在本实施例中,经过前述四个步骤,已经完成了对处理器PE1的分配,得到该处理器的任务分配表如下表10所示,其中未分配的任务集Γ={τ4,τ5,τ6,τ7,τ8,τ10,τ11,…,τ26,τ29},未分配的任务集不为空。且当前分配任务的处理器是PE1,它不是最后一个处理器。于是重新执行步骤二,将剩余任务分配到PE2上。直至分配完所有处理器后时,若任务集Γ非空,那么宣布静态调度失败。否则,保存静态调度将产生满足实时性和温度约束的调度方案。
表10处理器上的任务分配表
本实施例中,经过静态调度,每个处理器产生一个任务集Γ1,Γ2,...,Γ6:如表11所示:
表11处理器及其任务集表
产生并保存的静态分配矩阵表MR×N如表12所示:
表12静态分配矩阵表
最终所需的总功耗为:>
通过本发明,可以有效的在静态分配任务阶段寻找到能耗比较低的任务分配方案。并且该调度方案可以确保任务在动态执行过程中,处理器的温度始终在安全的范围内。对同对比该实施例相比于基于单调速率先合适优先算法(rate monotonicfirst fit,RMFF)的分配方法可降低13%左右的能耗。
本发明的保护内容不局限于以上实施例。在不背离发明构思的精神和范围下,本领域技术人员能够想到的变化和优点都被包括在本发明中,并且以所附的权利要求书为保护范围。
机译: 一种构造固定装置以记录临床玻璃和水银温度计最高温度的方法。 (通过Google翻译进行机器翻译,没有法律约束力)
机译: 一种基于路径质量和连接优先级的QoS优先级的DNS响应重分配方法
机译: 一种基于用户身份的LTE MAC调度器的优先级和优先级方法