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

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

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

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

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