簡易檢索 / 詳目顯示

研究生: 陳允聖
Chen,Yun-Sheng
論文名稱: 一個實用的檔案預先擷取方法於分散式檔案系統上之實現
A Practical Approach for File Prefetching in Distributed File System
指導教授: 黃冠寰
Hwang, Gwan-Hwan
林順喜
Lin, Shun-Shii
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2003
畢業學年度: 91
語文別: 中文
論文頁數: 68
中文關鍵詞: UnixLinux檔案預取快取分散式檔案系統
英文關鍵詞: Unix, Linux, File prefetching, Cache, Distributed file system
論文種類: 學術論文
相關次數: 點閱:213下載:1
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在Thin-client/Server系統架構下,任意一位使用者可透過區域網路,在任何一台Thin-client上存取遠端伺服主機內的服務。如同使用本機電腦一樣方便,使用者並不會感覺到他正在存取遠端檔案系統。黃冠寰博士提出的MAS TC/S乃是基於廣域網路上的Thin-client/Server系統架構,我們根據這個架構思考如何在廣域網路上解決因檔案提取誤失所造成的程式反應時間提升之問題。程式反應時間包含兩個部分,第一部份是取得所有程式執行時需要的資料檔案所花費的時間,第二部分是程式執行時間。由於程式執行時間一般而言為固定值,然取得程式執行所需之資料檔案所需花費的時間需視網路效能而定,在傳送大量的遠端資料時,往往會造成使用者的等待。因此若要降低使用者等待時間,則需加快反應時間,必須儘早取得檔案資料。現存的方法以檔案預取為主,透過過去的存取紀錄來分析未來可能需要存取的檔案資料,然後在程式執行前,預先取得所需的檔案,將它由遠端檔案伺服器上傳送到使用者所在之應用程式伺服主機上,加速反應時間。本篇論文提出一個方法進行檔案預取,根據過去的存取紀錄得到存取樣式,程式執行時所產生的存取紀錄將與過去的存取樣式進行比對,一旦符合便進行檔案預取。我們實驗的結果證明這一方法可有效提高檔案命中率並縮短程式執行時的延遲時間。

    In the Thin-client/Server system architecture, the user can access service of remote servers through local area network connections. The user will think that he is accessing the local personal computer, not the remote server. Dr. Gwan-Hwan Hwang proposes MAS TC/S—the wide-area-network-based Thin-client/Server. We will think about how to solve the problem of program response time increasing based on MAS TC/S. There are two parts in the program response time: one is the time that the program fetches all the data needed for executing; the other is the program execution time. Since the program execution time is the constant, the time that the program fetches all the data needed for executing depends on network bandwidth. Users will wait for program execution while the program is waiting for a large amount of data transferring. If we want to decrease the users’ waiting time, we need to increase the program response time. Hence, the system needs to fetch the needed data as soon as possible. The existing way is based on file prefetching. It will gain the future needed data by analyzing the past system access record, and before program executing, the server will prefetch the needed file for the program from the remote file server to the local application server. This paper proposes an algorithm for file prefetching. It will analyze the past system access record of program execution, and get the access pattern of the program. In the real-time access, if an application access pattern matches the existing access pattern, the file prefetching will do so. The result of the experiment proves that the algorithm in a simulator will increase file hit ratio and decrease the latency during program execution efficiently.

    中文摘要 1 ABSTRACT 2 1. 簡介 7 1.1. 背景與動機 7 1.2. 目標 9 1.3. 方法與步驟 10 1.4. 論文架構 10 2. 文獻探討 12 2.1. PROBABILITY GRAPH [11] 13 2.2. CONTEXT MODEL [12] 14 2.3. ACCESS TREE [4] 15 3. 系統架構 17 3.1. 檔案存取紀錄收集器(SYSTEM CALL TRACER) 17 3.2. 檔案存取記錄分析器(SYSTEM CALL ANALYZER) 19 3.3. 快取管理器(CACHE MANAGER) 20 4. 檔案預取機制與策略 22 4.1. 應用程式樹(APPLICATION TREE) 22 4.2. PATTERN TREE 30 4.3. APPLICATION TREE的比對演算法 34 4.3.1. 兩個application tree進行比對 34 4.3.2. 比對3個Application Trees 40 4.3.3. 比對N個Application Trees 41 4.4. 建立樣式樹表(PATTERN TREE TABLE) 41 4.4.1. 將Pattern Tree加入Pattern Tree Table中 42 4.4.2. 合併具有相同Prefix Pattern的Pattern Tree 43 4.5. 即時檔案預取機制(REAL-TIME FILE PREFETCHING MECHANISM) 45 4.5.1. 預取管理器(Prefetch Manager) 45 5. 模擬環境與實驗結果 48 5.1. 模擬器(SIMULATOR) 48 5.2. 模擬方法(SIMULATE METHOD) 48 5.3. 實驗結果 50 5.4. 實驗結果討論 55 6. 結論 61 7. 參考文獻 63 附錄A:攔截系統呼叫(INTERCEPT SYSTEM CALL) 66 A.1.修改LINUX KERNEL 66 A.2.採用KERNEL MODULE PROGRAMMING 66

    [1] Joel P. Kanter. Understanding Thin-Client/Server Computing. Microsoft Press, 1998.
    [2] Gwan-Hwan Hwang, San-Yih Hwang, Yun-Sheng, Chen, Jia-Qing Li. MAS TC/S: Roaming Thin Clients in a Wide Area Network with Transparent Working Environments. Proceedings of Advanced Technologies and Applications for Next Generation Information Communication Networks, 2002.
    [3] Elizabeth Shriver, Christopher Small, Keith A. Smith. Why Does File System Prefetching Work? Proceeding of the USENIX Annual Technical Conference, 1999.
    [4] Hui Lei, Dan Duchamp. An Analytical Approach to File Prefetching. Proceeding of the USENIX Annual Technical Conference, 1997.
    [5] P. Cao, E. W. Felten, A. Karlin, K. Li. A Study of Integrated Prefetching and Caching Strategies. Proceeding of 1995 ACM SIGMETRICS.
    [6] P. Cao, E. W. Felten, A. Karlin, K. Li. Implementation and Performance of Integrated Application-Controlled Caching, Prefetching and Disk Scheduling. Proceeding of First USENIX Symposium on Operating System Design and Implementation, 1994.
    [7] R. H. Patterson, G. A. Gibson, M. Satyanarayanan. A Status Report on Research in Transparent Informed Prefetching. Operating Systems Review, 1993.
    [8] R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, J. Zelenka. Informed Prefetching and Caching. Proceeding of Fifteenth Symposium on Operating System Principles, ACM, 1995.
    [9] 蘇元祺,分散式檔案系統存取行為之分析,交通大學資訊工程系碩士論文,1992。
    [10] 許凱平,分散式檔案系統評估環境,交通大學資訊工程系碩士論文,1993。
    [11] J. Griffioen and R.Appleton. Reducing File System Latency Using a Predictive Approach. In Proc. 1994 USENIX Summer Conf., pages 197-207, June 1994.
    [12] T. M. Kroeger and D. D. E. Long. Predicting Future File-System Actions from Prior Events. In Proc. 1996 USENIX Annual Technical Conf., pages 319-328, January 1996.
    [13] T. M. Kroeger and D. D. E. Long. The case for efficient file access pattern modeling. In Proceedings of the Seventh Workshop on Hot Topics in Operating Systems (HotOS-VII), IEEE, March 1999.
    [14] T. M. Kroeger and D. D. E. Long. Design and Implementation of a Predictive File Prefetching Algorithm. In Proceedings of the 2001 USENIX Annual Technical Conference.
    [15] T. C. Bell, J. G. Cleary, and I. H. Witten, Text Compression. Englewood Cliffs, New Jersey: Prentice Hall, 1990.
    [16] Arne Georg Gleditsch and Per Kristian Gjermshus, Cross-Referencing Linux, http://lxr.linux.no/.
    [17] Alessandro Rubini, Jonathan Corbet, and Allesandro Rubini, Linux Device Drivers, O'Reilly & Associates; 2nd edition (June 2001), ISBN: 0596000081.
    [18] Peter Jay Salzman and Ori Pomerantz. The Linux Kernel Module Programming Guide. 2001 Peter Jay Salzman.
    [19] Mark Mitchell, Jeffrey Oldham, and Alex Samuel, Advanced Linux Programming, New Riders, ISBN: 0735710430, 1st edition (june, 2001).

    QR CODE