Abstract
This paper investigates the intersection of dynamic speed scaling, sleep states, and profit-oriented job rejection in online deadline scheduling. Traditional scheduling models often overlook the interplay between these energy-saving mechanisms. We demonstrate that the introduction of sleep states causes standard "rejection-oblivious" strategies to perform poorly. To address this, we propose a new algorithm that utilizes a modified rejection policy and a "critical speed" threshold to maintain a near-optimal competitive ratio. Our analysis provides both lower and upper bounds for competitive performance in this realistic energy-aware model.
Introduction
Energy consumption is a primary operational cost for modern data centers. Hardware designers provide two main mechanisms for energy management: dynamic speed scaling (adjusting processor speed to save energy per operation) and power-down states (putting the processor to sleep during idle periods). While these have been studied independently, real-world scenarios require a unified approach that also considers job profitability.
In this "profit-oriented" model, jobs arrive with specific deadlines and values. A scheduler must decide whether to admit a job, at what speed to process it to meet its deadline, and when to transition to a sleep state. The "online" nature of the problem—where future job arrivals are unknown—presents a significant challenge in avoiding decisions that are locally profitable but globally inefficient.
Methodology
The core contribution is Algorithm A, an extension of the classical Optimal Available (OA) algorithm. Algorithm A incorporates several key features to handle the complexities of sleep states and job rejection:
- Modified Rejection Policy: Unlike traditional models, Algorithm A evaluates jobs based on their "value density" (value per unit of work). It rejects jobs if their value is insufficient to cover the energy costs, including the "idle cost" incurred while waiting for or processing the job.
- Critical Speed ($s_{cr}$): Given a power function $P(s) = s^\alpha + \beta$, the constant overhead $\beta$ implies a "critical speed" below which running the processor is less efficient than running at $s_{cr}$. Algorithm A ensures the processor never operates below this threshold.
The performance of the algorithm is evaluated using competitive analysis, comparing the cost of the online algorithm against an optimal offline scheduler. An amortized analysis using a potential function tracks the "work-debt" of the online algorithm to prove its effectiveness.
Key Insights and Results
Our analysis reveals several fundamental properties of energy-efficient scheduling with sleep states:
- Failure of Rejection-Obliviousness: We prove that algorithms making rejection decisions without considering previous state transitions (rejection-oblivious) have an unbounded competitive ratio when sleep states are present. Such algorithms can be exploited by sequences of low-value jobs that force frequent, energy-expensive wake-ups.
- The "Sleep" Penalty: Transitioning from a sleep state to an active state incurs a fixed energy cost $\gamma$. To remain competitive, a scheduler must be "stubborn," refusing to wake up for jobs whose value does not significantly outweigh this transition penalty.
- Competitive Bounds: We establish a lower bound for any rejection-oblivious algorithm of $\delta_{max} \cdot \frac{s_{cr}}{P(s_{cr})}$, where $\delta_{max}$ is the maximum value density. Conversely, Algorithm A achieves a competitive ratio of approximately $\alpha^\alpha + 2e\alpha$, assuming restricted value density for low-value jobs. This result is further extended to processors with a fixed maximum speed $T$.
Conclusion
This work provides a robust theoretical framework for combining speed scaling and sleep states in profit-driven scheduling. While currently limited to single-processor environments and standard power models, it highlights the critical role of value density and "stubborn" rejection policies. Future research will explore multi-processor systems and more complex power curves to better reflect modern hardware architectures.
Summary updated