[發(fā)明專利]一種基于單進(jìn)單出無鎖隊列的隨機取出對象的方法

有效

• 申請?zhí)枺?/td>: 202110294432.8
• 申請日: 2021-03-19
• 公開（公告）號: CN113176896B
• 公開（公告）日: 2022-12-13
• 發(fā)明（設(shè)計）人: 陳穩(wěn)
• 申請（專利權(quán)）人: 中盈優(yōu)創(chuàng)資訊科技有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 上海嘉藍(lán)專利代理事務(wù)所(普通合伙) 31407
• 代理人: 金波

1.一種基于單進(jìn)單出無鎖隊列的隨機取出對象的方法，其特征在于，該方法包括：

對size大小的對象池進(jìn)行內(nèi)存布局，包括：

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

設(shè)置對象指針數(shù)組p[size]中的各個指針指向，包括：

設(shè)置對象指針數(shù)組p[size]中的各個指針，指向?qū)ο髮嶓w數(shù)組obj[size]中對應(yīng)下標(biāo)處的對象；

設(shè)置對象實體數(shù)組obj[size]中每個對象實體攜帶的隱式尾部pos指向，包括：

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

將對象指針數(shù)組p[size]實現(xiàn)為無鎖環(huán)形隊列；

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

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

執(zhí)行釋放操作前的使用區(qū)間狀態(tài)；

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

交換p[N]此時指向的對象obj[M]與p[TAIL]此時指向的對象obj[T]對象的pos值，包括：

交換p[N]此時指向的對象obj[M]與p[TAIL]此時指向的對象obj[T]的pos值，最終形成p[N]與obj[T]，以及p[TAIL]與obj[M]的相互映射關(guān)系，將釋放p[N]操作轉(zhuǎn)換為釋放p[TAIL]操作。

2.根據(jù)權(quán)利要求1所述的基于單進(jìn)單出無鎖隊列的隨機取出對象的方法，其特征在于，將對象指針數(shù)組p[size]劃分為使用區(qū)間[HEAD,TAIL]和空閑區(qū)間，包括：

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

3.根據(jù)權(quán)利要求1所述的基于單進(jìn)單出無鎖隊列的隨機取出對象的方法，其特征在于，執(zhí)行釋放操作前的使用區(qū)間狀態(tài)，包括：

將p[N]此時指向的對象記作obj[M]，將p[TAIL]此時指向的對象記作obj[T]，此時消費者線程此時只有p[N]的值，沒有p[N]本身的地址，通過obj[M].pos即可獲取N值。

4.根據(jù)權(quán)利要求1所述的基于單進(jìn)單出無鎖隊列的隨機取出對象的方法，其特征在于，交換p[N]與p[TAIL]的值，包括：

交換p[N]與p[TAIL]的值，使p[TAIL]指向期望釋放的對象obj[M]，p[N]指向p[TAIL]原本指向的對象obj[T]。

5.根據(jù)權(quán)利要求1所述的基于單進(jìn)單出無鎖隊列的隨機取出對象的方法，其特征在于，所述對象實體數(shù)組obj[size]中每個對象實體與對象指針數(shù)組p[size]中的各個指針一一映射，并且對象指針數(shù)組p[size]的使用區(qū)間是連續(xù)的。