Многопоточный алгоритм двоичного дерева

Question

Итак, я попробовал один метод, который блокирует каждый узел, когда он смотрит на него, но для этого требуется ОЧЕНЬ МНОГО блокировки и разблокировки ... что, конечно, требует немало накладных расходов.Мне было интересно, если кто-нибудь знает о более эффективном алгоритме.Вот моя первая попытка:

typedef struct _treenode{
   struct _treenode *leftNode;
   struct _treenode *rightNode;
   int32_t data;
   pthread_mutex_t mutex;
}TreeNode;

pthread_mutex_t _initMutex = PTHREAD_MUTEX_INITIALIZER;

int32_t insertNode(TreeNode **_trunk, int32_t data){
   TreeNode **current;
   pthread_mutex_t *parentMutex = NULL, *currentMutex = &_initMutex;

   if(_trunk != NULL){
      current = _trunk;
      while(*current != NULL){
         pthread_mutex_lock(&(*current)->mutex);
         currentMutex = &(*current)->mutex;
         if((*current)->data < data){
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            pthreadMutex = currentMutex;
            current = &(*current)->rightNode;
         }else if((*current)->data > data){
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            parentMutex = currentMutex;
            current = &(*current)->leftNode;
         }else{
            pthread_mutex_unlock(currentMutex);
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            return 0;
         }
      }
      *current = malloc(sizeof(TreeNode));
      pthread_mutex_init(&(*current)->mutex, NULL);
      pthread_mutex_lock(&(*current)->mutex);
      (*current)->leftNode = NULL;
      (*current)->rightNode = NULL;
      (*current)->data = data;
      pthread_mutex_unlock(&(*current)->mutex);
      pthread_mutex_unlock(currentMutex);
   }else{
      return 1;
   }
   return 0;
}

int main(){
   int i;
   TreeNode *trunk = NULL;
   for(i=0; i<1000000; i++){
      insertNode(&trunk, rand() % 50000);
   }
}

Answer 1

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

Java представила список одновременных пропусков в версии 1.6.Списки пропуска работают как деревья, но (предположительно) немного медленнее.Тем не менее, они основаны на односвязных списках и поэтому могут быть теоретически изменены без блокировки с помощью сравнения и замены.Это обеспечивает превосходную многопотоковую производительность.

Я гуглил "skip list" C ++ сравните-и-поменяйте и получил некоторую интересную информацию, но без кода C ++.Тем не менее, Java с открытым исходным кодом, поэтому вы можете получить алгоритм, если вы достаточно отчаялись.Класс Java: java.util.concurrent.ConcurrentSkipListMap .

Answer 2

Другой простой способ - иметь 1 блокировку для полного дерева.

У вас есть более последовательный доступ к дереву, но у вас есть только один мьютекс и вы блокируете только один раз.Если сериализация является проблемой, вы используете блокировку чтения / записи .так что, по крайней мере, чтение может выполняться параллельно.

Answer 3

Использовать блокировку чтения-записи. Блокировка отдельных узлов станет исключительно трудной, если впоследствии вы решите переключить реализацию дерева. Вот небольшой демонстрационный код с использованием pthreads :

typedef struct {
    pthread_rwlock_t rwlock;
    TreeNode *root_node;
} Tree;

void Tree_init(Tree *tree) {
    pthread_rwlock_init(&tree->rwlock, NULL);
    tree->root_node = NULL;
}

int32_t Tree_insert(Tree *tree, int32_t data) {
    pthread_rwlock_wrlock(&tree->rwlock);
    int32_t ret = _insertNode(&tree->root_node, data);
    pthread_rwlock_unlock(&tree->rwlock);
    return ret;
}

int32_t Tree_locate(Tree *tree) {
    pthread_rwlock_rdlock(&tree->rwlock);
    int32_t ret = _locateNode(&tree->root_node);
    pthread_rwlock_unlock(&tree->rwlock);
    return ret;
}

void Tree_destroy(Tree *tree) {
    pthread_rwlock_destroy(&tree->rwlock);
    // yada yada
}

Answer 4

Вам не нужно блокировать каждый узел, который вы посещаете.Вы можете сделать что-то вроде этого.Блокировка узла, когда вы собираетесь сделать вставку.Сделайте вставку и разблокируйте.Если другой поток должен вставить его в ту же точку и узел заблокирован, он должен подождать, прежде чем продолжить работу.После того как узел разблокирован, он может продолжить обход обновленной части дерева.