[發明專利]一種多讀多寫無鎖隊列實現方法

在審

• 申請號: 201911343744.2
• 申請日: 2019-12-24
• 公開（公告）號: CN111143079A
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 李朝銘;王建華
• 申請（專利權）人: 浪潮軟件股份有限公司
• 主分類號: G06F9/52
• 分類號: G06F9/52;G06F9/54
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 闞恭勇

本發明提供一種多讀多寫無鎖隊列實現方法，屬于數據處理技術領域，先定義一套一讀一寫無鎖隊列結構及該隊列寫API和讀API，一讀一寫無鎖隊列具體由循環鏈表實現；然后根據最大并發度及多讀多寫中的最大值N，創建N個相對獨立的一讀一寫無鎖隊列，定義一個N個元素組成的結構指針數組，該結構指針數組分別指向一個一讀一寫無鎖隊列中的節點地址；最后根據該指針數組定義多讀多寫隊列寫API和讀API，可以滿足多線程環境中無鎖并發讀寫需要。

技術領域

本發明涉及數據處理技術，尤其涉及一種多讀多寫無鎖隊列實現方法。

背景技術

隊列是一種常用的數據結構，用于服務解耦、異步處理提高性能等，隊列的使用通常有生產者和消費者之分，一個隊列可以有一個生產者和一個消費者，簡稱一讀一寫，也可以有多個生產者和多個消費者，簡稱多讀多寫。無論一讀一寫模式或多讀多寫模式，在多線程環境中都可能會面臨對隊列同一消息的并發讀寫問題，并發讀寫會引起數據錯亂，從而隊列不能正確工作。

為了解決并發讀寫問題，一般會引入鎖，如pthread的互斥鎖或系統更低級的原子鎖。鎖的引入解決了并發讀寫問題，然而會產生新的問題即性能降低問題，對隊列的并發操作越多性能降低的越多，從而使隊列不能滿足性能需要。為此有人引入了一讀一寫無鎖隊列的概念，即隊列并發操作不用鎖，這種方式性能很高，但僅用于一讀一寫并發模式。人們于是繼續改造，提出了多讀一寫、一讀多寫模式或多讀多寫模式，一些實現實際使用的是低級的原子鎖，比pthread的互斥鎖性能高些，但仍然有并發性能問題，并不是真正的無鎖隊列，有些實現并未達到真正的并發，在并發時會有數據錯誤問題。

發明內容

為了解決以上技術問題，本發明提出了一種多讀多寫無鎖隊列實現方法，在成功實現一讀一寫無鎖隊列的基礎上，將多個一讀一寫無鎖隊列邏輯上組成一個大的無鎖隊列，并支持多讀多寫無鎖并發操作。

本發明是一種多讀多寫無鎖隊列實現方法，在成功實現一讀一寫無鎖隊列的基礎上，將多個一讀一寫無鎖隊列邏輯上組成一個大的無鎖隊列，并支持多讀多寫無鎖并發操作。

它是一種真正的無鎖操作并支持多讀多寫無鎖并發高性能操作，能適應多線程并發處理需要。

本發明的技術方案是：

一種多讀多寫無鎖隊列實現方法,

先定義一套一讀一寫無鎖隊列結構及該隊列寫API和讀API，一讀一寫無鎖隊列具體由循環鏈表實現；然后根據最大并發度及多讀多寫中的最大值N，創建N個相對獨立的一讀一寫無鎖隊列，定義一個N個元素組成的結構指針數組，該結構指針數組分別指向一個一讀一寫無鎖隊列中的節點地址；最后根據該指針數組定義多讀多寫隊列寫API和讀API。

進一步的，

最大并發度N是可以設定的，每個一讀一寫無鎖隊列可容納的最多消息個數也是可以設置的，根據用戶設置的這兩個參數生成多讀多寫無鎖隊列。

進一步的，

多讀多寫隊列寫API的參數包含寫線程Id號、消息Id、消息地址、消息大小四個參數，也可根據需要擴充，每個寫線程的Id號是唯一的。

多讀多寫隊列寫API根據線程的Id號唯一選擇一個一讀一寫無鎖隊列，并將消息寫入該無鎖隊列中且返回寫的結果，寫線程和一讀一寫無鎖隊列是一一對應的。

進一步的，

多讀多寫隊列讀API的參數包含讀線程Id號、消息Id地址、消息地址、消息大小地址四個參數，也可根據需要擴充，每個讀線程的Id號是唯一的。

多讀多寫隊列讀API根據線程的Id號唯一選擇一個一讀一寫無鎖隊列，并將從該無鎖隊列中讀出一條消息且返回讀的結果，讀線程和一讀一寫無鎖隊列是一一對應的。

進一步的，