2

对于单线程情况，标准的联合/查找或不相交集数据结构具有非常好的运行时间（有效地）。O(1)但是在多线程情况下它的有效性/性能是什么？我认为即使没有锁定或除了原子指针大小的写入之外的任何原子操作，它也是完全有效的。

有人看到以下逻辑有任何问题吗？

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

至于剩下的情况（几个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);
4

2 回答 2

1

可用于此结构的同步类型与Readers-writers problem类似。性能将取决于将执行多少个联合，因为随后将停止查找操作。

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

于 2009-04-14T17:11:39.790 回答
0

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

// 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);
}
于 2017-01-31T14:57:19.850 回答