Energy-aware disk scheduling for soft real-time I/O requests

Youjip Won; Jongmin Kim; Wonmin Jung
February 2008
Multimedia Systems;Feb2008, Vol. 13 Issue 5/6, p409
Academic Journal
Abstract  In this work, we develop energy-aware disk scheduling algorithm for soft real-time I/O. Energy consumption is one of the major factors which bar the adoption of hard disk in mobile environment. Heat dissipation of large scale storage system also calls for an energy-aware scheduling technique to further increase the storage density. The basic idea in this work is to properly determine the I/O burst size so that device can be in standby mode between consecutive I/O bursts and that it can satisfy the soft real-time requirement. We develop an elaborate model which incorporates the energy consumption characteristics, overhead of mode transition in determining the appropriate I/O burst size and the respective disk operating schedule. Efficacy of energy-aware disk scheduling algorithm greatly relies on not only disk scheduling algorithm itself but also various operating system and device firmware related concerns. It is crucial that the various operating system level and device level features need to be properly addressed within disk scheduling framework. Our energy-aware disk scheduling algorithm successfully addresses a number of outstanding issues. First, we examine the effect of OS and hard disk firmware level prefetch policy and incorporate its effect in our disk scheduling framework. Second, our energy aware scheduling framework can allocate a certain fraction of disk bandwidth to handle sporadically arriving non real-time I/O’s. Third, we examine the relationship between lock granularity of the buffer management and energy consumption. We develop a prototype software with energy-aware scheduling algorithm. In our experiment, proposed algorithm can reduce the energy consumption to one fourth if we use energy-aware disk scheduling algorithm. However, energy-aware disk scheduling algorithm increases buffer requirement significantly, e.g., from 4 to 140 KByte. We carefully argue that the buffer overhead is still justifiable given the cost of DRAM chip and importance of energy management in modern mobile devices. The result of our work not only provides the energy efficient scheduling algorithm but also provides an important guideline in capacity planning of future energy efficient mobile devices.


Related Articles

  • Basic Dual Feasible Solutions for a Class of Generalized Networks. Glover, Fred; Klingman, D.; Napier, A. // Operations Research;Jan/Feb72, Vol. 20 Issue 1, p126 

    The generalized network problem and the closely related restricted dyadic problem occur frequently in applications of linear programming. Although they are next in order of computational complexity after pure network or distribution problems, the jump in degree of difficulty is such that, in the...


    We show that a variant of Karmarkar's projective algorithm for linear programming can be viewed as following the approach of Dantzig-Wolfe decomposition. At each iteration, the current primal feasible solution generates prices which are used to form a simple subproblem. The solution to the...

  • An Algorithm for Solving Interval Linear Programming Problems. Charnes, A.; Granot, Frieda; Phillips, F. // Operations Research;Jul/Aug77, Vol. 25 Issue 4, p688 

    This paper presents an algorithm for solving interval linear programming (IP) problems. The algorithm is a finite iterative method. At each iteration it solves a full row rank, (IP) problem with any one additional constraint.

  • A Polynomial Primal-dual Dikin-type Algorithm for Linear Programming. Jansen, B.; Roos, C.; Terlaky, T. // Mathematics of Operations Research;May96, Vol. 21 Issue 2, p341 

    In this paper we present a new primal-dual affine scaling method for linear programming. The method yields a strictly complementary optimal solution pair, and also allows a polynomial-time convergence proof. The search direction is obtained by using the original idea of Dikin, namely by...

  • ON THE COMPLEXITY OF SOLVING SPARSE SYMMETRIC LINEAR PROGRAMS SPECIFIED WITH APPROXIMATE DATA. Filipowski, Sharon // Mathematics of Operations Research;Nov97, Vol. 22 Issue 4, p769 

    An algorithm that solves symmetric linear programs specified with approximate data is given. The algorithm uses knowledge that several of the constraint matrix coefficients of the actual (unknown) instance are equal to zero to reduce the data precision necessary to solve the instance in...

  • A MULTIPLIER ADJUSTMENT APPROACH FOR THE SET PARTITIONING PROBLEM. Chan, Thomas Justin; Yano, Candace Arai // Operations Research;Jan/Feb92 Supplement 1, Vol. 40 Issue 1, p40 

    We introduce an effective branch-and-bound algorithm for solving the set partitioning problem. The new algorithm employs a new multiplier-adjustment-based bounding procedure, and a complementary branching strategy which results in relatively small search trees. Computational results based on 20...

  • Asymptotic Linear Programming. Jeroslow, Robert G. // Operations Research;Sep/Oct73, Vol. 21 Issue 5, p1128 

    This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior...

  • Generalized Covering Relaxation for 0-1 Programs. Granot, Daniel; ranot, Frieda // Operations Research;Nov/Dec80, Vol. 28 Issue 6, p1442 

    We construct in this paper a general purpose cutting-plane algorithm for solving the 0-1 polynomial programming problem of finding a 0-1 n vector x = (x[sub j]) that maximizes c[sup T]x subject to f(x) is less than or equal to b where f(x) = (f,(x)) is an m vector of polynomials. The algorithm...

  • OFF-DAY SCHEDULING WITH HIERARCHICAL WORKER CATEGORIES. Emmons, Hamilton; Burns, Richard N. // Operations Research;May/Jun91, Vol. 39 Issue 3, p484 

    A work force includes workers of m types The worker categories are ordered, with type-1 workers the most highly qualified, type-2 the next, and so on. If the need arises, a type-k worker is able to substitute for a worker of any type j> k (k = 1,..., m-1). For 7-day-a-week operation, daily...


Other Topics