确保使用双比较和交换指令,用于无锁堆栈? [英] Ensuring usage of double-compare-and-swap instruction, for lock-free stack?
问题描述
(假设64位x86-64架构和英特尔第3代/第4代CPU)
(Assume 64-bit x86-64 architecture and Intel 3rd/4th generation CPU)
这是一个无锁的实现,第202页:
Here is a lock-free implementation for a stack from Concurrency in Action book, page 202:
template<typename T>
class lock_free_stack
{
private:
struct node;
struct counted_node_ptr
{
int external_count;
node* ptr;
};
struct node
{
std::shared_ptr<T> data;
std::atomic<int> internal_count;
counted_node_ptr next;
node(T const& data_):data(std::make_shared<T>(data_)),internal_count(0){}
};
std::atomic<counted_node_ptr> head;
public:
~lock_free_stack()
{
while(pop());
}
void push(T const& data)
{
counted_node_ptr new_node;
new_node.ptr=new node(data);
new_node.external_count=1;
new_node.ptr->next=head.load();
while(!head.compare_exchange_weak(new_node.ptr->next,new_node));
}
};
它在代码下面说:
在那些支持double-word-compare-and-swap
操作的平台上,这个结构将足够小,
std :: atomic是无锁的。 / p>
On those platforms that support a double-word-compare-and-swap operation, this structure will be small enough for std::atomic to be lock-free.
我相信x86-64确实支持double CAS(我不记得我头顶的指令名称) 。
I believe x86-64 does have support for the double CAS (I cannot remember the name of the instruction off the top of my head).
如果我要检查程序集(我看不到双CAS指令),我需要写入什么内联汇编函数,使用CAS?
更新 - 我想我已经找到了我在这里寻找的东西:
UPDATE - I think I have found what I was looking for here:
http:// blog.lse.epita.fr/articles/42-implementing-generic-double-word-compare-and-swap-.html
template<typename T>
struct DPointer <T,sizeof (uint64_t)> {
public:
union {
uint64_t ui[2];
struct {
T* ptr;
size_t count;
} __attribute__ (( __aligned__( 16 ) ));
};
DPointer() : ptr(NULL), count(0) {}
DPointer(T* p) : ptr(p), count(0) {}
DPointer(T* p, size_t c) : ptr(p), count(c) {}
bool cas(DPointer<T,8> const& nval, DPointer<T,8> const& cmp)
{
bool result;
__asm__ __volatile__ (
"lock cmpxchg16b %1\n\t"
"setz %0\n"
: "=q" ( result )
,"+m" ( ui )
: "a" ( cmp.ptr ), "d" ( cmp.count )
,"b" ( nval.ptr ), "c" ( nval.count )
: "cc"
);
return result;
}
// We need == to work properly
bool operator==(DPointer<T,8> const&x)
{
return x.ptr == ptr && x.count == count;
}
};
推荐答案
x86_64的最旧版本不支持此指令(CMPXCHG16B),这是Windows 8.1 / 64位及更高版本所必需的。 Afaik这是大部分的Athlon64系列(插座751,939和一些X2的,也许是第一代(8xx)Pentium D)
The oldest versions of the x86_64 do not support this instruction (CMPXCHG16B), which is required for Windows 8.1/64-bit and newer. Afaik this is most of the Athlon64 range (socket 751, 939 and some of the X2's, maybe the first generation (8xx) of Pentium D too)
如何强制编译器使用一定的指令变化,通常必须使用不完全移植的内在。
How to force a compiler to use a certain instruction varies, usually one must use a not wholly portable intrinsic.
这篇关于确保使用双比较和交换指令,用于无锁堆栈?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!