Boost Lockfree

Boost Lockfree

flyfish 2014-9-30

为了最大限度的挖掘并行编程的性能考虑使用与锁无关的数据结构来编程
与锁无关的数据结构不是依赖于锁和相互排斥来确保线程安全。


Lockfree的重要操作就是CAS（Compare And Set）原子操作
原子操作就是多个线程訪问同一个资源时，有且仅有唯一 一个线程对该资源进行操作
BOOST中的宏定义
BOOST_ATOMIC_DETAIL_X86_HAS_CMPXCHG8B
BOOST_ATOMIC_DETAIL_X86_HAS_CMPXCHG16B
cmpxchg：比較并交换，也就是
伪代码

bool CAS(int* p,int nOld,int nNew)
{
	bool bRet=false;
	if (*p == nOld)
	{
		*p=nNew;
		bRet=true;
	}


	return bRet;
}

CAS操作产生的ABA问题

两个线程P1和P2
P1读变量A
P1中断，
P2開始执行，读变量A，更改为B，又更改为A，
P2运行完
P1继续操作，A还是A，P1觉得什么也没有发生


比如
栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构，仅仅同意在栈顶操作。
如果有一个栈，有三个元素
A
B
C
线程P1，P2对该栈进行操作
P1 读栈顶A
P1 中断
P2 開始执行，A出栈，B出栈，A压栈（删除B）
P1 继续运行，A还是A
P1觉得该栈的结构还是ABC，而此时栈里仅仅有两个元素


就像小时候在家偷看电视，防止电视过热被父母发现，看一会儿就关上，等会儿再看。
当听见开门的声音时，以迅雷不及掩耳之势，换回開始的频道，调回音量图标的格数，关上电视，放回遥控器原来的位置并注意遥控器的朝向来表明没有看电视。


64位平台的处理方案
看boost::lockfree::detail::tagged_ptr代码

解决方案1
文件tagged_ptr_dcas.hpp
简化代码

template <class T>
class  tagged_ptr
{
public:
    typedef std::size_t tag_t;
protected:
    T * ptr;
    tag_t tag;
};

ABA问题解决方案是一个std::size_t类型的tag+指针，但不是全部平台都支持。


解决方案2
文件tagged_ptr_ptrcompression.hpp
简化代码

#if defined (__x86_64__) || defined (_M_X64)
class tagged_ptr
{
    typedef boost::uint64_t compressed_ptr_t;


public:
    typedef boost::uint16_t tag_t;


private:
    union cast_unit
    {
        compressed_ptr_t value;
        tag_t tag[4];
    };


    static const int tag_index = 3;
    static const compressed_ptr_t ptr_mask = 0xffffffffffffUL; //(1L<<48L)-1;
......
}


#else
#error unsupported platform
#endif

早期X86-64处理器不支持cmpxchg16b指令
在X86-64平台上，48位是地址，剩下的16位是ABA预防tag
代码
static const compressed_ptr_t ptr_mask = 0xffffffffffffUL; //(1L<<48L)-1;
0xffffffffffff二进制就是48个1。
tag就像一个版本，通过tag，线程能够知道操作的数据已经发生了变化。