[發(fā)明專利]并發(fā)非阻塞無鎖隊(duì)列及其實(shí)施方法和裝置

有效

• 申請?zhí)枺?/td>: 200710167568.2
• 申請日: 2007-10-26
• 公開（公告）號: CN101183304A
• 公開（公告）日: 2008-05-21
• 發(fā)明（設(shè)計）人: D·A·克里斯坦森
• 申請（專利權(quán)）人: 國際商業(yè)機(jī)器公司
• 主分類號: G06F5/10
• 分類號: G06F5/10
• 代理公司: 北京市金杜律師事務(wù)所
• 代理人: 朱海波

技術(shù)領(lǐng)域

本發(fā)明一般地涉及數(shù)字?jǐn)?shù)據(jù)處理領(lǐng)域。具體而言，本發(fā)明涉及利用處理器同步原語如加載鏈接/條件存儲(load-linked/storeconditional，LL-SC)的并發(fā)非阻塞無鎖(non-blocking，lock?free)先進(jìn)先出(FIFO)隊(duì)列。

背景技術(shù)

在二十世紀(jì)后半葉，開始出現(xiàn)了稱之為信息革命的現(xiàn)象。盡管信息革命是在范圍上比任一事件或者機(jī)器都更廣泛的歷史性發(fā)展，但是沒有哪個設(shè)備比數(shù)字電子計算機(jī)更能代表信息革命。毋庸置疑，計算機(jī)系統(tǒng)的發(fā)展已經(jīng)是一場革命。年復(fù)一年，計算機(jī)系統(tǒng)增長更快、存儲更多數(shù)據(jù)并提供更多應(yīng)用給它們的用戶。

現(xiàn)代計算機(jī)系統(tǒng)通常包括至少一個中央處理單元(CPU)以及為了存儲、獲取和傳送信息而必需的支持硬件如通信總線和存儲器。它也包括為了與外界通信而必需的硬件如輸入/輸出控制器或者存儲控制器以及與之附接的設(shè)備如鍵盤、監(jiān)視器、磁帶驅(qū)動器、磁盤驅(qū)動器、耦合到網(wǎng)絡(luò)的通信線路等。該一個或者多個CPU是該系統(tǒng)的核心。它們執(zhí)行如下指令，這些指令包括計算機(jī)程序并指引其它系統(tǒng)組件的操作。

通常通過增加并行性并且具體通過利用多個CPU(也稱為處理器)來提高計算機(jī)系統(tǒng)的整體速度。在集成電路芯片上封裝各個處理器的成本并不高，這已經(jīng)使多處理器系統(tǒng)成為現(xiàn)實(shí)，雖然這樣的多個處理器給系統(tǒng)增添了多重的復(fù)雜性。

從計算機(jī)硬件的觀點(diǎn)來看，多數(shù)系統(tǒng)以基本上相同的方式操作。處理器能夠執(zhí)行很簡單的操作，比如算術(shù)、邏輯比較以及將數(shù)據(jù)從一個位置移動到另一位置。但是各操作執(zhí)行得都很快。處于多個級別上的復(fù)雜軟件指引計算機(jī)執(zhí)行為數(shù)眾多的這些簡單操作，使計算機(jī)能夠執(zhí)行復(fù)雜任務(wù)。通過使用具有增強(qiáng)功能的軟件以及更快的硬件來執(zhí)行基本上相同的一組很簡單的操作，使得被用戶認(rèn)為是計算機(jī)系統(tǒng)的新功能或者改進(jìn)功能的那些功能成為可能。

先進(jìn)先出(FIFO)隊(duì)列廣泛地用于并行應(yīng)用和操作系統(tǒng)中。應(yīng)用和進(jìn)程線程頻繁地使數(shù)據(jù)入列到FIFO隊(duì)列上以及使數(shù)據(jù)從FIFO隊(duì)列中出列。一般而言，F(xiàn)IFO隊(duì)列是如下數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)提供了包含數(shù)據(jù)的不同存儲器位置的有序列表。隊(duì)列的各不同存儲器位置通常稱為“節(jié)點(diǎn)”。為了使節(jié)點(diǎn)保持有序，各節(jié)點(diǎn)具有“next”指針，該指針標(biāo)識(即指向)隊(duì)列中下一節(jié)點(diǎn)的存儲器位置。隊(duì)列的第一個節(jié)點(diǎn)稱為“頭節(jié)點(diǎn)”而隊(duì)列的最后一個節(jié)點(diǎn)稱為“尾節(jié)點(diǎn)”。由于尾節(jié)點(diǎn)是隊(duì)列的最后一個節(jié)點(diǎn)，所以尾節(jié)點(diǎn)的“next”指針通常為NULL(空)。隊(duì)列具有標(biāo)識(即指向)頭節(jié)點(diǎn)的頭指針以及標(biāo)識(即指向)尾節(jié)點(diǎn)的尾指針。

通過在隊(duì)列的當(dāng)前尾節(jié)點(diǎn)之后插入節(jié)點(diǎn)來使該節(jié)點(diǎn)入列，使得入列的節(jié)點(diǎn)變成隊(duì)列的新尾節(jié)點(diǎn)。因而，為了使節(jié)點(diǎn)入列到隊(duì)列上，線程必須確定哪個節(jié)點(diǎn)是當(dāng)前尾節(jié)點(diǎn)。為了實(shí)現(xiàn)這一點(diǎn)，線程通常利用隊(duì)列的尾指針。

在隊(duì)列的頭部使節(jié)點(diǎn)出列，使得當(dāng)前頭節(jié)點(diǎn)出列而下一節(jié)點(diǎn)變成隊(duì)列的新頭節(jié)點(diǎn)。因而，為了使節(jié)點(diǎn)從隊(duì)列中出列，線程必須確定哪個節(jié)點(diǎn)是當(dāng)前頭節(jié)點(diǎn)。為了實(shí)現(xiàn)這一點(diǎn)，線程通常利用隊(duì)列的頭指針。

如上所述，應(yīng)用和進(jìn)程線程在FIFO隊(duì)列上使數(shù)據(jù)入列和出列。多個不同的此類線程可以進(jìn)行對隊(duì)列的并發(fā)使用。隊(duì)列的并發(fā)使用使得難以維持隊(duì)列的完整性。然而，必須針對隊(duì)列可能遇到的所有可能條件來維持隊(duì)列的完整性。

必須使得并發(fā)訪問同步以維持隊(duì)列的完整性。用于包括FIFO隊(duì)列的并發(fā)數(shù)據(jù)結(jié)構(gòu)的算法是阻塞或者非阻塞的。阻塞算法使得緩慢或者延遲的進(jìn)程(或者線程)可以不確定地防止更快的進(jìn)程(或者線程)完成對并發(fā)數(shù)據(jù)結(jié)構(gòu)的操作。非阻塞算法保證了如果一個或者多個激活進(jìn)程(或者線程)試圖執(zhí)行對并發(fā)數(shù)據(jù)結(jié)構(gòu)的操作則一些操作將在有限數(shù)目的步驟內(nèi)完成。非阻塞算法通常比阻塞算法更為優(yōu)選，因?yàn)楫?dāng)由于發(fā)生比如處理器調(diào)度搶先、頁面故障和高速緩存未命中這樣的事件而暫?；蛘哐舆t進(jìn)程(或者線程)時，阻塞算法會不利地經(jīng)歷明顯的性能下降。

已經(jīng)針對包括并發(fā)FIFO隊(duì)列的共享數(shù)據(jù)結(jié)構(gòu)提出了無鎖算法。無鎖算法使得可以對共享數(shù)據(jù)結(jié)構(gòu)進(jìn)行并發(fā)更新而無需牽涉到由被操作系統(tǒng)管理的鎖來保護(hù)的關(guān)鍵部分。無鎖同步的一些最普遍益處包括：

·比基于鎖的算法更高效；

·提高了多處理器機(jī)器上的可伸縮性；

·可用于幾乎所有包括中斷句柄的環(huán)境中；

·非阻塞實(shí)施自然地避免了優(yōu)先級反轉(zhuǎn)；

·協(xié)作技術(shù)保證了完成進(jìn)度，這不同于無效(unproductive)的自旋鎖。