“非阻塞”数据结构是如何实现的？

Question

我有困难理解任何数据结构如何可以是“非阻塞”的。

假设你正在创建一个“非阻塞”哈希表。在某个时刻，你的哈希表变得太满了，所以你必须重新哈希到一个更大的表中。

这意味着你需要分配内存，这是一种全局资源。因此，似乎你必须获取某种锁来防止堆的全局破坏...无论你的数据结构本身可能存在的问题如何！
但是这意味着每个其他线程都必须在你分配内存时被阻塞...

我错过了什么？
（如何）可以在不阻塞正在执行相同操作的另一个线程的情况下分配内存吗？

- user541686

Answer 1

非阻塞设计的两个例子是乐观设计和事务内存。

这个想法是，在大多数情况下，阻塞是多余的，因为两个操作可以同时进行而不会相互干扰。然而，有时候当两个操作同时发生并且数据因此而损坏时，您可以回滚到先前的状态并重试。

这些设计中可能仍然存在锁，但数据被锁定的时间显著缩短，并且仅限于操作影响发生的关键时间。

- amit

---

我明白了...那么你如何保证不会永远陷入重试循环中呢？除了互斥锁之外，还有其他的方法吗？ - user541686

一种可能性是采用二进制指数退避的方法，直到事务成功为止。使用这种方法，无限循环的概率比任何epsilon>0都要小。您可以添加一个中断点（通常在迭代~#16处），尝试其他方法来写入数据，但您到达那里的可能性非常小。 - amit

哦，这很聪明...所以它仍然是无界的，但是有限的。酷！+1 - user541686

抱歉，还有一个问题：如何在不休眠的情况下进行二进制指数退避？（我猜你可以忙等待，但这不比睡眠更糟吗？） - user541686

这里有两个问题：(1) 只有在两个线程同时修改数据的概率很小的情况下才应该使用此解决方案（例如，99.9% 的数据访问是读取，只有其他的是写入），因此即使需要睡眠，通常也值得这种开销。(2) 由于这发生在写入时，而不是读取时 - 通常线程可以继续计算，并且不需要等待写入实际发生，因此这种等待不会减慢它的速度。（可以通过生成一个写入线程来实现，该线程将等待并在数据修改完成后死亡）。 - amit

我想可能还有其他的方法，但这是目前我所使用的基本方法。当两种修改同时发生的概率足够小时，处理这种情况所需的额外时间好像值得为了不需要互相等待的其他操作节省的时间而付出。 - amit

Answer 2

以下是一些定义，额外信息以及区分“非阻塞”、“无锁”和“无等待”术语的文章，建议阅读以下文章（由于篇幅过长，我不会在这里复制相关段落）：

非阻塞、无锁和无等待的定义

- MicSim

Answer 3

大多数策略都有一个基本的模式。它们在循环中使用比较和交换（CAS）操作，直到成功为止。

例如，让我们考虑使用链表实现的堆栈。我选择链表实现是因为它很容易通过CAS并发，但也有其他方法可以实现它。我将使用类似C语言的伪代码。

Push(T item)
{
  Node node = new Node(); // allocate node memory
  Node initial;
  do
  {
    initial = head;
    node.Value = item;
    node.Next = initial;
  }
  while (CompareAndSwap(head, node, initial) != initial);
}

Pop()
{
  Node node;
  Node initial;
  do
  {
    initial = head;
    node = initial.Next;
  }
  while (CompareAndSwap(head, node, initial) != initial);
  T value = initial.Value;
  delete initial; // deallocate node memory
  return value;
}

在上述代码中，CompareAndSwap 是一种非阻塞原子操作，它将内存地址中的值替换为新值并返回旧值。如果旧值与期望值不匹配，则需要循环尝试直到成功为止。

- Brian Gideon

---

我看到了...但这不只是“阻塞”调用者吗？（我猜它是使用CPU进行阻塞而不是睡眠，但从调用者的角度来看是否有任何实际区别？） - user541686

嗯，没错，它肯定会阻塞调用者。所以从调用者的角度来看，我想没有太大的区别。但是，至少这样所有的调用者都可以同时执行代码和分配内存，而不是在锁后面串行化。虽然我相信还有其他有效的解释方式，但通常我会这样解释“非阻塞数据结构”。重要的是，CAS 使事情高度并发。 - Brian Gideon

Answer 4

非阻塞的意思只是你永远不会无限期地等待，而不是根本不等待。只要你的堆也使用非阻塞算法实现，你就可以在其上实现其他非阻塞算法。

- Martin Hock

---

我不理解这个定义：如果唯一的保证是你不会无限期地等待，那么不是每个明智的系统都是非阻塞的吗？否则，系统将容易出现死锁，对吗？ - user541686