CAS操作
所谓CAS指Compare and Set(或Compare and Swap)。现在几乎所有CPU指令都支持CAS，如X86的CMPXCHG汇编指令。CAS通常被视为无锁(lock free)数据结构的基础。CAS的C语言描述如下：
intcompare_and_swap(int*reg,intoldv,intnewv){intold_reg_v=*reg;if(old_reg_v==oldv){*reg=newv;}returnold_reg_v;}boolcompare_and_swap(int*accum,int*dest,intnewv){if(*accum==*dest){*dest=newv;returntrue;}returnfalse;}
返回bool的好处在于调用者可以知道是否成功更新。与CAS类似的其他原子操作如：Fetch and Add(+1操作)、Test-and-set(写值到指定内存位置并返回旧值，汇编指令BST)、Test and Test-and-set。
无锁队列的链表实现。入队列：
push(x){q=newRecord();q->value=x;q->next=NULL;do{p=tail;/* fetch tail pointer */}while(!CAS(p->next,NULL,q));CAS(tail,p,q);/* set tail point to q (the new record) */}
当while循环结束时，q已经加入队列成为最后一个元素，但tail指针还没有更新，最后只需将tail指向q即可。分析可能存在的竞争：当thread1将q加入队列，但还未更新tail时，切换到thread2运行，此时thread2获取了tail的值