Rate-Controlled Scheduling of Expired Writes for Volatile Caches

Conventional disk schedulers use the same algorithm to schedule synchronous and asynchronous requests. To reap more performance, they should be scheduled differently. Asynchronous requests can be queued and delayed in the buffer cache and scheduled at times that improve disk utilization. In future systems, with larger memories and, thus, larger buffer caches in which more requests can be queued and delayed, further performance improvements can be attained. However, since main memory is volatile, small delays are acceptable but maximum queue latency must be bounded, i.e., request starvation or prolonged delays must be avoided. Accordingly, using the performance criteria of disk utilization and maximum queue latency, this paper analyzes the performance of six well-known disk schedulers using detailed I/O traces of the behavior of realistic benchmarks that issue asynchronous I/O requests. Then it proposes a new disk scheduler, for asynchronous I/O, that enforces latency requirements while improving disk utilization. Five of the schedulers (including the proposed one) were implemented in the Linux 2.6 kernel; two are already included. Our performance analysis, which provides insights into the behavior of each scheduler that cannot be gleaned from the algorithms themselves, indicates that the proposed rate-controlled deadline-based CLOOK (RDCLOOK) scheduler is best for servicing asynchronous I/O requests