A utility-based unified disk scheduling framework for shared mixed-media services

ABSTRACT

We present a new disk scheduling framework to address the needs of a shared multimedia service that provides differentiated multilevel quality-of-service for mixed-media workloads. In such a shared service, requests from different users have different associated performance objectives and utilities, in accordance with the negotiated service-level agreements (SLAs). Service providers typically provision resources only for average workload intensity, so it becomes important to handle workload surges in a way that maximizes the utility of the served requests.

We capture the performance objectives and utilities associated with these multiclass diverse workloads in a unified framework and formulate the disk scheduling problem as a reward maximization problem. We map the reward maximization problem to a minimization problem on graphs and, by novel use of graph-theoretic techniques, design a scheduling algorithm that is computationally efficient and optimal in the class of seek-optimizing algorithms. Comprehensive experimental studies demonstrate that the proposed algorithm outperforms other disk schedulers under all loads, with the performance improvement approaching 100% under certain high load conditions. In contrast to existing schedulers, the proposed scheduler is extensible to new performance objectives (workload type) and utilities by simply altering the reward functions associated with the requests.

REFERENCES

• 1: Aggarwal, G., Dubey, P. K., Ghosal, S., Kulshreshtha, A., and Sarkar, A. 2000. iPURE: Perceptual and user-friendly retrieval of images. In the IEEE International Conference on Multimedia and Expo (ICME).
• 2: Andrews, M., Bender, M. A., and Zang, L. 2002. New algorithms for the disk scheduling problem. Algorithmica 32, 2, 277--301.
• 3: John Bruno , Jose Brustoloni , Eran Gabber , Banu Ozden , Abraham Silberschatz, Disk Scheduling with Quality of Service Guarantees, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.400, June 07-11, 1999
• 4: Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle, Managing energy and server resources in hosting centers, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: Chen, S., Stankovic, J. A., Kurose, J. F., and Towsley, D. 1991. Performance evaluation of two new disk scheduling algorithms for real-time systems. J. Real-Time Syst. 3, 307--336.
• 6: Koustuv Dasgupta , Sugata Ghosal , Rohit Jain , Upendra Sharma , Akshat Verma, QoSMig: Adaptive Rate-Controlled Migration of Bulk Data in Storage Systems, Proceedings of the 21st International Conference on Data Engineering, p.816-827, April 05-08, 2005 [doi>10.1109/ICDE.2005.116]
• 7: Department of Distributed Systems. 2007. Index of MPEG traces. http://www3.informatik. uni-wuerzburg.de/MPEG/traces.
• 8: Ganger, G. R., Worthington, B. L., and Patt, Y. N. 1999. The DiskSim simulation environment: Version 2.0 reference manual. Tech. Rep. CSE-TR-358-98, Department of Electrical Engineering and Computer Science, University of Michigan.
• 9: Ghandeharizadeh, S., Huang, L., and Kamel, A. 2003. A cost driven disk scheduling algorithm for multimedia object retrieval. IEEE Trans. Multimedia 5, 2, 186--196.
• 10: Gallo, G., Malucelli, F., and Marre, M. 1995. Hamiltonian paths algorithms for disk scheduling. Tech. Rep. HPL-95-71, HP Labs.
• 11: W. Hsu , A. J. Smith, Characteristics of I/O traffic in personal computer and server workloads, IBM Systems Journal, v.42 n.2, p.347-372, April 2003
• 12: Huang, L. and Chiueh, T. 2002. Experiences in building a software-based SATF scheduler. Tech. Rep., State University of New York at StonyBrook, July.
• 13: Lan Huang , Gang Peng , Tzi-cker Chiueh, Multi-dimensional storage virtualization, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 14: Arun K. Iyengar , Mark S. Squillante , Li Zhang, Analysis and characterization of large-scale Web server access patterns and performance, World Wide Web, v.2 n.1-2, p.85-100, 1999 [doi>10.1023/A:1019244621570]
• 15: David E. Irwin , Laura E. Grit , Jeffrey S. Chase, Balancing Risk and Reward in a Market-Based Task Service, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing, p.160-169, June 04-06, 2004 [doi>10.1109/HPDC.2004.5]
• 16: Jin, W., Chase, J. S., and Kaur, J. 2004. Access method concurrency with recovery. In Proceedings of the ACM Conference on Electronic Commerce (EC), 213--223.
• 17: Liu, Z., Squillante, M. S., and Wolf, J. L. 2001. On maximizing service level agreement profits.ACM Trans. Comput. Syst.
• 18: Christopher R. Lumb , Arif Merchant , Guillermo A. Alvarez, Façade: Virtual Storage Devices with Performance Guarantees, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 19: Ketil Lund , Vera Goebel, Adaptive disk scheduling in a multimedia DBMS, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957024]
• 20: Mohamed F. Mokbel , Walid G. Aref , Khaled Elbassioni , Ibrahim Kamel, Scalable Multimedia Disk Scheduling, Proceedings of the 20th International Conference on Data Engineering, p.498, March 30-April 02, 2004
• 21: Papadimitriou, C. H. 1977. The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci. 4, 237--244.
• 22: PC Technology Guide. 2004. Storage-Hard disks. http://www.pctechguide.com/04disks.htm.
• 23: PC Technology Guide. 2002. Components-Processors. http://www.pctechguide.com/02procs.htm.
• 24: Popovici, F. I., Arpaci-Dusseau, A. C., and Arpaci-Dusseau, R. H. 2003. Robust, portable I/O scheduling with the disk mimic. In Proceedings of the USENIX Annual Technical Conference, 297--310.
• 25: A. L. Narasimha Reddy , Jim Wyllie, Disk scheduling in a multimedia I/O system, Proceedings of the first ACM international conference on Multimedia, p.225-233, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.166292]
• 26: Y. Rompogiannakis , G. Nerjes , P. Muth , M. Paterakis , P. Triantafillou , G. Weikum, Disk scheduling for mixed-media workloads in a multimedia server, Proceedings of the sixth ACM international conference on Multimedia, p.297-302, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290785]
• 27: Schindler, J. and Ganger, G. R. 1999. Automated disk drive characterization. Tech. Rep. CMU-CS-99-176, Carnegie Mellon University, December.
• 28: Jiri Schindler , John Linwood Griffin , Christopher R. Lumb , Gregory R. Ganger, Track-Aligned Extents: Matching Access Patterns to Disk Drive Characteristics, Proceedings of the Conference on File and Storage Technologies, p.259-274, January 28-30, 2002
• 29: Seagate Corporation. 2007. Cheetah4LP disk specification datasheet. http://www.seagate.com.
• 30: Seltzer, M., Chen, P., and Ousterhout, J. 1990. Disk scheduling revisited. In Proceedings of the USENIX Winter Technical Conference, 313--324.
• 31: Prashant J. Shenoy , Harrick M. Vin, Efficient support for interactive operations in multi-resolution video servers, Multimedia Systems, v.7 n.3, p.241-253, May 1999 [doi>10.1007/s005300050126]
• 32: Prashant J. Shenoy , Harrick M. Vin, Cello: a disk scheduling framework for next generation operating systems, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.44-55, June 22-26, 1998, Madison, Wisconsin, United States
• 33: Akshat Verma , Sugata Ghosal, On admission control for profit maximization of networked service providers, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775171]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

General Terms:
Algorithms, Performance

Keywords:
GSP, Profit maximization, disk scheduling, shortest path