TBB 동시 정렬되지 않은 맵으로 인해 segfault가 발생합니다.

Question

동시에 삽입하고 가져 오는 다중 스레드를 지원하는 거대한 해시 테이블을 구현해야합니다. 키는 int이고 두 번째 요소는 객체 T의 벡터입니다.

class T { 
     //class definitions here 
} 

현재 구현에는 tbb :: concurrent_unordered_map이 도움이됩니다. 이 문서에서는 삽입 및 순회를 동시에 허용하는 것으로 보입니다. 그러나 여러 개의 pthread를 실행하면 순차 테스트가 완벽하게 잘되지만 세그멘테이션 오류가 발생합니다. 지우기 또는 팝 작업이 전혀 없습니다. 즉 해시 테이블 만 커질 수 있습니다. 무슨 일이 있었는지 디버깅하려면

std::vector<T*> get(int key) { 
     //Note that the hash table hashTable is shared by multiple threads 
     tbb::concurrent_unordered_map<int, std::vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       return it->second; 
     else { 
       std::vector<T*> newvector; 
       return newvector; 
     } 
} 

void insert(int key, T *t) { 
     tbb::concurrent_unordered_map<int, std::vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       it->second.push_back(t); 
     else { 
       std::vector<T*> newTs; 
       newTs.push_back(t); 
       hashTable.insert(it, makepair(key, newTs)); 
     } 
} 

, 내가 먼저 :: TBB하는 concurrent_vector을 표준 : : 벡터를 변경 한 다음 함수의 get()를 수정 및 삽입() 다음과 같은.

std::vector<T*> get_test(int key) { 
     std::vector<T*> test; 
     //Note that the hash table hashTable is shared by multiple threads 
     tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       test.insert(test.end(), it->second.begin(), it->second.end()); 
     for (T* _t : test) 
       if (!_t) 
         printf("Bug happens here!\n"); //Segfault is originated here because a NULL is returned in the vector 
     return test; 
} 

void insert_test(int key, T *t) { 
     //Here t is guaranteed to be not NULL 
     if(!t) 
       std::terminate(); 
     tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       it->second.push_back(t); 
     else { 
       std::vector<T*> newTs; 
       newTs.push_back(t); 
       hashTable.insert(it, makepair(key, newTs)); 
     } 
} 

이제 우리는 병렬 프로그램이 충돌하는 이유는 일부 NULL 포인터가 get_test() 함수에서 반환된다는 것을 알 수 있습니다. insert_test() 함수에서 NULL은 절대로 두 번째 요소로 삽입되지 않습니다.

다음 질문을하십시오.

(1) tbb :: concurrent_unordered_map의 동시 삽입으로 인해 일부 삽입 시도가 실패하고 temp 객체가 손상 될 수 있습니다. 이것이 NULL이 get_test() 함수에서 관찰되는 이유입니까?

(2) TBB가 실제로 삽입 및 순회를 허용 할 수 있습니까? 즉, 일부 스레드가 삽입되는 동안 다른 스레드는 get()을 동시에 호출 할 수 있습니다.

(3) 더 나은 구현, 즉 동시 삽입 및 읽기를 지원하는 더 나은 동시 해시 테이블이 있습니까? @for_stack 제안으로

---

, 내가 확인 한 두 번째 요소는 concurrent_vectors하고 전체 프로그램은 실행 가능한 것입니다. 다음과 같은 추가의 시험은 실시된다

는

tbb::concurrent_vector<T*> get_test(int key) { 
      tbb::concurrent_vector<T*> test; 
      //Note that the hash table hashTable is shared by multiple threads 
      tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
      if (it != hashTable.end()) 
        test = it->second; 
      int i = 0; 
      for (T* _t : test) 
        if (!_t) 
          i++; 
      if (i > 0) 
        printf("%d of %lu Ts are NULL\n", i, test.size()); //Segfault is originated here because a NULL is returned in the vector 
      return test; 
} 

void insert_test(int key, T *t) { 
     //Here t is guaranteed to be not NULL 
     if(!t) 
       std::terminate(); 
     tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       it->second.push_back(t); 
     else { 
       tbb::concurrent_vector<T*> newTs; 
       newTs.push_back(t); 
       hashTable.insert(it, make_pair(key, newTs)); 
     } 
} 

출력이 모든 개체 (T)가 (이) NULL이다 GET에 반환되지 수단

1 of 2 Ts are NULL 

이다.

---

다시 한 번 순차적으로 (또는 1 스레드로) 실행해도 문제가 없습니다.

Answer 1

TBB 은 concurrent_xxx 컨테이너의 동시 삽입 및 순회를 지원합니다. 그러나, 원래의 코드가 경쟁 조건 : 다른 스레드가 vector<T*> (쓰기)을 수정할 insert를 호출하는 반면

std::vector<T*> get(int key) { 
    // other code 
    return it->second; # race condition 1 
    // other code 
} 

get 기능, vector<T*>의 사본을 (이을 읽기) 반환하려고합니다.

void insert(int key, T *t) { 
    // other code 
    it->second.push_back(t); # race condition 2 
    // other code 
} 

insert 함수는 잠금 가드로 vector<T*>을 수정하려고합니다. 여러 스레드가 동시에 insert을 호출하는 경우 (복수 쓰기), OOPS!

concurrent_unordered_map은 컨테이너 작업에 대해서만 안전성이 보장되며 mapped_value에서는 작동 할 수 없습니다. 너 혼자해야 해.

시도한 것처럼 vector<T*>을 concurrent_vector<T*>으로 바꿀 수 있습니다. 그러나 컴파일되지 않습니다 게시 된 새로운 코드, 당신은 insert_test의 구현을 수정해야합니다 ". TBB는 concurrent_xxx 컨테이너에 대한 동시 삽입 및 통과를 지원할 수있다"

void insert_test(int key, T *t) { 
    //Here t is guaranteed to be not NULL 
    if(!t) 
      std::terminate(); 
    tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
    if (it != hashTable.end()) 
      it->second.push_back(t); 
    else { 
      // std::vector<T*> newTs; # this is wrong! 
      tbb::concurrent_vector<T*> newTs; 
      newTs.push_back(t); 
      hashTable.insert(it, make_pair(key, newTs)); // it should be make_pair not makepair 
    } 
} 

Answer 2

을 - 정확히. 순회는 TBB 에서처럼 메모리 교정 지원이없고 컨테이너 (concurrent_hash_map)가 동시 삭제를 지원할 때 까다로운 작업입니다. 그러나 concurrent_unordered_map은 스레드 안전성 erase()을 지원하지 않으므로 스레드 안전성 탐색이 지원됩니다.

Answer 3

@Anton concurrent_unordered 컨테이너는 동시 트래버스와 삽입을 지원합니다. 그들은 건너 뛰기 목록으로 구현됩니다. non-multi 인 경우 포인터 스윙의 결과가 테스트되고 실패하면 삽입 지점에서 검색이 다시 시작됩니다.

이제 C++ 내가 인텔에서 근무하기 때문에 지난 몇 주에 변경되었을 수 있습니다,하지만 난 원래 코드에 심각한 버그가 있다고 생각 : 참조 또는 포인터하지,

if (it != hashTable.end()) 
     return it->second;   // return a copy??? 
else { 
     std::vector<T*> newvector; // this is stack-allocated 
     return newvector;   // return a copy?? 
} 

반환 값이 벡터 벡터이므로 현재 내용의 복사본을 반환 값으로 가져오고 복사본에 삽입하면 집합에있는 벡터가 변경되지 않습니다. 어쩌면이를 수정하고 벡터에 대한 비동기 참조가 없는지 확인한 다음 나머지 버그를 찾으십시오.