在无锁单链表的开头插入节点时，应使用什么正确的内存顺序? [英] What are the correct memory orders to use when inserting a node at the beginning of a lock free singly linked list?

问题描述

我有一个简单的链表.没有ABA问题的危险，我对阻塞类别感到满意，并且我不在乎我的列表是FIFO，LIFO还是随机的.只要插入成功而不使其他人失败.

I have a simple linked list. There is no danger of the ABA problem, I'm happy with Blocking category and I don't care if my list is FIFO, LIFO or randomized. At long as the inserting succeeds without making others fails.

该代码看起来像这样:

class Class {
  std::atomic<Node*> m_list;
  ...
};

void Class::add(Node* node)
{
  node->next = m_list.load(std::memory_order_acquire);
  while (!m_list.compare_exchange_weak(node->next, node, std::memory_order_acq_rel, std::memory_order_acquire));
}

我或多或少地随机填写了所使用的memory_order的. 在这里可以使用哪些正确的存储命令?

where I more or less randomly filled in the used memory_order's. What are the right memory orders to use here?

我已经看到人们在所有地方都使用std::memory_order_relaxed，SO上也有人使用过，但是对于compare_exchange_weak成功的案例来说，然后是std::memory_order_release-genmc项目在可比较的情况下使用memory_order_acquire/memory_order_acq_rel两次，但我无法让genmc用于测试用例:(.

I've seen people use std::memory_order_relaxed in all places, one guy on SO used that too, but then std::memory_order_release for the success case of compare_exchange_weak -- and the genmc project uses memory_order_acquire / twice memory_order_acq_rel in a comparable situation, but I can't get genmc to work for a test case :(.

推荐答案

使用Michalis Kokologiannakis的 excellent 工具 genmc ，我能够使用以下测试代码来验证所需的内存顺序.不幸的是，genmc当前需要C代码，但这与确定内存顺序当然无关紧要.

Using the excellent tool from Michalis Kokologiannakis genmc, I was able to verify the required memory orders with the following test code. Unfortunately, genmc currently requires C code, but that doesn't matter for figuring out what the memory orders need to be of course.

// Install https://github.com/MPI-SWS/genmc
//
// Then test with:
//
// genmc -unroll 5 -- genmc_sll_test.c

// These header files are replaced by genmc (see /usr/local/include/genmc):
#include <pthread.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <stdatomic.h>
#include <stdio.h>

#define PRODUCER_THREADS 3
#define CONSUMER_THREADS 2

struct Node
{
  struct Node* next;
};

struct Node* const deleted = (struct Node*)0xd31373d;

_Atomic(struct Node*) list;

void* producer_thread(void* node_)
{
  struct Node* node = (struct Node*)node_;

  // Insert node at beginning of the list.
  node->next = atomic_load_explicit(&list, memory_order_relaxed);
  while (!atomic_compare_exchange_weak_explicit(&list, &node->next,
             node, memory_order_release, memory_order_relaxed))
    ;

  return NULL;
}

void* consumer_thread(void* param)
{
  // Replace the whole list with an empty list.
  struct Node* head = atomic_exchange_explicit(&list, NULL, memory_order_acquire);
  // Delete each node that was in the list.
  while (head)
  {
    struct Node* orphan = head;
    head = orphan->next;
    // Mark the node as deleted.
    assert(orphan->next != deleted);
    orphan->next = deleted;
  }

  return NULL;
}

pthread_t t[PRODUCER_THREADS + CONSUMER_THREADS];
struct Node n[PRODUCER_THREADS]; // Initially filled with zeroes -->
                                 // none of the Node's is marked as deleted.

int main()
{
  // Start PRODUCER_THREADS threads that each append one node to the queue.
  for (int i = 0; i < PRODUCER_THREADS; ++i)
    if (pthread_create(&t[i], NULL, producer_thread, &n[i]))
      abort();

  // Start CONSUMER_THREAD threads that each delete all nodes that were added so far.
  for (int i = 0; i < CONSUMER_THREADS; ++i)
    if (pthread_create(&t[PRODUCER_THREADS + i], NULL, consumer_thread, NULL))
      abort();

  // Wait till all threads finished.
  for (int i = 0; i < PRODUCER_THREADS + CONSUMER_THREADS; ++i)
    if (pthread_join(t[i], NULL))
      abort();

  // Count number of elements still in the list.
  struct Node* l = list;
  int count = 0;
  while (l)
  {
    ++count;
    l = l->next;
  }

  // Count the number of deleted elements.
  int del_count = 0;
  for (int i = 0; i < PRODUCER_THREADS; ++i)
    if (n[i].next == deleted)
      ++del_count;

  assert(count + del_count == PRODUCER_THREADS);
  //printf("count = %d; deleted = %d\n", count, del_count);

  return 0;
}

其输出为

$ genmc -unroll 5-genmc_sll_test.c
探索的完整执行次数:6384
总挂钟时间:1.26s

$ genmc -unroll 5 -- genmc_sll_test.c
Number of complete executions explored: 6384
Total wall-clock time: 1.26s

将memory_order_release或memory_order_acquire替换为memory_order_relaxed会引起断言.

Replacing either the memory_order_release or memory_order_acquire with memory_order_relaxed causes an assertion.

实际上，可以检查出，仅插入节点时使用排他的memory_order_relaxed足以使它们清晰地出现在列表中(尽管以随机"顺序排列-没有顺序一致，因此顺序如果由于其他原因而存在这种相关性，则添加它们不一定与线程尝试添加它们相同.

In fact, it can be checked that using exclusive memory_order_relaxed when just inserting nodes is sufficient to get them all cleanly in the list (although in a 'random' order - there is nothing sequential consistent, so the order in which they are added is not necessarily the same as that the threads try to add them, if such correlation exists for other reasons).

但是，memory_order_release是必需的，因此当用memory_order_acquire读取head时，我们可以确定在消费者"线程中所有非原子的next指针都是可见的.

However, the memory_order_release is required so that when head is read with memory_order_acquire we can be certain that all non-atomic next pointers are visible in the "consumer" thread.

请注意，这里没有ABA问题，因为用于head和next的值在被"consumer_thread"功能删除之前是不能重用"的，这是唯一允许删除这些节点的地方(因此)，这意味着只能有一个使用者线程(此测试代码不会检查ABA问题，因此它也可以使用2 CONSUMER_THREADS起作用).

Note there is no ABA problem here because values used for head and next cannot be "reused" before they are deleted by the 'consumer_thread' function, which is the only place where these node are allowed to be deleted (therefore), implying that there can only be one consumer thread (this test code does NOT check for the ABA problem, so it also works using 2 CONSUMER_THREADS).

实际代码是一种垃圾回收机制，其中多个生产者"线程可以删除时将它们添加到指向单链接列表的指针，但实际上只有在一个特定线程中这样做才是安全的(在这种情况下，因此只有一个消费者"线程，该线程在主循环中一个众所周知的位置执行此垃圾回收.

The actual code is a garbage collection mechanism where multiple "producer" threads add pointers to a singly linked list when those can be deleted, but where it is only safe to actually do so in one specific thread (in that case there is only one "consumer" thread thus, which performs this garbage collection at a well-known place in a main-loop).

这篇关于在无锁单链表的开头插入节点时，应使用什么正确的内存顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！