微信服务号

微信订阅号

2025-4-24- 12
Home > Archive>Volume 21, Issue 8, 2010 >1820-1833
PDF HTML XML Export Cite reminder
File Prefetching Algorithm for Concurrent Streams
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [24]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    This paper proposes and implements a demand prefetching algorithm, which uses relaxed sequentiality criteria as well as page and page cache states as reliable sources of information. It can discover and prefetch sequential streams mixed in random accesses. It can also support the interleaved access patterns created by concurrent sequential reads on one file descriptor. Experimental results show that it performs much better than legacy Linux readahead: sequential reading intermixed with random ones are faster by 29%; I/O throughput of interleaved streams could be 4~27 times better, with application visible I/O latencies improved by up to 35 times. This demand prefetching algorithm has been adopted by Linux kernel 2.6.24.

    Reference
    [1] Shriver E, Small C, Smith KA. Why does file system prefetching work? In: Proc. of the Annual Technical Conf. on 1999 USENIX Annual Technical Conf. (ATEC’99). Berkeley: USENIX Association, 1999. 71?84.
    [2] Schmid P. 15 years of hard drive history: Capacities outran performance. 2006. http://www.tomshardware.com/reviews/15-years- of-hard-drive-history,1368.html
    [3] Kroeger TM, Long DDE. Design and implementation of a predictive file prefetching algorithm. In: Proc. of the General Track: 2002 USENIX Annual Technical Conf. Berkeley: USENIX Association, 2001. 105?118.
    [4] Lei H, Duchamp D. An analytical approach to file prefetching. In: Proc. of the 1997 USENIX Annual Technical Conf. Berkeley: USENIX Association, 1997. 275?288.
    [5] Paris JF, Amer A, Long DDE. A stochastic approach to file access prediction. In: Proc. of the Int’l Workshop on Storage Network Architecture and Parallel I/Os. New York: ACM Press, 2003. 36?40.
    [6] Whittle GAS, Paris JF, Amer A, Long DDE, Burns R. Using multiple predictors to improve the accuracy of file access predictions. In: Proc. of the 20th IEEE/11th NASA Goddard Conf. on Mass Storage Systems and Technologies (MSS 2003). Washington: IEEE Computer Society Press, 2003. 230?240.
    [7] Li ZM, Chen ZF, Zhou YY. Mining block correlations to improve storage performance. ACM Trans. on Storage, 2005,1(2): 213?245. [doi: 10.1145/1063786.1063790]
    [8] Cao P, Felten EW, Karlin AR, Li K. Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling. Trans. on Computer Systems, 1996,14(4):311?343. [doi: 10.1145/235543.235544]
    [9] Patterson RH, Gibson GA, Ginting E, Stodolsky D, Zelenka J. Informed prefetching and caching. In: Proc. of the 15th ACM Symp. on Operating Systems Principles. New York: ACM Press, 1995. 79?95.
    [10] Patterson RH, Gibson GA, Satyanarayanan M. A status report on research in transparent informed prefetching. ACM SIGOPS Operating Systems Review, 1993,27(2):21?34. [doi: 10.1145/155848.155855]
    [11] Chang F, Gibson GA. Automatic I/O hint generation through speculative execution. In: Proc. of the 3rd USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 1999. 1?14.
    [12] Fraser K, Chang F. Operating system I/O speculation: How two invocations are faster than one. In: Proc. of the General Track: 2003 USENIX Annual Technical Conf. Berkeley: USENIX Association, 2003. 325?338.
    [13] Brown AD, Mowry TC, Krieger O. Compiler-Based I/O prefetching for out-of-core applications. ACM Trans. on Computer Systems, 2001,19(2):111?170. [doi: 10.1145/377769.377774]
    [14] Papathanasiou AE, Scott ML. Aggressive prefetching: An idea whose time has come. In: Proc. of the 10th Workshop on Hot Topics in Operating Systems (HotOS). Berkeley: USENIX Association, 2005. 6?10.
    [15] Cao P, Felten EW, Karlin AR, Li K. A study of integrated prefetching and caching strategies. In: Proc. of the 1995 ACM SIGMETRICS Joint Int’l Conf. on Measurement and Modeling of Computer Systems. New York: ACM Press, 1995. 188?197.
    [16] Dini G, Lettieri G, Lopriore L. Caching and prefetching algorithms for programs with looping reference patterns. The Computer Journal, 2006,49(1):42?61. [doi: 10.1093/comjnl/bxh140]
    [17] Gill BS, Modha DS. SARC: Sequential prefetching in adaptive replacement cache. In: Proc. of the USENIX Annual Technical Conf. Berkeley: USENIX Association, 2005. 293?308.
    [18] Butt AR, Gniady C, Hu YC. The performance impact of kernel prefetching on buffer cache replacement algorithms. IEEE Trans. on Computers, 2007,56(7):889?908. [doi: 10.1109/TC.2007.1029]
    [19] Li CP, Shen K. Managing prefetch memory for data-intensive online servers. In: Proc. of the 4th Conf. on USENIX Conf. on File and Storage Technologies. (FAST 2005). Berkeley: USENIX Association, 2005. 253?266.
    [20] Gill BS, Bathen LAD. Optimal multistream sequential prefetching in a shared cache. ACM Trans. on Storage, 2007,3(3): 10:1?10:27. [doi: 10.1145/1288783.1288789]
    [21] Li CP, Shen K, Papathanasiou AE. Competitive prefetching for concurrent sequential I/O. In: Proc. of the ACM SIGOPS/EuroSys European Conf. on Computer Systems 2007. New York: ACM Press, 2007. 189?202.
    [22] Liang S, Jiang S, Zhang XD. STEP: Sequentiality and thrashing detection based prefetching to improve performance of networked storage servers. In: Proc. of the 27th Int’l Conf. on Distributed Computing Systems (ICDCS 2007). Washington: IEEE Computer Society Press, 2007. 64?73.
    [23] Wu FG, Xi HS, Xu CF. On the design of a new linux readahead framework. ACM SIGOPS Operating Systems Review, 2008, 42(5):75?84.
    [24] Wu FG, Xi HS, Li J, Zou NH. Linux readahead: Less tricks for more. In: Proc. of the Linux Symp., Vol.2. 2007. 273?284.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

吴峰光,奚宏生,徐陈锋.一种支持并发访问流的文件预取算法.软件学报,2010,21(8):1820-1833

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 07,2008
  • Revised:February 24,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038030Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063