一种实时异构系统的集成动态调度算法

《一种实时异构系统的集成动态调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1000-9825/2002/13(12)2251-08©2002JournalofSoftware软件学报Vol.13,No.12∗一种实时异构系统的集成动态调度算法乔颖,邹冰,方亭,王宏安,戴国忠(中国科学院软件研究所人机交互与智能信息处理实验室,北京100080)E-mail:lisa_qiao@sina.comhttp://iel.iscas.ac.cn摘要:提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(qualityofservice)

2、降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.关键词:异构系统;硬实时;软实时;动态调度;调度成功率;启发式搜索;回溯中图法分类号:TP393文献标识码:A随着实时应用范围的加大和复杂度的提高,实时系统中的非周期任务往往具有从硬截止期到软截止期范

3、[1]围的多种时间约束,因此,集成调度算法显得十分重要.另一方面,随着近几年来异构计算的兴起,实时异构系统也被广泛应用在航空航天、工业控制、电信行业、图像处理以及Internet等诸多领域.然而,目前所提出的算法却都是用来解决实时同构系统的集成动态调度问题的.例如,文献[2]提出的算法利用了多媒体服务器的方法,并引入QoS降级机制,解决了实时多处理系统中多媒体任务和硬实时任务的集成动态调度.文献[3]的算法通过降级软实时任务的结果质量,提高了整体的可调度性.本文对实时异构系统硬、软实时任务的集成动态调度

4、进行了研究,提出了一种新的实时异构系统的集成动态调度算法.1系统模型1.1调度器模型假设实时异构系统有m个处理器(m>1),且这些处理器具有不同的处理速度.调度器采用的是集中式的结构,系统中有一个处理器作为专门的调度器,所有任务都要先到达这个中心调度器,然后被分配到系统中其他的处理器去执行.每个处理器都有自己的一个调度队列,这样,在它执行完当前任务以后,就从其调度队列中取出一个任务来执行.调度器与各处理器之间的通信通过这些调度队列来实现.同时,调度器与各处理器并行地运行,它对新到达的任务进行调度,并周期

5、性地对调度队列进行修改.1.2实时异构系统的统一任务模型[4]非精确计算是一个通过妥协结果质量满足任务截止期,并以此来提供调度灵活性的典型模型.该模型尽∗收稿日期:2001-03-09;修改日期:2001-12-05基金项目:国家自然科学基金资助项目(69896250;79931000)作者简介:乔颖(1973－),女,北京人,博士,主要研究领域为数据库技术,信息系统;邹冰(1973－),女,浙江温州人,硕士生,主要研究领域为实时智能,CSCW;方亭(1978－),女,浙江人,硕士生,主要研究领域为实时

6、智能,GIS;王宏安(1963－),男,安徽和县人,博士,研究员,主要研究领域为实时智能,多通道用户界面;戴国忠(1944－),男,江苏无锡人,研究员,博士生导师,主要研究领域为多通道用户界面,实时智能,CIMS.2252JournalofSoftware软件学报2002,13(12)量避免截止期错过现象的发生,并在系统无法及时产生准确结果的时候,通过向用户提供具有可接受质量的近似结果来进行优雅的降级.由于软实时任务的截止期即使被错过也不会引起十分严重的后果,因此,允许其在截止期之前只被部分地完成.于是

7、,我们便可以利用非精确计算模型来构造实时异构系统的统一任务模型.在这个任务模型中,每一个软实时任务都有多个逻辑版本.同一任务的不同逻辑版本具有不同的运行时间.同时,任务的每一个逻辑版本都代表了任务的一个服务等级.注意到实时异构系统中处理器间的速度差异,我们可以对统一任务模型进行如下描述:定义1.Sta(T)表示任务T的可开始时间.定义2.Attri(T)表示任务T的属性.1,若任务T为硬实时任务Attri(.T)=0,若任务T为软实时任务设系统中有m个处理器(m>1),记为p1,p2,…,pm.Γ

8、表示任务集.于是,实时异构系统硬、软实时任务的统一任务模型可以表示为如下形式:(1)∀T,T∈Γ,均可表示成一个多元组θT,且θ=(a,r,D,v,ET).TTTTTTaT:任务T的到达时间,aT≥0.rT:任务T就绪时间,rT≥0,且rT≥aT.DT:任务T的截止期,DT≥0.vT:任务T所具有的不同逻辑版本的数目,同时也表示了任务T的服务等级数,=1,Attri(T)=1vT,>1,Attri(T)=0ETT:任务T的运行时间.对