Minimizing migrations in fair multiprocessor scheduling of persistent tasks

Minimizing migrations in fair multiprocessor scheduling of persistent tasks

0.00 Avg rating0 Votes
Article ID: iaor20081240
Country: United Kingdom
Volume: 9
Issue: 4
Start Page Number: 365
End Page Number: 379
Publication Date: Aug 2006
Journal: Journal of Scheduling
Authors: , ,
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 nm 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) + 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 2qd and m = 2r. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time.

Reviews

Required fields are marked *. Your email address will not be published.