多线程模型下的无锁编程

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

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

因此又有人提出了,多线程模型下无锁编程的一些方式:
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;
}

其免锁原理与入栈基本一样，估不再赘述。

另外还有一点, 在使用CAS实现免锁数据结构时, 容易出现ABA问题, 这里也暂时不作讨论, 可以从参考资料中得到更多的信息。

参考资料：

2.设计不用互斥锁的并发数据结构
3.透过linux内核看无锁编程