| Despite impressive advances in file system throughput resulting from technologies such as high-bandwidth networks and hard disk arrays, file system latency has not improved and in many cases has become worse. To complicate matters, emerging technologies such as wireless computing, widely distributed telecomputing environments, and wide area file systems are growing in use but often offer higher latency and lower performance than standard file systems. Consequently, file system I/O remains one of the major bottlenecks to computer system performance (Ous90) and is expected to remain a major bottleneck for the foreseeable future.; This dissertation describes the design, implementation and evaluation of an automated predictive approach towards reducing file latency. Automatic Prefetching uses past file accesses to predict future file system requests. The objective is to copy the data into the local cache in advance of the request for the data, effectively masking access latencies. We turn the file cache from a repository of recently used data into a staging area for data about to be used.; Our algorithms are able to use the recent history of file accesses to make heuristic predictions of future requirements while "forgetting" less useful history from the distant past. Our algorithms predict which files will be needed soon, which portions of the predicted files are required and when that data will be needed. The algorithms are computationally inexpensive and require little storage.; We have developed and tested a simulator to tune the algorithms and developed a working prototype to test its real world performance. Further, we compare our results to both standard nonprefetching file systems and a prefetching file system that makes near optimal predictions. Results from the prototype show that prefetching can reduce the time needed by realistic applications to read a set of files by over 50%. |
