Linux系统编程之----如何开发无锁数据结构（获奖名单已公布-2013-7-12）

T-Bagwell

无锁，有些是atomic，有些barrier
也有多队列，池的操作，看场景，资源，和需求进行调配了

不知道带上setaffinity会不会更帅一些

z78290250

是来围观的，新人刚接触Linux 系统编程。

这个应该是实现某种原子操作。 加锁会限制多核CPU的发展，到内核级的程序也会有IO开销，只能取舍。

send_linux

z78290250 发表于 2013-06-21 23:45
是来围观的，新人刚接触Linux 系统编程。

这个应该是实现某种原子操作。 加锁会限制多核CPU的发展，到内 ...

欢迎新人围观哈，有能力的话也可以多发表发表自己的见解，很多网友一起交流学习能够进步更快

joker0910

分享一个应用层的RCU的实现：

http://lttng.org/urcu

send_linux

joker0910 发表于 2013-06-22 13:02
分享一个应用层的RCU的实现：

http://lttng.org/urcu

兄弟自己写的？厉害啊！

yanjingfei

水平还不够参与讨论，不过喜欢楼主的舍甫琴科头像，换上米兰的队衣就更好了。

chishanmingshen

强烈支持一下！

最近对此很感兴趣！

tc1989tc

无锁数据结构没有用过，，新人也是第一次听说，，，一般涉及到多线程多进程共享访问同一资源  都使用互斥锁

joker0910

回复 15# send_linux

不是不是, 看到一份好代码， 拿来分享了

锁确实是让人纠结的东西， 打断了代码的流畅性和编程的思路。实在是对实时性要求很高时，再用锁吧，
如果实时性要求较低，那么可以考虑使用队列+单进程的方式将临界区的操作串行化，并将临界区资源合理分组，规避掉锁的问题。


   

cjdao

多线程模式是比较流行的一种并发编程模型,多线程编程的一个特点就是线程间共享内存空间;这可以降低线程间通信的开销,但却引来了另外的一个难缠的问题:竟态条件!(因此,甚至有人对多线程模型提出了质疑,看这里)

在多线程编程模型下,解决竟态条件的传统方法就是加锁保护临界区,但这存在影响系统性能、优先级反转等问题.

因此又有人提出了,多线程模型下无锁编程的一些方式:
1.线程内通信框架: Disruptor, 这是一款开源的并发框架,用于线程间无锁的共享数据,看这里。

2.无锁数据结构
无锁数据结构一般基于一个很重要的操作：CAS--Compare And Swap(看这里)。
用C语言表达的一个CAS实现的操作是这样的：

1. bool compare_and_swap (int *accum, int *dest, int newval)
   
2. {
   
3.   if ( *accum == *dest ) {
   
4.       *dest = newval;
   
5.       return true;
   
6.   } else {
   
7.       *accum = *dest;
   
8.       return false;
   
9.   }
   
10. }

复制代码

CAS的一个重要特性是其必须是原子操作。现在大多数CPU都支持指令级别的CAS操作。GCC编译也提供了这样的接口:bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)

有了这个原子的CAS后，我们就能实现自己的无锁数据结构了，下面我们就尝试着来实现一个无锁栈为例：

下面的代码中，我们假设malloc与free是线程安全的(至于malloc与free的可重入性与线程安全问题，可以看这里和这里)

1. /*定义CAS操作*/
   
2. #define CAS __sync_bool_compare_and_swap
   
3. /*
   
4. * 定义stack的数据结构
   
5. */
   
6. typedef struct stack_node {
   
7.         struct node *next;
   
8.         void *data;
   
9. }stack_node;
   
10. /*栈顶指针*/
    
11. stack_node *top = NULL;

复制代码

1. /*压栈操作*/
   
2. void stack_push(void *data)
   
3. {
   
4.         stack_node *new = malloc(sizeof(struct node));
   
5.         new->data = data;
   
6.         do {
   
7.                 new->next = top;
   
8.         }while(CAS(&top, new->next, new)!=true);
   
9. }

复制代码

1. /*出栈操作*/
   
2. void * stack_pop(void)
   
3. {
   
4.         stack_node *tmp;
   
5.         void *data;
   
6.        
   
7.         do {
   
8.                 tmp = top;
   
9.                 if (!tmp) return NULL;
   
10.         }while(CAS(&top, tmp, tmp->next) != true);
    
11.         data = tmp->data;
    
12.         free(tmp);
    
13.         return data;
    
14. }

复制代码