资源描述：
《一种新的实时多处理器系统的动态调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2002/13(01)0051-08©2002JournalofSoftware软件学报Vol.13,No.1一种新的实时多处理器系统的动态调度算法Ã乔颖,王宏安,戴国忠(中国科学院软件研究所人机交互技术与智能信息处理实验室,北京100080)E-mail:qiaoyingbj@hotmail.comhttp://iel.iscas.ac.cn摘要:实时多处理器系统的动态调度算法一直是实时系统研究中的重要课题,而评价实时调度算法性能的一个最重要的指标是调度成功率.在近视算法的基础上提出了一种新的实时多处理器系统的动态调度算法——节约算法.
2、在该算法中,提出了一个新的处理器选择策略,从而提高了算法的调度成功率.同时,为了研究节约算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与近视算法的调度成功率进行了比较.模拟结果显示,节约算法的调度成功率要优于近视算法.关键词:多处理器;实时系统;动态调度;调度成功率;回溯中图法分类号:TP301文献标识码:A随着实时应用的日趋复杂,多处理器系统由于其高性能及可靠性,逐渐成为处理这种复杂应用的有效计算手段.目前,实时多处理器系统已被广泛应用于航天控制、核反应堆控制等领域,而实时多处理器系统的动态调[1]度算法则成为一个重
3、要的研究课题.然而,Mok等人指出,对于实时多处理器的调度,并不存在最优算法.这一结论导致了我们需要使用启发式搜索来解决这类调度问题.[2]目前,已有多种使用启发式搜索的实时多处理器系统的动态调度算法.KrithiRamamritham等人提出了针对动态实时多处理器调度的近视算法.它在传统的基于启发式搜索的基础上,限定了在一次调度中被考虑的任务数,从而降低了算法的复杂度.同时,该算法首次考虑了任务除了处理器以外还需其他资源的情况.在近视算[3]法的基础上,G.Manimaran等人又提出了一种新的动态实时多处理器系统的调度算法.它利用了任务的并行性[4]来提
4、高调度算法的性能.AnitaMittal等人提出的实时多处理器系统中的集成动态调度算法也是基于近视算[2~4]法的.它是针对在实时多处理器系统中硬实时与软实时任务并存的情况而提出的.但是,在以上这些算法中,当选择了某一任务来扩充当前局部调度时,要为该任务分配一个处理器来运行,而这些算法所采用的选择方法是,在可满足该任务截止期的处理器中,选择一个最早可运行的.这种处理器的选择方法将延迟未被调度任务的可开始运行时间,从而可能会造成对这些任务调度的失败.这便阻碍了算法调度成功率的提高.同时,若系统中的任务均不具备并行性,或者系统中的任务均为硬实时任务,则文献[3,
5、4]中的调度算法就不适用了.为了解决上述问题,本文在近视算法的基础上,提出了一种新的实时多处理器的动态调度算法——节约算法.该算法引入了一个新的处理器选择策略.这一策略提高了调度成功率.本文第1节对节约算法所涉及的概念进行了定义.第2节是算法描述,并进行了算法举例及分析.第3节是对算法性能的模拟研究.第4节是结论.Ã收稿日期:2000-04-12;修改日期:2000-07-19基金项目:国家自然科学基金资助项目(69896250;79931000)作者简介:乔颖(1973－),女,北京人,博士,主要研究领域为实时系统;王宏安(1963－),男,安徽和县人,博
6、士,副研究员,主要研究领域为实时智能,用户界面;戴国忠(1944－),男,江苏无锡人,研究员,博士生导师,主要研究领域为用户界面,计算机图形学,实时智能.52JournalofSoftware软件学报2002,13(1)1基本概念1.1任务模型我们假设一个实时多处理器系统有m个处理器(m>1),且这些处理器是同构的.该系统中的实时任务具有以下特性:(1)每一个任务T都是非周期性的,其到达时间为aT,就绪时间为rT,最坏运行时间为cT,截止期为dT.(2)任务是不可抢占的,且相互间是独立的.(3)任务不具有并行性.(4)除了处理器以外,任务可能还需要其他一些资
7、源,如变量及缓冲区等.同时,每个任务对资源的访问方式有两种:互斥访问和共享访问.1.2调度器模型在这个调度算法中,我们采用集中式调度.在这种调度方案中,有一个处理器作为专门的调度器,所有任务都要先到达这个中心调度器,然后被分配到系统中其他的处理器去执行.每个处理器都有自己的一个调度队列(dispatchqueues),这样,在它执行完当前任务之后,就从其调度队列中取出一个任务来执行.调度器与各处理器之间的通信通过这些调度队列来实现.同时,调度器与各处理器并行地运行,它对新到达的任务进行调度,并周[3]期性地对调度队列进行修改.1.3相关定义定义1.在一个调度
8、中,若某任务的时间约束和资源需求都可以满足,则称该任
