Безопасен ли нормальный алгоритм объединения / поиска без дополнительной работы?

Question

Стандартная структура данных union / find или Disjoint-set имеет очень хорошие времена выполнения (эффективно O(1)) для однопоточных случаев. Однако что такое валидность / производительность в многопоточных случаях? Я думаю , что он полностью действителен даже без блокировки или каких-либо атомарных операций, кроме операций записи размером атомного указателя.

Кто-нибудь видит проблемы со следующей логикой?

Сначала я предположу, что записи размером с указатель являются атомарными. Исходя из этого, нетрудно утверждать, что вы можете безопасно запускать функцию find в нескольких потоках, поскольку единственные обновления, которые будут происходить, - все они имеют одно и то же значение. Если вы позволите функции find возвращать ответ, который был истинным при его вызове (в отличие от того, когда он возвращался), нетрудно утверждать, что многие find s и один union могут выполняться одновременно время; аргумент для find s не меняется, а union только обновляет корни, а find s никогда не обновляет корни.

Что касается оставшегося случая (несколько union с), я думаю, что это работает, но я не уверен в этом.

Кстати: я не требую, чтобы решение было таким же эффективным, как однопоточная версия. (Чтобы избежать блокировок / атомарных, я также хочу отказаться от глобально связного состояния.)

---

edit: если взглянуть по-другому, случаи множественного объединения не работают, потому что если сторона, которая не является новым корнем, объединена с чем-то другим (также не как корень), то вы можете вырезать это с другой стороны второго союза.

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

Тип синхронизации, который вы можете использовать для этой структуры, аналогичен проблеме Readers-writers . Производительность будет зависеть от того, сколько объединений будет выполнено, потому что тогда операция поиска будет остановлена.

Я не уверен, что вы можете запустить много находок и одно объединение одновременно, поскольку последний случай операции объединения не является атомарным.

Answer 2

Немного поздно, но для дальнейшего использования. С помощью атомарных операций вы можете построить непересекающуюся структуру данных набора. Инвариант состоит в том, что каждый набор представлен своим наименьшим членом, что позволяет избежать циклов из-за условий гонки.

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