代码之家 › 专栏 › 技术社区 › BCS

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

lock-free data-structures multithreading algorithm

2

BCS · 技术社区 · 15 年前

union/find or Disjoint-set 数据结构有很好的运行时间(有效 O(1) )对于单螺纹的情况。然而,在多线程情况下,它的有效性/性能是什么?我它是完全有效的,即使没有锁定或除了原子指针大小的写入之外的任何原子操作。

首先,我假设指针大小的写入是原子的。从这一点上说,你可以安全地运行 find 在多个线程中执行函数,因为只有将发生的更新都设置为相同的值。如果你允许 找到 函数返回调用时为真的答案(与返回时相反)不难证明 s和一个单曲 union 可以同时运行;参数 s不变而 找到 根从不更新。

至于剩下的情况(几个 联盟

顺便说一句:我不要求解决方案和单线程版本一样高效。(为了避免锁/原子,我也愿意放弃全局相干态。)

编辑:

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

2 回复 | 直到 4 年前

1

Ionel Bratianu 15 年前

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

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

2

0

Eph 8 年前

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

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