多线程模型下的无锁编程「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。多线程模式是比较流行的一种并发编程模型,多线程编程的一个特点就是线程间共享内存空间;这可以降低线程间通信的开销,但却引来了另外的一个难缠的问题:竟态条件!，因此,甚至有人对多线程模型提出了质疑,看
这里
。

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

因此又有人提出了,多线程模型下无锁编程的一些方式:

1.线程内通信框架: Disruptor, 这是一款开源的并发框架,用于线程间无锁的共享数据,看
这里
。

2.无锁数据结构

无锁数据结构一般基于一个很重要的操作：CAS–Compare And Swap(看
这里
)。

用C语言表达的一个CAS实现的操作是这样的：

  /*定义CAS操作*/
 
 #define CAS __sync_bool_compare_and_swap
 
 /*
 
 * 定义stack的数据结构
 
 */
 
 typedef struct stack_node {
 
     struct node *next;
 
     void *data;
 
 }stack_node;
 
 /*栈顶指针*/
 
 stack_node *top = NULL;

CAS的一个重要特性是其必须是原子操作。现在大多数CPU都支持指令级别的CAS操作。

GCC编译也提供了这样的接口:bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, …)

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

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

首先定义必要的数据结构:

  /*定义CAS操作*/
 
 #define CAS __sync_bool_compare_and_swap
 
 /*
 
 * 定义stack的数据结构
 
 */
 
 typedef struct stack_node {
 
     struct node *next; /*指向下一个节点,即通过链表的形式实现栈*/
 
     void *data;/*指向该节点的数据*/
 
 }stack_node;
 
 /*栈顶指针*/
 
 stack_node *top = NULL;

接下来是
压栈操作:

  /*压栈操作*/
 
 void stack_push(void *data)
 
 {
 
     stack_node *new = malloc(sizeof(struct node));
 
     new–>data = data;
 
     do {
 
         new–>next = top;/*获取top的快照, 同时初始化了new的next指针*/
 
     }while(!CAS(&top, new–>next, new));
 
 }

在取得top的快照后后, 就通过CAS操作查看top的内容与line 7取得的快照是否一致，如果一致则将top的内容更换为new，CAS函数返回true。

假设有线程A在
stack_push里获取top快照后暂时失去了执行权, 切换至另一个线程B, 而线程B完成了一次
stack_push操作，然后执行权再次回到线程A,

线程A执行CAS操作, 发现top里的内容与快照里的内容已经不一致了，CAS返回false, 估do…while语句重新执行。

接下来是出栈操作:

  /*出栈操作*/
 
 void * stack_pop(void)
 
 {
 
     stack_node *tmp;
 
     void *data;
 
     do {
 
         tmp = top;
 
         if (!tmp) return NULL;
 
     }while(CAS(&top, tmp, tmp–>next) = true);
 
     data = tmp–>data;
 
     free(tmp);
 
     return data;
 
 }