在没有互斥锁的情况下并发地附加到列表尾部

我有一个由多个线程同时访问的单链表。

事实上，唯一同时执行的操作是将数据附加到列表的尾部。现在，我使用互斥来确保一致性。这就是函数的样子：

void AppendCommand(BackEndCommand * beCmd)
{
    Lock();
    if (cmdHead == nullptr)
    {
        beCmd->next = nullptr;
        cmdHead = beCmd;
        cmdTail = beCmd;
    }
    else
    {
        cmdTail->next = beCmd;
        cmdTail = beCmd;
    }
    ++numCommands;
    Unlock();
}

以及相关列表数据和BackEndCommand类型：

struct BackEndCommand {
    // Command number. Any of the BackEndCommandId.
    BackEndCommandId id;
    // Next on the command queue or null if end of list.
    struct BackEndCommand * next;
};
BackEndCommand * cmdHead = nullptr;
BackEndCommand * cmdTail = nullptr;
uint32_t numCommands = 0;

现在我很好奇，在我的情况下，是否可以用某种无锁/原子操作来替换互斥锁，也许可以使用新的C++11atomics库或类似的操作？

一些答案展示了如何通过在列表的开头添加元素来实现这一点。也可以在列表的末尾添加元素。注意：在下面的代码中，_tail_hint并不总是指向最后一个元素，而是指向靠近尾部的元素。

我还通过添加伪元素简化了if条件。

struct list
{
    struct node
    {
        int _id;
        std::atomic<node*> _next;
        explicit node(int id, node* next)
            : _id{id}, _next{next}
        { }
    };
    node _head{0, nullptr};
    std::atomic<node*> _tail_hint{&_head};
    void append(node* n)
    {
        node* tail = _tail_hint;
        node* expected = nullptr;
        while (!tail->_next.compare_exchange_weak(expected, n)) {
            if (expected) {
                tail = expected;
                expected = nullptr;
            }
        }
        _tail_hint = n;
    }
};

是的，这是很可能的，只要只添加列表(至少在并发访问期间(。

如果你不介意你的列表按相反的顺序排列，这是最简单的，因为只有一个变量需要更新(尾部(，而且你在遍历它时不必做那么多原子负载。

我从我的一个项目中改编了一些工作代码(经过彻底的单元测试(。它实现了一个只添加后进先出法链表。(请注意，为了清楚起见，我已将您的next重命名为prev。(

#include <atomic>
std::atomic<BackEndCommand*> tail(nullptr);
// Thread-safe
void add(BackEndCommand* element)
{
    assert(element != nullptr);
    auto prevTail = tail.load(std::memory_order_relaxed);
    do {
        element->prev = prevTail;
    } while (!tail.compare_exchange_weak(prevTail, element, std::memory_order_release, std::memory_order_relaxed));
}
// Thread-safe
void iterate()
{
    for (auto ptr = tail.load(std::memory_order_acquire); ptr != nullptr; ptr = ptr->prev) {
        // Do something with ptr
    }
}

是的，您可以

以下是来自的示例代码http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

你甚至可以在网页上运行它

#include <atomic>
template<typename T>
struct node
{
    T data;
    node* next;
    node(const T& data) : data(data), next(nullptr) {}
};
template<typename T>
class stack
{
    std::atomic<node<T>*> head;
 public:
    void push(const T& data)
    {
        node<T>* new_node = new node<T>(data);
//      // put the current value of head into new_node->next
//      new_node->next = head.load(std::memory_order_relaxed);
//
//      // now make new_node the new head, but if the head
//      // is no longer what's stored in new_node->next
//      // (some other thread must have inserted a node just now)
//      // then put that new head into new_node->next and try again
//      while(!head.compare_exchange_weak(new_node->next, new_node,
//                                        std::memory_order_release,
//                                        std::memory_order_relaxed))
//          ; // the body of the loop is empty
//
// Note: the above use is not thread-safe in at least 
// GCC prior to 4.8.3 (bug 60272), clang (bug 18899), MSVC (bug 819819).
// The following is a workaround:
        node<T>* old_head = head.load(std::memory_order_relaxed);
        do {
            new_node->next = old_head;
        } while(!head.compare_exchange_weak(old_head, new_node,
                                            std::memory_order_release,
                                            std::memory_order_relaxed));
    }
};
int main()
{
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
}

可以。您需要使用atomic_compare_exchange_weak()或atomic_compare_exchange_strong()将上一个尾部的next指针与指向新元素的指针进行交换。算法如下：

设置新元素，将其next指针设置为零。重要的是，在调用atomic<>魔术之前完成此操作。
确定列表中的最后一个元素。用你喜欢的任何方法。确保其next指针是nullptr。让我们称之为oldTail。
执行atomic_compare_exchange_xxx()，指定您希望oldTail->next仍然是nullptr。这可能会失败。如果是这样，则其他进程在您不查看时已将一个元素附加到列表中。在这种情况下，您需要返回到2来确定新的尾部。
如果atomic_compare_exchange_xxx()成功，则完成。

此方法要求仅追加列表末尾。它还要求列表元素保持有效，只要另一个线程可能持有指向它的指针以便附加另一个元素。确保这一点很棘手，尤其是如果你试图以无锁定的方式进行，但这是可能的(可以通过RCU模式实现，请参阅http://en.wikipedia.org/wiki/Read-copy-update)。

相关内容

最新更新

热门标签：