[ Ngnix与高并发服务器 ] 【守望者高并发】使用CAS实现高效并发处理

2014-10-26 22:30| 发布者: watchmen | 查看: 1800 | 收藏

摘要: 守望者：在并发处理应用中，一般使用锁的方式来解决竞争问题，但锁的效率比较低，因此，在高并发处理中，无锁队列成为应用的需要。CAS无锁算法主要依赖于处理器的支持，绝大多数处理器都支持。 ... ... ...

在并发处理应用中，一般使用锁的方式来解决竞争问题，但锁的效率比较低，因此，在高并发处理中，无锁队列成为应用的需要。CAS无锁算法主要依赖于处理器的支持，绝大多数处理器都支持：

X86平台：CMPXCHG 汇编指令。

在一个指令周期内执行完成，因此是原子性的。

这一原理性操作过程如果采用C描述如下：

intcompare_and_swap (int* reg, int oldval, int newval)

{

int old_reg_val = *reg;

if (old_reg_val == oldval)

*reg = newval;

return old_reg_val;

}

boolcompare_and_swap (int *accum, int *dest, int newval)

{

if ( *accum == *dest ) {

*dest = newval;

return true;

}

return false;

}

API函数GCC4.1

bool__sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)

type__sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

Linux内核中实现方法：

ARM实现版本

staticinline int atomic_cmpxchg(atomic_t *ptr, int old, int new)

{

unsigned long oldval, res;

smp_mb();/*内存屏障*/

do {

__asm__ __volatile__("@atomic_cmpxchg\n"

"ldrex %1, [%2]\n"

"mov %0, #0\n"

"teq %1, %3\n"

"strexeq %0, %4, [%2]\n"

: "=&r" (res), "=&r" (oldval)

: "r" (&ptr->counter), "Ir" (old),"r" (new)

: "cc");

} while (res);

smp_mb();

return oldval;

}

X86版本

staticinline unsigned long __cmpxchg(volatile void *ptr, unsigned long old,

unsigned long new, int size)

{

unsigned long prev;

switch (size) {

case 1:

asm volatile(LOCK_PREFIX"cmpxchgb %b2,%1"

: "=a"(prev),"+m"(*__xg(ptr))

: "q"(new), "0"(old)

: "memory");

return prev;

case 2:

asm volatile(LOCK_PREFIX"cmpxchgw %w2,%1"

: "=a"(prev),"+m"(*__xg(ptr))

: "r"(new), "0"(old)

: "memory");

return prev;

case 4:

asm volatile(LOCK_PREFIX"cmpxchgl %2,%1"

: "=a"(prev),"+m"(*__xg(ptr))

: "r"(new), "0"(old)

: "memory");

return prev;

}

return old;

}

应用代码无锁队列的具体应用示例

以下是作者在某NOSQL数据库中针对高并发情况使用无锁队列的应用示例。

typedefstruct _pool

{

……

node_object *pool_link_head;

node_object *pool_link_tail;

}pool;

获取结点

{

ptr = pool->pool_link_head;

if(ptr->next == NULL)

{

DERROR("pool empty,but norealloc.exit.....\n");

KDB_EXIT;

}

}while(B_CAS(&(pool->pool_link_head), ptr , ptr->next) !=TRUE);

pool->free_count++; /*this is not thread safe, may use atomic_t */

return ptr;

释放结点：

1 do{

2 ptr = pool->pool_link_tail;

3 }while(B_CAS(&(ptr->next),NULL,temp)!= TRUE );

5 pool->free_count++; /*during this critical area ,no other thread can modify thepool ds*/

7 B_CAS(&(pool->pool_link_tail),oldtail , temp);

说明：

多一个空结点解决head和tail同时指向同一个结点（只剩下一个结点的时候）的冲突问题。在具体实现上，如果发现只有一个结点，将再次申请新结点

implementing lockfree_queue.pdf (173.95 KB, 下载次数: 60)

kdb_CAS.rar (149.63 KB, 下载次数: 75)

上一篇：【守望者服务器】服务器异常终止的几种情况 下一篇：【守望者高并发】C10K/C500K与I/O框架

评论: 0 赞: 0

		自动登录	找回密码
密码			立即注册

[ Ngnix与高并发服务器 ] 【守望者 高并发】使用CAS实现高效并发处理

推荐阅读

[ Ngnix与高并发服务器 ] 【守望者高并发】使用CAS实现高效并发处理