异构实时多处理器系统的动态调度算法研究

异构实时多处理器系统的动态调度算法研究 1, 2 2 1 1杨玉海, 宾雪莲, 余胜生, 周敬利 1( )华中科技大学 计算机学院, 湖北 武汉 430074 2( ) 空军雷达学院 指挥自动化系, 湖北 武汉 430019 E 2m a il: yyh andy@ yeah. ne t 摘 要: 实时多处理器系统的动态调度算法一直是实时系统中的重要研究课题. 根据异构实时多处理器的特点, 提出了一种新 的异构实时动态调度算法 . 该算法采用了一个新的处理器分配策略—— 将任务分配到能最早完成任务的处理器上. 该 P - I E F T 策略能够缩短调度长度, 提高后继任务被接受的可能性, 从而能够提高成功调度率. 模拟结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明, 该调度算法的成功调度率高 于近视算法和节约算法的成功调度率. 关 键 词: 异构多处理器; 实时系统; 动态调度 () 文 章 编 号: 100021220 20080120130205 中图分类号: 391 文献 标识 采样口标识规范化 下载危险废物标识 下载医疗器械外包装标识图下载科目一标识图大全免费下载产品包装标识下载 码: T P A - Study on D ynam ic Schedul in g A lgor ithm f or Rea lt im e He terogen eous M ult iproce ssor Sy stem s 1, 2 2 1 12, 2, 2, 2YA N G Yu h a iB IN X uelianYU Sh engsh engZHOU J ingli 1(), , 430074, S ch ool of C om p u ter S cienceH u az h ong U n iv ersity of S cience and T ech nology W u h an C h ina 2(), 430019, A irf orce A rm y R ad a r A cad em y W u h an C h ina : . A bstrac tE ff ic ien t app lica t io n sch edu ling is c r it ica l fo r ach iev ing h igh p e rfo rm ance in m u lt ip ro ce sso r sy stem sA new dynam ic . sch edu ling a lgo r ithm fo r th e h e te ro geneo u s m u lt ip ro ce sso r sy stem s is p ropo sedT h e a lgo r ithm u se s a new po licy th a t a ta sk . w h ich h ave th e m in im a l ea r lie st f in ish t im e w ill be a ssigned to th e p ro ce sso rT h e po licy is ab le to reduce sch edu le leng th so . , . th a t th e new ly a r r iv ing ta sk w ill h ave be t te r ch ance to be accep tedH enceit s succe ss ra t io w ill r iseS im u la t io n re su lt s show th a t th is a lgo r ithm o u tp e rfo rm s th e o th e r tw o a lgo r ithm s : ; 2; Key wordsh e te ro geneo u s m u lt ip ro ce sso r s sy stem srea lt im e sy stem sdynam ic sch edu ling ()P 和 s 个资源 s> = 1. 这些处理器具有不同的处理速度, 每 m 1 引 言 ( ) ( ) 一个处理器的速度用一个实数 = 1, , 来表示.S p e ii m 随着异构计算的兴起, 实时异构系统已被广泛应用在航 ( ) 处理器 的速度越慢, 越大. 在系统中, 另有一个处理 P i S p e i天控制、核反应堆控制、遥感检测等领域, 尤其是出于节省资 器作为专门的调度器, 所有任务都要先到达这个中心调度器, 金的目的, 将不同类型的计算机连接起来共同处理一个实时 然后被分配到系统中其它的处理器上去执行. 每个调度器都应用的工作站机群系统就更加普遍了. 然而, 大多数实时多处 ()有自己的一个调度队列 . 这样, 在它执行完 d isp a tch queue s1 25, 8212 理器系统的动态调度算法都是针对同构系统提出的, 当前任务后, 便从其调度队列中取出一个任务来执行, 调度器 6, 7 对 异构系统的动态调度算法研究的比较少. 在 2, 3 中考与各处理器之间的通信通过这些调度队列来实现. 同时, 调度 虑了任务的资源需求和处理器需求, 分别提出了实时多处理 器与各处理器并行地运行, 它对新到达的任务进行调度并周 器系统的近视算法和节约算法. 6, 7 分别对节约算法进行了 期性地对各调度队列进行修改. 任务队列中的任务按照启发 扩展, 使之能够用于异构多处理器系统和具有强实时和弱实 式函数值进行排序, 相同启发式函数值按截止期限的大小顺 时任务的多处理器系统. 8 对近视算法和节约算法进行了改 序排序. 进, 提出了分组适度算法. 本文针对异构实时多处理器系统, 2. 2 任务模型 对各种启发式方法进行研究, 并通过试验进行对比, 以得出一 在实时异构系统中, 由于处理器的速度不同, 一个任务在 个较好的异构多处理器系统的动态调度算法. 不同的处理器上有不同的运行时间, 在实时异构系统中的实 时任务具有以下特性:2 基本概念 () 1每一个任务 都是非周期的, 其到达时间为 , 就绪 T aT 时间为 , 最大运行时间 为 , 截 止 期 限 为 . 其 中, 为rT C T d TC T 2. 1 异构多处理器模型 )( 一个向量, 记为: , ,, . 表 示 任 务在 处 理 器cT cT cTcT T ( ) 假设一个实时异构系统有> 1个处理器 , ,, m m P 1 P 2 1 2 m j ( ) 收稿日期: 2006209218 基金项目: 国家自然科学基金项目 60073003资助. 作者简介: 杨玉海, 男, 1971 年生, 博士研究生, 讲师, 主要研 究方向为实时系统、网络技术、海量存储系统等; 宾雪莲, 女, 1974 年生, 博士, 讲师, 主要研究方向为实时系统, 专家系统; 余胜生, 男, 1944 年生, 教授, 博士生导师, 主要研究方向为多媒体技术, 网络技术等. 1 期杨玉海 等: 异构实时多处理器系统的动态调度算法研究131 ( ) ) = 1, , 上运行时的最大运行时间. 对处理器最早可用时间的影响, 其成功调度率比较低; P j j m c lo ck () 节约算法在选择处理器时, 选择能满足任务截止期限且最早 2任务之间是不可抢占的, 且相互独立. ( ) 3一个任务不能在同一时间在多个处理器上执行, 即 可用时间最小的处理器, 并没有考虑处理器之间速度的差异. 1一个任务不具有并行性. 因此异构多处理器系统动态调度算法需要进一步研究. 本节 () 将分析各种处理器选择策略, 通过实验验证这些处理器选择 4除了处理器以外, 任务可能还需要其它一些资源, 任 务对资源的访问方式为互斥或共享方式. 在本文中, 任务所需 策略的优劣, 进而提出一个新的异构多处理器调度算法. 资源都不包括处理器. 3. 1 处理器选择策略 2. 3 相关定义由于异构多处理器系统的处理器速度不同, 当任务在一 )(定义 1. 在一个调度中, 若某任务的时间约束和资源需求 个处理器上运行时, 其执行时间为 C T = c, c, , cT T T I , 1 I , 2 I , m 都可以满足, 则称该任务在这个调度中是可行的; 任务的可行 中的一个值. 从而导致任务在最早可用时间最小的处理器上 性是指任务在调度中是“可行的”的概率. 同时, 如果一个任务 执行时其完成时间可能大于在其它处理器上执行时的完成时 集合中的所有任务在调度中都是可行的, 则称该调度对于此 间. 因此对于异构系统选择最早可用时间最小的处理器不能 任务集合来说是一个可行调度. 保证调度长度最小, 不利于提高算法性能. 那么在异构系统 定义 2. 局部调度是指任务子集的一个可行调度. 若一个 中, 如何选择处理器才能使算法具有较高的性能呢? 处理器速 局部调度被任务集合中所剩的任何一个任务扩展后仍是可行 度以及处理器的使用率是否影响算法性能呢? 为了回答这些 调度, 则称该局部调度是强可行调度. 问题, 对于以下几种可能的处理器选择策略进行了研究. 定义 3. 可行性检查窗口: 在判断一个局部调度是否是一 () () 1在所有, = 1 的处理器中, 选择最早可用时 av a il T P 个强可行调度时, 不是检查任务队列中所剩的所有任务, 而只 间最小的处理器 P IES T 是检查在任务队列中的前个任务. 这前个任务称作可行性 k k () () 2在所有av a il T , P = 1 的处理器中, 选择最早完成时检查窗口. 间最小的处理器 P IE F Ts 定义 4. 为资源 在共享访问方式下的最早可用 EA T k R k () () 3在所有, = 1 的处理器中, 选择运行速度最 av a il T P e 时间; 为资源 在互斥访问方式下的最早可用时间;EA T k R k 快的处理器 P m inS p e () () E C P P 为处理器 P 的最早可用时间, E F T T , P 为任务 T() () 4在所有av a il T , P = 1 的处理器中, 选择运行速度最 () 在处理器 上的最早完成时间; 为任务的理想最早 P I E S T T 慢的处理器 P m ax S p e () 可运行时间; 为任务的理想最早完成时间.I E F T T () () 5在所有, = 1 的处理器中, 选择使用率最低 av a il T P ( ) ( ( ) = , , ,I E S T T M A X rT m inP ?P E , i= 1, , m E C P T P i 的处理器 P low es t iu )() () m axR ?R EA T k 6在所有av a il T , P = 1 的处理器中, 选择使用率最高k T 的处理器 P h ig hest( ) ( ) ( = {, , ,I E F T T M inP ?P E , i= 1, , m M ax rT E C P T P i iu 缩短调度长度, 就为后继到达的任务提供了较多的机会 ) + }EA T cT , i k 得到成功运行, 从而能提高成功调度率, 因此我们从调度长度 () 其中 表示一个处理器集合, , 表P E m inP ?P E , i= 1, , m E C P T P i iu . 上对以上处理器选择策略进行分析 示系统中处理器的最小最早可用时间; m axEA T 表示R ?R k k T 对于 处理器选择策略, 将任务分配到一个最早可用P I ES T 任务 所需资源的最早可用时间, 且当资源为共享方式时, T u 时间最小的处理器上执行, 不能保证其完成时间最小, 那么就 = , 当资源为互斥方式时, = .su e不能保证调度长度最小. 对于 处理器选择策略, 由于考 P IE F T () 定义5. , 表示任务在处理器上运行是否能 av a il T P T P ( 虑了任务在各个处理器的执行时间 实际上就是考虑了处理 () 满足截止期限, 若处理器能满足截止期限, 则, =P av a il T P ) 器处理速度的差异, 并且选择完成时间最小的处理器, 因而() 1; 否则, av a il T , P = 0. 能够缩短调度长度. 对于 处理器选择策略, 当所有处理 P m inS p e 器的最早可用时间都相同或者最快的处理器的最早可用时间 3 调度算法 小于其它处理器时, 选择运行速度最快的处理器一定能缩短 调度长度; 然而在实际运行过程中, 速度快的处理器, 其最早 来选择任在近视算法和节约算法中采用目标函数值 H ()可用时间可能大于其它处理器, 若不考虑任务在各个处理器 越小, 目标函数值越优. 近视务. H = d + W × I E S T T . H T 上的执行时间, 仍将任务分配到运行速度最快的处理器上执 算法将任务分配到最早可用时间最小的处理器上; 而在节约 行, 可能导致其在最快处理器上的完成时间要大于在其它处算法中, 首先求出哪些处理器能满足任务的截止期限, 然后利 () () () 理器上的完成时间, 也不能保证缩短调度长度. 对于 处 用 函数 = + 3 , 在这些处理器中选择P m ax S p e S p E C P P W S p e P () 理器选择策略, 在前文中已提到由于未考虑到墙上时钟时间, S p 最大的处理器, 并将任务分配到该处理器上. 我们在文 ( 章 8 中 指 出, 由 于 近 视 算 法 没 有 考 虑 到 墙 上 时 间 会浪费处理器的处理时间, 并且速度越慢的处理器越忙, 速度w a ll 1 这里的任务不具有并行性, 是指一个任务本身不能并行执行, 而任务之间在没有资源冲突的情况下, 是可以并行执行的. 1 期杨玉海 等: 异构实时多处理器系统的动态调度算法研究133 准. 中, P - I E F T 的成功调度率始终高于其它处理器选择策略, 4. 3 近视算法采用的 处理器选择策略其次, 节约算法采 处理器选择策略的性能比较 P - I E S T 4. 3. 1 处理器处理速度差异对成功调度率的影响用的 最差. 与近视算法采用的 相比, P - m ax S p e P - I E S T P - 图 1 反映了处理器速度差异对成功调度率的影响. 在模I E F T 的成功调度率大约提高了 15%. 拟中对, , , , 和分别取值 0. 5,4. 3. 3 资源利用率对成功调度率的影响U se- P S h a re- P K W R B ack num 0. 5, 5, 4, 0. 1 和 1. 由于 的成功调度率基本上都为 P - h ig h es t 图 3 反映了资源利用率对成功调度率的影响. 在模拟中 0, 没 有 画 出 在 图 1 中. 从 图 1 中 可 以 看 出 , 随 着 的 增 加 , 各对S h a reP , K , Α, R 和B ack num 分别取值 0. 5, 5, 1. 1, 0. 1 和Α - 1. 从图 3 中可以看出, 随着资源利用率的增加, 各种处理器选 择策略的成功调度率随之下降. 同时在资源利用率的变化过 图 1 处理器处理速度差异对成功调度率的影响 . 1 F igE ffec t o f p a ram e te r (= 0. 5, = 0. 5, = 5,U se- P S h a re- P K 图 3 资源利用率对成功调度率的影响 )= 0. 1, = 1,= 4R B ack num W . 3 F igE ffec t o f back num p a ram e te r 种处理器选择策略性能都有所增加. 同时在 的变化过程中,Α ()= 0. 5, = 0. 1, = 1. 1, = 5,= 4, = 1S h a re- P R Αk W B ack num 的成功调度率始终高于其它处理器选择策略, 近视 P - I E F T 程 中, 的 成 功 调 度 率 始 终 高 于 其 它 处 理 器 选 择 策P - I E F T 算法采用的 处理器选择策略其次, 节约算法采用的P - I E S T 略, 近视算法采用的 处理器选择策略其次, 节约算 P - I E S T 最差. 从图1 可以看出当> = 1. 2 时, 的 P - m ax S p e ΑP - I E F T 成 功调度率达到 100% ; 当 > = 1. 4 时, 的成功调 ΑP - m inS p e 法采用的最差. 与近视算法采用的相比, P - m ax S p e P - I E S T 度率接近 100% , 这是因为当 足够大时, 最快的处理器已能 Α的成功调度率大约提高了 15%.P - I E F T 够满足所有任务的运行; 当 > = 1. 4 时, 的性能也 ΑP - low es t 4. 3. 4 可行性检查窗口对成功调度率的影响大幅度提高. 而此时 的性能仍然很差. 即使 增加 P - m ax S p e Α图 4 反 映 了 可 行 性 检 查 窗 口 对 成 功 调 度 率 的 影 响. 在 到 1. 6 以上, 其成功调度率也才仅为 2. 5%. 模拟 中 对, , , 分 别 取 值 0. 5 ,和U se- P S h a re- P R ΑB ack num 4. 3. 2 回溯次数对成功调度率的影响0. 5, 0. 1, 1. 1 和 1. 由于 的成功调度率基本上都 P - h ig h es t 图 2 反映了回溯次数对成功调度率的影响. 在模拟中对为0, 没有画出在图4中. 从图4 中可以看出, 在可行性检查窗 U seP , S h a reP , K , Α和 R 分别取值 0. 5, 0. 5, 5, 1. 1 和 0. 1.- - 由 于的成功调度率基本上都为0 , 没有画出在图2P - h ig h es t 图 4 可行性检查窗口对成功调度率的影响 . 4 F igE ffec t o f k p a ram e te r 图 2 回溯次数对成功调度率的影响 (= 0. 5, = 0. 5, = 0. 1,U se- P S h a re- P R . 2 F igE ffec t o f back t rack num be r )= 1. 1,= 4, = 1ΑW B ack num ()= 0. 5, = 0. 5, = 0. 1, = 1. 1, = 5,= 4U se- P S h a re- P R Αk W 口 的变化过程中, 的性能始终要高于其它处理器k P - I E F T . 从图2 中可以看出, 随着回溯次数back num 的增加, 各种处 中选择策略. 同时在可行性检查窗口的变化过程中, P - I E F T 理器选择策略性能都有所增加. 同时在 的变化过程back num 的成功调度率始终高于其它处理器选择策略, 近视算法采用 134 小 型 微 型计算 机 系 统2008 年 4 M an im a ran T , M u r th y C S R. A n eff ic ien t dynam ic sch edu ling 的 P - I E S T 处 理 器 选 择 策 略 其 次, 节 约 算 法 采 用 的 P - 2[ . a lgo r ithm fo r m u lt ip ro ce sso r rea lt im e sy stem s J IE E E 最差. 与近视算法采用的 相比, 的 m ax S p e P - I E S T P - I E F T ( ) 1998, 9 3: T ran sac t io n s o n P a ra lle l and D ist r ibu ted Sy stem s, 成功调度率大约提高了 15%. 3122319. 4. 3. 5 任务的可延迟度对成功调度率的影响5 M it ta l A , M an im a ran G, M u r th y C S R. In tege ra ted dynam ic 图 5 反 映 了 任 务 的 可 延 迟 度 对 成 功 调 度 率 的 影 响. 在2sch edu ling o f h a rd and Q O S deg radab le rea lt im e ta sk s in m u lt i2 模 拟 中 对U seP , S h a reP , K , Α和B ack num 分 别 取 值 0. 5 ,- - [. : 5 p ro ce sso r sy stem s C InP ro ceed ing s o f th e th In te rna t io na l 0. 5, 5, 1. 1 和 1. 由于 的成功调度率基本上都为 0, P - h ig h es t 2,Co nfe rence o n R ea lt im e Com p u t ing Sy stem s and A pp lica t io n s 没有画出在图 5 中. 从图 5 可以看出, 在任务可延迟度的变化 , ; , 1998: 1622172. L o s A lam ito sCA IE E E p re ss过程中, 的性能始终要高于其它处理器选择策略, P - I E F T W ang Kun , Q iao Y ing, W ang H o ng2an, e t a l. S tudy o f a dy2 6 近视算法采用的 处理器选择策略其次, 节约算法采 P - I E S T 2nam ic sch edu ling a lgo r ithm fo r rea lt im e h e te ro geneo u s sy stem s 用的 最差. 与近视算法采用的 处理器选 P - m ax S p e P - I E S T [. , 2002, 39J Jo u rna l o f Com p u te r R e sea rch and D eve lopm en t 择策略相比, 的成功调度率大约提高了 15%.P - I E F T ( ) 6: 7252731. , , , . Q iao Y ingZo u B ingF ang T inge t a lD e sign and eva lua t io n 7 o f an a lgo r ithm fo r in teg ra ted dynam ic sch edu ling in rea l2t im e ( ) [ . , 2002, 13 12:h e te ro geneo u s sy stem sJ Jo u rna l o f So f tw a re 225122258. 222, , . B in X uelian Yang Yu h a iJ in Sh iyaoA new dynam ic 8 2sch edu ling a lgo r ithm fo r rea lt im e m u lt ip ro ce sso r sy stem s ba sed o n g ro up ing and p rop e r ly choo sing po lic ie s [ J . Jo u rna l o f ( ) , 2006, 29 1: 81291.Com p u te r B in X ue2lian, Yang Yu 2h a i, J in Sh i2yao. A n a ssignm en t a lgo 2 9 图 5 任务可延迟度对成功调度率的影响 [ . r ithm o f sta t ic p r io r ith fo r lim ited p r io r ity leve ls J Jo u rna l o f ( ) , 2004, 15 6: 8152822.So f tw a re . 5 F igE ffec t o f R p a ram e te r B in X ue2lian, J in Sh i2yao , Yang Yu 2h a i. U neven ly d ist r ibu ted (= 0. 5, = 0. 5, = 5,10 U se- P S h a re- P K 2[ . b lue ta sk s a lgo r ithm s ba sed o n sk ip o ve r m o de l J Jo u rna l o f )= 1. 1, = 1,= 4ΑB ack num W ( ) , 2003, 40 10 : 15292Com p u te r R e sea rch and D eve lopm en t 通过实验结果可以看出, 采用 P - I E F T 处理器选择策略 1534. 的算法性能最优, 采用 处理器选择策略的近视算法 2222, , . P - I E S T B in X uelianYang Yu h a iJ in Sh iyaoT h e be stca se re2 11 [ . spo n se t im e ana ly sis o f ED F p reem p t ive sch edu led ta sk s J 性能其次, 采用 的节约算法的性能最差.P - m ax S p e ( ) , 2004, 31 9: 1142116Com p u te r Sc ience 5 结 论 222, , . B in X uelianYang Yu h a iJ in Sh iyaoSch edu ling ana ly sis o f12 () , [ . , 2006, 33 ta sk s w ith m k gua ran tee s J Com p u te r Sc ience目前, 对于异构实时多处理器系统调度算法研究的较少. ( ) 1: 1812183. 如何切实提高异构、实时环境下多处理器调度的性能成为一 个迫切的问题. 本文提出了各种可能的处理器选择策略, 采用 附中文参考文献: 3 乔 颖, 王宏安, 戴国忠. 一种新的实时多处理器系统的动态调 调度长度分析了各种处理器选择策略的优劣, 指出将任务分 ( ) 度算法[J . 软件学报, 2002, 13 1: 51258. 配到最早完成时间最小的处理器上的策略是最优的处理器选 6 王 , 乔 颖, 王宏安, 等. 实时异构系统的动态调度算法研究 择策略, 并基于该策略提出一个新的调度算法 , 分析 P - I E F T [.( ) J 计算机研究与发展, 2002, 39 6: 7252731.了其时间复杂度. 最后通过实验验证了 算法性能较P - I E F T 7 颖, 邹 冰, 方 亭, 等. 一种实时异构系统的集成动态调度乔高. ( ) 算法[. 软件学报, 2002, 13 12: 225122258. J 8 宾雪莲, 杨玉海, 金士尧. 一种基于分组与适当选取策略的多处 Ref eren ce s: ( ) 理器动态调度算法[ . 计算机学报, 2006, 29 1: 81291.J 1 Zh ao W , R am am r ith am K , S tanko v ic J A. Sch edu ling ta sk s 9 2宾雪莲, 杨玉海, 金士尧. 基于有限优先级的静态优先级分配算[. w ith re so u rce requ irem en t s in h a rd rea lt im e sy stem s J IE E E ( ) ( ) 法[ . 软件学报, 2004, 15 6: 8152822., 1987, 13 5: 5642577.J T ran sac t io n s o n So f tw a re E ng inee r ing 10 , . 宾雪莲, 金士尧, 杨玉海. 基于跳跃因子模型的不规则分布蓝色R am am r ith am K S tanko v ic A JE ff ic ien t sch edu ling a lgo 2 2 ( ) 2任务法[J . 计算机研究与发展, 2003, 40 10: 152921534. [. r ithm s fo r rea lt im e m u lt ip ro ce sso r sy stem s J IE E E T ran sac2 11 ( ) 2194., 1990, 1 2: 184宾雪莲, 杨玉海, 金士尧. 基于 ED F 抢占式调度的周期任务最小 t io n s o n P a ra lle l and D ist r ibu ted Sy stem s ( ) 响应时间分析[., 22计算机科学, 2004, 31 9: 1142116. , . J Q iao Y ingW ang H o ngan D a i Guo zho ngD eve lop ing a new 3 () 212 宾 雪 莲, 杨 玉 海, 金 士 尧. 基 于 , 模 型 的 任 务 可 调 度 分 析 dynam ic sch edu ling a lgo r ithm fo r rea lt im e m u litp ro ce sso r sy s2 m k ( ) ( ) 258.[. , 2002, 13 1: 51[. 计算机科学, 2006, 33 1: 1812183.tem s J Jo u rna l o f So f tw a re J