[發(fā)明專利]用于具有事務(wù)能力的排隊的方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201410098848.2
• 申請日: 2014-03-17
• 公開（公告）號: CN104063271B
• 公開（公告）日: 2017-04-12
• 發(fā)明（設(shè)計）人: J·勒威爾;I·C·愛德華茲;T·洛班;A·J·肖非爾德
• 申請（專利權(quán)）人: 國際商業(yè)機器公司
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 北京市金杜律師事務(wù)所11256
• 代理人: 酆迅,陳穎

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

本發(fā)明涉及在計算機系統(tǒng)中排隊的領(lǐng)域。具體而言，本發(fā)明涉及具有事務(wù)能力的排隊。

背景技術(shù)

消息隊列在計算中是廣泛使用的概念。具體而言，在消息接發(fā)中間件中，隊列可以用來緩沖在應(yīng)用之間發(fā)送的消息。這些隊列的性能經(jīng)常對于系統(tǒng)作為整體的性能是關(guān)鍵的；因此，許多研究已經(jīng)投入到創(chuàng)建高效實現(xiàn)方式中。

如果系統(tǒng)需要嚴格FIFO（先入先出）隊列，則存在寫入無鎖/無等待隊列的大量方式，該隊列將縮放至同時向這樣的隊列放入和從這樣的隊列取出消息的大量應(yīng)用。這樣的設(shè)計的缺點是它們往往復(fù)雜并且在其中有向隊列放入消息的單個應(yīng)用和從隊列取出消息的單個應(yīng)用的情況下比更簡單隊列更慢。這樣的算法通常依賴于用于執(zhí)行原子操作、比如比較和交換（CAS）（稍后討論）的能力。這些原子操作通常是單個機器指令并且在常規(guī)意義上未視為鎖。

嚴格FIFO隊列經(jīng)常是不夠的，例如JMS（消息服務(wù)）要求隊列支持事務(wù)，從而可以在兩級中向隊列放入/從隊列取出（多個）消息。首先放入/取出消息，然后（潛在地作為組）提交消息或者代之以取消所有放入/取出，這稱為回滾。為了保留消息順序（并且為了簡化應(yīng)當(dāng)快速且不應(yīng)失敗的提交操作），事務(wù)的實現(xiàn)經(jīng)常涉及到將事務(wù)中涉及到的消息留在隊列上、但是在“鎖”狀態(tài)中，從而它們不能被其它應(yīng)用所訪問。以這一方式實施事務(wù)的隊列不再FIFO；可以鎖在隊列的頭部/尾部的消息，并且可用于取回的第一消息可以實際上在消息列表的中間。Java和所有基于Java的商標(biāo)和標(biāo)志是Oracle和/或它的隸屬機構(gòu)的商標(biāo)或者注冊商標(biāo)。

就目前已知，不存在對于這一類型的非FIFO隊列工作的無鎖算法。

已知“兩鎖”FIFO隊列，該隊列允許應(yīng)用得以向隊列放入并且不同應(yīng)用同時可以取出，從而消息可以經(jīng)過隊列高效地用流發(fā)送。如果多個應(yīng)用有可能需要同時放入（或者取出），則放入（或者取出）權(quán)由時鐘序列化（因此兩個鎖是放入鎖和取出鎖）。Herb Sutter在http://www.ddj.com/cpp/211601363提供如何可以實施兩鎖隊列的說明。

在兩鎖FIFO隊列中，無串行化出現(xiàn)于放入器與取出器之間——取出器無論放入器正在做什么都總是取出在隊列上的第一消息。在提到的非FIFO的支持事務(wù)的隊列中，不可能有這樣的隔離。取出應(yīng)用需要高效地找到待取出的消息，并且如果放入應(yīng)用在放入應(yīng)用正在檢查的在隊列中的位置“之前”提交消息，則取出器必須代之以發(fā)現(xiàn)該消息。

支持事務(wù)為原子，這意味著如果在單個事務(wù)中提交向隊列放入的兩個消息，則必須先取出先放入的消息。這強調(diào)需要在放入器與取出器之間的高效通信。如果取出器只是逐個檢查在隊列上的消息，在它在事務(wù)中發(fā)現(xiàn)第一消息時，它可能仍然被鎖，但是到這時第二消息被檢查（如果提交已經(jīng)出現(xiàn)），繼而該消息可以為可用，并且可能從隊列取出錯誤消息。

因此，在本領(lǐng)域中需要解決前述問題。

發(fā)明內(nèi)容

根據(jù)本發(fā)明的第一方面，提供一種用于具有事務(wù)能力的排隊的方法，該方法包括：提供具有有序消息列表的隊列；在隊列內(nèi)提供取出光標(biāo)操作，以指向用于取出應(yīng)用開始搜尋要取回的消息的當(dāng)前開始位置；如果存在多于一個放入應(yīng)用，則提供用于放入操作的第一鎖以保證一次僅一個應(yīng)用正在向隊列放入；如果存在多于一個取出應(yīng)用，則提供用于取出操作的第二鎖以保證一次僅一個應(yīng)用正在從隊列取出；在放入與取出應(yīng)用之間進行同步，以檢查并更新取出光標(biāo)操作。

該方法可以包括放入應(yīng)用在它提交比光標(biāo)的當(dāng)前位置更早的消息時使用用于倒回光標(biāo)的指令。該方法可以包括取出應(yīng)用使用用于向前移動光標(biāo)的指令。

取出光標(biāo)操作可以包括由用于同步的原子指令使用的一個或者兩個存儲器字。

在一個實施例中，隊列可以是單鏈接列表，并且可以通過對在隊列上的每個消息進行編號來提供有序消息列表。取出光標(biāo)操作可以使用：指向搜索應(yīng)當(dāng)在隊列上開始的消息的指針；以及在隊列上的消息的順序編號。同步可以使用雙寬度比較和交換（DWCAS）操作，并且取得光標(biāo)操作包括用于指針的兩個存儲器字和消息的順序編號。

在另一實施例中，隊列可以是以索引充當(dāng)指針和順序編號二者的數(shù)據(jù)結(jié)構(gòu)；并且取出光標(biāo)操作可以指向數(shù)據(jù)結(jié)構(gòu)的索引。同步可以使用比較和交換CAS操作，并且取出光標(biāo)操作包括用于索引的一個存儲器字。

同步可以備選地使用對取出光標(biāo)操作的鎖。

如果存在單個放入應(yīng)用，則可以不提供第一鎖；如果存在單個取出應(yīng)用，則可以不提供第二鎖；并且在這些情況下，同步可以圍繞取出光標(biāo)操作。

該方法可以包括提供虛消息以防止空隊列。