Restrained utilization of idleness for transparent scheduling of background tasks

ABSTRACT

A common practice in system design is to treat features intended to enhance performance and reliability as low priority tasks by scheduling them during idle periods, with the goal to keep these features transparent to the user. In this paper, we present an algorithmic framework that determines the schedulability of non-preemptable low priority tasks in storage systems. The framework estimates when and for how long idle times can be utilized by low priority background tasks, without violating pre-defined performance targets of user foreground tasks. The estimation is based on monitored system information that includes the histogram of idle times. This histogram captures accurately important statistical characteristics of the complex demands of the foreground activity. The robustness and the effectiveness of the proposed framework is corroborated via extensive trace driven simulations under a wide range of system conditions and background activities, and via experimentation on a Linux kernel 2.6.22 prototype.

REFERENCES

• 1: Michael Abd-El-Malek , Gregory R. Ganger , Michael K. Reiter , Jay J. Wylie , Garth R. Goodson, Lazy Verification in Fault-Tolerant Distributed Storage Systems, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.179-190, October 26-28, 2005 [doi>10.1109/RELDIS.2005.20]
• 2: Eitan Bachmat , Jiri Schindler, Analysis of methods for scheduling low priority disk drive tasks, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 3: Lakshmi N. Bairavasundaram , Garth R. Goodson , Shankar Pasupathy , Jiri Schindler, An analysis of latent sector errors in disk drives, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 4: John R. Douceur , William J. Bolosky, Progress-based regulation of low-importance processes, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.247-260, December 12-15, 1999, Charleston, South Carolina, United States
• 5: Fred Douglis , P. Krishnan , Brian N. Bershad, Adaptive Disk Spin-down Policies for Mobile Computers, Proceedings of the 2nd Symposium on Mobile and Location-Independent Computing, p.121-137, April 10-11, 1995
• 6: Lars Eggert , Joseph D. Touch, Idletime scheduling with preemption intervals, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 7: Richard Golding , Peter Bosch , Carl Staelin , Tim Sullivan , John Wilkes, Idleness is not sloth, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.17-17, January 16-20, 1995, New Orleans, Louisiana
• 8: Ajay Gulati , Arif Merchant , Peter J. Varman, pClock: an arrival curve based approach for QoS guarantees in shared storage systems, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 9: David P. Helmbold , Darrell D. E. Long , Tracey L. Sconyers , Bruce Sherrod, Adaptive disk spin—down for mobile computers, Mobile Networks and Applications, v.5 n.4, p.285-297, Dec. 2000 [doi>10.1023/A:1019129116852]
• 10: Hai Huang , Wanda Hung , Kang G. Shin, FS2: dynamic data replication in free disk space for improving disk performance and energy consumption, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 11: Ilias Iliadis , Robert Haas , Xiao-Yu Hu , Evangelos Eleftheriou, Disk scrubbing versus intra-disk redundancy for high-reliability raid storage systems, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 12: Sang-Won Lee , Bongki Moon , Chanik Park , Jae-Myung Kim , Sang-Woo Kim, A case for flash memory ssd in enterprise database applications, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376723]
• 13: Adam Leventhal, Flash storage memory, Communications of the ACM, v.51 n.7, July 2008 [doi>10.1145/1364782.1364796]
• 14: Arif Merchant , Philip S. Yu, An analytical model of reconstruction time in mirrored disks, Performance Evaluation, v.20 n.1-3, p.115-129, May 1994
• 15: Ningfang Mi , Alma Riska , Qi Zhang , Evgenia Smirni , Erik Riedel, Efficient management of idleness in storage systems, ACM Transactions on Storage (TOS), v.5 n.2, p.1-25, June 2009 [doi>10.1145/1534912.1534913]
• 16: Zhisheng Niu , Tao Shu , Yoshitaka Takahashi, A vacation queue with setup and close-down times and batch Markovian arrival processes, Performance Evaluation, v.54 n.3, p.225-248, November 2003 [doi>10.1016/S0166-5316(03)00058-0]
• 17: Alma Riska , Erik Riedel, Disk drive level workload characterization, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.9-9, May 30-June 03, 2006, Boston, MA
• 18: Alma Riska , Erik Riedel, Idle read after write: IRAW, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.43-56, June 22-27, 2008, Boston, Massachusetts
• 19: Thomas J. E. Schwarz , Qin Xin , Ethan L. Miller , Darrell D. E. Long , Andy Hospodor , Spencer Ng, Disk Scrubbing in Large Archival Storage Systems, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.409-418, October 04-08, 2004
• 20: Muthian Sivathanu , Vijayan Prabhakaran , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Awarded Best Student Paper! -- Improving Storage System Availability with D-GRAID, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 21: H. Takagi. Queuing Analysis Volume 1: Vacations and Priority Systems. North-Holland, New York, 1991.
• 22: Eno Thereska , Jiri Schindler , John Bucy , Brandon Salmon , Christopher R. Lumb , Gregory R. Ganger, Awarded Best Student Paper! -- A Framework for Building Unobtrusive Disk Maintenance Applications, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 23: Arun Venkataramani , Ravi Kokku , Mike Dahlin, TCP Nice: a mechanism for background transfers, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060320]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Design studies

General Terms:
Algorithms, Design, Management, Performance, Reliability

Keywords:
continuous data histogram, idleness, low priority work, performance guarantee