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

Abstract: 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.

Key words: multiprocessor scheduling, algorithm, real-time tasks, precedence constraints, hybrid tasks