Sequential File Prefetching in Linux

Sequential File Prefetching in Linux

Fengguang Wu (Intel Corporation, China)
DOI: 10.4018/978-1-60566-850-5.ch011
OnDemand PDF Download:


Sequential prefetching is a well established technique for improving I/O performance. As Linux runs an increasing variety of workloads, its in-kernel prefetching algorithm has been challenged by many unexpected and subtle problems; As computer hardware evolves, the design goals should also be adapted. To meet the new challenges and demands, a prefetching algorithm that is aggressive yet safe, flexible yet simple, scalable yet efficient is desired. In this chapter, the author explores the principles of I/O prefetching and present a demand readahead algorithm for Linux. He demonstrates how it handles common readahead issues by a host of case studies. Both static, logic and dynamic behaviors of the readahead algorithm are covered, so as to help readers building both theoretical and practical views of sequential prefetching.
Chapter Preview

Principles Of I/O Prefetching

Bandwidth and latency are the two major aspects of I/O performance. For both metrics, there have been huge and growing performance gaps between disk, memory and processor. For example, the Intel(R) QuickPath(TM) Interconnect(QPI) can provide 12.8GB/s bandwidth per direction for processor-to-processor and processor-to-io data transfers. Today's DDR3-1333 memory has a theoretical bandwidth of 10666MB/s and response time of 12 nanoseconds, while a Seagate(R) 7200.11 SATA disk has a maximum sustained transfer rate of 105MB/s and average seek time of 8.5ms. Hence the performance gap as of 2009 is about 10 times for bandwidth and 7e5 times for latency. In this section, we demonstrate how I/O prefetching can help fill the performance gaps.

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
Yair Wiseman, Song Jiang
Chapter 1
Yair Wiseman, Joel Isaacson, Eliad Lubovsky, Pinchas Weisberg
The Linux kernel stack has a fixed size. There is no mechanism to prevent the kernel from overflowing the stack. Hackers can exploit this bug to put... Sample PDF
Kernel Stack Overflows Elimination
Chapter 2
Michael M. Swift
Despite decades of research in extensible operating system technology, extensions such as device drivers remain a significant cause of system... Sample PDF
Device Driver Reliability
Chapter 3
Arati Baliga, Pandurang Kamat, Vinod Ganapathy, Liviu Iftode
The authors demonstrate a new class of attacks and also present a novel automated technique to detect them. The attacks do not explicitly exhibit... Sample PDF
Identifying Systemic Threats to Kernel Data: Attacks and Defense Techniques
Chapter 4
Art Taylor
With the rise of the Internet, computer systems appear to be more vulnerable than ever from security attacks. Much attention has been focused on the... Sample PDF
The Last Line of Defense: A Comparison of Windows and Linux Authentication and Authorization Features
Chapter 5
Song Jiang
Most computer systems use the global page replacement policy based on the LRU principle to reduce page faults. The LRU principle for the global page... Sample PDF
Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing
Chapter 6
Song Jiang
As the hard disk remains as the mainstream on-line storage device, it continues to be the performance bottleneck of data-intensive applications. One... Sample PDF
Application of both Temporal and Spatial Localities in the Management of Kernel Buffer Cache
Chapter 7
Moses Reuven, Yair Wiseman
A technique for minimizing the paging on a system with a very heavy memory usage is proposed. When there are processes with active memory... Sample PDF
Alleviating the Thrashing by Adding Medium- Term Scheduler
Chapter 8
Timothy R. Leschke
There are two forces that are demanding a change in the traditional design of operating systems. One force requires a more flexible operating system... Sample PDF
The Exokernel Operating System and Active Networks
Chapter 9
Daniel G. Waddington, Nilabja Roy, Douglas C. Schmidt
As software-intensive systems become larger, more parallel, and more unpredictable the ability to analyze their behavior is increasingly important.... Sample PDF
Dynamic Analysis and Profiling of Multithreaded Systems
Chapter 10
Feng Chen, Xiaoning Ding, Song Jiang
As the major secondary storage device, the hard disk plays a critical role in modern computer system. In order to improve disk performance, most... Sample PDF
Exploiting Disk Layout and Block Access History for I/O Prefetch
Chapter 11
Fengguang Wu
Sequential prefetching is a well established technique for improving I/O performance. As Linux runs an increasing variety of workloads, its... Sample PDF
Sequential File Prefetching in Linux
Chapter 12
Wei Wu, Kian-Lee Tan
Caching and prefetching are two effective ways for mobile peers to improve access latency in mobile environments. With short-range communication... Sample PDF
Peer-Based Collaborative Caching and Prefetching in Mobile Broadcast
Chapter 13
Yannis Smaragdakis, Scott Kaplan
Replacement algorithms are a major component of operating system design. Every replacement algorithm, however, is pathologically bad for some... Sample PDF
Adaptive Replacement Algorithm Templates and EELRU
Chapter 14
Moshe Itshak, Yair Wiseman
The concept of Super-Paging has been wandering around for more than a decade. Super-Pages are supported by some operating systems. In addition... Sample PDF
Enhancing the Efficiency of Memory Management in a Super-Paging Environment by AMSQM
About the Contributors