Minimizing migrations in fair multiprocessor scheduling of persistent tasks

Tracy Kimbrel, Baruch Schieber, Maxim Sviridenko

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. As jobs are persistent we measure the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio less than r(m - r)/(n(q(d - 1)) + ε > 0; namely, it asymptotically requires r(m - r) job migrations every n(q(d - 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal by proving a lower bound of r(m - r)/(nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for a special case when 2q ≤ d and m = 2r. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time.

Original languageEnglish (US)
Pages (from-to)365-379
Number of pages15
JournalJournal of Scheduling
Volume9
Issue number4
DOIs
StatePublished - Aug 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Fair scheduling
  • Multiprocessor scheduling
  • Persistent tasks
  • Process migration

Fingerprint

Dive into the research topics of 'Minimizing migrations in fair multiprocessor scheduling of persistent tasks'. Together they form a unique fingerprint.

Cite this