打印本文   关闭窗口

LockFree结构开发注意事项

作者：佚名  文章来源：不详  点击数  更新时间：2008/10/22 21:33:20  文章录入：杜斌  责任编辑：杜斌

重写内存分配器，系统上用的内存分配器很不方便，为了加入引用计数功能而牺牲了简单性，而且为了线程安全用了一些锁。这次做到了所有内存分配和释放都是Lock Free的。因为内存块之间是单链表，所以实现Lock Free比较简单。难的地方是管理空闲资源是用的一个数组，这时要使用DCAS及类似的方法（k word compare and k-th swap）。我的电脑不支持CAS操作，所以无法判断。在远程服务器上，100个线程同时分配1000~100000不等个4字节大小的内存，内存池从40字节起增长，无锁结构用时15秒左右，有锁结构用时9秒左右。用10个线程同时分配900000~1000000不等个4字节大小的内存，内存池从40字节起增长，无锁结构用时14秒左右，有锁结构用时14秒左右。用5个线程同时分配1800000~2000000不等个4字节大小的内存，内存池从40字节起增长，无锁结构用时8秒左右，有锁结构用时13秒左右。 　　考试大测试显示，无锁结构在线程数接近内核实际数量的时候表现才优于有锁结构。而在大量线程工作时候效果不佳。因为内存分配使用的是数组结构而不是单链表结构，理论上，每次操作都和整个数组相关，因此会造成数个线程的原子操作都在等待一个数组的完成，产生大量垃圾代码，影响了执行效率。而在线程数量较少的情况下，锁的开销会比垃圾代码执行的开销大。 　　下面是DCAS利用CAS进行模拟的一个方法： 　　bool cas(volatile void** x, void* new_x, void* old_x); 　　bool dcas(volatile void** x, void* new_x, void* old_x, volatile void** y, void* new_y, void* old_y) 　　{ 　　if (old_x == DCAS_BUSY_VAL) 　　return false; 　　if (!cas(x, DCAS_BUSY_VAL, old_x)) 　　return false; 　　if (!cas(y, new_y, old_y)) 　　{ 　　x = old_x; 　　return false; 　　} 　　x = new_x; 　　return true; 　　} 　　基本模拟思路是在对y变量进行更新之前，用一个DCAS_BUSY_VAL的变量将x变量锁定，然后就可以安全更新y变量，再安全更新x变量。其他的k-compare-and-k-swap都可以用这个思路实现。 来源：考试大

打印本文   关闭窗口