잠금없는 참조 카운트 역 참조에 레이스 조건을 극복

Question

이런 구조를 상상해

가

struct my_struct** table; 

my_struct* my_struct_lookup(const char* name) 
{ 
    my_struct* s = table[hash(name)]; 

    /* EDIT: Race condition here. */ 

    atomic_inc(&s->refs); 

    return s; 
} 

레이스 사이에 존재한다 : 포인터는 룩업 테이블을 통해 획득되는

struct my_struct { 
    uint32_t refs 
    ... 
} 

다중 참조 모델에서 참조 해제 및 원자 증가. 이것이 매우 중요한 코드라는 것을 감안할 때, 나는이 레이스가 어떻게 역 참조와 원자 증가가 일반적으로 해결되거나 해결되는지 궁금해하고 있었습니까?

편집 : 룩업 테이블을 통해 my_struct 구조체에 대한 포인터를 획득 할 때 먼저 참조를 증가시키기 위해 구조를 역 참조해야합니다. 다른 스레드가 참조 카운트를 변경하고 잠재적으로 객체 자체의 할당을 해제 할 때 다른 스레드가 존재하지 않는 메모리에 대한 포인터를 비 참조 할 때 다중 스레드 코드에서 문제가 발생합니다. 선매 및 불운과 결합하여 재앙을 초래할 수 있습니다.

Answer 1

누군가 위에서 말했듯이, 나중에 링크 된 메모리 목록을 해제하여 포인터를 무효로 만들 수 없습니다. 어떤 경우에는 편리한 방법입니다.

또는 ....당신은 당신의 32 비트 포인터로 64 비트 구조체를 만들 수 있고 ref 카운트와 다른 플래그들에 대해 32 비트를 가질 수 있습니다. 당신이 노동 조합에 포장하는 경우는 구조체에 64 비트 원자 작전을 사용할 수 있습니다

union my_struct_ref { 
    struct { 
     unsigned int  cUse  : 16, 
         fDeleted : 1; // etc 
     struct my_struct *s; 
    } Data; 
    unsigned long n64; 
} 

당신은 인간이 판독 가능 구조체의 데이터 부분을 작업 할 수 있습니다, 그리고 당신은 N64 비트 부분에 CAS를 사용할 수 있습니다.

my_struct* my_struct_lookup(const char* name) 
{ 
    struct my_struct_ref Old, New; 
    int iHash = hash(name); 

    // concurrency loop 
    while (1) { 
     Old.n64 = table[iHash].n64; 
     if (Old.Data.fDeleted) 
     return NULL; 
     New.n64 = Old.n64; 
     New.Data.cRef++; 
     if (CAS(&table[iHash].n64, Old.n64, New.n64)) // CAS = atomic compare and swap 
     return New.Data.s; // success 
     // we get here if some other thread changed the count or deleted our pointer 
     // in between when we got a copy of it int old. Just loop to try again. 
    } 
} 

64 비트 포인터를 사용하는 경우 128 비트 CAS를 수행해야합니다.

Answer 2

한 가지 해결책은 malloc() 및 free() 대신 freelist를 사용하는 것입니다. 이것은 명백한 결점이있다.

또 하나는 잠금 해제 가비지 수집 (안전한 메모리 교정이라고도 함)을 구현하는 것입니다.

이 필드에는 많은 특허가 있지만 획기적인 LFGC가 방해받지 않는 것처럼 보입니다.

이 방법을 사용하는 것은 요소가 스레드를 가리키고 있지 않을 때에 만 할당을 해제한다는 것입니다.

이전 솔루션은 구현하기가 쉽습니다. 물론 자물쇠가없는 프리리스트가 필요합니다. 그렇지 않으면 전체 시스템에 더 이상 자물쇠가 없습니다.

후자는 실제로 복잡하지 않지만 문제의 알고리즘을 학습해야합니다. 시간과 연구가 필요합니다.

Answer 3

당신이 확인한 경주 이외에도,의 메모리 일관성 문제가 있습니다.

테이블 수정을 자물쇠가없는 방식으로 만들 수 있다고해도 메모리 블록 my_struct*은 마지막으로 수정 한 스레드와 다른 스레드에서 볼 때 여전히 "부실"할 수 있습니다. 이는 my_struct.refs에는 적용되지 않으며 (은 항상에 원자 단위로 액세스 함) 다른 모든 필드에도 적용됩니다. 이것은 각 CPU 코어에 대해 "전용"인 쓰기 버퍼와 캐시의 결과입니다.

올바른 메모리 내용을 보도록 보장하는 유일한 방법은 메모리 장벽을 사용하는 것입니다. 그러나 일반적인 자물쇠는 입니다.은 메모리 장벽입니다. 그래서 처음부터 자물쇠를 사용하지 않는 이유는 무엇입니까?

잠금없는 프로그래밍은 처음에는 생각했던 것보다 훨씬 까다 롭습니다. OTOH 잠금은 특히 경합이 거의 발생하지 않는 경우 매우 빠릅니다. 실제로 잠금 기반 구현을 벤치 마크하고 잠금이 실제로 병목 현상임을 확인 했습니까?