[發明專利]一種基于無鎖緩沖區的數據采集方法

有效

• 申請號: 201510192246.8
• 申請日: 2015-04-21
• 公開（公告）號: CN104809027B
• 公開（公告）日: 2018-03-16
• 發明（設計）人: 王友釗;黃靜
• 申請（專利權）人: 浙江大學
• 主分類號: G06F9/52
• 分類號: G06F9/52
• 代理公司: 杭州求是專利事務所有限公司33200
• 代理人: 邱啟旺

技術領域

本發明涉及計算機應用領域，尤其涉及一種基于無鎖緩沖區的數據采集方法。

背景技術

在傳統的數據并發采集系統中，使用基于鎖的生產者—消費者緩沖區隊列模型，同一時間只能有一個線程獲得數據隊列緩沖區。基于鎖的數據結構能夠部分解決多線程并發的問題，但是由于鎖結構本身依賴于操作系統內核的實現方式，獲得鎖和釋放鎖設計線程從用戶態到內核態的上下文切換問題，而且鎖粒度大小難以控制，因此，在并發程序中的性能問題也逐漸顯露。

阻塞型算法試圖用不同形式的鎖(Lock)來解決并行算法遇到的訪問沖突問題，但是這種方法存在著死鎖、活鎖、條件競爭等多種多樣的問題，為了解決這些問題，另一種并行算法——非阻塞型算法被提出來。非阻塞型算法一般要滿足如下的前進條件之一：

(1)無等待條件(wait-free)：該條件要求當前線程的任務在有限步驟內完成，在任務所有的操作完成前，并不管其他線程的任何操作。也就是說把只有當前線程的所有操作完成之后，其他的線程才能開始任務，但在現實中一個線程的任務數量可能很大，這種方法十分依賴線程的數目，因此在實際中應用的比較少；

(2)無鎖條件(lock-free)：該條件要求當前線程的任務能夠在有限的步驟內完成，但是不同于無等待模型的是，每一次線程執行時只用保證完成部分操作。這就保證了多任務的調度順利，因此在大多數的無鎖數據結構都是采用此種模型；

(3)無干擾條件(obstruction-free)：該條件同樣要求線程能夠在有限的步驟內完成，同時要求當前線程被其它線程影響后能夠繼續執行。

這些條件中的每一個都能夠保證能實現和阻塞鎖達到的要求，但是在實踐中條件越嚴苛的實現起來的代價就越高，但是性能也越好，目前主要的研究集中在滿足無鎖(lock-free)條件的并發數據結構上面。

無鎖(lock-free)數據結構的實現基礎是高級別的原子操作(High-level atomic operation)，原子操作提供一個一致性接口：要么操作完成，要么操作失敗什么也不做——如果操作失敗，用戶必須重試，失敗后進行其他操作，因此用原子操作實現共享資源使用的線性化進而實現無鎖數據結構成為研究者的首選。這其中CAS(Compare-And-Swap)操作更加簡潔和高效，用它能夠實現解決多線程無鎖同步問題。

發明內容

本發明的目的在于針對現有技術的不足，提供一種基于無鎖緩沖區的數據采集方法。

本發明的目的是通過以下技術方案來來實現的：一種基于無鎖緩沖區的數據采集方法，包括以下步驟：

(1)建立生產者-消費者數據采集模型；所述生產者-消費者數據采集模型包括采集部分和處理部分，采集部分和處理部分并行進行；

(2)建立數據生產者線程和測點數據消費者線程；

(3)使用有序堆建立數據緩沖區，數據緩沖區中的數據按時間戳有序排放，數據緩沖區容量固定，數據節點在邏輯上是樹形結構；

(4)數據生產者線程和測點數據消費者線程對緩沖區進行同步操作，操作完成后緩沖區恢復有序；

(5)使用CAS原子操作實現對緩沖區的無鎖增加、刪除和排序，實現線程同步操作，避免兩組工作線程阻塞。

進一步地，所述步驟(2)中，生產者和消費者可能是單一線程也可能是一組工作線程，兩個線程單獨工作互不影響。

進一步地，所述步驟(4)具體為：生產者采集數據存入數據緩沖區，若緩沖區不滿，將生產者采集的數據直接放入緩沖區的末尾，并且對緩沖區中的數據按時間戳自動排序；若緩沖區滿，生產者采集的數據與緩沖區中時間戳最舊的數據交換后按時間戳自動排序；消費者從數據緩沖區取數據，若緩沖區不空，將緩沖區中時間戳最新的數據取出，并且對緩沖區中剩余數據按時間戳自動排序；若緩沖區空，則等待生產者采集的數據。

本發明的有益效果是：本發明使用生產者-消費者緩沖區實現有序的數據排列，并且能夠以無鎖的方式實現兩部分線程的同步訪問而不出現數據污染和沖突。

附圖說明

圖1無鎖緩沖區的插入算法流程圖；

圖2無鎖緩沖區的刪除算法流程圖。

具體實施方式

下面結合附圖和具體實施例對本發明作進一步詳細說明。

本發明一種基于無鎖緩沖區的數據采集方法，包括以下步驟：

(1)建立生產者-消費者數據采集模型；所述生產者-消費者數據采集模型包括采集部分和處理部分，采集部分和處理部分并行進行；