一、JAVA锁实现

锁是用来控制多个线程访问共享资源的方式，JDK提供三种方式的锁实现：（1）Synchronized 关键字（2）Lock（3）原子操作类（无锁）

1.Synchronized

synchronized是基于JVM内置锁实现，基于进入与退出Monitor对象实现方法同步和代码块同步，监视器锁的实现依赖底层操作系统的Mutex lock(互斥锁)实现

代码块同步是使用monitorenter 和monitorexit指令实现的。

private static Object lock = new Object();
public void test(){ //
    synchronized(lock){//编译后，插入monitorenter指令到同步代码块开始位置
            
    }//编译后，插入monitorexit指令到同步代码块结束位置
}

任何对象都有一个monitor与之关联，获取对象的锁即是获取对象所对应的monitor的所有权，synchronized用的锁是存在JAVA对象头里的

JAVA对象头包括 MarkWord，类型指针，数据长度三部分；MarkWord存储对象的锁，hashcode等信息

JDK1.6 对synchronized 进行优化，引入了偏向锁和轻量级锁，减少获取锁和释放锁带来的性能消耗。

锁级别从低到高依次是：无锁状态- 偏向锁-轻量级锁-重量级锁

• 无锁：表示没有对资源进行锁定，所有的线程都能访问并修改同一个资源，但同时只有一个线程能修改成功，其它线程循环重试

• 偏向锁：偏向锁是指一段同步代码一直被一个线程所访问，那么该线程会自动获取锁，降低获取锁的代价（第一次进入同步代码，用CAS把线程 ID 设置到对象的 Mark Word 头）

• 轻量级锁：指当锁是偏向锁的时候，被另外的线程所访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，不会阻塞，从而提高性能。

• 重量级锁：升级为重量级锁时，锁标志的状态值变为“10”，此时Mark Word中存储的是指向重量级锁的指针，此时等待锁的线程都会进入阻塞状态

例子：

public class SynchronizedTest {

    private static Object lock = new Object();
    public synchronized static void staticMethod(){  //实际上是对该类对象加锁，俗称“类锁”
            ...
    }
    public synchronized void method(){ //实际上是对调用方法的对象加锁，俗称“对象锁”
            ...
    }
    public void method1(){ 
        synchronized (SynchronizedTest.class){ //对SynchronizedTest.class对象加锁
                ...
        }
    }
    public void method2(){
        synchronized (lock){ //对lock对象加锁
                ...
        }
    }
    public static void main(String[] args) {
    }
}

同一个对象在两个线程中分别访问该对象的两个同步方法 会互斥

不同对象在两个线程中调用同一个同步方法 不会互斥

用类直接在两个线程中调用两个不同的同步静态方法 会互斥

一个对象在两个线程中分别调用一个静态同步方法和一个非静态同步方法 不会互斥

2. Lock

JDK1.5 引入Lock接口（以及相关实现类）（java.util.concurrent.locks包中）实现锁功能，需要显示的获取和释放锁。Lock拥有了锁获取与释放的可操作性、可中断的获取锁以及超时获取锁等多种同步特性。

class X {     
  private final ReentrantLock lock = new ReentrantLock();     
  // ...        
  public void m() {       
    lock.lock();  // block until condition holds   不要写到try里，防止获取锁（自定义锁的实现）发生异常，导致锁无故释放    
    try {         
      // ... method body       
    } finally {   //确保最终能释放锁      
      lock.unlock();      
    }     
  }   
}

读写锁：

public class ReadWriteTest{
    ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private Object data = null;
    public void read(){
        readWriteLock.readLock().lock();
        try{
            System.out.println(Thread.currentThread().getName() + " ready to read data" );
            Thread.sleep(new Random().nextInt(1000));
            System.out.println(Thread.currentThread().getName() + ":" + data);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            readWriteLock.readLock().unlock();
        }
    }
    public void write(Object data){
        readWriteLock.writeLock().lock();
        try {
            System.out.println(Thread.currentThread().getName() + " ready to write" + data);
            Thread.sleep(new Random().nextInt(2000));
            this.data = data;
            System.out.println(Thread.currentThread().getName() + ":" + this.data);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            readWriteLock.writeLock().unlock();
        }
    }
    public static void main(String[] args) {
        ReadWriteTest readWriteTest = new ReadWriteTest();
        for(int i = 0; i < 5; i++){
            new Thread(() -> {
                int j= 10;
                while (j > 0) {
                    readWriteTest.read();j--;
                }
            }, "Reader"+i).start();
        }
        for(int i = 0; i < 2; i++){
            new Thread(() -> {
                int j= 10;
                while (j > 0) {
                    readWriteTest.write(new Random().nextInt(10000));
                    j--;
                }
            }, "Writer"+i).start();
        }
    }
}

• 互斥关系：写锁与写锁是互斥的，写锁与读锁也是互斥的，只有读锁和读锁共享的
• 可重入性：如果当前线程已持有写锁，可再次持有写锁或者读锁
• 不允许锁升级：如果当前线程持有读锁，不能直接申请写锁

实现原理

利用队列同步器AbstractQueuedSynchronizer（AQS）实现，AQS当中的同步等待队列也称CLH队列，CLH队列是Craig、Landin、Hagersten三人发明的一种基于双向链表数据结构的队列，是FIFO先入先出线程等待队列，Java中的CLH队列是原CLH队列的一个变种,线程由原自旋机制改为阻塞机制。

• 状态：volatile int state（代表共享资源状态), 设置成volatile类型，以保证其修改的可见性
• 同步队列：等待对象的集合，以双向链表的形式实现
• CAS：同步队列的操作采用CAS

lock.png AQS.png lock-share.png lock-share-release.png

Node 属于AQS的内部类，成员：除了前置和后置节点还有节点对应的线程(thread),节点的状态（waitStatus）,nextWaiter(主要用于条件变量)

自定义同步类

自定义同步器在实现时只需要实现共享资源state的获取与释放方式即可，至于具体线程等待队列的维护（如获取资源失败入队/唤醒出队等），AQS已经在底层实现好了。自定义同步器实现时主要实现以下几种方法：

• isHeldExclusively()：该线程是否正在独占资源。只有用到condition才需要去实现它。
• tryAcquire(int)：独占方式。尝试获取资源，成功则返回true，失败则返回false。
• tryRelease(int)：独占方式。尝试释放资源，成功则返回true，失败则返回false。
• tryAcquireShared(int)：共享方式。尝试获取资源。负数表示失败；0表示成功，但没有剩余可用资源；正数表示成功，且有剩余资源。
• tryReleaseShared(int)：共享方式。尝试释放资源，如果释放后允许唤醒后续等待结点返回true，否则返回false。

同步类在实现时一般都将自定义同步器（sync）定义为内部类，供自己使用；而同步类自己（Mutex）则实现某个接口，对外服务。当然，接口的实现要直接依赖sync，它们在语义上也存在某种对应关系！而sync只用实现资源state的获取-释放方式tryAcquire-tryRelelase，至于线程的排队、等待、唤醒等，上层的AQS都已经实现好了，我们不用关心。内置同步类ReentrantLock/ReentrantReadWriteLock/CountDownLatch/Semaphore/ 都是基于AQS实现的。

• 自定义同步类，同一时刻最多有两个线程在运行

public class TwinsLock implements Lock {

    private final Sync sync = new Sync(2);

    static class Sync extends AbstractQueuedSynchronizer {
        public Sync(int state){setState(state);}

        protected final int tryAcquireShared(int unused) {
            for (;;) {
                int c = getState();
                int newState = c - unused;
                if(newState < 0 || compareAndSetState(c, newState)){
                    return newState;
                }
            }
        }
        protected final boolean tryReleaseShared(int unused) {
            for (;;) {
                int c = getState();
                if (compareAndSetState(c, c + unused))
                    return true;
            }
        }
    }
    @Override
    public void lock() {
        sync.acquireShared(1);
    }
    @Override
    public void unlock() {
        sync.releaseShared(1);
    }
    //其它接口省略
    public static void main(String[] args) {
        TwinsLock twinsLock = new TwinsLock();
        for (int i = 0; i < 20; i++) {
            new Thread(()->{
                twinsLock.lock();
                try{
                    String name = Thread.currentThread().getName();
                    System.out.println(name+" start ...");
                    Thread.sleep(3000);
                    System.out.println(name+" end ...");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    twinsLock.unlock();
                }
            }, "Thread-"+i).start();
        }
    }
}

3.原子操作类

JDK 1.5 新增原子操作类（java.util.concurrent.atomic包中），是CAS非阻塞算法的实现方式，相对于synchronized/lock 这种阻塞算法，它性能更好。

原子操作类主要解决变量并发访问的同步问题。Atomic包里的类基本都是使用Unsafe实现。

（1）原子更新基本类型

• AtomicBoolean：原子更新布尔类型, 常用方法：getAndSet(boolean), compareAndSet(boolean,boolean)
• AtomicInteger：原子更新整形, 常用方法：addAndGet(int), getAndIncrement(), compareAndSet(int,int)
• AtomicLong：原子更新长整形, 常用方法：addAndGet(long), getAndIncrement(), compareAndSet(long,long)

public class BasicType extends Thread{

    public static final AtomicInteger aInt = new AtomicInteger(0);

    @Override
    public void run() {
        for (int i = 0; i < 10000; i++) {
            aInt.incrementAndGet(); //并发操作是原子性，无须加锁
        }
        System.out.println(Thread.currentThread().getName()+":"+ aInt);
    }
    public static void main(String[] args) throws InterruptedException{
        Thread a = new BasicType();
        a.start();
        Thread b = new BasicType();
        b.start();
        a.join();
        b.join();
        System.out.println("main exit");
    }
}

（2）原子更新数组

• AtomicIntegerArray：原子更新整型数组里的元素。

• AtomicLongArray：原子更新长整型数组里的元素。

• AtomicReferenceArray：原子更新引用类型数组里的元素.

int array[] = {1,2,3};
AtomicIntegerArray atomicIntegerArray = new AtomicIntegerArray(array);
int result = atomicIntegerArray.addAndGet(1, 100);
System.out.println(atomicIntegerArray.get(1));//输出结果102
System.out.println(array[1]);//输出结果2

AtomicIntegerArray(array) 会将当前数组复制一份，所以对AtomicIntegerArray 数组元素修改，不会影响传入的数组

（3）原子更新引用

AtomicReference：原子更新引用类型。
AtomicReferenceFieldUpdater：原子更新引用类型里的字段。
AtomicMarkableReference：原子更新带有标记位的引用类型

class Person {
    private String name;
        ...
}
public static void main(String[]args){
    Person old =  new Person("A");
  AtomicReference<Person> reference = new AtomicReference(old);
  reference.getAndSet(new Person("B")); //更新应用指向，不会改变旧引用值
  System.out.println(reference.get().getName());//输出B
  System.out.println(old.getName());//输出 A
}

class Person {
    volatile public String name; //更新属性必须是volatile
    public Person(String name){this.name = name;}
}
public static void main(String[]args){
    //所在类需有访问name属性的权限
    AtomicReferenceFieldUpdater referenceFieldUpdater = AtomicReferenceFieldUpdater.newUpdater(Person.class,String.class,"name");
    Person initOld = new Person("C");
    referenceFieldUpdater.set(initOld,"D");
    System.out.println(referenceFieldUpdater.get(initOld)); //输出D
    System.out.println(initOld.getName());//输出D
}

String val = "hello";
AtomicMarkableReference<String> atomicMarkableReference = new AtomicMarkableReference(val, false);
atomicMarkableReference.compareAndSet(val,"hello world",false, true);
atomicMarkableReference.compareAndSet("hello world","hello",true, true);

（4）原子更新属性类

• AtomicIntegerFieldUpdater：原子更新整型的字段的更新器。
• AtomicLongFieldUpdater：原子更新长整型字段的更新器。
• AtomicStampedReference：原子更新带有版本号的引用类型。该类将整数值与引用关联起来，可用于原子的更新数据和数据的版本号，可以解决使用 CAS 进行原子更新时可能出现的 ABA 问题。

class Person {
    volatile public int age; //更新属性必须是volatile
    public Person(int age){this.age = age;}
}
public static void main(String[]args){
        AtomicIntegerFieldUpdater  atomicIntegerFieldUpdater = AtomicIntegerFieldUpdater.newUpdater(Person.class, "age");
    Person initOld = new Person(10);
    atomicIntegerFieldUpdater.getAndSet(initOld,50);
    System.out.println(atomicIntegerFieldUpdater.get(initOld));//输出50
    System.out.println(initOld.getAge());//输出50
}

AtomicStampedReference<String> atomicStampedReference = new AtomicStampedReference(val,1);
int stamp =  atomicStampedReference.getStamp();
atomicStampedReference.compareAndSet(val, "hello world", stamp, stamp+1);
stamp = atomicStampedReference.getStamp();
atomicStampedReference.compareAndSet("hello world", "hello", stamp, stamp+1);

AtomicMarkableReference 与 AtomicStampedReference 一样也可以解决 ABA的问题，两者唯一的区别是，AtomicStampedReference 是通过 int 类型的版本号，而 AtomicMarkableReference 是通过 boolean 型的标识来判断数据是否有更改过。可以理解成AtomicMarkableReference是AtomicStampedReference的简化版

二、JAVA锁的种类

• 死锁： 线程A 持有锁A 并试图获取锁B，线程B 持有锁B 并试图获取锁A

• 乐观锁&悲观锁： 乐观锁认为自己使用数据时，不会有别的线程修改数据，典型算法是CAS算法，JAVA原子操作类就是通过CAS实现的

  悲观锁总是认为自己使用数据时候一定有别的线程修改数据，java中采用synchronized关键字和Lock的实现类都是悲观锁。

• 自旋锁&适应性自旋锁：当同步资源的锁定时间很短，采用自旋锁避免了线程切换的开销，提高效率。缺点：如果锁被占用的时间很长，自旋的线程会浪费CPU资源。自旋的次数上限默认是10次，-XX:PreBlockSpin; JDK1.6 引入适应性自旋锁，自旋的时间(次数)可以动态变化. 典型实现是JAVA原子操作类

• 无锁&偏向锁&轻量级锁&重量级锁： JDK1.6 针对synchronized重量级锁的优化，提出偏向锁和轻量级锁。

• 公平锁和非公平锁：非公平锁是指多个线程获取锁的顺序并不是按照申请锁的顺序，有可能后申请的线程比先申请的线程优先获得锁，有可能造成优先级反转或者饥饿现象。ReentrantLock 默认锁是非公平锁，非公平锁效率更高，对于Synchronized而言，也是一种非公平锁。

• 可重入锁&非可重入锁：Java中ReentrantLock和synchronized都是可重入锁，可重入锁的一个优点是可一定程度避免死锁。

• 独享锁(也叫排它锁或者互斥锁)&共享锁：独享锁的实现有Synchronized 和 ReentrantLock， ReentrantReadWriteLock 其读锁是共享锁，其写是独享锁。

• 读写锁：java中实现ReentrantReadWriteLock

• 分段锁：分段锁其实是一种锁的设计，并不是具体的一种锁，对于ConcurrentHashMap而言，其并发的实现就是通过分段锁的形式来实现高效的并发操作