论文部分内容阅读
实时异构系统已被广泛应用在航空航天、工业控制、电讯行业、图像处理以及Internet应用等诸多领域。在这些应用中,存在大量的硬、软实时任务共存的情况,对实时异构系统的集成动态调度模型与算法的研究具有重大理论和实际意义。本文对实时异构系统的集成动态调度问题进行了深入的研究,提出了一种实时异构系统的集成动态调度模型,基于这种模型,提出批优化的调度策略和批任务在处理器上运行的目标函数构造原则。在此基础上,提出了一种基于分批优化的实时异构系统的集成动态调度算法——GOIDSH算法。本文针对实时异构多任务调度的特点,采用集中式调度模型;提出软、硬实时任务形式化描述非精确计算的统一任务模型,清晰地描述实时任务的特点。系统任务描述简单,节省存储空间,为实现基于批优化的集成动态调度打下基础。论文提出了一种新的实时异构系统的集成动态调度算法——基于分批优化的集成动态调度算法(GOIDSH算法)。该算法以启发式搜索为基础,主要包括任务分批、构造目标函数和基于批优化的调度策略三大部分,采用统一形式完成了实时异构系统的集成动态调度。同时,在构造目标函数时,算法还引入软实时任务服务质量(Ouality of Service,Qos)降级策略来提高调度成功率。GOIDSH算法的核心思想是:在每次扩充当前局部调度时,首先按一定规则在待调度的任务集中选取一批任务组成任务子集,保证所选取的任务子集中某一任务对某个资源有访问需求时,子集中的其它任务不能对该资源有访问需求。然后,综合各种因素,对该批任务中的每项任务在每个处理器上的运行构造目标函数,将问题转化为非平衡指派问题,利用非平衡指派问题直接解法对任务进行优化分配,一次性为这些任务分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,增大未被调度任务的被成功调度的可行性。论文通过仿真和模拟,从调度成功率、软实时任务的降级比率(DR)和被降级软实时任务的服务质量(QoS)三个方面,验证了GOIDSH算法的有效性及其调度性能。在仿真实验时,提出了一种按如下顺序设定的价值最高最优先的任务队列排序原则:①任务的截止期越近,其价值越高;②任务需要访问的资源越多,其价值越高;③任务要需访问的资源中,互斥方式的访问越多,其价值越高;④任务的空闲时间越短,其价值越高;⑤相同情形下,硬实时任务的价值高于软实时任务的价值。仿真实验结果表明,基于分批优化的实时异构系统集成动态调度算法(GOIDSH算法)不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题,而且还有效地提高了调度成功率,确保了软实时任务具有良好的服务质量,与其它相关算法,如传统的近视算法和节约算法相比较,具有明显优势。