일반 노동 조합/찾기 알고리즘 스레드가 추가 작업없이 안전합니까?

Question

표준 union/find or Disjoint-set 데이터 구조는 단일 스레드 케이스에 대해 매우 좋은 실행 시간 (효과적으로 O(1))을가집니다. 멀티 스레드 케이스에서 유효성/성능은 무엇입니까? I 은 원자 포인터 크기의 쓰기를 제외하고는 잠금 또는 원자 연산이 없이도 완전히 유효하다고 생각합니다.

누구나 다음과 같은 논리에 문제가 있습니까?

우선 포인터 크기의 쓰기는 원자 적이라고 가정합니다. 그로 인해 발생하는 유일한 업데이트가 모두 같은 값으로 설정되므로 안전하게 여러 스레드에서 find 함수를 실행할 수 있다고 주장하는 것이 어렵지 않습니다. find 함수가 호출되었을 때 true를 반환하도록 허용하면 (반환되었을 때와 반대) 많은 find과 하나의 union이 동시에 실행될 수 있다고 주장하는 것이 어렵지 않습니다. find에 대한 인수는 변경되지 않으며 union은 뿌리만을 업데이트하고 find은 뿌리를 업데이트하지 않습니다.

나머지 사례 (여러 union 초)에 대해서는 잘 작동하지만 잘 모르겠습니다.

BTW : 솔루션이 단일 스레드 버전만큼 효율적일 필요는 없습니다. (/ 원자 잠금을 방지하기 위해, 또한 전 세계적으로 일관된 상태를 폐기 할 용입니다.)

---

이 편집 : 다른 모양을 가지고, 많은 노조의 경우는 작동하지 않기 때문에 경우 측면이 새 루트가 다른 루트와 결합되지 않았 으면 (루트가 아닌) 두 번째 조합의 다른 쪽에서 잘라낼 수 있습니다.

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 problem와 유사하다. 성능은 검색 작업이 중단되므로 실행될 노조의 수에 따라 달라집니다.

마지막으로 대 집합 연산의 결과가 원 자성이 아니므로 같은 시간에 많은 검색과 단일 통합을 실행할 수 있는지 확신하지 못합니다.

Answer 2

조금 늦었지만 나중에 참조 할 수 있습니다. 원자 연산을 사용하면 분리 된 집합 데이터 구조를 만들 수 있습니다. 불변량은 각 집합이 경쟁 조건으로 인한 회피를 허용하는 가장 작은 구성원으로 표현된다는 것입니다. 나는 CAS와도 생각

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