Virtual I/O scheduler: a scheduler of schedulers for performance virtualization

ABSTRACT

Virtualized storage systems are required to service concurrently executing workloads, with potentially diverse data delivery requirements, that are running under multiple operating systems. Although a number of algorithms have been developed for I/O performance virtualization among operating system (OS) instances and their applications, none results in absolute performance virtualization. By absolute performance virtualization we mean that the performance experienced by applications of one operating system does not suffer due to variations in the I/O request stream characteristics of applications of other operating systems. Key requirements of I/O performance virtualization are fairness and performance isolation. In this paper, we present a novel virtual I/O scheduler (VIOS) that provides absolute performance virtualization by being fair in sharing I/O system resources among operating systems and their applications, and provides performance isolation in the face of variations in the characteristics of I/O streams. The VIOS controls the coarse grain allocation of disk time to the different operating system instances and is OS independent; optionally, a set of OS-dependent schedulers may determine the fine-grain interleaving of requests from the corresponding operating systems to the storage system.

REFERENCES

• 1: Guillermo A. Alvarez , Elizabeth Borowsky , Susie Go , Theodore H. Romer , Ralph Becker-Szendy , Richard Golding , Arif Merchant , Mirjana Spasojevic , Alistair Veitch , John Wilkes, Minerva: An automated resource provisioning tool for large-scale storage systems, ACM Transactions on Computer Systems (TOCS), v.19 n.4, p.483-518, November 2001 [doi>10.1145/502912.502915]
• 2: Eric Anderson , Michael Hobbs , Kimberly Keeton , Susan Spence , Mustafa Uysal , Alistair C. Veitch, Hippodrome: Running Circles Around Storage Administration, Proceedings of the Conference on File and Storage Technologies, p.175-188, January 28-30, 2002
• 3: J. Axboe, "Linux Block IO -- Present and Future," Proceedings of the Ottawa Linux Symposium 2004, Ottawa, Ontario, Canada, July 21--24, 2004, pp. 51--61.
• 4: S. Bhattacharya, S. Pratt, B. Pulavarty, J. Morgan, "Asynchronous I/O Support in Linux 2.5," Proceedings of the Ottawa Linux Symposium 2003, Ottawa, Ontario, Canada, July 23--26, pp. 371--386.
• 5: 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
• 6: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 7: S. J. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications," Proceedings of IEEE INFOCOM'94, Toronto, Canada, June 12--16, 1994, pp. 636--646.
• 8: Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, ACM SIGCOMM Computer Communication Review, v.26 n.4, p.157-168, Oct. 1996
• 9: A. G. Greenberg , N. Madras, How fair is fair queuing, Journal of the ACM (JACM), v.39 n.3, p.568-598, July 1992 [doi>10.1145/146637.146658]
• 10: Micha Hofri, Disk scheduling: FCFS vs.SSTF revisited, Communications of the ACM, v.23 n.11, p.645-653, Nov. 1980 [doi>10.1145/359024.359034]
• 11: A. Huffman, J. Clark, "Serial ATA: Native Command Queuing -- An Exciting New Performance Feature for Serial ATA," A Joint White Paper By: Intel Corporation and Seagate Technology LLC, July 2003.
• 12: Wei Jin , Jeffrey S. Chase , Jasleen Kaur, Interposed proportional sharing for a storage service utility, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 13: 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
• 14: D. T. Marr, F. Binns, D. L. Hill, G. Hinton, D. A. Koufaty, J. A. Miller, and M. Upton, "Hyper-threading Technology Architecture and Microarchitecture," Intel Technology Journal, 2002, 6(1):4--15.
• 15: N. Marushak and R. Jeppsen, "Deciding between SATA and SAS? Compare their Behind-the-Scenes Command Queuing Techniques," Storage Networking Work Online, September 2004.
• 16: P. McKenney, "Stochastic Fairness Queueing," Internetworking: Research and Experience, January 1991, Vol. 2, pp. 113--131.
• 17: S. Pratt, and D. Heger, "Workload Dependent Performance Evaluation of the Linux 2.6 I/O Schedulers," Proceedings of the Ottawa Linux Symposium 2004, Ottawa, Ontario, Canada, July 21-24, pp. 425--448.
• 18: S. Seelam and P. Teller, "Fairness and Performance Isolation: an Analysis of Disk Scheduling Algorithms," Proceedings of International Workshop on High Performance I/O Techniques and Deployment of Very Large Scale I/O Systems (HiperIO'06), Barcelona, Spain, September 25-28, 2006.
• 19: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round-robin, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.375-385, June 1996 [doi>10.1109/90.502236]
• 20: Prashant Shenoy , Harrick M. Vin, Cello: A Disk Scheduling Framework for Next Generation Operating Systems*, Real-Time Systems, v.22 n.1-2, p.9-48, Jan.-March 2002 [doi>10.1023/A:1013437003242]
• 21: Godfrey Tan , John Guttag, Time-based fairness improves performance in multi-rate WLANs, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.23-23, June 27-July 02, 2004, Boston, MA
• 22: Andrew S. Tanenbaum, Modern Operating Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 23: Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]
• 24: Ravi Wijayaratne , A. L. Narasimha Reddy, Providing QoS guarantees for disk I/O, Multimedia Systems, v.8 n.1, p.57-68, Jan. 2000 [doi>10.1007/s005300050005]
• 25: Jianyong Zhang , Anand Sivasubramaniam , Qian Wang , Alma Riska , Erik Riedel, Storage Performance Virtualization via Throughput and Latency Control, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.135-142, September 27-29, 2005 [doi>10.1109/MASCOT.2005.71]
• 26: T. Zanussi, K. Yaghmour, R.Wisniewski, R. Moore, and M. Dagenais, "relayfs: an Efficient Unified Approach for Transmitting Data from Kernel to User Space," Proceedings of the 2003 Linux Symposium, Ottawa, Canada, July 23--26, 2003.
• 27: tiobench: Thread I/O Bench for Linux, tiobench.sourceforge.net.
• 28: J. Axboe, "Patch: Block Device IO Tracing," http://lwn.net/Articles/155340/.
• 29: J. Axboe, "Time Sliced CFQ I/O Scheduler," http://kerneltrap.org/node/4406.
• 30: From SCSI to SATA, http://www.westerndigital.com/en/library/sata/2579--001097.pdf
• 31: TCQ, RAID, SCSI, and SATA, http://www.storagereview.com/articles/200406/20040625TCQ_1.html
• 32: Tagged Command Queuing: http://en.wikipedia.org/wiki/Tagged_Command_Queueing
• 33: Tagged Command Queuing (TCQ): http://www.wdc.com/en/library/sata/2579-001076.pdf
• 34: Setting SCSI-Adapter and Disk-Device Queue Limits, www.unet.univie.ac.at/aix/aixbman/prftungd/scsiqueue.htm

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
I/O scheduler, fairness, performance isolation, predictable performance, virtual I/O