[發明專利]構造數據隊列的方法、裝置及從其插入和消費對象的方法

有效

• 申請號: 201410132403.1
• 申請日: 2014-04-02
• 公開（公告）號: CN104978321B
• 公開（公告）日: 2018-12-04
• 發明（設計）人: 羅實;封仲淹;陳昱
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F8/30
• 代理公司: 北京清源匯知識產權代理事務所(特殊普通合伙) 11644
• 代理人: 馮德魁

1.一種構造數據隊列的方法，其特征在于，包括:

設置環形數組，所述環形數組具有規定數個用于存儲規定格式的數據的存儲單元，稱為槽位，首尾槽位銜接，形成環形，所述規定數用size表示；向該環形數組中存儲數據對象稱為插入對象，從該環形數組中拉取數據對象并清空相應的槽位稱為消費對象；所述插入和消費均沿環形數組規定方向順序操作，所述規定方向稱為操作方向；所述size為2的指數倍；

為環形數組設置生產者計數器和消費者計數器，所述生產者計數器對向環形數組插入對象進行計數；所述消費者計數器對從環形數組消費對象進行計數；所述生產者計數器和消費者計數器為初始值為零的遞增變量。

2.根據權利要求1所述的構造數據隊列的方法，其特征在于，所述生產者計數器和消費者計數器為遞增變量具體是，所述生產者計數器和消費者計數器均為64字節填充的長整形嚴格遞增變量。

3.根據權利要求1-2任一項所述的構造數據隊列的方法，其特征在于，對環形數組中的槽位賦予從0開始沿操作方向遞增的槽位值。

4.一種向數據隊列中插入對象的方法，其特征在于，所述數據隊列為根據上述權利要求1-3任一項所述的構造數據隊列的方法構造的數據隊列；該向數據隊列中插入對象的方法包括：

獲取數據隊列中生產者計數器的值；

原子遞增生產者計數器的值，作為生產者計數器的當前值；

獲取數據隊列中消費者計數器的當前值；

根據生產者計數器的當前值與消費者計數器的當前值判斷是否可以插入對象；若判斷結果為是，則進入下一步；

向數據隊列中指定槽位插入對象；

將生產者計數器的當前值作為最新的生產者計數器的值發布。

5.根據權利要求4所述的向數據隊列中插入對象的方法，其特征在于，所述原子遞增生產者計數器的值，作為生產者計數器的當前值的步驟采用下述方法：

若生產者為一個，將生產者計數器的值原子遞增1，作為生產者計數器的當前值；

若生產者為至少兩個，則對生產者計數器的值以CAS原子操作的方式進行所述原子遞增，操作結果作為生產者計數器的當前值。

6.根據權利要求4所述的向數據隊列中插入對象的方法，其特征在于，所述根據生產者計數器的當前值與消費者計數器的當前值判斷是否可以插入對象，包括：

作生產者計數器的當前值減去消費者計數器的當前值的差運算；

判斷運算結果是否等于size值，若是，則是否可以插入對象的判斷結果為否，并進入判斷是否等待步驟；若否，則所述是否可以插入對象的判結果為是；

判斷是否等待步驟的判斷結果如果為是，則繼續作前述差運算；判斷結果如果為否，則結束插入對象的操作。

7.根據權利要求4所述的向數據隊列中插入對象的方法，其特征在于，當所述數據隊列為根據權利要求1的構造數據隊列的方法構造的數據隊列時，向數據隊列中指定槽位插入對象的步驟中，以下述方式確定所述指定槽位：

以生產者計數器當前值的二進制形式與size-1的值的二進制形式進行按位與運算，計算的結果賦予插入槽位值Slot_put，該插入槽位值Slot_put即為所述指定槽位。

8.一種從數據隊列中消費對象的方法，其特征在于，所述數據隊列為根據上述權利要求1-3任一項所述的構造數據隊列的方法構造的數據隊列；該從數據隊列中消費對象的方法包括：

獲取生產者計數器及消費者計數器的值；

根據上述計數器的值，判斷是否可以消費對象；若是，則進入下一步；

將消費者計數器的值原子遞增，作為消費者計數器的當前值；

根據消費者計數器的當前值，確定消費對象相對應的槽位值；

從相對應的槽位值的槽位中消費對象。