Мелкозернистая блокировка в Skip List

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);

Документ, приведенный в кодировке скиплиста

@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},
}

Редактировать: Код для вставки узла в список пропусков

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. Таким образом, каждый поток будет пытаться получить такую ​​же блокировку в то же время через список пропусков.

Я предлагаю поискать копию "Искусство многопроцессорного программирования", глава 14 рассказывает о скиплистах.