正常的union/find算法是线程安全的吗?

可用于此结构的同步类型与 Readers-writers problem

我不确定是否可以同时运行多个find和一个union,因为union操作的最后一个case不是原子的。

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

// 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);
}