优先约束的混合实时任务动态调度算法  

Dynamic scheduling algorithm for hybrid real-time tasks with precedence constraints

作　　者：殷进勇 顾国昌[1] 赵靖[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《计算机集成制造系统》2010年第2期411-416,422,共7页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(60873036)~~

摘　　要：为了对较大规模问题在短时间内给出满意的解并调度随机到达的非周期任务,提出了一种动态混合调度算法。在第一个截止期限错失时刻,通过分析系统的运行情况,推导出具有优先约束的实时任务可调度的充分条件。在系统运行前,判定周期任务的可调度性,预分配足够的处理机。当非周期任务到达系统时,在保证周期任务可调度的前提下重新给周期任务和非周期任务分配处理机。该算法具有多项式时间复杂性,适合解决较大规模的多处理机调度问题。实验结果表明,该算法有效提高了处理机的利用率和非周期任务的接收率。To get satisfied solution for larger-scale problem in short time,and to schedule stochastically arriving aperiodic tasks,a dynamic hybrid scheduling algorithm was proposed. The sufficient conditions for schedulable real-time tasks with precedence constraints were derived from analyzing system operation conditions when the first deadline was missed. Before the system operations,schedulability of periodic tasks was testified to allocate enough processors. When an aperiodic task arrived at the system,the algorithm reallocated processors to periodic and aperiodic tasks dynamically without violating the periodic tasks＇ schedulability. This algorithm had polynomial time complexity and was suitable for dealing with large-scale multiprocessor scheduling problems. Experimental results demonstrated that the processor＇s utilization rate and the aperiodic tasks＇ acception rate were both increased.

关 键 词：多处理机调度 算法 实时任务 优先约束 混合任务 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]