我们在编写多线程程序的时候，往往会涉及到多个线程访问共享数据。如果不对这种访问进行限制，往往会导致程序运行结果与预期不符。在写代码的时候，我们习惯使用锁来保护数据。那么，这里的锁是什么？为什么它符合我们的要求？它存在于何处？让我们从最简单的例子开始---多个线程并发修改一个全局变量：/*globalvariable*/intg_sum=0;/*每个线程条目*/void*thread(void*arg){for(inti=0;i<100;i++){g_sum++;}returnNULL;}在多核处理器上，如果两个线程同时进行上述累加操作，最终的g_sum几乎不可能是预期的200（每个线程累加100次），更倾向于一个接近200的随机值。这是因为当CPU累加g_sum时，它们都：1.从内存中读取2.修改它的值3.将新值写回内存。由于CPU是独立的，内存是共享的，所以可能会有一个时序：两个CPU依次从内存中读取g_sum的值，并各自递增，最后将新值写入g_sum，此时。两个线程的两次累加只是在临界区将g_sum加1。为了解决上面的问题，想办法在同一时间内只允许一个线程读-修改-写全局变量是一个很自然的想法。我们可以使用锁来保护临界区临界区的概念就介绍到这里。临界区是访问共享资源（如上例中的“g_sum++”）的程序片段。线程进入临界区时锁定，退出临界区时解锁。换句话说，锁“保护”了临界区。临界区是人们强加给一段代码的概念，但加锁不同于解锁，它必须实际存在于代码中。那么问题来了，锁应该怎么实现呢？为了回答这个问题，我们先列出锁需要具备的特性：1.需要同时支持加锁和解锁操作。2.需要有状态（State），需要记录锁当前是上锁还是解锁。3.锁的状态改变必须是原子的（Atomic）。4、处于Locked状态时，加锁操作不会成功。第一条，对于实现者，一个是提供两个API对应这两个操作。第2条需要一个地方来记录锁的状态。对于计算机系统来说，这个地方只能是内存。第三条，在内存中记录锁的状态和全局变量有同样的问题，即如何防止多个线程同时改变锁的状态？不能用锁来保护锁吗？幸运的是，各种系统的CPU都提供了这种原子操作的原语。对于x86来说，就是指令的LOCK前缀，可以在指令执行时控制总线，直到指令执行完毕。这样也保证了锁的状态修改是通过原子操作完成的。第四条锁定操作成功的前提条件是锁定状态为“解锁”。如果不满足这个条件，则本次加锁操作将失败。失败后的行为如何？不同的锁有不同的实现。一般来说，可选的行为有3种：1.立即返回失败2.不断尝试加锁，直到成功。3.休眠线程本身，直到可以获取锁。典型实现当然，我们不需要重新发明锁的轮子。在用户空间，glibc提供了spinlock、semaphore、rwlock、mutex等锁的实现。我们只需要使用API。intsem_wait(sem_t*sem);intsem_post(sem_t*sem);intpthread_mutex_lock(pthread_mutex_t*mutex);intpthread_mutex_trylock(pthread_mutex_t*mutex);intpthread_mutex_unlock(pthread_mutex_t*mutex);....在内核空间，Linux也是有类似的实现。性能损失在刚才的例子中，如果我们用锁来保护g_sum，那么最后肯定会得到200。然而，我们在获得准确结果的同时也在性能上付出了代价。如果把临界区比作独木桥，那么线程就是需要过独木桥的人。显然，如果过桥的人越多（并发访问临界区的线程），独木桥越长（被锁保护的临界区范围越大），那么其他人等待的时间就越长（即性能会更差）。下面是测试程序在8核CPU虚拟机环境下的运行结果。横坐标是并发运行的线程数，纵坐标是完成同一任务的运行时间（累计一定次数）。更多的线程会带来更多的冲突，因此总的运行时间会逐渐增加。如果你增加临界区的长度（在每个循环中增加一些额外的指令），你会得到如下结果：横坐标表示额外的指令，纵坐标仍然表示时间。可见并发线程越多，临界区越大，都会导致程序的性能下降。这就是为什么追求性能的程序会选择使用per-cpu变量（或per-thread变量），尽量减少锁保护的粒度。Futex前面说了，锁是有状态的，这个状态需要保存在内存中。所以？具体到linux平台，锁对象存放在内核空间还是用户空间？在早期的内核（2.5.7）中，这个对象存储在内核中，这是一种自然的做法。因为当一个线程（任务）在等待获取互斥锁的时候，如果获取不到，那么就需要主动休眠，直到锁可用，然后再唤醒。具体来说，这个过程就是把自己的task_struct挂在锁对象的waitinglist上。当锁持有者解锁时，内核可以从等待列表中找到并唤醒链表上的所有任务。可见，每一个用户的加锁和解锁操作都必须落入内核（即使当前没有其他线程持有锁）。陷入内核意味着消耗了数百个时钟。在冲突不大的场景中，这种消耗就被浪费掉了。因此，从2.5.7版本开始，Linux引入了Futex（FastUserspacemuTEXes），这是一种快速的用户态互斥机制。这种机制是由用户态和内核态共同完成的。用户状态。如果用户在加锁的时候发现锁处于（Unlocked）状态，那么直接修改状态即可（快速路径），不会落入内核。当然，如果此时锁处于（Locked）状态，还是需要落入内核（慢路径）。那么我们如何使用Futex机制呢？答案是我们根本不需要明确地使用它。glibc库中semaphore和mutex底层就是使用的Futex。无锁锁通过有状态的原子操作确保对共享数据的访问互斥。而无锁就是不需要这样的状态。CAS说到无锁，就不得不提CAS指令（也叫CSW）。CAS是CompareAndSwap的缩写，即compare-exchange。不同系统的CPU有不同的CAS指令实现。在x86上，这是以LOCK为前缀的CMPXCHG指令。因此，CAS操作是原子的，其功能用伪代码描述如下（仅供理解，实际上是原子指令）：boolcompare_and_swap(int*src,int*dest,intnewval){if(*src==*dest){*src=newval;返回真；}else{返回错误；}}比较第一个操作数的内容和第二个操作数的内容，如果相同则将第三个操作数赋值给第一个操作数返回TRUE，否则返回FALSE。较新版本的gcc具有用于CAS操作的内置API（见下文）。其他编译器也提供了类似的API，但这不是本文的重点。bool__sync_bool_comware_and_swap（类型*ptr，类型oldval，类型newval）；基于链表的无锁队列无锁队列（Lock-FreeQueue）通常是在没有锁的情况下构建的。顾名思义，无锁队列是指不使用锁结构来控制多线程并发互斥的队列。我们知道队列是一个典型的先进先出（FIFO）数据结构，它有两个操作：入队（Enqueue）和出队（Dequeue）。在并发条件下，多个线程在入队或出队时可能会发生竞争。基于单向链表实现的队列如下图所示（带Dummy链表头）。线程1和线程2都希望自己能够完成入队操作。一般来说，enqueue需要完成两件事：更新tai??l节点（节点2）next指向新节点更新tai??l指向的节点为新加入的节点如果可以使用锁，我们就可以完成线程的互斥通过将以上两种东西放在锁的保护范围内。锁呢？《Implemeting Lock-Free Queues》中JohnD.Valois提出的无锁队列入队算法如下（伪代码）：EnQueue(x){/*创建一个新节点n*/n=newnode();n->值=x；n->下一个=NULL；做{t=尾巴;//获取尾节点succ=CAS(t->next,NULL,n)//尝试更新尾节点的Next指向新节点ifsucc!=TRUECAS(tail,t,t->next)//更新失败，尝试向后移动tail}while(succ!=TRUE);CAS（尾部，t，n）；//更新队列的Tail指针，使其指向新节点}这里的Enqueue算法用到了三个CAS操作。1、第一个CAS操作更新尾节点的Next指向新节点。在单线程环境中，这个操作必须成功。但是，在多线程环境下，如果有多个线程在执行Enqueue操作，线程T1获取尾节点后，线程T2可能已经完成了新节点的入队操作。此时T1的CAS操作会因此失败，此时t->Next不再为NULL，而是成为T2新插入的节点。同样，CAS操作将锁定总线！所以T1和T2只有一个线程会成功，成功的线程会更新尾节点的Next，另一个线程会因为CAS失败而回收。如果CAS操作成功，链表会变成如下，此时Tail指针还没有更新。2.如果第一次CAS失败，说明其他线程在干坏事（入队元素），此时第二次CAS操作会尝试推进Tail指针。这样做是为了防止第一个CAS成功的线程突然挂掉，不更新Tail指针。3.第三个CAS操作更新尾节点的Nextpaper也给出了另一个版本的enqueue算法，如下图EnQueue2(x){/*创建一个新节点n*/n=newnode();n->值=x；n->下一个=NULL；oldt=t=taildo{while(t->next!=NULL)//继续到达队尾t=t->next}while(CAS(t->next,NULL,n)!=TRUE);//更新tai??l节点的Next指向新节点CAS(tail,oldt,n);//更新队列的Tail指针，使其指向新的节点}新版本相比之前的版本，在循环内部增加了一个不断向后遍历的过程，即如果已经有一个节点则通过添加其他线程，本线程不等待Tail更新，直接向后遍历。让我们再看看dequeue。论文中给出的出队算法如下：DeQueue(){do{h=head;如果h->next=NULL错误queue_empty；}while(CAS(head,h,h->next)!=TRUE)returnh->next->value;}需要特别注意的是，出队算法不会返回队头的元素，但返回Head->Next节点。出队完成后，将Head指针移动到刚刚出队的元素。算法中使用CAS操作来控制竞争下Head指针的更新。另外，该算法没有描述队列元素的资源释放。基于数组的无锁队列的一个缺点是需要频繁申请和释放内存。在某些语言实现中，此应用程序版本本身是锁定的。涉及锁操作的行为自然不是无锁的。因此，更通用的无锁队列都是基于数组来实现的。论文描述了一种基于数组的无锁队列算法，具有以下特点：1.数组是预先分配的，即优先考虑可容纳的元素个数。2.用户可以向数组中填入值，此外，数组还有三种特殊的值：HEAD、TAIL、EMPTY。队列初始化时（下图），除了相邻的两个位置填满了HEAD和TAIL外，其他位置都是EMPTY。显然，userdata不能再使用这三个值了。.入队操作：假设用户要入队一个值x，它会找到TAIL的位置，然后对这个位置和之后的位置进行Double-WordCAS。此操作自动将
