普通的联合/查找算法在不需要任何额外工作的情况下线程安全吗？

Question

标准的 union/find 或 Disjoint-set 数据结构具有非常好的运行时间（有效地对于单线程情况，O(1))。 然而，它在多线程情况下的有效性/性能如何？ 我认为即使没有锁定或除了原子指针大小的写入之外的任何原子操作，它也是完全有效的。

有谁发现以下逻辑有问题吗？

首先，我假设指针大小的写入是原子的。 由此看来，不难看出您可以在多个线程中安全地运行 find 函数，因为唯一会发生的更新都是设置为相同的值。 如果您允许 find 函数返回调用时（而不是返回时）正确的答案，那么不难认为许多 find 和 a单个union可以同时运行； find 的参数不会改变，union 仅更新根，而 find 永远不会更新根。

至于剩下的情况（几个union），我认为这也有效，但我不太确定。

顺便说一句：我不要求解决方案与单线程版本一样高效。 （为了避免锁/原子，我也愿意放弃全局一致的状态。）

---

编辑：再看一下，多联合的情况不起作用，因为如果一侧不是新的根与其他东西联合（也不是作为根），然后你可以将它从第二个联合的另一侧切掉。

A = find(a)  // union 1
B = find(b)  // union 1
----
X = find(x)  //   union 2 (x == a) -> (X == A) -> (X.par aliases A.par)
Y = find(y)  //   union 2
X.par = Y    //   union 2
----
A.par = B    // union 1

这可以通过 CAS 来回避：

while(!CAS(A == A.par, B)) A = find(A); 

Answer 1

有点晚了，但供以后参考。 通过原子操作，您可以构建不相交的集合数据结构。 不变的是每个集合都由其最小成员表示，这可以避免由于竞争条件而导致的循环。

// atomic_compare_and_exchange(unsigned int *data, unsigned int new_value, unsigned int comparator)


// "The result used to be the root of v once"
static unsigned int GetSet(volatile unsigned int *H_RESTRICT set, const unsigned int v)
{
  unsigned int next;
  unsigned int root = v;
  unsigned int prev = v;

  while (root != (next = set[root]))
  {
    /* Update set[prev] to point to next instead of root.
      * If it was updated by some other thread in the meantime, or if this
      * is the first step (where set[prev]==next, not root), ignore. */
    atomic_compare_and_exchange(set + prev, next, root);

    prev = root;
    root = next;
  }

  /* Update the path to the root */

  return root;
}

// FALSE == "They used not to be in the same set"
// TRUE == "They are in the same set, and will be forever"
static HBOOL IsInSameSet(volatile unsigned int *H_RESTRICT set, unsigned int v1, unsigned int v2)
{
  do
  {
    v1 = GetSet(set, v1);
    v2 = GetSet(set, v2);
  } while (set[v1] != v1 || set[v2] != v2);

  return v1 == v2;
}

static void Union(volatile unsigned int *H_RESTRICT set, unsigned int v1, unsigned int v2)
{
  unsigned int result;

  do
  {
    v1 = GetSet(set, v1);
    v2 = GetSet(set, v2);
    if (v1 == v2)
    {
      /* Already same set. This cannot be changed by a parallel operation. */
      break;
    }
    if (v1 < v2)
    {
      /* Make sure we connect the larger to the smaller set. This also avoids
       * cyclic reconnections in case of race conditions. */
      unsigned int tmp = v1;
      v1 = v2;
      v2 = tmp;
    }

    /* Make v1 point to v2 */
    result = atomic_compare_and_exchange(set + v1, v2, v1);
  } while (result != v1);
}

Answer 2

可用于此结构的同步类型与读写器问题。 性能将取决于将执行多少个联合，因为这样查找操作将停止。

我不确定您是否可以同时运行多个查找和一个联合，因为联合操作的最后一个案例不是原子的。