이 test_and_set 스레드 사용은 안전합니까?

Question

나는 lock-free singlely linked list를 구현하는 방법을 생각 해왔다. 그리고 솔직히 말해서, 나는 그것을하는 많은 총알 증명 방법을 보지 못합니다. 밖에 나가는 을 사용하는 더 튼튼한 방법은 결국 어느 정도의 ABA problem을가집니다.

그래서 생각하고 있습니다. 부분적으로 자물쇠가없는 시스템이 항상 자물쇠를 사용하는 것보다 낫지 않습니까? 일부 작업은 원자 적이며 잠금이 해제 될 수 있습니까? 그렇게 할 수 있다면 여전히 스레드로부터 안전해야합니다.

그래서, 질문에. 나는 단순하게 연결된 목록을 생각하고있다. 2 가지 주요 작업. push 및 pop. push은 항상 앞쪽에 삽입합니다. 이 같은 것 :

void push(int n) { 
    T *p = new T; 
    p->n = n; 
    p->next = root; 
    root = p; 
} 

항상 첫 번째 요소를 취하는 pop. 이런 식으로 :

T *pop() { 
    T *p = root; 
    root = root->next; 
    return p; 
} 

분명히 간단하게 잠글 수는 없으므로 잠금이 필요하지 않습니다. 그러나 대중 음악은 아마도 가능할 것 같습니다. gcc-intrinsics를 사용하여 다음과 같이 생각했습니다.

T *pop() { 
    return __sync_lock_test_and_set(&root, root->next); 
} 

기능상으로 동일합니까? 예. 자물쇠가 없습니까? 예. 쓰레드 안전? 잘 모르겠 음. 내 직감 반증은 아니오이며, 여기에 이유가 있습니다.

test_and_set에 대한 매개 변수 중 하나가 메모리를 비 참조 화해야한다는 사실에 대해 우려하고 있습니다. root->next과 __sync_lock_test_and_set 사이의 루트가 변경되면 어떻게 될까요?

나는이 코드는 다음에 해당한다고 가정 : 내가 말했듯이

T *pop() { 
    T *temp = root->next; 
    // are we broken if a push/pop happens here? 
    return __sync_lock_test_and_set(&root, temp); 
} 

그래서,이 코드가 올바르지 않은 것을 생각 . 그러나 누군가가 내가 올바른 결론을 내리고 있다고 말할 수 있는가? (잘 작동하는 것을 쓸어내는 것이 싫다.) 내가 의심하는 한 실제로 깨진 경우. 간단한 해결책이 있습니까?

Answer 1

정확합니다. C++에서 함수에 대한 인수는 순서에 관계없이 평가되지만 확실하게 컴파일러는 root->next이 시퀀스의 원자 연산임을 알 방법이 없습니다.

는 pop()를 호출하는 두 개의 스레드를 고려 하나의 스레드가 root->next을 평가 한 후 다른 root->next을 평가하고, 모두 전화 test_and_set(). 이제 노드 하나가 터졌습니다.

T *pop() { 
    T *p = root; 
    root = root->next; 
    return p; 
} 

및

T *pop() { 
    return __sync_lock_test_and_set(&root, root->next); 
} 

당신은 당신이 당신의 목록/스택 전에 비어 있지 않은지 확인되지 않습니다이다, 이미 오류가을 : pop의 두 버전에서

Answer 2

가정 된 루트 노드에서 읽는 중.

이 문제는 test_and_set이 발생하기 전에 다음에 도달하기 위해 root을 참조 해제해야하는 것에 대해 언급 한 문제를 합성합니다. 그것은 본질적으로 test_and_then_test_and_set 연산이되며, and_then은 하나 이상의 단계가 필요함을 나타냅니다.

T *pop() { 
    T *p = root; 
    if (root) { 
     root = root->next; 
    } 
    return p; 
} 

을 나는 확신 당신이 믹스에 더 많은 단계를두고 볼 수 있습니다 : 팝의

첫 번째 버전은 할 필요가있다.

Answer 3

두 가지 : (1) 테스트 & 세트는 2의 합의 수만 있습니다. 이러한 약한 동기화 프리미티브의 경우 전문화 된 명령어의 오버 헤드없이 읽기/쓰기 메모리 장벽을 사용하는 것만으로 충분합니다. (2) ABA 문제는 해결책이별로없는 현실적인 문제입니다. 그러나 CAS (32 비트 시스템에서는 cmpxchg8b, x86/-64에서는 64 비트 시스템에서 cmpxchg16b)를 사용하면 ABA가 실제로 발생하지 않는 큰 시간 스탬프를 저장하기에 레지스터의 윗부분에 충분한 공간이 있습니다 (상당히 고안된 설정이라 할지라도 하나의 스레드가 며칠 또는 몇 주 동안 멈추고 정확한 순간에 깨어나야합니다).

그러나 잠금없는 대기열 (목록이 아닌)을 구현하려고합니다. 대기열은 목록보다 구현하기가 훨씬 쉽습니다. Edya Lazan-Mozes와 Nir Shavit의 "Lock-free FIFO 큐에 대한 낙관적 접근"과 Maged M. Michael과 Michael L. Scott의 "Simple, Fast, Practical Non-Blocking 및 Blocking Concurrent Queue Algorithms" 잠금없는 큐 구현을 위해 매우 유익하고 쉽게 접근 할 수 있습니다.

그러나 잠금없는 연결 목록을 주장하는 경우 Michail Fomitchev 및 Eric Ruppert의 "Lock-Free Linked Lists 및 Skip Lists"의 구현을 고려하십시오. Damian Dechev의 lock-free 동적 배열 (Wikipedia의 링크가 있음)을 살펴볼 수도 있습니다.