0

きめの細かいロック メカニズムを使用して、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;
    }   
}
4

1 に答える 1