无锁队列 java_无锁队列的总结

无锁队列 java_无锁队列的总结首次接触无锁数据结构的设计,请各位大佬多多指教~~~CAS(Compare&&Swap)原子操作CAS是无锁(lockfree)的数据结构的基础。用伪代码描述:input:reg,old_val,new_val/*是old_val,reg替换为new_val,返回为true;否则返回为false*/if(*reg==old_val){*reg==new...

首次接触无锁数据结构的设计,请各位大佬多多指教~~~

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

架构君码字不易,如需转载,请注明出处:https://javajgs.com/archives/209282
0

发表评论