0

尝试我的运气来实现无锁单链表。

typedef _Atomic struct _node
  {
    void *data;
    struct _node *next;
  } Node;

这是否也使 _Atomic 结构的所有成员都具有原子性？

void add_head ( Linked_list* list, void* data )
{
  if ( debugging )
  {
      printf ( "%s\n", __func__ );
  }
  Node *node = ( Node* ) calloc ( 1, sizeof (Node ) );
  //init_node_mutex(node);
  //lock_node_mutex(node);
  atomic_exchange ( &node->next, NULL );
  atomic_exchange ( &node->data, data );

  if ( list->head == NULL )
  {
      Node* the_tail = atomic_load ( &list->tail );
      //  lock_node_mutex ( the_tail );
      atomic_exchange ( &node->next, NULL );
      atomic_compare_exchange_weak ( &list->tail, the_tail, node );

      //unlock_node_mutex ( the_tail );

  }
  else
  {

      Node* the_next = atomic_load ( &node->next );
      // lock_node_mutex ( the_next );
      atomic_compare_exchange_weak ( &node->next, the_next, list->head );
      // unlock_node_mutex ( the_next );
  }

  Node* the_head = atomic_load ( & list->head );
  //lock_node_mutex ( the_head );
  atomic_store ( &list->head, node );
  atomic_store ( &list->current, node );
  //unlock_node_mutex ( the_head );
  //unlock_node_mutex(node);
  atomic_fetch_add ( &list->size, 1 );
}

atomic_load 和 atomic_store 的用法是否正确？

4

2 回答 2

2

好的，我争论过是否将其发布为“评论”或“答案”，但我将在这里破产。

我的直觉对我大喊：“你正在执行的单个操作是否是‘原子的’并不重要，因为你连续执行许多操作以完成你所要做的事情最终尝试去做。即使这些单独的步骤是“原子的”，整个操作也不是。

“原子”操作是使用专门的机器指令（例如LOCKx86 上的前缀或 big-iron 上的“比较和交换”指令）来执行单个操作而没有其他CPU（或内核）会干扰的操作用那个单一的操作。

但是，你不能在“一条指令”中做你想做的事情，不管是原子的还是非原子的。

因此，我诚挚地建议您现在放弃当前的课程，将那些“互斥”调用放回原处，并删除“原子”。您的代码（以及所有此类代码......）需要这些互斥锁。在我看来，你是在死胡同里追一只白兔。

（顺便说一句， “互斥”操作有时会很好地利用这些“原子指令”，因此它们可能比您担心的要高效得多。）

于 2016-07-12T00:02:09.850 回答
1

除了@MikeRobinson 的评论，我还要补充一点，虽然您的代码是“无锁”的，因为它不包含任何明确使用的锁，但它现在（有点讽刺地）不再是线程安全的。编写无锁代码非常困难。我建议通读此书以鸟瞰世界，然后阅读此书以了解一些细节或本书的第 7 章（使用 C++ 编写）。您可以随时查看Boost.LockFree的源代码以获取灵感。

于 2016-07-12T05:00:36.280 回答