Robust, Portable I/O Scheduling with the Disk MimicFlorentina I. Popovici, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-DusseauComputer Sciences Department, University of Wisconsin, MadisonAbstractWe propose a new approach for I/O scheduling that per-forms on-line simulation of the underlying disk. Whensimulation is integrated within a system, three key chal-lenges must be addressed: first, the simulator must beportable across the full range of devices; second, all con-figuration must be automatic; third, the computation andmemory overheads must be low. Our simulator, the DiskMimic, achieves these goals by building a table-basedmodel of the disk as it observes the times for previousrequests. We show that a shortest-mimicked-time-first(SMTF) scheduler performs nearly as well as an approachwith perfect knowledge of the underlying device and thatit is superior to traditional scheduling algorithms such asC-LOOK and SSTF; our results hold as the seek and ro-tational characteristics of the disk are varied.1 IntroductionHigh-performance disk schedulers explored in the re-search literature are becoming progressively more tunedto the performance characteristics of the underlying disks.Each generation of disk schedulers has accounted formore of the behavior of storage devices at the time. Forexample, disk schedulers analyzed in the 1970s and 1980sfocused on minimizing seek time, given that seek timewas often an order of magnitude greater than the expectedrotational delay [10, 26, 29]. In the early 1990s, the fo-cus of disk schedulers shifted to take rotational delay intoaccount, as rotational delays and seek costs became morebalanced [13, 21, 31].At the next level of sophistication, a disk schedulertakes all aspects of the underlying disk into account: trackand cylinder switch costs, cache replacement policies,mappings from logical block number to physical blocknumber, and zero-latency writes. For example, Worthing-ton et al. demonstrate that algorithms that effectively uti-lize a prefetching disk cache perform better than those thatdo not [31].However, the more intricate the knowledge a schedulerhas of the disk, the more barriers there are to its realizationwithin operating system kernels. Specifically, there arethree obstacles that must be overcome. First, the schedulermust discover detailed knowledge of the underlying disk.Although a variety of tools have been described that auto-matically acquire portions of this knowledge [19, 25, 32],it must still be embedded into the disk model employed bythe scheduler; the resulting scheduler is then configured tohandle only a single disk with those specific characteris-tics. Second, the disk scheduler must also have knowl-edge of the current state of the disk, such as the exactposition of the disk head. Given that head position isnot exposed by current disk controllers and its positionis not predictable due to low-level disk techniques suchas wear leveling, predictive failure analysis, and log up-dates, the scheduler must control the current position us-ing non-trivial techniques [11, 33]. Finally, the computa-tional costs of detailed modeling can be quite high [31]; itis not uncommon for the time to model request time to belarger than the time to service the request [4].Due to these difficulties, few disk schedulers that lever-age more than basic seek costs have been implementedfor real disks. When considering rotational position, mostprevious work has been performed within simulation en-vironments [13, 21, 23, 31]. The schedulers that haverecently been implemented by researchers have eithercontained substantial simplifications [12] or have beenpainstakingly tuned for a small group of disks [11, 33].Not surprisingly, the disk schedulers found in modern op-erating systems such as Linux, NetBSD, and Solaris, at-tempt only to minimize seek time.1.1 A Different ApproachWe believe that a promising alternative approach to em-bedding detailed knowledge of the disk into the sched-uler is to embed an on-line simulator of the disk into thescheduler. An I/O scheduler is able to use on-line simula-tion of the underlying storage device to predict which re-quest in its queue will have the shortest positioning time.Although a variety of disk simulators exist [4, 14, 30],most are targeted for performing traditional, off-line sim-ulations, and unfortunately, the infrastructure for perform-ing on-line simulation is fundamentally different.In many respects, the requirements of an on-line sim-ulator are more stringent than those of an off-line simu-lator. First, the on-line simulator must be portable; thatis, the simulator must be able to model the behavior ofany disk drive that could be used in practice. Second, theon-line simulator must have automatic run-time configu-ration, since one cannot know the precise characteristics1Proceedings of the USENIX 2003 Annual Technical Conference, June 9–14, 2003, San Antonio, Texasof the underlying device when constructing the simula-tor; it is highly undesirable if a human administrator mustinteract with the simulator. Finally, the on-line simula-tor must have low overhead; the computation and mem-ory overheads of an on-line simulator must be minimizedsuch that the simulator does not adversely impact systemperformance.In addition to the complexity it introduces, an on-linesimulator also provides ample opportunities for simplifi-cation. First, the on-line simulator has the opportunity toobserve the run-time behavior of the device; not only doesthis allow the simulator to configure itself on the fly, it alsoallows the simulator to adjust to changes in the behavior ofthe device over time. Second, the on-line simulator can bespecialized for the problem domain in question. Finally,the on-line simulator does not need to be parameterizable;that is, since an on-line simulator is not exploring differentversions of the device itself, the simulator does not needto contain a functional model of the device.1.2 ContributionsWe address how to implement an I/O scheduler that isaware of the underlying disk technology in a simple,portable, and robust manner. To achieve this goal, we in-troduce the Disk Mimic, which meets the requirements ofan on-line simulator for disk scheduling. The Disk Mimicis based upon a simple table-based approach, in which in-put parameters to the simulated device are used to indexinto a table; the corresponding entry in the table gives thepredicted output for the device. A table-based approach isappropriate for