Linux內核中的預取算法.pdf

1、計算機系統(tǒng)中最嚴重的不平衡來自CPU與I/O之間持續(xù)擴大的性能差距。磁盤傳輸帶寬的改善速度跟不上CPU計算能力的增長，數據訪問延遲的改善更是嚴重地滯后。預取作為提升磁盤I/O性能的一種重要技術，可以有效地將來自應用程序的同步的小I/O轉化為異步的大I/O，從而減少訪問延遲，并促成I/O的并行化。 對順序文件訪問的預讀是現代操作系統(tǒng)的一項必備功能。Linux內核在虛擬文件系統(tǒng)層實現了一個通用的文件預讀算法。隨著Linux的廣泛應用

2、和在越來越多樣化的負載環(huán)境中運行，它的預取算法遇到了很多微妙問題的挑戰(zhàn)。例如：當內存壓力較大的時候，預讀頁面會被過早地回收，出現預讀抖動；對已經緩存在內存中的頁面進行預讀操作是毫無意義的；被中斷的讀請求及其重試讀可能使順序性檢測算法陷于混亂。本文設計了一個模塊化的按需預讀框架。通過引入一對預取觸發(fā)條件，使一些原本復雜的問題以統(tǒng)一和自然的方式得到了處理。在此基礎上，對訪問模式的檢測和預讀邏輯被簡化，并可以獨立地進行擴展。 隨著多核

3、、多線程處理器成為新的硬件設計方向，軟件的并行化也隨之成為新的潮流，并帶來更多的并發(fā)I/O。如何在交織的并發(fā)I/O中有效地識別和處理順序流，已經成為預取算法所面臨的一個現實挑戰(zhàn)。我們在按需預讀框架的基礎上，設計并實現了被動和主動兩種順序流的檢測和預讀算法，引入頁面狀態(tài)作為對不可靠的預讀狀態(tài)變量的必要補充，采用更寬松的順序性判決條件。它們可以有效地支持：淹沒在隨機讀中的順序訪問；對單個文件實例的并發(fā)訪問產生的交織訪問模式；稀疏的順序讀；局

4、部重排序的NFS順序讀；高密度的隨機讀區(qū)域；對大矩陣的列掃描，等等。 被動算法在單線程的情況下不會造成額外的開銷，而在多線程情況下的時空復雜度與并發(fā)度的大小無關。主動算法通過高效的檢測邏輯，確保發(fā)現順序流和隨機訪問的熱點區(qū)域，自適應的預讀大小可以避免預讀抖動，因而往往可以獲得更好的性能。實驗表明本文算法相對傳統(tǒng)預讀有突出的優(yōu)勢：在發(fā)生預讀抖動的情況下，網絡輸出流量可達到傳統(tǒng)算法的3～4倍；在隨機干擾之下的順序讀性能可提高29％；