10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10 '01)
Livelock Avoidance for Meta-Schedulers
San Francisco, California
August 07-August 09
ISBN: 0-7695-1296-8
Abstract: Meta-scheduling, a process which allows a user to schedule a job across multiple sites, has a potential for livelock. Current systems avoid livelock by locking down resources at multiple sites and allowing a meta-scheduler to control the resources during the lock down period or by limiting job size to that which will fit on one site. The former approach leads to poor utilization; the later poses limitations on job size. This research uses BYU's Meta-scheduler (YMS) which allows jobs to be scheduled across multiple sites without the need for locking down the nodes. YMS avoids livelock through exponential back-off. This research quantifies the potential for livelock, determines a suitable back-off period, and provides a structure upon which to test theoretical local schedulers. The results show that livelock exists and that a suitable exponential back-off not only avoids livelock but reduces the scheduling time for each job.
Index Terms:
Livelock, meta-scheduling, exponential back-off.
Citation:
John Jardine, Quinn Snell, Mark Clement, "Livelock Avoidance for Meta-Schedulers," hpdc, pp.0141, 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10 '01), 2001