多线程无锁队列实现

Question

我和我的搭档开始相信，在我们所写的无锁队列中，可能会出现一种去同步的可能性，但我们希望能对这个问题有一些新的看法。你对我们的设计有什么看法？

// nolockqueue.hpp:
#ifndef NOLOCKQUEUE_HPP
#define NOLOCKQUEUE_HPP

template<typename T>
class noLockQueue {
public:
    noLockQueue();
    ~noLockQueue();
    void push(const T dataVar);
    bool pop(T &dataVar);

private:
    struct node {
        node(T dataPassed) : dataVar(dataPassed), next(NULL) {};
        T dataVar;
        node* next;
    };

    node* topOfList;
    node* bottomOfList;
};

template<typename T>
noLockQueue<T>::noLockQueue() {
    topOfList = NULL;
    bottomOfList = NULL;
}

template<typename T>
noLockQueue<T>::~noLockQueue() {
    node* temp;

    while (topOfList != NULL) {
        temp = topOfList->next;
        delete topOfList;
        topOfList = temp;
    }

    if (bottomOfList != NULL)
        throw("Not All Nodes Deleted - nolockqueue/38/.cpp"); // TODO: Strange error to throw.
}

template<typename T>
void noLockQueue<T>::push(const T dataVar) {
    if (topOfList == NULL) {
        topOfList = bottomOfList = new node(dataVar);
        return;
    } else {
        bottomOfList->next = new node(dataVar);
        bottomOfList = bottomOfList->next;
    }
}

template<typename T>
bool noLockQueue<T>::pop(T &dataVar) {
    if (topOfList == NULL)
        return false;

    dataVar = topOfList->dataVar;
    node* temp = topOfList->next;
    delete topOfList;
    topOfList = temp;
    return true;
}

#endif


// main.cpp (purely a test unit):
#include <iostream>
#include <thread>

#include "nolockqueue.hpp"
#include <windows.h> // For Sleep().

noLockQueue<int> queue;

void threadFunc() {
    int var = 0;
    Sleep(10);
    while (queue.pop(var)) {
        std::cout << "\nPopped: " << var;
        Sleep(1);
    }
}

int main(int argc, char* argv[]) {
    std::thread myThread(threadFunc);

    for (int i = 0; i < 1000; ++i) {
        queue.push(i);
        std::cout << "\nPushed: " << i;
        Sleep(1);
    }

    myThread.join();

    std::cin >> argc;
    return 0;
}

Answer 1

这不是一个无锁队列，而是一个与锁定无关的队列。这意味着在多个线程上使用是不安全的。这在您的实现中起作用的原因是，推送调用改变了队列的结束，而pop调用改变了开始(因此或多或少避免了冲突)。

如果尝试同时从多个线程添加元素(例如)，则会泄漏元素。

由于析构函数中的bottomOfList从未更改，因此如果初始化它，则始终会抛出异常。

考虑将pop拆分为const T& top() const和void pop()；这将允许操作的异常安全实现。