P/PA-SPTF: Parallelism-aware request scheduling algorithms for MEMS-based storage devices

ABSTRACT

MEMS-based storage is foreseen as a promising storage media that provides high-bandwidth, low-power consumption, high-density, and low cost. Due to these versatile features, MEMS storage is anticipated to be used for a wide range of applications from storage for small handheld devices to high capacity mass storage servers. However, MEMS storage has vastly different physical characteristics compared to a traditional disk. First, MEMS storage has thousands of heads that can be activated simultaneously. Second, the media of MEMS storage is a square structure which is different from the platter structure of disks. This article presents a new request scheduling algorithm for MEMS storage called P-SPTF that makes use of the aforementioned characteristics. P-SPTF considers the parallelism of MEMS storage as well as the seek time of requests on the two dimensional square structure. We then present another algorithm called PA-SPTF that considers the aging factor so that starvation resistance is improved. Simulation studies show that PA-SPTF improves the performance of MEMS storage by up to 39.2% in terms of the average response time and 62.4% in terms of starvation resistance compared to the widely acknowledged SPTF algorithm. We also show that there exists a spectrum of scheduling algorithms that subsumes both the P-SPTF and PA-SPTF algorithms.

REFERENCES

• 1: Carley, L. R., Bain, J. A., Fedder, G. K., Greve, D. W., Guillou, D. F., Lu, M. S. C., Mukherjee, T., Santhanam, S., Abelmann, L., and Min, S. 2000. Single-chip computers with microelecromechanical systems-based magnetic memory. J. Appl. Phy. 87, 9, 6680--6685.
• 2: Peter J. Denning, Effects of scheduling on file memory operations, Proceedings of the April 18-20, 1967, spring joint computer conference, April 18-20, 1967, Atlantic City, New Jersey [doi>10.1145/1465482.1465485]
• 3: Ivan Dramaliev , Tara Madhyastha, Optimizing Probe-Based Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 4: John Linwood Griffin , Steven W. Schlosser , Gregory R. Ganger , David F. Nagle, Operating system management of MEMS-based storage devices, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.16-16, October 22-25, 2000, San Diego, California
• 5: John Linwood Griffin , Steven W. Schlosser , Gregory R. Ganger , David F. Nagle, Modeling and performance of MEMS-based storage devices, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.56-65, June 18-21, 2000, Santa Clara, California, United States
• 6: Hong, B. Exploring the usage of MEMS-based storage as metadata storage and disk cache in storage hierarchy. http://www.cse.ucsc.edu/~hongbo/publications/mems-metadata.pdf.
• 7: Hong, B., Brandt, S. A., Long, D.D.E., Miller, E. L., Glocer, K. A., and Peterson, Z. N. J. 2003. Zone-based shortest positioning time first scheduling for MEMS-based storage devices. Proceedings of the 11th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS).
• 8: Bo Hong , Feng Wang , Scott A. Brandt , Darrell D. E. Long , Thomas J. E. Schwarz, S. J., Using MEMS-based storage in computer systems---MEMS storage architectures, ACM Transactions on Storage (TOS), v.2 n.1, p.1-21, February 2006 [doi>10.1145/1138041.1138042]
• 9: Bo Hong , Scott A. Brandt , Darrell D. E. Long , Ethan L. Miller , Ying Lin, Using MEMS-based storage in computer systems---device modeling and management, ACM Transactions on Storage (TOS), v.2 n.2, p.139-160, May 2006 [doi>10.1145/1149976.1149978]
• 10: Jacobson, D. M. and Wilkes, J. 1992. Disk scheduling algorithms based on rotational position. Tech. Rep. HPL-CSP-91-7rev1, Hewlett-Packard Laboratories, Concurrent Systems Project.
• 11: Tara M. Madhyastha , Katherine Pu Yangy, Physical Modeling of Probe-Based Storage, Proceedings of the Eighteenth IEEE Symposium on Mass Storage Systems and Technologies, p.207, April 17-20, 2001
• 12: Rangaswami, R., Dimitrijevic, Z., Chang, E., and Schauser, K. E. 2003. MEMS-based disk buffer for streaming media server. Proceedings of the International Conference on Data Engineering (ICDE).
• 13: Samsung Flash Memory, http://www.samsung.com/global/business/semiconductor/productList.do?fmly_id=159.
• 14: Steven W. Schlosser , John Linwood Griffin , David F. Nagle , Gregory R. Ganger, Designing computer systems with MEMS-based storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.1-12, November 2000, Cambridge, Massachusetts, United States
• 15: Schlosser, S. W., Schindler, J., Ailamaki, A., and Ganger, G. R. 2003. Exposing and exploiting internal parallelism in MEMS-based storage. Tech. Rep. CMU-CS-03-125, Carnegie Mellon University, Pittsburgh, PA.
• 16: Steven W. Schlosser , Gregory R. Ganger, MEMS-based Storage Devices and Standard Disk Interfaces: A Square Peg in a Round Hole?, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 17: Mustafa Uysal , Arif Merchant , Guillermo A. Alvarez, Awarded Best Paper! - Using MEMS-Based Storage in Disk Arrays, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 18: Vettiger, P., Despont, M., Drechsler, U., Dürig, U., Häberle, W., Lutwyche, M. I., Rothuizen, H. E., Stutz, R., Widmer, R., and Binnig, G. K. 2000. The Millipede—More than one thousand tips for future AFM data storage. IBM J. Resear. Devel. 44, 3, 323--340.
• 19: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States
• 20: Hailing Yu , Divyakant Agrawal , Amr El Abbadi, Towards Optimal I/O Scheduling for MEMS-Based Storage, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.58, April 07-10, 2003
• 21: Hailing Yu , Divyakant Agrawal , Amr El Abbadi, Tabular placement of relational data on MEMS-based storage devices, Proceedings of the 29th international conference on Very large data bases, p.680-693, September 09-12, 2003, Berlin, Germany

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

General Terms:
Algorithms, Design, Management, Performance

Keywords:
MEMS-based storage, parallelism, scheduling, seek time, starvation