为什么需要锁

    计算机在多线程环境下，并发写共享内存是很普遍的。大部分场景下需要保证数据并发写的准确性，此时则需要锁对共享数据进行保护。

    比如count初始化为0，有2个线程访问一个叠加器将执行叠加操作既count=count+1，若不用锁进行保护此代码块，则可能出现两个线程同时执行count+1，导致两个线程执行完毕后count=1而不是count=2，出现错误。

锁实现的基础

    硬件实现：利用CPU的原子操作如CAS，test-and-set操作来实现锁，对应的汇编指令有CMPXCHG,  TSL等。

    软件实现：使用，Peterson算法等。现代CPU由于为了优化性能，会使CPU指令乱序[1]。对这种情况，需要来保证指令操作的顺序性以使算法有效。

锁设计与实现

    为了实现锁的高性能。现代锁理论提出两种思路既乐观锁与悲观锁策略来针对不同情况提出锁的解决方案。

乐观策略

    顾名思义，总是乐观的认为，当前锁的竞争小，当前线程很大概率可以取到锁。不断重试取锁操作，直到成功[2]。

    于是我们可以通过CAS原子操作来实现一个自旋锁，自旋锁使用了乐观锁的思想。

//区1：CAS原子操作，只有一个线程可以进入//val_ptr：val共享变量的指针。expect：共享变量的预期值。update：假如val的值为expect，则将val设置为updateint compare_and_swap(int* val_ptr, int expect, int update){  if(*val_ptr == expect)  {    *val_ptr = update;    return true  }  return false;}//区2：共享变量int val = 0;int counter = 0;//区3：多线程进入{  int expect = 0, update = 1;  while(!compare_and_swap(&val, expect, update)){} //若未取到锁，则自旋  //取到锁，进入临界区  counter++;  val = 0; //释放锁}

    区1描述了一个CAS逻辑。从代码逻辑可以看到，只有预期的expect与被多线程共享的变量*val相等，才会去把*val的值更新为update，并且返回true表明此次CAS操作成功。

    区2定义了一个共享变量val以供实现CAS操作，以及一个我们想要实现的一个多线程安全的计数器。

    区3描述的多线程竞争取锁与释放锁的过程。如果线程通过CAS方法（compare_and_swap函数）取得锁成功，则进入临界区进行计数器加1，执行完同步块后，通过将val设为0，释放锁。一旦锁val设为0，立马会有一个线程通过CAS操作取到锁。

    乐观锁遇到多线程竞争锁非常激烈或临界区执行时间过长的情况，由于其他取不到锁的线程会进行大量自旋操作，会对操作系统的资源的消耗过大，从而影响整体程序性能。故自旋锁仅适用于多线程竞争小，线程执行速率快的场景。

悲观策略

    与乐观策略相反。

    采用悲观策略，这里的悲观是相对而言。悲观锁一般使用内核态的锁，一般情况下涉及到线程挂起，用户态与内核态的转换，故较为耗时。每次线程进入同步代码块，就进行加锁，没有获取到锁的线程被阻塞挂起，直到持有锁的线程执行完后释放锁来唤醒它们。

行业流行的锁解决方案

    对于加锁操作，先采用乐观锁，后采取悲观锁。若线程进入悲观锁模式被挂起时，需要维护一个线程任务队列以供之后线程被唤醒继续竞争取锁，用线程安全的方式进入队列，比如CAS入队。

    如下图所示，描述了一种锁实现，多线程先通过对a值进行原子操作递增1操作，如有线程A递增操作得到a值为1则表明取到锁，则进入临界区。其他线程未能递增取到1的则通过原子方式进入FIFO队列尾部，并且对a值进行减1。如果线程A执行完毕离开临界区时，则原子方式将a值减1，并唤醒FIFO队列头线程继续竞争递增a取锁操作。

    下面介绍几种行业已经实现的锁。   

    操作系统信号量[3]P/V操作，当信号量的值通过P操作递减为负数时，则会将该线程放入队列（通常是FIFO）后被暂停，当信号量的值通过V操作递增为正时，则转换等待队列的一个线程进入就绪队列。对P/V操作的递增与递减操作要求原子性。原子性可以由软件层面的互斥算法实现[4]或者硬件层面的test-and-set实现。

    JVM对synchronized锁的优化。以HotSpot1.7为例，对于synchronized锁升级的顺序为，偏向锁，轻量级锁，重量锁。基本思路是先乐观认为只有一个线程竞争锁，于是采用偏向锁，若发现有多个线程进入临界区竞争偏向锁，则升级为轻量级锁，若多个线程竞争轻量级锁，则进入重量级锁。对于偏向锁与轻量级锁均采用CAS方式乐观锁策略实现，而对于重量级锁则采用操作系统mutex机制[5]。

    JDK的rt.jar里，通过AQS实现的锁，也是先进行乐观CAS做取锁操作，如果几次尝试取锁失败则进入LockSupport .unpark()调用里面native函数，执行比CAS更重量级别线程挂起睡眠操作。当然对于未取到锁而被挂起而睡眠的线程，通过CAS方式将线程任务放入队列，以供下次锁释放时唤醒被挂起的线程进行竞争取锁操作。

实现锁的现有基本工具

    大部分含有原子操作的软件以及一些编程语言锁实现库均可以实现锁操作，比如Java中的synchronized修饰符和AQS框架，操作系统的信号量，数据库DML语句的update操作，Redis的incr操作，zookeeper的序列号递增，均可以做为锁实现的基础。

分布式锁

    本质上与多线程的锁的原理上没有差异，只要存在提供原子操作的组件比如redis，采用incr指令既可实现分布式锁。当然分布式锁，涉及到高可用问题，目前分布式组件有zookeeper可以支持高可用分布式锁的实现。设计到高性能问题，则需要有锁释放广播机制。

参考文献：

[1]

[2]

[3]

[4] 

[5]