Reducing preemptions and migrations in EKG

Geoffrey Nelissen, Shelby Funk, Joël Goossens

Research output: Contribution to conferencePaperAcademic

6 Citations (Scopus)


EKG is a multiprocessor scheduling algorithm which is optimal for the scheduling of real-time periodic tasks with implicit deadlines. It consists in a semi-partitioned algorithm which adheres to the deadline partitioning fair (DP-Fair) theory. It was shown in recent studies that the division of the time in slices bounded by two successive deadlines and the systematic execution of migratory tasks in each time slice inherent in DP-Fair algorithms, significantly reduce the practicality of EKG. Nevertheless, its semi-partitioned approach allows to bound the number of migrating tasks and increases the locality of the tasks in memories, thereby lowering the time overheads imposed by task preemptions and migrations. Hence, we propose two techniques with the aim of reducing the amount of preemptions and migrations incurred by the system when scheduled with EKG, while maintaining the advantages of its semi-partitioned approach. The first improvement consists in a swapping algorithm which exchanges execution time between tasks and time slices. The second one aims at decreasing the number of time slices needed to ensure that all job deadlines are respected. Both have a strong impact on the number of preemptions and migrations while keeping the optimality of EKG.

Original languageEnglish
Number of pages10
Publication statusPublished - 19 Nov 2012
Externally publishedYes
Event18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012 - Seoul, Korea, Republic of
Duration: 19 Aug 201222 Aug 2012


Conference18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012
Country/TerritoryKorea, Republic of


  • EKG
  • migrations
  • optimal
  • preemptions
  • scheduling algorithm


Dive into the research topics of 'Reducing preemptions and migrations in EKG'. Together they form a unique fingerprint.

Cite this