c++鏈表實(shí)現(xiàn)的阻塞隊(duì)列

最近從java源碼里發(fā)現(xiàn)了阻塞隊(duì)列的實(shí)現(xiàn)，覺(jué)得非常有趣。

首先，介紹下什么是阻塞隊(duì)列。阻塞隊(duì)列代表著一個(gè)隊(duì)列可以線程安全的往該隊(duì)列中寫(xiě)數(shù)據(jù)和從該隊(duì)列中讀數(shù)據(jù)。也就是說(shuō)，我們可以在多個(gè)線程之間并發(fā)的進(jìn)行寫(xiě)數(shù)據(jù)和讀數(shù)據(jù)，而不會(huì)引發(fā)任何并發(fā)問(wèn)題。

下面我們就說(shuō)說(shuō)如何實(shí)現(xiàn)一個(gè)阻塞隊(duì)列。

而實(shí)現(xiàn)一個(gè)阻塞隊(duì)列的前提：

1. 需要能夠使用鏈表實(shí)現(xiàn)一個(gè)隊(duì)列
2. 能夠使用c++的鎖機(jī)制，去給隊(duì)列的寫(xiě)和讀操作加鎖。

為了性能，這里的讀和寫(xiě)的鎖不能是同一把鎖。而對(duì)于一個(gè)鏈表隊(duì)列來(lái)說(shuō)，讀取操作肯定需要涉及頭指針，寫(xiě)操作肯定涉及尾指針。既然要實(shí)現(xiàn)讀操作一把鎖和寫(xiě)操作一把鎖。那么就要求讀操作只能更改頭指針而不能更改尾指針，寫(xiě)操作只能更改尾指針而不能更改頭指針。不滿足這個(gè)要求，那么讀寫(xiě)操作就不可能實(shí)現(xiàn)用兩把鎖分別對(duì)讀寫(xiě)進(jìn)行加鎖。

基本隊(duì)列的實(shí)現(xiàn)

現(xiàn)在我們先說(shuō)說(shuō)如何實(shí)現(xiàn)這個(gè)隊(duì)列。

要求：入隊(duì)操作(enqueue)只能操作尾指針(last), 出隊(duì)操作(dequeue)只能操作頭指針(head)。

對(duì)于隊(duì)列的初始化，這里不能單純的設(shè)置為空指針，需要將頭尾指針同一節(jié)點(diǎn)。

下面我們來(lái)看入隊(duì)操作如何實(shí)現(xiàn)

從這個(gè)入隊(duì)操作來(lái)看，該操作只更改了尾指針last, 而沒(méi)有更改頭指針head。

其代碼實(shí)現(xiàn)為：

 void enqueue(int item) {
    Node *node = new Node(item);
    last = last->next = node;
  }

接下來(lái)我們來(lái)看出隊(duì)操作如何實(shí)現(xiàn)

從出隊(duì)操作來(lái)看就有趣的多，它拋棄了head所指向的節(jié)點(diǎn)，而這個(gè)節(jié)點(diǎn)有可能是那些節(jié)點(diǎn)呢？

• 初始化時(shí)所賦值的那個(gè)節(jié)點(diǎn)
• 出隊(duì)后的節(jié)點(diǎn)

也就是說(shuō)，head所指向的節(jié)點(diǎn)中的val值沒(méi)有任何實(shí)際含義。當(dāng)需要出隊(duì)時(shí)，出隊(duì)head指向的下一個(gè)節(jié)點(diǎn)first中val的值，然后拋棄head本身指向的值，讓head指向head的下一個(gè)節(jié)點(diǎn)first，此時(shí)head原來(lái)所指向的節(jié)點(diǎn)將被刪除?，F(xiàn)在我們可以看出出隊(duì)操作也只改變了頭指針head的值。

其代碼實(shí)現(xiàn)為：

 int dequeue() {
    Node *h = head;
    Node *first = head->next;
    delete h;
    head = first;
    int x = first->item;
    return x;
  }

現(xiàn)在隊(duì)列已經(jīng)實(shí)現(xiàn)，下面就看看阻塞隊(duì)列如何實(shí)現(xiàn)。

阻塞隊(duì)列的實(shí)現(xiàn)

既然是阻塞隊(duì)列，那就意味這加鎖和等待。那就需要對(duì)c++的一些鎖知識(shí)和條件變量有了解。

先來(lái)看看我們需要實(shí)現(xiàn)阻塞隊(duì)列的那些方法：

入隊(duì)

讓我們先來(lái)實(shí)現(xiàn)put這個(gè)方法。

先看其實(shí)現(xiàn)流程圖：

由于該隊(duì)列實(shí)現(xiàn)有最大值限制，故在插入數(shù)據(jù)之前需要先判斷該隊(duì)列是否已滿，已滿則需等待該隊(duì)列有可用空間。在該線程入隊(duì)操作完成后，可能有別的線程也在等待入隊(duì)，需要喚醒其他寫(xiě)數(shù)據(jù)的線程，使其繼續(xù)執(zhí)行后續(xù)操作。如果入隊(duì)前隊(duì)列為空，可能有出隊(duì)操作正在阻塞等待讀數(shù)，也需要去喚醒讀數(shù)據(jù)的線程。

在看代碼實(shí)現(xiàn)之前，我們需要定義一些變量用于代碼實(shí)現(xiàn)環(huán)節(jié)：

 /* The capacity bound*/
  int64_t capacity;
  /*Current number of elements */
  std::atomic<int64_t> count;  
	/** Lock held by take, pool, etc */
  std::mutex takeLock;
  /** Wait queue for waiting takes */
  std::condition_variable notEmpty;
  /** Lock held by put, offer, etc */
  std::mutex putLock;
  /** Wait queue for waiting puts */
  std::condition_variable notFull;

put函數(shù)的代碼實(shí)現(xiàn)：

void LinkedBlockingQueue::put(const int item){
  int c;
  {
    std::unique_lock<std::mutex> lck{putLock};
    if( count == capacity) {
      notFull.wait(lck, [this](){return count < capacity;}); //（1）
    }
    enqueue(item); //不應(yīng)該把申請(qǐng)空間放在鎖里面，耗時(shí)有點(diǎn)大
    c = count.fetch_add(1);
  }
  if(c + 1 < capacity) {
    notFull.notify_one();
  }

  if(0 == c) {
    notEmpty.notify_one();
  }
}

對(duì)于offer(o)的實(shí)現(xiàn)，主要更改是對(duì)上述代碼(1)中的等待改為直接返回false, 表示，當(dāng)前沒(méi)有可用空間插入數(shù)據(jù)。正常插入就返回true.

對(duì)于offer(o,timeout)的實(shí)現(xiàn)，就需要在上述代碼(1)中的wait函數(shù)添加上時(shí)間參數(shù)，使其可以在timeout時(shí)間內(nèi)返回，如果是正常喚醒，正常入隊(duì)，則返回ture,否則返回false.

該更改為：

 if(!notFull.wait_for(lck, rel_time, [this](){return count < capacity;})){
        return false;
      }

出隊(duì)

對(duì)于出隊(duì)，其實(shí)現(xiàn)和入隊(duì)基本相同，基本上只需要更改其中的關(guān)鍵判斷和通知。

take函數(shù)的代碼實(shí)現(xiàn)為：

void LinkedBlockingQueue::take(int & returnVal) {
  int c;
  {
    std::unique_lock<std::mutex> lck{takeLock};
    if( 0 == count) {
      notEmpty.wait(lck, [this](){return count > 0 ;});
    }
    returnVal = dequeue();
    c = count.fetch_sub(1);
  }

  if( c > 1 ) {
    notEmpty.notify_one();
  }

  if(c == capacity) {
    notFull.notify_one();
  }
}

剩下的實(shí)現(xiàn)細(xì)節(jié)可以參考我的實(shí)現(xiàn)

到此這篇關(guān)于c++實(shí)現(xiàn)LinkBlockedQueue的問(wèn)題的文章就介紹到這了,更多相關(guān)c++實(shí)現(xiàn)LinkBlockedQueue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！