[發明專利]一種基于單進單出無鎖隊列的隨機取出對象的方法

有效

• 申請號: 202110294432.8
• 申請日: 2021-03-19
• 公開（公告）號: CN113176896B
• 公開（公告）日: 2022-12-13
• 發明（設計）人: 陳穩
• 申請（專利權）人: 中盈優創資訊科技有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 上海嘉藍專利代理事務所(普通合伙) 31407
• 代理人: 金波

本發明公開一種基于單進單出無鎖隊列的隨機取出對象的方法，其中，該方法包括：對size大小的對象池進行內存布局；將對象指針數組p[size]劃分為使用區間[HEAD,TAIL]和空閑區間；消費者線程取出p[N]指向的對象(N∈[HEAD,TAIL])，并且在使用完畢之后釋放。該方法相比于現有單進單出無鎖隊列，它多具備了“支持異步無鎖/同步隨機取出”、“已分配區間即隊列”和“空閑對象無須查找”三個特點，將現有單進單出無鎖隊列的應用場景擴展到“網絡會話管理”這類需求，并且還具有性能優勢。

技術領域

本發明涉及單進單出無鎖隊列領域，尤其是一種基于單進單出無鎖隊列的隨機取出對象的方法。

背景技術

單進單出無鎖隊列，是一種已經存在的算法，支持單生產者線程向HEAD位置添加對象，單消費者線程從TAIL位置取出對象，如圖1所示。

但是，現有單進單出無鎖隊列，同時也是FIFO(first in first out)隊列，即消費者線程只可以固定從TAIL位置取出對象，不可以越過TAIL位置，在[HEAD,TAIL)區間執行取出對象操作，如圖2所示。

發明內容

為克服現有單進單出無鎖隊列存在的上述問題，本發明提供一種基于單進單出無鎖隊列的隨機取出對象的方法，可以從[HEAD,TAIL]區間隨機取出對象。

為實現上述目的，本發明采用下述技術方案：

在本發明一實施例中，提出了一種基于單進單出無鎖隊列的隨機取出對象的方法，該方法包括：

對size大小的對象池進行內存布局；

將對象指針數組p[size]劃分為使用區間[HEAD,TAIL]和空閑區間；

消費者線程取出p[N]指向的對象(N∈[HEAD,TAIL])，并且在使用完畢之后釋放。

進一步地，對size大小的對象池進行內存布局，包括：

對象池前面部分為對象指針數組p[size]，后面部分為對象實體數組obj[size]；

設置對象指針數組p[size]中的各個指針指向；

設置對象實體數組obj[size]中每個對象實體攜帶的隱式尾部pos指向；

將對象指針數組p[size]實現為無鎖環形隊列。

進一步地，設置對象指針數組p[size]中的各個指針指向，包括：

設置對象指針數組p[size]中的各個指針，指向對象實體數組obj[size]中對應下標處的對象。

進一步地，設置對象實體數組obj[size]中每個對象實體攜帶的隱式尾部pos指向，包括：

讓對象實體數組obj[size]中每個對象實體攜帶一個隱式尾部pos，用于存儲指向該對象的指針，在對象指針數組p[size]中的下標值，使得對象池剛建立時，形成對象指針與對象實體的相互映射關系。

進一步地，將對象指針數組p[size]劃分為使用區間[HEAD,TAIL]和空閑區間，包括：

[HEAD,TAIL]為使用區間，指向生產者線程添加且未被消費者線程取出的對象，其余部分為空閑區間，指向空閑對象。

進一步地，消費者線程取出p[N]指向的對象(N∈[HEAD,TAIL])，并且在使用完畢之后釋放，包括：

執行釋放操作前的使用區間狀態；

交換p[N]與p[TAIL]的值；