Linux內(nèi)核中的預(yù)取算法.pdf

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

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

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

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