MEMS-based storage is expected to be adopted as a secondary storage of mobile computing devices such as portable media players and digital cameras. Due to its desirable features such as small size, lightweight, low power consumption, and low cost, MEMS-based storage will be widely used for mobile applications that require large volume of multimedia data. However, physical structures of MEMS-based storage are different from other storage devices such as hard disk especially in the way of data placement and head positioning. Hence, it is important to revise OS-level software management schemes for MEMS-based storage. In this paper, we present a new I/O scheduling algorithm for MEMS-based storage called G-MST that exploits two-dimensional structure of MEMS-based storage. The new algorithm aims at reducing total seek distance in the two dimensional MEMS structure and at the same time providing fast and uniform response times. Through simulation experiments, we show that the new I/O scheduling algorithm performs better than existing algorithms in terms of average response time and the variation of response times.