P. Krishnan, P. M. Long and J. S. Vitter. Adaptive disk spindown via optimal
rent-to-buy in probabilistic environments.
Algorithmica, 23(1):31-56, 1999.
(Available in Postscript and PDF formats.)
Abstract
In the single rent-to-buy
decision problem, without a priori knowledge of the amount of time
a resource will be
used we need to decide when to buy the resource, given that we can rent the
resource for $1 per unit time
or buy it once and for all for $c. In this paper we study algorithms
that make a sequence of
single rent-to-buy decisions,
using the assumption that the resource
use times are independently
drawn from an unknown probability distribution. Our study of
this rent-to-buy
problem is motivated by important systems applications, specifically, problems
arising from deciding when to
spindown disks to conserve energy in mobile computers,
thread blocking decisions during lock acquisition in
multiprocessor applications, and virtual
circuit holding times in IP-over-ATM networks.
We develop a provably optimal and computationally
efficient algorithm for the rent-to-buy
problem.
We describe the experimental results for the application of our algorithm to one of the
motivating systems problems: the question of when to spindown a disk to save power in a mobile
computer. Simulations using disk access traces obtained from an HP workstation environment
suggest that our algorithm yields significantly improved power/response time performance over
the non-adaptive 2-competitive algorithm which is optimal in the worst-case competitive analysis
model.