Reducing the Interprocessors Migrations of the EKG Algorithm

Abstract

In this work, we consider the scheduling problem of a set of periodic implicit-deadline and synchronous tasks, on a real-time multiprocessor composed of m identical processors. It is known that the cost of migrations and preemptions has significant influence on global system performances. The EKG algorithm which is optimal for k=m, can generate a great number of migrant tasks, but it has the advantage that each migrant task migrates between two processors only. Later, Kato et al. [10] have proposed the EDHS algorithm in order to minimize the number of migrant tasks of EKG. Although EDHS minimizes the number of migration compared to EKG, its drawback is the generation of additional preemptions caused by the migrations on several processors. In this paper we propose a new tasks allocation algorithm that aims to combine the advantages of EKG (migrations between two processors only) and those of EDHS (reduction of number of migrations).