积分商城

最新搜索： iar hs2241p cserialport 无人机 N76E616 goldwave注册机
您现在的位置是：首页 > 技术资料 > 嵌入式多核系统中三维立体调度模型的研究
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

嵌入式多核系统中三维立体调度模型的研究

更新时间：2019-12-30 20:24:39 大小：2M 上传用户：IC老兵查看TA发布的资源 标签：嵌入式多核系统 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

针对嵌入式多核平台下分区调度算法不能满足系统高效的需求,提出一种三维立体调度模型,该模型根据任务各项参数将任务划分为可调和任务和不可调和任务,并将其执行区域用面积表示,根据区域的特征分为执行区域、干扰区以及空闲区。利用干扰区的特征将不同性质的任务分派到不同的处理器核上运行。实验表明,该方法无论在提高系统利用率还是在吞吐量方面都优于PEDF。


部分文件列表

文件名 大小
1577708673嵌入式多核系统中三维立体调度模型的研究.pdf 2M

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
2018  
10  
Oct． 2018  
Vol．36 No．5  
年
月
西 北 工 业 大 学 学 报  
Journal of Northwestern Polytechnical University  
36  
5
期
第
卷第  
嵌入式多核系统中三维立体调度模型的研究  
1
2
1
1
， ， ，  
黄姝娟 朱怡安 刘白林 肖锋  
( 1．  
，
西安工业大学 计算机科学与工程学院 陕西 西安  
710021; 2．  
，
西北工业大学 计算机学院 陕西 西安  
710072)  
: ，  
要 针对嵌入式多核平台下分区调度算法不能满足系统高效的需求 提出一种三维立体调度模  
摘
， ，  
型 该模型根据任务各项参数将任务划分为可调和任务和不可调和任务 并将其执行区域用面积表  
， 、 。  
示 根据区域的特征分为执行区域 干扰区以及空闲区 利用干扰区的特征将不同性质的任务分派到  
。 ，  
不同的处理器核上运行 实验表明 该方法无论在提高系统利用率还是在吞吐量方面都优于  
PEDF。  
: ; ; ; ;  
词 嵌入式系统 多核 调度算法 调度模型 实时任务  
关
键
: TP302  
: A  
: 1000-2758( 2018) 05-1020-06  
文章编号  
中图分类号  
文献标志码  
， ，  
嵌入式多核平台下 任务调度是系统的核心 如  
。
数量  
， ，  
何优化调度算法 充分发挥多核处理器性能优势 是  
［1-3］  
。
当今研究的主要方向  
当前多核实时任务的调  
1
三维调度模型  
( global scheduling al-  
度算法主要分为全局调度算法  
［4-6］  
gorithm)  
( partitioned scheduling  
和分区调度算法  
1．1  
实时周期任务模型  
［7-8］  
algorithm)  
2
。GEDF( global earliest deadline  
大类  
n
假设一个包含 个实时周期任务的嵌入式多核  
［9］  
first )  
PEDF ( partitioned earliest deadline  
和
=
I
{ T ，T ，T …T } ，  
0 1 2 n  
T
为一个四元组  
i
系统  
其中  
［10］  
first)  
， 2  
是
。
类调度算法的典型代表 对于全局调  
T ( R ，C ，D ，P ) ，R  
i i i i i  
，C  
表示该任务首次发布时刻  
i
i
， ，  
度算法来说 如果一个任务不允许抢占 而另外一个  
WCET( worst case execution time) ，D  
表示该任务的  
i
，
任务必须执行 那么就要将该任务迁移到其他核上  
D
C ，P  
表示该任务的执行周期  
i
表示相对时限且  
≥
i
i
［11］  
。
。
这种迁移开销比较大 对于分区调度算  
执行  
P
D
C 。 Job ( r ，c ，d )  
用
i，j i，j  
T
表示 的第  
i
j
且
≥
≥
i
i
i
i，j  
i，j  
，
法而言 划分在一个范围内的任务只能在同一个处  
=
+
－
，
次执行 其中  
r
job r  
的发布时间  
i，j  
R
( j  
job  
为 的绝  
为
i，j  
i，j  
i，j  
i，j  
i，j  
i
［12］  
， ，  
理器核上调度 虽避免了迁移 简化了问题  
，
但对  
=
1) P ，c  
i
job  
c
C ，d  
i
为
的执行时间  
i，j  
i，j  
i，j  
，
划分的精确度有很高要求 划分不好会直接影响丢  
=
+
=
+
－ +  
( j 1) P D 。  
i
d
r
D
R
对时限  
1．2  
i，j  
i
i
i
。
失时限的任务数量 很多情况下任务划分方法是很  
三维调度模型  
。 ，  
棘手的问题 为此 研究者提出了半分区调度算法  
1
T ( R ，C ，D ，  
对于一个实时周期任务  
i
定义  
i
i
i
［13］  
( semi-partitioned scheduling algorithm)  
，
该方法将  
=
P ) ，  
如果  
i
C
D
;
则称该任务为不可调和任务 如果  
i
i
，
全局调度算法与分区调度算法相结合 旨在减少迁  
C ＜ D ， ; job  
则称该任务为可调和任务 对应的 称为  
i
i
，
移开销的同时减少进行划分的任务数量 降低划分  
job。  
可调和  
。 ，  
难度 尽管如此 该类算法仍然存在迁移开销和划  
2
T ( R ，C ，D ，  
i i i i  
定义  
对于一个可调和任务  
。 ，  
分方法如何精确的问题 为此 本文提出一种三维  
P ) ，  
若 用  
i
hf  
( harmonic  
表 示 该 任 务 的 调 和 因 子  
i
，
立体调度模型和调度算法 该方法以区域面积作为  
=
－
C 。  
i
factor) ， hf  
则
D
T
则 的任何一个  
i
job  
都会  
i，j  
i
i
， ，  
划分方法 降低划分的难度 提高划分算法的精确  
+
=
+
+
+
c k］|  
i，j  
hf  
1
HF  
个调和区间  
{ ［r  
k，r  
有
i
i，j  
i，j  
i，j  
， ，  
度 在提高系统效率的同时 降低丢失时限的任务  
: 2017-09-09  
: ( 61572392) 、  
基金项目 国家自然科学基金 新型网络与检测控制国家地方联合工程实验室基金  
收稿日期  
( GSYSJ2017004) 、  
陕西省工业科技攻关项目  
( 2015GY031)  
( MJ-2015-D-066)  
与民用飞机专项科研项目 资助  
:
作者简介 黄姝娟  
( 1975—) ， ， 、 ， 。  
女 西安工业大学讲师 博士 主要从事嵌入式与分布式计算及物联网研究  
5
， :  
黄姝娟 等 嵌入式多核系统中三维立体调度模型的研究  
第
期
·1021·  
Λ
=
k
0，1，2，…，hf } 。  
i
=
对应的每个调和区间衍生出来  
S /S 。  
i，j  
的干扰因子为 ξ  
v，w/i，j  
job  
job， job ( r ，c ，d ) ，  
记为 其  
i，j，k  
的
中
d
称为衍生  
6
2 job，  
对于任何 个具有干扰区的 如果  
定义  
至少有一个是可调和  
job l-job  
i，j，k  
i，j，k  
i，j，k  
=
+
=
k，( k 0，1，2…hf ) ，c  
i
=
=
C ，  
i
，r  
i，j，k  
r
c
job，  
且其衍生出来的任意一个  
i，j  
i，j，k  
i，j  
=
d 。  
i，j  
job  
［R ，  
在区间  
i
而对于可以被抢占性的  
job  
或
或者是  
其任意一个衍生  
干扰 区 为 可 调 和 干扰 区 否 则 称 为 不 可 调 和 干  
中存在执行区域与另外一个  
i，j，k  
=
D ］  
i
l
D
job ( r ，c  
个
i，j，k  
，
－
之间可以衍生出来  
job  
l
job  
，
相互独立 则称这  
或者是  
i
i，j，k  
i，j，k  
=
+
=
k，( k 0，1，2…d  
－
1) ，  
d
)
，r  
r
其中  
，
i，j，k  
i，j，k  
i，j  
i，j  
l
。
扰区  
=
c
=
=
d 。  
i，j  
c
C ，d  
i
l job  
那么把这 个 整体  
∑
i，j，k  
i，j  
i，j，k  
=
7
k
t ，  
重干扰区 如果在某段时间 内 存  
k
1
定义  
job  
个
l-job。  
称为衍生  
k
在
的执行区都覆盖了同一干扰区且该干扰  
=
{ T ，T ，  
1
3
I
对于任意实时调度系统  
定义  
0
job  
，
都不可调和 那么称该干扰区  
区对于任何一个  
=
T …T } ，  
2 n  
{ x，y，z} ，  
必然存在一个三维调度空间 Ω  
k
。
重干扰区  
为
x ，y  
其中 表示时间轴 表示当前运行在该平面的任务  
=
z
平面上存在某个区域既  
8
Z
定义  
如果在  
i
，z  
。
表示处理器核数 对于任何一个实时周期任务  
数
，
不是执行区也不是干扰区 则该区域称为闲置区  
。
T
job ，  
该调度空间上必然会存在  
i，j  
的任何一次执行  
i
=
{ x，y，z}  
9
定义  
给定一个三维空间 Ω  
在某  
z
和 分别为三维空间在该时  
job  
， 4  
执行的一个矩形区域 Φ 该区域的 个顶点  
i，j  
该
t ，  
段时间 内 假设  
x ，y  
t
t
t
+
A ( r ，0，z ) ，B ( r  
i，j i，j i，j  
c ，0，  
i，j  
坐 标 分 别 为  
i，j i，j  
3 ，  
间段内 个坐标轴所能取到的最大值 则在任意的  
+
z ) C ( r ，y ，z ) ，D ( r  
i，j i，j i，j i，j i，j  
c ，y ，z )  
i，j i，j i，j  
z
其中  
表
i，j i，j  
i，j  
=
=
z ( i 1，2，…t)  
i
Z
，
的平面内 所有单位面积之和称  
job  
，y  
z
示给  
分配的处理器号  
表示在第  
平面上  
i，j  
=
x * y 。  
t
i，j  
i，j  
，
为可调度空间面积 记为  
S
t
;
所分配的任务的个数 把该矩形区域 Φ 称为  
i，j  
job  
i，j  
1．3  
可调度性证明  
，
对应在该三维调度空间 Ω 上的执行区域 简单记为  
，
由上述定义可知 调度空间面积为执行区面积  
=
+
c ，y ，z ) } 。  
i，j  
{ ( r ，r  
Φ
i，j  
=
i，j i，j  
i，j i，j  
。
和闲置区面积之和 对于  
Z
z
，
的平面 任何一个区  
i
对应于该矩形 Φ 区域上的面积称为执行区域  
i，j  
、 ，  
域无非为干扰区 执行区和闲置区三者之一 其中干  
=
S
c * y  
i，j  
1 。  
如图 所示  
面积即  
i，j  
i，j  
。
扰区必定是执行区  
1
I
如果系统 中所有任务之间在任何时  
推论  
，
间段不产生不可调和干扰区 则该系统中所有任务  
。
可以被调度在同一个处理器上  
:
，
证 如果在任何时间段内不产生干扰区 就说明  
所有任务都有自己的执行区且执行区并不被相互覆  
job  
，
盖 那么所有任务在任何时间段内产生的  
都能  
1
Job ( r ，c ，d )  
的执行区域  
i，j i，j i，j i，j  
图
。
在时限之前被调度完成 故可以被分配到同一个处  
。
理器上  
4
Z 2 job  
对于在同一 平面上任何 个 和  
i，j  
定义  
如果在任何时间段内产生的干扰区都是可调和  
job  
，
如果它们的执行区域面积没有任何交叉覆盖  
，
干扰区 就说明所有任务都有自己的执行区且执行  
v，w  
，
情况 则称  
job  
job  
。
相互独立 如果在某段时间  
v，w  
和
job  
l-job  
区通过调和区间衍生  
或者  
调和后并不被相  
job  
都能在时限之前被调度完成 故可以被分配到同一  
i，j  
t
，2  
T
T
和 在该时间段内所有需要执行的  
j
内
个任务  
，
互覆盖 那么所有任务在任何时间段内产生的  
i
job  
， 2 t  
都相互独立 则称这 个任务在时间段 内相互  
。
。 t  
独立 如果 为无穷大都能满足 则  
， T  
T
和 称为永  
j
。
个处理器上  
i
。
久相互独立任务  
2
t ， I k  
若在某段时间 内 系统 产生 重干  
推论  
5
2
job  
job  
和
定义  
job  
面积存在交叉覆盖情况 则称这 个  
对于任何 个  
的执行区域  
， k  
扰区 则在该时间段内必须有 个处理器核才能完  
i，j  
v，w  
，
2
具有互干扰  
。
成调度  
。
。
交叉覆盖的区域称为干扰区 相对应的干扰区  
性
: k ， k job  
证 因为产生了 重干扰区 说明有 个 的执  
Λ
S
，
为交叉覆盖面积 相对应的  
job  
job  
对
面积  
的
v，w  
，
行区域都覆盖在同一区域 且没有任何可调和空间  
，
i，j  
Λ
=
S /S  
job  
job  
对
干扰因子为 ξ  
而相对应的  
k ，  
若采用小于 个处理器核来调度 则必然还会产生  
i，j/v，w  
v，w  
v，w  
i，j  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号