7

我无法理解任何数据结构如何“非阻塞”。

假设您正在制作一个“非阻塞”哈希表。在某些时候，您的哈希表太满了，因此您必须重新哈希到一个更大的表中。

这意味着您需要分配内存，这是一种全局资源。所以看起来你必须获得某种锁来防止堆的全局损坏......不管你的数据结构本身可能存在的问题！
但这意味着在您分配内存时，所有其他线程都必须阻塞......

我在这里想念什么？
（如何）你能在不阻塞另一个做同样事情的线程的情况下分配内存吗？

4

4 回答 4

4

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

这样做的想法是——在大多数情况下，阻塞是多余的——因为两个 OP 可以同时发生而不会相互中断。但是，有时当 2 个 OP 同时发生并且数据因此而损坏时 - 您可以回滚到以前的状态，然后重试。

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

于 2012-05-30T07:41:15.787 回答
2

只是为了一些定义，附加信息以及区分non-blocking，lock-free和wait-free术语，我建议阅读以下文章（我不会在这里复制相关段落，因为它太长了）：

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

于 2012-05-30T07:54:08.063 回答
2

大多数策略都有一个共同的基本模式。他们在循环中使用比较和交换 (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中是一个非阻塞的原子操作，它将内存地址中的值替换为新值并返回旧值。如果旧值与预期值不匹配，那么您将通过循环并再次尝试。

于 2012-05-30T15:29:05.013 回答
0

所有这些非阻塞意味着你永远不会无限期地等待，而不是你永远不会等待。只要您的堆也是使用非阻塞算法实现的，您就可以在它之上实现其他非阻塞算法。

于 2012-05-30T07:46:51.513 回答