java中的锁

在java中，synchronized可保证在同一个时刻只有一个线程可执行某个方法或某个代码块，另外还可保证一个线程的变化被其他线程所看到，也就是可见性，作用同volatile。

synchronized有三种应用方式，修饰实例方法，作用于当前实例加锁，进入同步代码块前需要获得当前实例的锁；修饰静态方法，作用于当前类对象加锁，进入同步代码块前需获得当前类对象的锁；修饰代码块，指定加锁对象，对给定对象加锁，进入同步代码块前需获得给定对象的锁。

synchronized修饰实例方法时，当前线程的锁便是实例对象，java中线程的同步锁可以是任意对象。当一个线程正在访问一个对象的synchronized实例方法，其它线程是不能访问该实例所有被synchronized修饰的实例方法的，因为一个对象只有一把锁，但其它线程还是可以访问该实例的其他非synchronized方法。另外，如果两个线程对应的是两个实例，则不受上面的限制，因为每个实例都有一把自己的锁。

synchronized作用于静态方法时，对象锁为当前类对象，由于无论创建多少实例对象，对应的类对象只有一个，因此对象锁也是唯一的。当一个线程调用一个实例对象的非静态synchronized方法，另外一个线程调用该实例对象所属类的静态synchronized方法，是不会发生互斥现象的，因为前者的锁为当前实例对象的锁，而后者为当前实例对应类的类对象的锁。

synchronized修饰代码块，将作用于一个给定的实例对象，也就是锁对象，既可以是某个实例对象，如synchronized(this)，也可以是class对象，如synchronized(Test.class)。

jvm中同步是基于基于进入和退出管程(Monitor)对象实现，无论显式同步还是隐式同步都是这样的。同步方法并不是由monitorenter和monitorexit指令实现同步，而是由方法调用指令读取运行时常量池中的方法ACC_SYNCRONIZED标志来隐式实现。

jvm中，对象在内存中的布局分为三块区域，对象头、实例数据、对齐填充。

实例变量存放类的属性数据信息，包括父类的属性信息；填充数据，由于虚拟机要求对象的起始地址必须是8字节的整数倍，所以未对齐时进行填充，填充数据仅仅是为了字节对齐。

一般而言，synchronized使用的锁对象便是存储在java对象头里面的，jvm使用2个字节来存储对象头（数组为3个字节，多出一个字节存储长度），主要由Mark Word和Class Metadata Address组成。Mark Word默认存储对象的hashcode、分代年龄、锁标志位等。

Mark Word的内容，无锁，也就是默认情况下，存储对象hashcode、对象分代年龄、是否是偏向锁(0)；轻量锁，存储指向栈中锁记录的指针；重量锁，存储指向互斥量（重量锁）的指针；偏向锁，存储偏向线程id、偏向时间戳、对象分代年龄、是否是偏向锁(1)。

偏向锁会偏向第一个获得它的线程，如果在接下来的执行中，该锁没有被其他线程获取，则持有偏向锁的线程永远不需要同步。大多数情况下，锁不仅不存在多线程竞争，而且总是由同一个线程获得。当锁对象第一次被线程获取时，线程使用cas把线程id记录到对象的Mark Word中，同时设置偏向标志位，以后该线程在进入和退出同步块时不需要进行cas操作来加锁和解锁，只需简单测试下对象头的Mark word里是否存储指向当前线程的锁。

如果线程使用cas操作失败，则表示该锁对象上存在竞争并另外一个线程取得了偏向锁。当到达全局安全点时，获得偏向锁的线程被挂起，膨胀为轻量锁，同时被撤销偏向锁的线程继续执行同步代码。

线程在执行同步块之前，jvm会先在当前线程的栈帧中创建用于存储锁记录的空间，并将对象头中的Mark Word复制到锁记录中，称为Displaced Mark Word。然后，线程尝试使用cas将对象头中的Mark Word替换为指向锁记录的指针。如果成功，当前线程获得锁，失败，表示其他线程竞争锁，当前线程便尝试使用自旋锁来获取锁，如果自旋失败则膨胀为重量锁。如果自旋成功则依然处于轻量锁。

轻量锁的解锁过程也是通过cas来进行的，如果对象的Mark Word仍然指向线程的锁记录，那就用cas操作把对象当前的Mark Word和线程中赋值的Displaced Mark Word替换回来，如果替换成功，整个同步过程完成，如果失败，说明有其他线程尝试过获取该锁，就要在释放锁的同时，唤醒被挂起的线程。

轻量锁的依据是，对于绝大部分的锁，在整个同步周期内都是不存在竞争的（区别于偏向锁），这是一个经验数据，如果没有竞争，轻量锁使用cas操作避免了使用互斥锁的开销，但如果存在竞争，除了互斥锁的开销，还额外发生了cas，因此在有竞争的情况下，轻量锁比重量锁开销更大。

重量级锁也就是synchronized的对象锁，标志位为10，指针指向的是monitor对象的起始地址。每个对象都存在一个与之关联的monitor对象，对象与其monitor之间的关系有多种实现方式，如monitor可与对象一起创建销毁，或当线程试图获取对象锁时自动生成。monitor对象存在于每个java对象的对象头中，synchronized锁便是通过这种方式获取锁的，也是任意对象可作为锁的原因。

synchronized的流程，检测Mark word里面是不是当前线程id，如果是，表示当前线程处于偏向锁；如果不是，则使用cas将当前线程id替换Mark Word，如果成功则表示当前线程获得偏向锁，设置偏向标志位；如果失败，则说明发生竞争，撤销偏向锁，升级为轻量锁；当前线程使用cas将对象头的Mark Word替换为锁记录指针，如果成功，当前线程获得锁；如果失败，表示其他线程竞争锁，当前线程尝试使用自旋锁来获取锁；如果自旋成功则依然处于轻量锁；自旋失败，升级为重量锁。

同步语句块的实现通过monitorenter和monitorexit指令实现，当monitorenter执行时，当前线程试图获取对象所对应的monitor的持有权，当monitor的进入计数器为0，当前线程获取成功，并将计数器设置为1，如果当前线程已经持有monitor，则可以重入该monitor，计数器的值加1。如果其他线程已经拥有monitor，当前线程被阻塞，直到其他线程执行完毕，monitor计数器为0。

方法级同步是隐式的，即无需通过字节码指令控制，它实现在方法调用和返回操作中。jvm可从方法常量池中的ACC_SYNCHRONIZED访问标志区分一个方法是否同步。当方法调用时，调用指令将会检查方法的ACC_SYNCHRONIZED访问标志是否被设置，如果设置了，执行线程将先持有monitor，然后执行，最后完成释放monitor。

锁的状态共有四种，无锁状态、偏向锁、轻量级锁和重量级锁。随着锁的竞争，锁可从偏向锁升级到轻量级锁，然后重量级锁。升级是单向的。

偏向锁是，如果一个线程获得了锁，那么锁就进入偏向模式，此时Mark Word结构也变为偏向锁结构，当该线程再次请求锁时，无需再做任何同步操作，这样省去了大量有关锁申请的操作。对于锁竞争很少的场合，偏向锁有很好的优化效果，但对于锁竞争比较激烈的场合，偏向锁就失效了，升级为轻量级锁。

轻量级锁能够提升性能的依据是，绝大部分的锁，在整个同步周期内都不存在竞争。轻量级锁所适应的场景是线程交替执行同步块的场合，如果存在同一时间访问同一锁的场合，则升级为重量级锁。

轻量级锁失败后，jvm为了避免线程真实地在os层面挂起，还会进行自旋锁的优化。大多数情况下，线程持有锁的时间都不长，如果直接在os层面挂起，线程之间切换需要从用户状态换到核心态，成本很高。自旋锁假设在不久的将来，当前线程可获得锁，因此jvm会让当前想获得锁的线程做空询缓，一般不太久，经过若干次循环后如果得到锁，则进入临界区，否则，os层面挂起。

锁消除，通过对运行上下文的扫描，去除不可能存在共享资源竞争的锁，从而消除没有必要的锁，节省无意义的请求锁时间。

在获取当前实例对象锁后进入synchronized代码块执行同步代码，并在代码块中调用当前实例对象的另外一个synchronized方法，再次请求当前实例锁，是允许的，也就是所谓的可重入锁。由于synchronized是基于monitor实现的，每次重入，monitor中的计数器都加1。

中断的两种情况，一种是当线程处于阻塞状态或试图执行一个阻塞操作时，可使用实例方法interrupt进行线程中断，执行操作后，抛出interruptexception，并将中断状态复位。另外一种是当线程处于运行状态时，也可调用实例方法interrupt进行线程中断，但必须手动判断中断状态。

线程的中断操作对于正则等待获取锁对象的synchronized方法或者代码块不起作用，也就是一个线程在等待锁，那么结果只有两种，要么它获得锁继续执行，要么继续等待，即使调用中断线程操作，也不生效。

所谓等待唤醒机制主要指notify/notifyAll/wait方法，在使用这三个方法时，必须处于synchronized方法或代码块中，否则抛出illegalmonitorstateexception异常，这是因为调用这几个方法前必须拿到当前对象monitor对象，也就是notify/notifyAll/wait依赖于monitor对象。与sleep不同，wait方法调用完成后，线程将被暂停，并释放当前持有的monitor对象，直到线程调用notify/notifyAll后方可继续执行，而sleep方法只让线程休眠并不释放锁。notify/notifyAll调用后，并不马上释放锁，同步块执行结束后方自动释放锁。

锁又分为乐观锁和悲观锁，加锁是一种悲观策略，如上面的synchronized；而无锁则是一种乐观策略，无锁策略采用CAS来保证线程执行的安全性。

cas全称compare and swap，既比较交换，核心思想为：cas(v,e,n)，v表示要更新的值，e表示预期的值，n表示新值，如果v等于e，则更新v为n，如果不等，则说明其他线程已经做了更新，当前线程不能进行更新。cas是一种系统原语，属于操作系统用语范畴，由若干条指令组成，用于完成某个功能的一个过程，原语的执行必须是连续的，执行过程中不允许被中断，也就是说cas是一个cpu原子指令，不会造成数据不一致问题。

cas实现依赖sun.misc.Unsafe类，其内部方法可像c指针一样直接操作内存。cas依赖Unsafe类的下面方法：

//o为给定对象，offset为对象内存偏移量，通过偏移量可快速定位字段并设置或读取字段值，
//expected表示期望值，x需要设置的新值，只有o为期望值expected时才更新
public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object x);
public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);
public final native boolean compareAndSwapLong(Object o, long offset, long expected, long x);

java中的cas应用主要通过java.util.concurrent.atomic包中的工具类实现。主要分：原子更新基本类型、原子更新引用、原子更新数组、原子更新属性。

原子更新基本类型主要包括，AtomicBoolean、AtomicInteger、AtomicLong。其中cas实现主要为：

private static final long valueOffset;
private volatile int value
valueOffset = unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

原子更新引用，如AtomicReference类，主要实现：

private static final long valueOffset;
private volatile V value
valueOffset = unsafe.objectFieldOffset(AtomicReference.class.getDeclaredField("value"));
public final boolean compareAndSet(V expect, V update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

原子更新数组指通过原子的方式更新数组中的某个元素，包括AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray。实现思路如下，

private static final int base = unsafe.arrayBaseOffset(int[].class);
private static final int shift;
private final int[] array;
//array中一个元素占用的内存空间，
//java中int占4个字节，所有scale=4
int scale = unsafe.arrayIndexScale(int[].class);
//shift为31-29
shift = 31 - Integet.numberOfLeadingZeros(scale)；
//计算每个元素在内存中的地址，base+ i *4
private static long byteOffset(int i) {
    return ((long) i << shift) + base;
}
public final int getAndAdd(int i, int delta) {
    return unsafe.getAndAddInt(array, checkedByteOffset(i), delta);
}
//unsafe类中的getAndAddInt方法，执行cas
public final int getAndAddInt(Object o, long offset, int delta) {
    int v ;
    do {
        v = getIntVolatile(o, offset);
    } while(!compareAndSwapInt(o, offset, v, v+delta))
    return v ;
}

原子更新属性，包括AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater。操作的字段不能是static类型，不能是final类型，字段必须volatile修饰，属性必须对当前updater所在区域可见。

cas的aba问题，假设一个线程执行cas(v,e,u)操作，获取当前变量v，准备更新为u，另外两个线程连续修改两次v，使得该值恢复为旧值，这样就无法正确判断变量是否被修改了。java中可使用AtomicStampedReference类，它是一个带有时间戳的对象引用。另外AtomicMarkableReference通过维护一个boolean标识来降低aba问题，但不能完全杜绝。

自旋锁假设不久的将来，当前线程可获得锁，一次jvm会让当前线程做几个空循环，经过若干次循环后，如果得到锁，就进入临界区，如不能获得锁，就在os层面挂起。但线程竞争激烈时，重用cpu的时间变长而导致性能急剧下降。自旋锁是非公平锁，实现思路如下，

private AtomicReference<Thread> sign = new AtomicReference<>();
pubilc void lock() {
    Thread curr = Thread.currentThread();
    while(! sign.compareAndSet(null, current)){}
}
public void unlock() {
    Thread curr = Thread.currentThread();
    sign.compareAndSet(curr, null);
}

公平锁指多个线程在等待同一个锁时，必须按照申请锁的先后顺序来一次获得锁。公平锁的好处是等待锁的线程不会饿死，但整体效率相对低一些；非公平锁的好处是整体效率相对高一些，但有些线程可能会饿死或很早就在等待锁，但需要等很久才会获得锁。公平锁严格按照请求的顺序获得锁，而非公平锁可以抢占，公平锁可用new ReentrantLock(true)实现。

锁粗化，编码的时候，总是将同步块的作用域限制的尽量小，但如果一系列的操作都是同一个对象加锁和解锁，甚至加锁还出现在循环中，那么，即使没有线程竞争，频繁进行互斥锁同步操作也导致不必要的性能损失。该情况下，jvm会把加锁同步的范围扩展到整个操作序列的外部，锁范围的扩展称为锁粗化。

可重入锁又叫递归锁，指同一个线程外层函数获得锁之后，内层递归函数仍然可以获取该锁。ReentrantLock和synchronized都是可重入锁。

悲观锁，假定肯定发生并发冲突，进而屏蔽一切可能违反数据完整性的操作；乐观锁，则假定不会发生并发冲突，只是在提交操作的时候检测是否违反数据的完整性，比如使用版本号或者时间戳来配合实现。

共享锁，如果事务t对数据a加上共享锁后，则其他事务只能对a再加共享锁，不能加排他锁，获得共享锁的事务只能读数据，不能修改数据。排他锁，如果事务t对数据a加排他锁后，则其他事务不能再对a加任何类型的锁，获得排他锁的事务可以读或者修改数据。排他锁就是一次最多一个线程持有的锁，java中的synchronized和lock都是排他锁。

读写锁是一个资源可被多个读线程访问，或者被一个写线程访问但不能同时存在读线程；java中读写锁通过ReentrantReadWriteLock实现。

分段锁，concurrenthashmap使用了分段锁，字面理解也就是将保存的数据进行分段存储，为每一段数据创建一个锁进行保护，它由segment和hashentry组成，segment是一种可重入锁，hashentry用于存储键值对数据。一个concurrenthashmap包含一个segment数组，segment结构类似hashmap，是一种数组和链表结构，一个segment守护着一个hashentry数组里面的元素，当对hashentry数组中的数据进行修改时，必须首先获得它对应的segment锁。

hashmap死锁原因，在内部，hashmap使用entry数组保存k、v数据，当一对kv被加入到hashmap时，首先通过hash算法得到数组下表，然后将entry保存到数组指定位置，但如果该位置已经有值了，也就是hash冲突了，就会在指定位置形成链表，最差的情况，所有的元素都定位到同一个位置，这样hashmap就退化为一个list。

当插入新节点时，如果不存在相同的key，则首先判断当前内部元素是否已经达到阈值，该值为数组大小的0.75，如果达到，会对数组进行扩容，对链表中的元素进行rehash，并把原来的元素移动到新的数组中，transer逻辑如下，

void transfer(Entry[] newTable, boolean rehash) {
  int newCapacity = newTable.length;
  for(Entry<K,V> e : table) {
    while(null != e) {
      Entry<K,V> next = e.next;
      if(rehash){e.hash = null == e.hash ? 0 : hash(e.key);}
      int i = indexFor(e.hash, newCapacity);
      e.next = newTable[i];
      newTable[i] = e;
      e = next;
    }
  }
}

假设在同一个链a->b->c上，两个线程同时触发transfer，线程a执行到Entry<K,V> next = e.next时，cpu时间片用完，此时e指向a节点，next指向b节点。另一个线程b继续执行，并完成节点移动，此时：c->b->a，线程b时间片用完，线程a又继续执行，线程b执行完newTable[i]为c，但是当线程a重新开始执行时，对于线程a来说，newTable[i]为null。

线程a第一次循环完，依赖关系为：c->b->a，newTable[i]为a，e为b，e.next为a，由于e不为null，继续执行，第二次循环完，依赖关系为：c->b->a，newTable[i]为b，e为a，e.next为null，接着执行第三次循环，执行完，依赖关系为：c->b->a->b，newTable[i]为a，由于e此时为null，中止循环，此时a，b形成循环依赖，由于newTable[i]的入口为a，从而在get元素时，直接导致死循环，并且丢失c元素。