Efficient I/O Scheduling in Tertiary Libraries

With the recent improvements in network and processor speeds, several dataintensive applications have become much more feasible than ever before. Theonly practical solution for storing such enormous amounts of data istertiarystorage. Automated access to tertiary storage is made possible throughrobotic libraries for tapes and optical disks. Due to the slow speeds ofoperation of the drives and library robotics, access times for suchlibrariesare high resulting in the accumulation of I/O requests. In this paperwe study the problem of scheduling these requests for efficient performance.We focus on scheduling policies that process all requests on a loaded mediumbefore unloading it. For single drive settings an efficient algorithm thatproduces optimal schedules is developed. For multiple drives the problem isshown to be NP-Complete. Efficient and effective heuristics are presented forthe multiple drive case. The scheduling policies developed achieve significantperformance gains over more naive policies. The algorithms developed aresimple to implement and are not restrictive. The study is general enough to beapplicable to any storage library handling removable media, such as tapes andoptical disks.