Automatic inter-request interval estimation for scheduling disk I/O requests.

摘要

Although advances in technology have produced significantly higher disk speeds in recent years, there still exists a considerable performance gap between the processor and I/O subsystem. Request prefetching (and caching) has been one of the primary techniques used to reduce or eliminate I/O latency, thereby narrowing the performance gap. The effectiveness of prefetching strongly depends on the availability of information about future I/O requests. It is conjectured that, with little difficulty, information about future I/O requests can be obtained for most I/O intensive applications. In addition to requiring knowledge about data needed from disk, we believe that an accurate estimate of the time between successive read requests, also referred to as the inter-request interval, could be exploited to improve prefetching performance.; In this thesis, we study the inter-request intervals for a large and diverse set of I/O-intensive applications. The goal was to determine the feasibility of building an estimator and/or using an existing estimator to predict inter-request intervals. Based on the observations and analysis of the patterns formed by inter-request times, we found the majority could be classified and estimated fairly accurately, even with noise present. We also present an analysis of the structure of all applications for which source code was available. The objective was finding a correlation between the observed pattern in the inter-request times and the corresponding program structure, which would explain the predictability and determine the classes of applications possessed inter-request intervals that are amenable to estimation. The results of our analysis revealed a correlation between the observed patterns in the inter-request times and the loop structure of the applications that we examined. We then investigate the performance of two estimators, linear and decay that were adapted for our purposes, in predicting our classified patterns types. Our results illustrate that simple, accurate and computationally cheap estimators can be adapted and used to predict the identifiable classes of patterns in inter-request times. Finally, we present a simulation study that evaluates the utility of our technique for prefetching algorithms that (1) attempt to leverage deep queues to minimize application-level I/O waiting time and (2) orders requests in deep queues to maximize deadlines satisfied for soft-realtime applications. The results show that in select cases prediction of inter-request intervals provides an incremental gain over and above the performance achieved by generic prefetching algorithms.