无锁编程

好久没写blog, 最近都在研究无锁算法, 一直在纠结为什么无锁高效, 无锁是否是真的无锁.

看了coolshell的无锁队列后, 曾经专门做过锁的性能测试. 自以为发现了无锁的高效之处.

可是真到我的无锁队列写出之后, 突然间感觉之前的测试太片面了, 无锁对于效率的提升也许并没有我想象的那么高, 也许并非无锁
当然其效率提升其实已经很显著了在某些条件下.

再回过头看重新看了一下coolshell中对的无锁队列下面的那行总结”如果不用专门的车锁, 那么就得自己锁自己”, 突然间发现大牛的观点与我一样.

下面看一段coolshell上的代码:

EnQueue(x) //进队列
{
//seg1
q = new record();

//seg2
q->value = x;
q->next = NULL;

//seg3
do {
p = tail;
} while( CAS(p->next, NULL, q) != TRUE);

CAS(tail, p, q); //置尾结点
//seg4
}

从代码上分析看出, 整个函数可分为3段:

seg1~seg2之间其实肯定是有锁的, 因为分配内存函数必然有锁.
seg2~seg3之间是可以并发执行的, 如果有2核的cpu同时跑2个线程那么这一段代码是可以并行执行的.
seg3~seg4之间作用也与锁等价, 在这段区间内如果cas失败了, 必然会引起线程切换, 否则这个线程永远也不会成功(同时有3个线程执行到seg3之后, cpu只有两个核的情况下).

如果EnQueue写成有锁的话那么seg1~seg4是全段加锁的.

所以比较一下有锁与无锁的本质来看, 可以看出其实虽然是无锁编程虽然号称无锁但其实也是有锁的, 只不过是换了一种形式的锁而已.
从锁的范围来看, 可以看出无锁编程中锁的区域更小, 线程之间碰撞概率更小, 那么引起线程切换的概率会更小, 线程切换带来的开锁会更小.



发表评论