A Markov Decision Model for Low-LayerReadaheads

Readahead is an important technology forimproving IO performances. Its performance rests withthe prefetching policy. We introduced a Markov decisionmodel to describe low-level read processes and readaheadbehaviors such as those in modern operating system kernelswhen there is enough memory for caching. By usingthis model, it is possible to analyze various readaheads andfind better prefetching policies for specific read patternswith fewer practical tests. For illustration, we presentedan example about the ondemand readahead in linux kernel.The experiments show the model agrees with the realreadahead and the found policies significantly outperformthe current in real world.