多核系統(tǒng)上可伸縮的讀寫同步.pdf

1、隨著計算機(jī)硬件技術(shù)的飛速發(fā)展，單個處理器性能的增長已經(jīng)遇到了瓶頸，處理器個數(shù)的增長成為了提高單個計算機(jī)性能的主要發(fā)展方向。處理器個數(shù)的增長給應(yīng)用程序的性能提升帶來了新的機(jī)遇，也帶來了性能和正確性上的挑戰(zhàn)。
　　為了充分的利用這些處理器資源，操作系統(tǒng)和計算密集型的應(yīng)用正在向并行化的模型演進(jìn)。在一個并行的系統(tǒng)中，多個任務(wù)之間往往需要共享一些信息以進(jìn)行協(xié)同工作。為了使得多個任務(wù)可以正確有序的訪問這些共享信息，并行程序采用同步的方法對不同

2、任務(wù)的訪問進(jìn)行控制和限制，使得對每一個單獨的任務(wù)來說，這些共享信息都維持著某種一致性。
　　錯誤的使用同步可能會導(dǎo)致并行程序的錯誤或者影響其執(zhí)行的性能，設(shè)計一個易于正確使用，而又具有良好性能的同步原語是一個十分重要的問題。一個理想的同步原語應(yīng)該具有定義清晰的較強(qiáng)的語義保證，同時又盡量不影響應(yīng)用在多核系統(tǒng)上的可伸縮性。讀寫鎖是一種在語義上非常清晰的同步機(jī)制，它將對共享狀態(tài)的訪問者分為讀者和寫者兩個類別，在同一時刻，僅允許一個寫者進(jìn)入

3、臨界區(qū)更新共享狀態(tài)，或允許多個讀者同時進(jìn)入臨界區(qū)讀取共享狀態(tài)。因為其易于理解的語義，讀寫鎖在操作系統(tǒng)內(nèi)核以及并行應(yīng)用程序中得到了廣泛的應(yīng)用。
　　理論上說，因為讀寫鎖中的不同的讀者并沒有邏輯上的依賴，多個讀者在沒有寫者的情況下應(yīng)該可以快速的進(jìn)入和離開臨界區(qū)，并且不需要相互通信。事實上，現(xiàn)有的讀寫鎖設(shè)計中，往往讀者獲取鎖時要產(chǎn)生相互通信，或者使用昂貴的內(nèi)存屏障指令確保同步的正確性。這些設(shè)計限制了使用讀寫鎖的并行系統(tǒng)中讀者的可伸縮性和

4、吞吐量。
　　針對讀寫鎖的潛在性能問題，我們設(shè)計了一個高可伸縮的讀寫鎖算法PRWLock，這一算法巧妙利用了現(xiàn)代多核系統(tǒng)較短的內(nèi)存寫可見時間以及較小的核間中斷開銷，在滿足TSO內(nèi)存一致性模型的系統(tǒng)上實現(xiàn)了不需要共享信息以及內(nèi)存屏障的讀者鎖，同時保證了寫者鎖可接受的性能。
　　我們進(jìn)一步發(fā)現(xiàn)，在現(xiàn)代主流操作系統(tǒng)中的睡眠，喚醒機(jī)制會對同步機(jī)制的可伸縮性造成限制。當(dāng)多個因為某一條件而進(jìn)入睡眠的任務(wù)的喚醒條件達(dá)到時，喚醒操作是由單一

5、任務(wù)串行完成的。針對這一問題，我們設(shè)計了操作系統(tǒng)中可以并發(fā)的喚醒睡眠任務(wù)的機(jī)制PWake，并將其與PRWLock相結(jié)合實現(xiàn)了可伸縮性更好的讀寫同步機(jī)制。
　　為了驗證這兩種機(jī)制的有效性，我們在Linux的內(nèi)核和用戶態(tài)分別實現(xiàn)了PRWLock，并結(jié)合了PWake喚醒機(jī)制。我們將PRWLock應(yīng)用在了Linux內(nèi)核的地址空間管理機(jī)制上和一個用戶態(tài)的內(nèi)存數(shù)據(jù)庫中，多項實驗表明PRWLock具有同前人研究成果相似或更好的性能特性，并且更加