CPMD-mindful task assignment for NPS-F

Geoffrey Nelissen, Konstantinos Bletsas, Joël Goossens

Research output: Contribution to journalArticleAcademicpeer-review


The multiprocessor scheduling scheme NPS-F for sporadic tasks has a high utilisation bound and an overall number of preemptions bounded at design time. NPS-F binpacks tasks offline to as many servers as needed. At runtime, the scheduler ensures that each server is mapped to at most one of the m processors, at any instant. When scheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overall number of preemptions, the migrations per se are not tightly bounded. Moreover, we cannot know a priori which task a server will be currently executing at the instant when it migrates. This uncertainty complicates the estimation of cache-related preemption and migration costs (CPMD), potentially resulting in their overestimation. Therefore, to simplify the CPMD estimation, we propose an amended bin-packing scheme for NPS-F allowing us (i) to identify at design time, which task migrates at which instant and (ii) bound a priori the number of migrating tasks, while preserving the utilisation bound of NPS-F.

Original languageEnglish
Pages (from-to)585-591
Number of pages7
JournalReal-Time Systems
Issue number5-6
Publication statusPublished - 22 Oct 2014
Externally publishedYes


  • Bin packing
  • CPMD estimation
  • Multiprocessor
  • NPS-F
  • Real-time scheduling
  • Semi-partitioned


Dive into the research topics of 'CPMD-mindful task assignment for NPS-F'. Together they form a unique fingerprint.

Cite this