标签： lockfree

无锁编程

好久没写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是全段加锁的.

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

锁对于性能的影响

很偶然的机会发现了无锁队列，然后又很偶然的接触到并行编程，虽然还没弄明白内存屏障等问题，但是历史遗留下一小段测试代码，在这段测试代码中我用分别用lock-free或lock-based方式将一个变量进行自增, 效果竟然差的惊人, 肉眼都能感觉到效率不止差了至少四倍之多。下面看代码：

#include <Windows.h>

#define	LOCK_FREE	1

int cnt;
HANDLE hMutex;

static DWORD WINAPI work_thread(void *param)
{
	int i;
	for (i = 0; i < 1000000; i++) {
		#if LOCK_FREE
		//WaitForSingleObject(hMutex, -1);
		InterlockedIncrement((unsigned long *)&cnt);
		//ReleaseMutex(hMutex);
                #else
		WaitForSingleObject(hMutex, -1);
		cnt++;
		ReleaseMutex(hMutex);

                #endif
	}

        return 0;
}

HANDLE thread_begin(int a)
{
        HANDLE hThread = CreateThread(NULL, 0, work_thread, (void *)a, 0, NULL);

	return hThread;

        return 0;
}


int main(int argc, _TCHAR* argv[])
{
	HANDLE h1, h2;

	hMutex = CreateMutex(NULL, FALSE, NULL);

	h1 = thread_begin(0);
	h2 = thread_begin(1);

	WaitForSingleObject(h1, -1);
	WaitForSingleObject(h2, -1);

	printf("%dn", cnt);

	return 0;
}

在这里我使用LOCK_FREE宏来进行切换lock-free方式还是lock-based方式，虽然没有计算时间，但是肉眼都能大概比较出效率至少差了四倍。另外有一点要说的是，这里只是开了两个线程，而且只做了变量自增而已，试想在其他高并发的场合，那么lock-based效率或许将远低于现在的测试情况，所以锁是效率的大敌之一。当然我现在还不太敢用无锁，因为我还没有搞懂什么时间用内存屏障。

————————————————————————–
为了证明是由于资源冲突而不是函数调用拖效率的后腿，可以将main函数中的两句改为如下：

h1 = thread_begin(0);
Sleep(1000);
h2 = thread_begin(1);

Sleep(1000)是为了等第一个线程跑完，这样两个线程跑的次数一样，但是将不再会产生资源冲突， 而且可以看到就算我们延时了1s,但效率远高于两个线程并发执行.