CAS-无锁实现线程同步实验

例如对于一个全局数据 int num, 线程A 和 线程B 均对其进行执行 "+1操作"，由于写操作实际涉及到"读取内存数据到寄存器"，"修改新数据"，"写回新数据到内存"。因此如果不进行线程同步，两个线程没有任何限制的对全局数据 num 进行增加操作，则结果可能不符合预期。 
例如 num=1时， 线程 A,B均对其进行 +1时，可能A刚做完 从内存读取数据到寄存器，cpu又切换到B线程，B线程也开始读取数据到寄存器，此时读到的还是1，因为A还未完成修改和写会。之后两个线程做完后续的修改和写会，num的最终值是2，但预期应该是3。

因此对于上述全局变量 num 的修改需要进行互斥访问，使用互斥量来对访问代码进行加锁，可以避免2个线程竞争的问题。但由于加锁和释放锁都涉及用户态和内核态的切换，这会影响效率。

使用CAS则可以实现线程同步的同时，避免频繁的加锁/释放锁带来的效率问题。
CAS-Compare And Swap ：使用原子操作"比较和交换"来实现线程同步，CPU需要支持 原子操作"比较和交换"。
上面的问题中，2个线程对 num 的数据的修改造成冲突的原因在于：读取 num的值，修改，写回。这三部步中，执行写回操作时，此时num的值可能已经不是原先读取的值了，因为可能被B在中间修改了。 所以执行写回操作时应该 先比较当前的值 是之前读取的值，如果是才执行写操作。
注意： 这里的 比较和写 需要CPU提供原子操作，即一条指令实现比较和写回操作，否则 比较和写回中间还是可能插入其它线程的修改。
因此，利用CAS实现线程A和B无冲突的对 num进行+1操作，可表示如下：

do{
    old_val = num;
}while(!CAS(&num, old_val, num+1));

即读取 num 旧值，在修改num为新值时需要原子的执行  "比较当前值和旧值相等后再修改"

下面的代码实现 A,B两个线程对别对 全局变量 num执行 10000000次 +1 操作，期望的 num 最终值应该是200000000。
不加锁时， num 最终结果不是 20000000，表明出现访问冲突。
加锁时，num 值正确，但运行时间明显更长。
使用CAS, num正确，并且运行时间比使用 锁 更短。

#include <stdio.h>
#include <pthread.h>
#include <time.h>

unsigned int loop_counter = 10000000;
unsigned int num = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;


void *my_thread(void *arg)
{
    int i;
    for(i=0; i<loop_counter; i++)
    {
        num += 1;
    }

    return 0;
}

void *my_thread_with_mutex(void *arg)
{
    int i;
    for(i=0; i<loop_counter; i++)
    {
        pthread_mutex_lock(&mutex);
        num += 1;
        pthread_mutex_unlock(&mutex);
    }

    return 0;
}


unsigned long CAS(volatile unsigned int *addr, unsigned int old,
                  unsigned int new)
{
    int ret = 0;

    __asm__ volatile (" lock; cmpxchg %2, %3"
                          : "=a" (ret), "=m"(*addr)
                          : "r" (new), "m" (*addr), "0" (old)
                          : "cc"
                      );
    return ret==old;
}


void *my_thread_with_cas(void *arg)
{
    int i;
    int old_val;
    for(i=0; i<loop_counter; i++)
    {
        do{
            old_val = num;
        }while(!CAS(&num, old_val, num+1));
    }
    return 0;
}

void test(void *(my_thread)(void *arg))
{
    pthread_t thread1_id,thread2_id;
    clock_t start,end;

    start = clock();
    pthread_create(&thread1_id, NULL, my_thread, NULL);
    pthread_create(&thread2_id, NULL, my_thread, NULL);

    pthread_join(thread1_id, NULL);
    pthread_join(thread2_id, NULL);
    end = clock();
    printf("num:%d\n",num);
    printf("time:%d\n",(unsigned int)(end-start));
    printf("\n");
}
int main(void)
{

    test(my_thread);
    num = 0;
    printf("use mutex\n");
    test(my_thread_with_mutex);

    num=0;
    printf("use cas\n");
    test(my_thread_with_cas);
    return 0;
}

运行结果：