Mechanisms and Policies for Supporting Fine-Grained Cycle Stealing

In The 13th International Conference on Supercomputing (ICS), June 1999.

Kyung Dong Ryu, Jeffrey K. Hollingsworth, and Pete Keleher

This paper investigates local mechanisms and scheduling policies that allow guest processes to efficiently exploit otherwise-idle workstation resources. The opportunity for harvesting cycles in idle workstations has long been recognized [13], as the majority of workstation cycles go unused. In combination with ever-increasing needs for cycles, this presents an obvious opportunity to better exploit existing resources. Two long-term trends are increasing this opportunity. First, increased connectivity across the Internet allows for utilization of resources in much wider domains. Second, new software technologies are making it possible to better exploit heterogeneous sets of workstations. For example, new Java compilers promise to allow write-once/run-anywhere applications to perform within a small factor of the best host-code compilers for traditional languages. These two trends vastly increase the set of candidates for wide-area resource computing.

Systems like Condor exploit this opportunity by allowing guest processes to run on idle participating machines. Existing systems focus on coarse-grained idle periods when users are away from their workstations. Returning users, or the start of any significant host processes, cause guest processes to be migrated off the local machine in order to avoid impacting the local user.

The thesis of this paper is that such policies waste many opportunities to exploit cycles because of overly conservative estimates of resource contention. We show that the potential negative impact of guest processes can be severely limited through the use of a few, simple modifications to existing kernel policies. We have developed a strict priority scheduling system that ensures that local processes receive priority in both processing cycles and memory. This paper describes these mechanisms and presents both a micro-benchmark study to demonstrate their efficacy, and an application-oriented workload study to show the overall impact of our policies on typical interactive workloads.

	title = "Mechanisms and Policies for Supporting Fine-Grained Cycle Stealing",
	author = "Kyung Dong Ryu and Jeffrey K. Hollingsworth and Pete Keleher",
	booktitle = {The 13th International Conference on Supercomputing (ICS)},
	month = {June},
	year = {1999},

Available: bibtex, abstract,