首次接触无锁数据结构的设计，请各位大佬多多指教~~~
CAS(Compare && Swap)原子操作
CAS是无锁(lock free)的数据结构的基础。用伪代码描述：
input: reg, old_val, new_val
/*是old_val， reg替换为new_val，返回为true；否则返回为false*/
if (* reg == old_val) {
* reg == new_val;
return true;
} else {
return false;
}
CAS相似的原子操作：
fetch and add，一般用来对变量做+1的原子操作
test and set， 写值到内存位置并传回其旧值
test test and set : 和双检查锁一样为了减少对锁的多次竞争，对锁的竞争代价比普通判断锁的状态要大，这里需要着重强调，在high level programming的背景下，尽量少用双重检测锁的形式，因为第二次检查和设置并不一定是原子操作。test test and set伪代码（Wikipedia test test and set）如下:
boolean locked := false // shared lock variable
procedure EnterCritical() {
do {
while (locked == true) skip // spin until lock seems free
} while TestAndSet(locked) // actual atomic locking, this cost of step >> the cost above !!!;
}
在此稍微记录一下，
- GCC的原子CAS的API
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
- C++11的CAS
C++11的STL中的atomic类的函数可以跨平台。
template< class T >
bool atomic_compare_exchange_weak( std::atomic* obj,
T* expected, T desired );
template< class T >
bool atomic_compare_exchange_weak( volatile std::atomic* obj,
T* expected, T desired );
无锁队列的链表实现
EnQueue(x) {
// 准备新加入的结点数据
q = new record();
q->value = x;
q->next = NULL;
do {
p = tail; // 链表尾指针的快照
} while( CAS(p->next, NULL, q)!= true)
CAS(tail, p, q);
}
do while的Re-Try-Loop，如果别的进程已经加成功了，tail就变了，p!=tail, p->next!= NULL，那么就重试。
这里存在一个问题，如果在CAS(tail, p, q)之前线程挂掉了或者停掉了，其它线程更新了p->next，却没有更新tail，然后就一直进入死循环。为了解决这个问题，下面推出了改良版的EnQueue()
EnQueue(x)
{
q = new record();
q->value = x;
q->next = NULL;
p = tail;
oldp = p;
do {
while (p->next!= NULL) {
p = p->next;
} while (CAS(p->next, NULL, q)!= TRUE); // 如果没有把结点链在尾上，再试
CAS (tail , oldp, q); // 置尾结点
}
}
fetch会很影响性能， 所以可以结合以上两个版本，如果retry的次数超过一个阈值，那么自己就fetch指针。
但是这里存在一个问题，就oldq能不能及时更新，若不能及时更新，其余线程在插入时会插到未定义的位置。个人觉得还是选择未改良版比较好。
DeQueue // 出队列
DeQueue() {
do {
p = head;
if (p -> next == NULL) {
return ERR_EMPTY_QUEUE;
}
} while ( CAS(head, p, p->next)!= TRUE);
return p->next->value;
}
CAS的ABA问题：
- 进程p1在共享变量中读到值为A
- p1被抢占了，进程p2执行
- p2把共享变量里的值从A改成B，再改回到A，此时被p1抢占。
- p1回来看到共享变量里的值没有被改变，于是继续执行。
看来好像没有问题，但是上式的CAS其实判断的是指针地址，然而指针内容改变了，不就炸了？这就是内存管理中的重用内存问题。
解决ABA的问题
例如在32位系统上检查64位的内容：
- 一次用CAS检查双倍长度的值，前半部分是指针，后半部分是一个计数器
- 只有这两个都一样，才算通过，要用该指针符新的值，计数器加1。
这种方法线程次数上应该也没问题，但是一旦多了，可能会溢出循环计数。
所以有论文提出了使用结点内存的引用计数，这和智能指针没啥区别嘛，但是需要保证加引用计数和减引用计数为原子操作。
用数组实现无锁队列
无锁队列可以用ring buffer实现，定位head和tail可以声明两个计数器，一个用来计数EnQueue的次数，一个用来计数DeQueue的次数，当队列满或空，可以抛出异常，没有内存泄露的问题。
reference
[1]. 无锁队列的实现
[2]. 无锁队列的环形数组实现
