Мелкозернистая блокировка в списке пропуска

Question

Я пытаюсь реализовать skiplist на основе замка в c, используя мелкозернистый механизм блокировки. При запуске кода применяемый механизм блокировки выглядит грубозернистым. Я установил блокировки в предыдущих узлах для вставки, используя переменную блокировки pthread_mutex_t, определенную внутри структуры узла, и освобождает их после использования. Весь список не заблокирован только узлами заблокированы, но, похоже, он реализует механизм крупнозернистого запирания. Ниже представлен фрагмент кода, в котором выполняется механизм блокировки. Неправильное внедрение?

for(level = 0; valid && (level <=topLevel); level++){ 
      pred = preds[level]; 
      succ = succs[level]; 

      if(pred != prevPred){ 
       pthread_mutex_lock(pred -> lock); 
       highestLocked = level; 
       prevPred  = pred; 
      } 

      valid = !(pred -> marked) && !(succ -> marked) && (pred -> next[level] == succ); 
     } 
     if(!valid){ 
      for(level = 0;level <= highestLocked; level++) 
       pthread_mutex_unlock(preds[level] -> lock); 
      continue; 
     } 
     newNode = createNewNode(x -> val, topLevel); 
     for(level = 0; level <= topLevel; level++){ 
      newNode -> next[level] = succs[level]; 
      preds[level] -> next[level] = newNode; 
     } 
     newNode -> fullyLinked = 1; 
     for(level = 0;level <= highestLocked; level++) 
       pthread_mutex_unlock(preds[level] -> lock); 

Бумага следуют в кодировании skiplist является

@inproceedings{DBLP:dblp_conf/sirocco/HerlihyLLS07, 
    author    = {Maurice Herlihy and 
          Yossi Lev and 
          Victor Luchangco and 
          Nir Shavit}, 
    title    = {A Simple Optimistic Skiplist Algorithm.}, 
    booktitle   = {SIROCCO}, 
    year    = {2007}, 
    pages    = {124-138}, 
    ee     = {http://dx.doi.org/10.1007/978-3-540-72951-8_11}, 
    crossref   = {2007}, 
} 

Edit: Код для вставки узла в skiplist

int add(Node *x, int *preval){ 
    int lFound, highestLocked, valid, level; 
    Node *nodeFound, *pred, *succ, *prevPred, *newNode; 
    // int topLevel = randomLevel(MAX_LEVEL); 
    int topLevel = (rand()%MAX_LEVEL)+1; 
    *preval=topLevel; 
    Node **preds = (Node **)malloc(sizeof(Node *) * (MAX_LEVEL + 1));//predecessor list 
    Node **succs = (Node **)malloc(sizeof(Node *) * (MAX_LEVEL + 1));//successor list 
    while(1){ 
     lFound = find(x, preds, succs);//gets predecessor and successor list of node where x to be inserted 
     if(lFound != -1){ 
      nodeFound = succs[lFound]; 
      if(!nodeFound->marked){ 
       while(!nodeFound->fullyLinked){;} 
       return 0; 
      } 
      continue; 
     } 
     highestLocked = -1; 
     prevPred  = NULL; 
     valid   = 1; 
     for(level = 0; valid && (level <=topLevel); level++){ 
      pred = preds[level]; 
      succ = succs[level]; 
      //locking the predecessor node level 
      if(pred != prevPred){ 
       pthread_mutex_lock(pred -> lock); 
       highestLocked = level; 
       prevPred  = pred; 
      } 

      valid = !(pred -> marked) && !(succ -> marked) && (pred -> next[level] == succ); 
     } 
     //releasing locked nodes 
     if(!valid){ 
      for(level = 0;level <= highestLocked; level++) 
       pthread_mutex_unlock(preds[level] -> lock); 
      continue; 
     } 
     newNode = createNewNode(x -> val, topLevel); 
     for(level = 0; level <= topLevel; level++){ 
      newNode -> next[level] = succs[level]; 
      preds[level] -> next[level] = newNode; 
     } 
     newNode -> fullyLinked = 1; 
     //releasing locked nodes 
     for(level = 0;level <= highestLocked; level++) 
       pthread_mutex_unlock(preds[level] -> lock); 
     return 1; 
    } 
} 

Answer 1

Подумайте о том, какие данные заблокированы ваш «мелкозернистый» замок. Вы блокируете доступ к внутренним спискам скиписта. Доступ к этим спискам необходим, чтобы любой поток мог выполнить поиск по скиписту. На вашей первой итерации цикла for (предполагая pred! = PrevPred в этом случае) вы заблокируете pred-> lock уровня 0. Таким образом, каждый поток попытается получить тот же самый замок одновременно с помощью skiplist.

Предлагаю найти копию книги «Искусство многопроцессорного программирования», глава 14 рассказывает о скипистах.