Ich schreibe eine doppelt verknüpfte Liste ohne Sperre auf der Grundlage dieser Papiere:

"Effiziente und zuverlässige sperrenfreie Speicherrückgewinnung basierend auf Referenzzählung" Anders Gidenstam, Mitglied, IEEE, Marina Papatriantafilou, Hou akan Sundell und Philippas Tsigas

"Lock-free-Deques und doppelt verknüpfte Listen" Håkan Sundell, Philippas Tsigas

Für diese Frage können wir das erste Blatt beiseite legen.

In diesem Artikel verwenden sie eine intelligente Methode zum Speichern eines Löschflags und eines Zeigers in einem Wort. (Mehr InfoHier)

Pseudocode für diesen Abschnitt im Artikel:

union Link
    : word
    (p,d): {pointer to Node, boolean} 

structure Node
    value: pointer to word
    prev: union Link
    next: union Link

Und mein Code für den obigen Pseudocode:

template< typename NodeT >
struct LockFreeLink
{
public:
    typedef NodeT NodeType;

private:

protected:
    std::atomic< NodeT* > mPointer;

public:
    bcLockFreeLink()
    {
        std::atomic_init(&mPointer, nullptr);
    }
    ~bcLockFreeLink() {}

    inline NodeType* getNode() const throw()
    {
        return std::atomic_load(&mPointer, std::memory_order_relaxed);
    }
    inline std::atomic< NodeT* >* getAtomicNode() const throw()
    {
        return &mPointer;
    }
};

struct Node : public LockFreeNode
{
    struct Link : protected LockFreeLink< Node >
    {
        static const int dMask = 1;
        static const int ptrMask = ~dMask;

        Link() { } throw()
        Link(const Node* pPointer, bcBOOL pDel = bcFALSE) throw()
        { 
            std::atomic_init(&mPointer, (reinterpret_cast<int>(pPointer) | (int)pDel)); 
        }

        Node* pointer() const throw() 
        { 
            return reinterpret_cast<Node*>(
                std::atomic_load(&data, std::memory_order_relaxed) & ptrMask); 
        }
        bool del() const throw() 
        { 
            return std::atomic_load(&data, std::memory_order_relaxed) & dMask; 
        }
        bool compareAndSwap(const Link& pExpected, const Link& pNew) throw() 
        { 
            Node* lExpected = std::atomic_load(&pExpected.mPointer, std::memory_order_relaxed);
            Node* lNew = std::atomic_load(&pNew.mPointer, std::memory_order_relaxed);

            return std::atomic_compare_exchange_strong_explicit(
                &mPointer,
                &lExpected,
                lNew,
                std::memory_order_relaxed,
                std::memory_order_relaxed); 
        }

        bool operator==(const Link& pOther) throw() 
        { 
            return std::atomic_load(data, std::memory_order_relaxed) == 
                std::atomic_load(pOther.data, std::memory_order_relaxed); 
        }
        bool operator!=(const Link& pOther) throw() 
        { 
            return !operator==(pOther); 
        }
    };

    Link mPrev;
    Link mNext;
    Type mData;

    Node() {};
    Node(const Type& pValue) : mData(pValue) {};
};

In diesem Artikel gibt es diese Funktion, um die Löschmarkierung des Links auf true zu setzen:

procedure SetMark(link: pointer to pointer to Node)
    while true do
       node = *link;
       if node.d = true or CAS(link, node, (node.p, true)) then break;

Und mein Code für diese Funktion:

void _setMark(Link* pLink)
{
    while (bcTRUE)
    {
        Link lOld = *pLink;
        if(pLink->del() || pLink->compareAndSwap(lOld, Link(pLink->pointer(), bcTRUE)))
            break;
    }
}

Aber mein Problem ist incompareAndSwap Funktion, in der ich drei atomare Variable vergleichen und tauschen muss. Informationen zum Problem sindHier

(Tatsächlichnew Variable in der Vergleichs- und Tauschfunktion ist nicht wichtig, da sie threadlokal ist)

Nun meine Frage: Wie kann ich eine compareAndSwap-Funktion schreiben, um drei atomare Variablen zu vergleichen und zu tauschen, oder wo mache ich einen Fehler?

(Entschuldigung für die lange Frage)

Bearbeiten:

Ein ähnliches Problem tritt beim Speichermanager auf:

function CompareAndSwapRef(link:pointer to pointer toNode,
old:pointer toNode, new:pointer toNode):boolean
    if CAS(link,old,new) then
        if new=NULL then
            FAA(&new.mmref,1);
            new.mmtrace:=false;
    if old=NULLthen FAA(&old.mmref,-1);
    return true;
return false; 

Auch hier muss ich drei atomare Variablen vergleichen und tauschen. (Beachten Sie, dass meine Argumente von Art sindLink und ich muss vergleichen und tauschenmPointer vonLink)