Minimizing migrations in fair multiprocessor scheduling of persistent tasks |
| |
Authors: | Tracy Kimbrel Baruch Schieber Maxim Sviridenko |
| |
Affiliation: | (1) IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY, 10598 |
| |
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. |
| |
Keywords: | Multiprocessor scheduling Fair scheduling Process migration Persistent tasks |
本文献已被 SpringerLink 等数据库收录! |