锁

锁的意义

公平锁/非公平锁

公平锁的作用就是严格按照线程启动的顺序来执行的，不允许其他线程插队执行的；而非公平锁是允许插队的

• 公平锁是指多个线程按照申请锁的顺序来获取锁

非公平锁的时候，会立刻尝试配置状态，成功了就会插队执行，失败了就会和公平锁的机制一样，调用acquire()方法，以排他的方式来获取锁，成功了立刻返回，否则将线程加入队列，直到成功调用为止

因为从线程进入了RUNNABLE状态，可以执行开始，到实际线程执行是要比较久的时间的。
在一个锁释放之后，其他的线程会需要重新来获取锁。
持有锁的线程释放锁，其他线程从挂起恢复到RUNNABLE状态，其他线程请求锁，获得锁，线程执行，这一系列步骤。
如果这个时候，存在一个线程直接请求锁，可能就避开挂起到恢复RUNNABLE状态的这段消耗，所以性能更优化。

• 非公平锁是指多个线程获取锁的顺序并不是按照申请锁的顺序，有可能后申请的线程比先申请的线程优先获取锁。有可能，会造成优先级反转或者饥饿现象

• ReentrantLock而言，通过构造函数指定该锁是否是公平锁，默认是非公平锁。非公平锁的优点在于吞吐量比公平锁大（基于AQS架构）

• Synchronized是一种非公平锁（不能变成公平锁）

可重入锁

重入锁源码分析
可重入锁又名递归锁，是指在同一个线程在外层方法获取锁的时候，在进入内层方法会自动获取锁（避免继承类的方法吊用父类时，已被锁定导致的死锁问题）

ReentranLock是可重入锁，不具备自旋功能
Synchronized是可重入锁，具备自旋功能

// 加锁判断
if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
// 锁状态判断
        protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                // List<Node>如果为空允许修改状态+1
                // 如果head.next 等于当前线程并且状态为0也没有锁 则允许修改状态+1
                // 否则当前队列存在前驱，不允许加锁
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            // 如果当前线程等于加锁的线程(重入机制)
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                // 状态+1
                setState(nextc);
                return true;
            }
            return false;
        }

独享锁(悲观锁)/共享锁

独享锁/共享锁就是一种广义的说法

独享锁是指该锁一次只能被一个线程所持有
共享锁是指该锁可被多个线程所持有

五个状态：
1. 新建状态
2. 就绪状态
3. 运行状态
4. 阻塞状态
5. 死亡状态

互斥锁(排他锁、阻塞锁)/读写锁

互斥锁/读写锁就是具体的实现
读锁存在的时候不允许更新，但是CopyOnWrite读没有使用锁，写的时候使用副本做修改，因此不用读锁

互斥锁在Java中的具体实现就是ReentrantLock，Synchronized
读写锁在Java中的具体实现就是ReadWriteLock
读写锁升级和降级

"读-读" 不互斥
"读-写" 互斥
"写-写" 互斥
线程进入读锁的前提条件：
  1. 没有其他线程的写锁
  2. 没有写请求，或者有写请求但调用线程和持有锁的线程是同一个线程
进入写锁的前提条件：
  1. 没有其他线程的读锁
  2. 没有其他线程的写锁

CopyOnWrite（延时懒惰策略）

在并发访问的情景下，当需要修改JAVA中Containers的元素时，不直接修改该容器，而是先复制一份副本，在副本上进行修改。修改完成之后，将指向原来容器的引用指向新的容器(副本容器)

适用于读多写少的场景。因为写操作时，需要复制一个容器，造成内存开销很大，也需要根据实际应用把握初始容器的大小
不适合于数据的强一致性场合。若要求数据修改之后立即能被读到，则不能用写时复制技术。因为它是最终一致性
写的时候加lock，防止并发写的时候出现多发副本占用内存

CopyOnWriteArrayList

如果不实用 读/写 分离，也就是写的时候使用额外副本的方式
那么在读数据的时候也需要对实例加锁，因为需要循环List，而List可能add和remove，如果不加锁会出现问题

ConcurrentHashMap

读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，不用对整个ConcurrentHashMap加锁

image.png

乐观锁/悲观锁（DBMS和JAVA实现方式不同）

悲观锁适合写操作非常多的场景，先加锁再访问
乐观锁适合读操作非常多的场景，不加锁会带来大量的性能提升，在提交更新的时候才校验冲突

悲观锁认为对于同一个数据的并发操作，一定是会发生修改的，哪怕没有修改，也会认为修改。因此对于同一个数据的并发操作，悲观锁采取加锁的形式。悲观的认为，不加锁的并发操作一定会出问题。
乐观锁则认为对于同一个数据的并发操作，是不会发生修改的。在更新数据的时候，会采用尝试更新，不断重新的方式更新数据。乐观的认为，不加锁的并发操作是没有事情的。
CAS(compare and swap)是乐观锁(无锁)，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试

此方法为什么是无锁?因为由硬件提供了原子的指令
比较并交换(Compare-And-Swap - CAS) -> cmpxchg(x86)
加载链接/条件存储(Load-Linked / Store - Conditional)

CAS相对MySQL的乐观锁，会存在ABA问题：->更新后可能此A非彼A。通过版本号可以解决，类似于上文Mysql 中提到的的乐观锁

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。”这其实和乐观锁的冲突检查+数据更新的原理是一样的

悲观锁在Java中的使用，就是利用各种锁。
乐观锁在Java中的使用，是无锁编程，常常采用的是CAS算法，
典型的例子就是原子类，通过CAS自旋实现原子操作的更新。

分段锁

分段锁其实是一种锁的设计，并不是具体的一种锁
分段锁的设计目的是细化锁的粒度，当操作不需要更新整个数组的时候，就仅仅针对数组中的一项进行加锁操作

以ConcurrentHashMap来说一下分段锁的含义以及设计思想，ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap（JDK7与JDK8中HashMap的实现）的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表；同时又是一个ReentrantLock（Segment继承了ReentrantLock)。
当需要put元素的时候，并不是对整个hashmap进行加锁，而是先通过hashcode来知道他要放在那一个分段中，然后对这个分段进行加锁，所以当多线程put的时候，只要不是放在一个分段中，就实现了真正的并行的插入。
但是，在统计size的时候，可就是获取hashmap全局信息的时候，就需要获取所有的分段锁才能统计。

偏向锁/轻量级锁/重量级锁

java锁优化
synchronized内置锁
这三种锁是指锁的状态，并且是针对Synchronized。在Java 5通过引入锁升级的机制来实现高效Synchronized（而且内置锁是JVM的发展方向）。这三种锁的状态是通过对象监视器在对象头中的字段(Mark Word 32/64位)来表明的。

锁可以升级但不能降级
存在锁的时候，对象的hashCode保存在栈帧中
无锁态时：存储的是hashCode、分代年龄。
重量级锁时：存储的是指向monitor的指针。synchronized是重量级锁。

• 偏向锁[MarkWord保存的threadId指向当前线程，且biased_lock标记为1代表是偏向所]是指一段同步代码首次/一直被同一个线程所访问，当执行monitorenter获取锁的时候，会判断当前锁类型，如果是偏向锁在取判断是否是当前threadId或者不存在，相等(ThreadRecord需要通过CAS初始化一次threadId，后续不需要CAS操作)则执行代码块，否则进行偏向锁升级，通知运行线程暂停去升级为偏向锁后恢复线程运行，当前线程进入偏向锁逻辑。

降低CAS获取锁的代价，只需要get即可，偏向首次获取的线程。
偏向锁的释放不需要做任何事情，所及基本上偏向锁没有开销

• 轻量级锁是指当锁是偏向锁的时候，存在其它的线程访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋有限尝试获取锁，不会阻塞，提高性能（有限次尝试后会膨胀为重量锁）。
  然后线程尝试使用CAS将对象头中的Mark Word替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，则自旋获取锁，当自旋获取锁仍然失败时，表示存在其他线程竞争锁(两条或两条以上的线程竞争同一个锁)，则轻量级锁会膨胀成重量级锁
  轻量级锁能提升程序同步性能的依据是“对于绝大部分的锁，在整个同步周期内都是不存在竞争的”，这是一个经验数据。如果没有竞争，轻量级锁使用CAS操作避免了使用互斥量(mutex)的开销，但如果存在锁竞争，除了互斥量的开销外，还额外发生了CAS操作，因此在有竞争的情况下，轻量级锁会比传统的重量级锁更慢。
• 重量级锁是指当锁为轻量级锁的时候，另一个线程虽然是自旋，但自旋不会一直持续下去，当自旋一定次数的时候，还没有获取到锁，就会进入阻塞，该锁膨胀为重量级锁，自旋过程中会使用yield货park放弃cpu。重量级锁会让其他申请的线程进入阻塞，性能降低。
  重量级锁使用操作系统互斥量Mutex Lock来实现，操作系统实现线程之间的切换需要从用户态->内核态的切换，切换成本很高

锁膨胀（膨胀为重量级锁）并不意味着获取锁，还需要取竞争锁，竞争失败，加入_cxq/entry进入队列，并自旋尝试获取锁，获取失败，park挂起等待唤醒
当持有锁的进程完成后释放锁，从_cxq/entry队列中获取头结点，会执行unpark唤醒进程，而进程之间相互竞争

自旋锁

自旋锁是指尝试获取锁的线程不会立即阻塞，而是采用循环的方式去尝试获取锁
好处：减少线程上下文切换的消耗，适合段时间的锁，不适合大范围的锁
缺点：循环会消耗CPU
JDK1.6后的自适应自旋锁会根据程序锁的过去状态来自动调整

锁消除

即时编译器运行时，对代码上要求同步，监测到实际不可能存在共享数据竞争的锁进行消除。

锁粗化

StringBuffer sb = new StringBuffer();
for(int i=0;i<10; i++) sb.append(i);

这样不断的对小模块大量请求加锁的情况，就会粗化锁到整个for循环

死锁

指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程

原因：
1. 竞争资源
2. 进程间推进顺序非法

导致死锁的四个条件：

1. 互斥（Mutual exclusion）
2. 持有（Hold and wait）
3. 不可剥夺（No preemption）
4. 环形等待（Circular wait）