Two-level Hierarchical Scheduling Algorithm for Real-time Multiprocessor Systems
The Earliest Deadline First (EDF) scheduling algorithm has the least runtime complexity among joblevel fixed-priority algorithms for scheduling tasks on multiprocessor architectures. However, EDF suffers from suboptimality in multiprocessor systems. This paper proposes a new restricted migration-based scheduling algorithm for multiprocessor real-time systems, called Two-level Hierarchical Scheduling Algorithm (2L-HiSA), to address this sub-optimality. 2L-HiSA algorithm divides the problem of multiprocessor scheduling into a two-level hierarchy of schedulers. This algorithm works in two phases: i-A task-partitioning phase in which, each task from application task set is assigned to a specific processor by following simple bin-packing approach.