微信服务号

微信订阅号

2025年5月30日 19:51 星期五
首页 > 过刊浏览>2010年第21卷第8期 >1820-1833
PDF HTML阅读 XML下载 导出引用 引用提醒
一种支持并发访问流的文件预取算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60774038 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2008AA01A317 (国家高技术研究发展计划(863)); the Intel Research Council Project under Grant No.4507345522 (英特尔研究委员会项目)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [24]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    设计并实现了一种按需预取算法,采用更为宽松的顺序性判决条件,并以页面和页面缓存的状态作为可靠的决策依据.它可以发现淹没在随机读中的顺序访问并进行有效的预读,支持对单个文件实例的并发访问而产生的交织访问模式.实验结果表明:相对于原Linux预读算法,该算法在随机干扰下的顺序读性能可提高29%;交织读的性能是传统算法的4~27倍;同时,应用程序可见延迟改善可达35倍.该算法已被Linux 2.6.24内核采用.

    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.

    参考文献
    [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.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:5642
  • 下载次数: 9348
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2008-06-07
  • 最后修改日期:2009-02-24
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19983637位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号