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

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

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

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

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

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