Я пишу безблокировочного двусвязного список, основанный на этих работах:атомарные операции для безблокировочного двусвязному список
«Эффективная и надежная блокировка свободной Рекультивация памяти на основе Reference Counting» Андерс Gidenstam, член , IEEE, Марина Papatriantafilou, ˙h акан Санделл и Philippas Tsigas
«Блокировка-двусторонние очереди бесплатно и дважды связанные списки» Хакан Санделл, Philippas Tsigas
Для этого вопроса мы можем отложить первый документ.
В этой статье они используют умный способ хранения флага удаления и указателя в слове. (Подробнее here)
Псевдо-код для этого раздела в газете:
union Link
: word
(p,d): {pointer to Node, boolean}
structure Node
value: pointer to word
prev: union Link
next: union Link
И мой код выше псевдокода:
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) {};
};
В этой статье есть эта функция для набора метка удаления ссылки ссылается на true:
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;
И мой код для этой функции:
void _setMark(Link* pLink)
{
while (bcTRUE)
{
Link lOld = *pLink;
if(pLink->del() || pLink->compareAndSwap(lOld, Link(pLink->pointer(), bcTRUE)))
break;
}
}
Но моя проблема заключается в compareAndSwap функции, где я должен сравнить и поменять три атомные переменные. Информация о проблеме является here
(на самом деле new переменными сравнения и функция подкачки не важна, потому что нить местным)
Теперь моим вопрос: как я могу написать функцию, чтобы сравнить сравнение с обменом и своп три атомного varialbe или где я делаю ошибку?
(Извините за длинный вопрос)
Edit:
похожей проблема в менеджер памяти бумаге:
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;
здесь я должен сравнить и своп три атомных переменный. (Обратите внимание, что мои аргументы типа Link и я должен сравнить и поменять mPointer из Link)
Я думаю, что все еще нормально использовать верхний бит, если вы маскируете логическое значение, прежде чем пытаться использовать указатель. Хотя технически это было бы неопределенное поведение. –
Ваш разговор о побитом ИЛИ правилен, но, в общем, я хочу использовать CAS. – MRB
@AlanStokes: это не нормально на x86-64. Все биты над «допустимыми» битами должны быть правильными значениями (такое же значение, как бит 47). Конечно, вы можете использовать высокий бит, но тогда вам нужно найти способ установить его на правильное одно или нулевое значение на основе бит 47, который имеет тенденцию становиться довольно грязным. –