2021-11-19

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

2019-03-13

java基础

java常量池

概述

java 包括三种常量池，分别是字符串常量池、Class 常量池（也叫常量池表）和运行时常量池。

字符串常量池（String Pool）

String Pool 是 JVM 实例全局共享的，而 Runtime Constant Pool 是每个类都有一个。

JVM 用一个哈希表记录对常量池的引用。

String Pool 在 JDK1.7 之前是存放在方法区中的，JDK1.7 移入到堆中。可以测试下往List中无限放入String，看jdk各个版本的异常信息。jdk6是PermGen Space内存溢出，jdk7和8都是Java heap space内存溢出。

常量池表（Constant Pool Table）

为了让 java 语言具有良好的跨平台性，java 团队提供了一种可以在所有平台上使用的中间代码——字节码（byte code），字节码需要在虚拟机上运行。像 Groovy、JRuby、Jython、Scala等，也会编译成字节码，也能够在 Java 虚拟机上运行。

java 文件会编译成 Class 文件，ClassClass 文件包含了 Java 虚拟机指令集和符号表以及其他辅助信息。Class文件中除了包含类的版本、字段、方法、接口等描述信息外，还有一项信息(constant pool table)，用于存放编译器生成的各种字面量(Literal)和符号引用(Symbolic References)。也就是说常量池表示属于 Class 字节码文件中的一类结构化数据，Class 文件内容如下

Class 文件结构

举个栗子。

一个 HelloWord.java 文件

public class HelloWord {
    public static void main(String[] args) {
        String s = "helloword";
    }
}

会编译成 HelloWord.class 文件，通过反编译命令 javap -v HelloWorld.class 可以查看其内容。

Classfile /Users/zhouxinghang/workspace/study/target/classes/com/zxh/study/test/HelloWord.class
  Last modified 2019-3-13; size 465 bytes
  MD5 checksum 3a7da1e8436a92ff3dacb4f45d30e7d9
  Compiled from "HelloWord.java"
public class com.zxh.study.test.HelloWord
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Methodref          #4.#20         // java/lang/Object."<init>":()V
   #2 = String             #21            // helloword
   #3 = Class              #22            // com/zxh/study/test/HelloWord
   #4 = Class              #23            // java/lang/Object
   #5 = Utf8               <init>
   #6 = Utf8               ()V
   #7 = Utf8               Code
   #8 = Utf8               LineNumberTable
   #9 = Utf8               LocalVariableTable
  #10 = Utf8               this
  #11 = Utf8               Lcom/zxh/study/test/HelloWord;
  #12 = Utf8               main
  #13 = Utf8               ([Ljava/lang/String;)V
  #14 = Utf8               args
  #15 = Utf8               [Ljava/lang/String;
  #16 = Utf8               s
  #17 = Utf8               Ljava/lang/String;
  #18 = Utf8               SourceFile
  #19 = Utf8               HelloWord.java
  #20 = NameAndType        #5:#6          // "<init>":()V
  #21 = Utf8               helloword
  #22 = Utf8               com/zxh/study/test/HelloWord
  #23 = Utf8               java/lang/Object
{
  public com.zxh.study.test.HelloWord();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 7: 0
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       5     0  this   Lcom/zxh/study/test/HelloWord;

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=1, locals=2, args_size=1
         0: ldc           #2                  // String helloword
         2: astore_1
         3: return
      LineNumberTable:
        line 9: 0
        line 10: 3
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0       4     0  args   [Ljava/lang/String;
            3       1     1     s   Ljava/lang/String;
}

字面量（literal）

在计算机科学中，字面量（literal）是用于表达源代码中一个固定值的表示法（notation）。几乎所有计算机编程语言都具有对基本值的字面量表示，诸如：整数、浮点数以及字符串；而有很多也对布尔类型和字符类型的值也支持字面量表示；还有一些甚至对枚举类型的元素以及像数组、记录和对象等复合类型的值也支持字面量表示法。

上述是计算机科学对字面量的解释，在 Java 中，字面量包括：1.文本字符串 2.八种基本类型的值 3.被声明为 final 的常量等。

字面量只可以右值出现。如 String s = "helloword"，s 为左值，helloword 为右值，helloword 为字面量。

符号引用（Symbolic References）

符号引用是编译原理的概念，1是相对于直接引用来说的。在 Java中，符号引用包括：1.类和方法的全限定名 2.字段的名称和描述符 3.方法的名称和描述符。

常量池表的作用

常量池表（Class 常量池）是 Class 文件的资源仓库，保存了各种常量。

在《深入理解Java虚拟机》中有这样的描述：

Java代码在进行Javac编译的时候，并不像C和C++那样有“连接”这一步骤，而是在虚拟机加载Class文件的时候进行动态连接。也就是说，在Class文件中不会保存各个方法、字段的最终内存布局信息，因此这些字段、方法的符号引用不经过运行期转换的话无法得到真正的内存入口地址，也就无法直接被虚拟机使用。当虚拟机运行时，需要从常量池获得对应的符号引用，再在类创建时或运行时解析、翻译到具体的内存地址之中。关于类的创建和动态连接的内容，在虚拟机类加载过程时再进行详细讲解。

运行时常量池（Runtime Constant Pool）

JVM 运行时内存中方法区的一部分，所以也是全局共享的，是运行时的内容
运行时常量池相对于 Class 常量池一大特征就是其具有动态性，Java 规范并不要求常量只能在运行时才产生，也就是说运行时常量池中的内容并不全部来自 Class 常量池，Class 常量池并非运行时常量池的唯一数据输入口；在运行时可以通过代码生成常量并将其放入运行时常量池中
同方法区一样，当运行时常量池无法申请到新的内存时，将抛出 OutOfMemoryError 异常。
这部分数据绝大部分是随着 JVM 运行，从常量池表转化而来，每个 Class（不是 Java 对象）都对应一个运行时常量池。（上面说绝大部分是因为：除了Class 中常量池内容，还可能包括动态生成并加入这里的内容）

为什么 Java 需要设计常量池，而 C 没有？

在 C/C++ 中，编译器将多个编译器编译的文件链接成一个可执行文件或 dll 文件，在链接阶段，符号引用就解析为实际地址。而 java 中这种链接是在程序运行时动态进行的。

jvm 在栈帧(frame) 中进行操作数和方法的动态链接(link)，为了便于链接，jvm 使用常量池来保存跟踪当前类中引用的其他类及其成员变量和成员方法。

当一个 java class 被编译时，所有的变量和方法都装载到 Class 常量池作为一个符号引用。JVM 实现何时去解析符号引用，可以发生在类加载后的验证步骤称为静态解析，也可以发生在第一次使用的时候称为延迟解析。

java 常量池

参考

https://blog.csdn.net/u010297957/article/details/50995869

https://blog.csdn.net/luanlouis/article/details/39960815

http://blog.jamesdbloom.com/JVMInternals.html

2019-03-12

并发编程

AQS相关

AQS 简单介绍

AbstractQueuedSynchronizer，抽象同步队列。是实现同步的基础组件，并发包中的锁都是基于 AQS 实现。

内部有一个 state 变量，用于表示一些状态信息，这个状态信息具体由实现类决定，比如一个 ReentrantLock 类这个 state 就表示获取锁的次数。

内部维持两个队列，Sync Queue 和 Condition Queue，Sync Queue 是一个双向 FIFO 链表，是锁的时候用到。而 Condition Queue 是条件队列，作为锁的等待条件时用到。

这个类使用到了模板方法设计模式：定义一个操作中算法的骨架，而将一些步骤的实现延迟到子类中。

AQS

AQS 类简单介绍

先看一下 AQS 的类图

AQS 类图

AQS 是一个 FIFO 的双向队列，内部通过 tail 和 head 来记录队尾和队首，队列元素为 Node，状态信息为 state，通过内部类 ConditionObject 来结合锁实现线程同步

Node 节点：
Note 的属性 thread 来存储进入 AQS 的线程（竞争锁失败进入等待队列）；Node 节点内部 SHARED 表示是获取共享资源被阻塞挂起后放入 AQS 队列的，EXCLUSIVE 表示获取独占资源被阻塞后挂起放入到 AQS 队列的；prev 记录当前节点的前驱节点，next 记录当前节点的后续节点。

waitStatus 表示当前线程等待状态，分别为 CANCELLED（线程被取消），SIGNAL（线程需要被唤醒），CONDITION（线程在条件队列里面等待），PROPAGATE（释放共享资源时候需要通知其他节点），

state 状态信息：

AQS 中维持了一个单一的状态信息 state，可以通过 getState、setState 和 compareAndSetState 函数修改其值

ReentrantLock：当前线程获取锁的次数
ReentrantReadWriteLock：state 高16位表示读状态也就是获取读锁的线程数，低16位表示写状态也就是获取写锁的次数
Semaphore：当前可用信号个数
FutureTask：开始，运行，完成，取消
CountDownlatch 和 CyclicBarrie：计数器当前的值

ConditionObject 内部类：

AQS 通过内部类 ConditionObject 来结合锁实现线程同步，ConditionObject 可以直接访问 AQS 内部变量（state 状态值和 Node 队列）。ConditionObject 是条件变量，每个条件变量对应一个条件队列（单向链表），线程调用条件变量的 await 方法后阻塞会放入到该队列，如类图，条件队列的头尾元素分别为 firstWaiter 和 lastWaiter。

AQS 实现同步原理

AQS 通过操作 state 状态变量实现同步的操作。操作 state 分为共享模式和独占模式。

独占模式获取和释放锁方法为：

1
2
3

void acquire(int arg) 
void acquireInterruptibly(int arg) 
boolean release(int arg)

共享模式获取和释放锁方法为：

1
2
3

void acquireShared(int arg) 
void acquireSharedInterruptibly(int arg) 
boolean releaseShared(int arg)

Interruptibly关键字的方法：

带 Interruptibly 关键字的方法会对中断进行相应，也就是在线程调用 acquireInterruptibly（或 acquireSharedInterruptibly）方法获取资源时或获取资源失败被挂起的时候，其它线程中断了该线程，那么该线程会抛出 InterruptedException 异常而返回。

独占模式获取锁与共享模式获取锁区别：

独占模式获取锁是与具体线程绑定的，比如独占锁 ReentrantLock，如果线程获取到锁，会通过 CAS 操作将 state 从0变为1并且将当前锁的持有者设为该线程。当该线程再次获取锁时发现锁的持有者为自己，就会将 state +1，当另外的线程尝试获取锁，发现当前锁持有者不是自己，会被放入到 AQS 队列并挂起。

共享模式获取锁是与具体线程不相关的，多个线程请求请求资源时候是通过 CAS 方式竞争获取的，也就是说 CAS 操作只要成功就 OK。比如 Semaphore 信号量，当一个线程通过 acquire() 方法获取一个信号量时候，会首先看当前信号量个数是否满足需要，不满足则把当前线程放入阻塞队列，如果满足则通过自旋 CAS 获取信号量。

独占模式 acquire 源码分析

public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

这是一个模板方法,获取锁 tryAcquire(arg) 的具体实现定义在子类中。

获取到锁 tryAcquire 就直接返回，否则调用 addWaiter 将当前节点添加到等待队列末尾。

private Node addWaiter(Node mode) {
    // 将当前线程封装为 Node，设为独占模式
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    // 如果 tail 不为空，将 node 插入末尾
    if (pred != null) {
        node.prev = pred;
        // 可能多个线程同时插入，用 CAS 操作
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 如果 tail 节点为空，或调用 CAS 操作将 当前节点设为 tail 节点失败
    enq(node);
    return node;
}

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        // 可能多个线程同时插入，重新判断是否为空
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

addWaiter 和 enq 方法是为了将当前线程 node 插入到队列末尾。插入成功后不会立即挂起当前线程，因为在 addWaiter 过程中前面的线程可能已经执行完。此时会调用自选操作 acquireQueued 让该线程尝试重新获取锁，如果获取锁成功就退出，否则继续。

 final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            // 如果其前驱节点为头结点，尝试获取锁，将该节点设为头结点，然后返回
            if (p == head && tryAcquire(arg)) {
                // Called only by acquire methods
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // 如果获取锁失败，则判断是否需要挂起
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

先尝试获取锁，失败再判断是否需要挂起，这个判断是通过它的前驱节点 waitStatus 确定的。

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        /*
         * This node has already set status asking a release
         * to signal it, so it can safely park.
         */
        return true;
    if (ws > 0) {
        /*
         * Predecessor was cancelled. Skip over predecessors and
         * indicate retry.
         */
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        /*
         * waitStatus must be 0 or PROPAGATE.  Indicate that we
         * need a signal, but don't park yet.  Caller will need to
         * retry to make sure it cannot acquire before parking.
         */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

如果前驱节点的 waitStatus 为：

SINGAL，其前驱节点将要被唤醒，该节点可以安全的挂起，直接返回 true
> 0，其前驱节点被取消，轮训将所有被取消的前驱节点都剔除，然后返回 false
< 0，其前驱节点为 0 或 PROPAGATE，将前驱节点置为 SINGAL 表示自己将处于阻塞状态（下次判断时，会走 ws == Node.SIGNAL 的分支），然后返回 false。

返回 false，表示会重新执行 acquireQueued 方法，然后再重新检查前驱是不是头结点重新try一下什么的，也是之前描述的流程。

获取独占锁过程总结：

AQS的模板方法acquire通过调用子类自定义实现的tryAcquire获取同步状态失败后->将线程构造成Node节点(addWaiter)->将Node节点添加到同步队列对尾(addWaiter)->节点以自旋的方法获取同步状态(acquirQueued)。在节点自旋获取同步状态时，只有其前驱节点是头节点的时候才会尝试获取同步状态，如果该节点的前驱不是头节点或者该节点的前驱节点是头节点单获取同步状态失败，则判断当前线程需要阻塞，如果需要阻塞则需要被唤醒过后才返回。

独占模式 release 源码分析

AQS 的 release 释放同步状态和 acquire 获取同步状态一样，都是模板方法，tryRealease 具体操作都由子类实现，父类 AQS 只是提供一个算法骨架。

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

如果释放成功，会解锁头节点的后续节点。

private void unparkSuccessor(Node node) {
    /*
     * If status is negative (i.e., possibly needing signal) try
     * to clear in anticipation of signalling.  It is OK if this
     * fails or if status is changed by waiting thread.
     */
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    /*
     * Thread to unpark is held in successor, which is normally
     * just the next node.  But if cancelled or apparently null,
     * traverse backwards from tail to find the actual
     * non-cancelled successor.
     */
    Node s = node.next;
    // 如果后续节点为空或是作废节点
    if (s == null || s.waitStatus > 0) {
        s = null;
        // 从末尾开始找合适的节点
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    // 唤醒
    if (s != null)
        LockSupport.unpark(s.thread);
}

如果 node 的后续节点不为空，且不是作废节点，就唤醒这个后续节点。否则从末尾开始找到合适的节点，如果找到便唤醒

AQS 对于条件变量的支持

Object 类的 notify 和 wait 是配合 synchronized 内置锁（ObjectMonitor，每个对象都有一个对应的监视器锁）来实现线程间通信与协作的。而条件变量的 singal 和 await 是配合锁（基于 AQS 实现的锁）实现线程间同步的。

一个条件变量实现线程同步的栗子：

public class ConditionDemo {
    private static final  ExecutorService EXECUTOR_SERVICE = Executors.newFixedThreadPool(2);
    public static void main(String[] args) {
        ReentrantLock lock = new ReentrantLock();
        Condition condition = lock.newCondition();
        EXECUTOR_SERVICE.submit(new AwaitThread(lock, condition));
        EXECUTOR_SERVICE.submit(new SignalThread(lock, condition));
    }
}

class AwaitThread implements Runnable {
    private ReentrantLock lock;
    private Condition condition;

    public AwaitThread(ReentrantLock lock, Condition condition) {
        this.lock = lock;
        this.condition = condition;
    }

    @Override
    public void run() {
        try {
            lock.lock();
            System.out.println("begin wait");
            condition.await();
            System.out.println("end wait");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
}

class SignalThread implements Runnable {
    private ReentrantLock lock;
    private Condition condition;

    public SignalThread(ReentrantLock lock, Condition condition) {
        this.lock = lock;
        this.condition = condition;
    }

    @Override
    public void run() {
        try {
            lock.lock();
            System.out.println("begin signal");
            condition.signal();
            System.out.println("end signal");
        } finally {
            lock.unlock();
        }
    }
}

一个 Lock 对象可以创建多个 Condition 条件变量。调用条件变量的 await 方法类似于 Object 的 wait 方法，会阻塞挂起当前线程，并释放锁，如果没有获取到锁就调用条件变量的 await 方法会抛出 java.lang.IllegalMonitorStateException 异常。

上述通过 lock.newConditio() 会在 AQS 内部声明一个 ConditionObject 对象，每个 ConditionObject 内部会维持一个条件队列，用于存放调用 await 方法而阻塞的线程。

await 方法如下：

public final void await() throws InterruptedException {
    if (Thread.interrupted())
        throw new InterruptedException();
    // 创建新的 node，并插入条件队列末尾
    Node node = addConditionWaiter();
    // 释放当前线程获取的锁
    int savedState = fullyRelease(node);
    int interruptMode = 0;
    // 调用 LockSupport.park 方法阻塞挂起当前线程
    while (!isOnSyncQueue(node)) {
        LockSupport.park(this);
        if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
            break;
    }
    if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
        interruptMode = REINTERRUPT;
    if (node.nextWaiter != null) // clean up if cancelled
        unlinkCancelledWaiters();
    if (interruptMode != 0)
        reportInterruptAfterWait(interruptMode);
}

signal 方法如下：

public final void signal() {
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    Node first = firstWaiter;
    if (first != null)
        // Transfers a node from a condition queue onto sync queue.
        doSignal(first);
}

private void doSignal(Node first) {
    do {
        if ( (firstWaiter = first.nextWaiter) == null)
            lastWaiter = null;
        first.nextWaiter = null;
    } while (!transferForSignal(first) &&
             (first = firstWaiter) != null);
}

一个锁对应一个 AQS 阻塞队列和多个条件变量，每个条件变量对应一个条件队列。

Lock 与 Condition

LockSupport 对于 AQS 阻塞和唤醒线程的支持

LockSupport 用来创建锁和其它同步类的基本线程阻塞原语，主要作用是挂起和唤醒线程。

LockSupport 类与每个使用它的线程都会关联一个许可证，默认调用 LockSupport 类方法的线程是不持有许可证的，LockSupport 类内部通过 UnSafe 类实现。先看下类图：

LockSupport 类图

主要看私有变量 UNSAFE 和 parkBlockerOffset，和一些 park 和 unpark 方法。

UNSAFE

park unpark 都是由 Unsafe 类实现的，都是 native 方法

parkBlockerOffset

私有变量 parkBlockerOffset 保存 parkBlocker 的偏移量。parkBlocker 记录的是线程的阻塞者，用于线程监控和分系工具定为原因的。可以通过 getBlocker 来获取阻塞者。注意的是为了防止滥用，setBlocker 是私有方法。

为什么不直接保存阻塞者，而用偏移量这样的方式保存阻塞者信息？

仔细想想就能明白，这个parkBlocker就是在线程处于阻塞的情况下才会被赋值。线程都已经阻塞了，如果不通过这种内存的方法，而是直接调用线程内的方法，线程是不会回应调用的。

park 相关方法

如果调用 park() 的线程已经拿到了与 LockSupport 关联的许可证（调用 unpark 方法获取许可证），则调用 LockSupport.park() 会马上返回，否者调用线程会被禁止参与线程的调度，也就是会被阻塞挂起。

parkNanos(long nanos) 与其类似，如果没有拿到许可调用线程会被阻塞挂起 nanos 时间后在返回。

parkUntil(long deadline) 也一样

park(Object blocker) 会记录阻塞者到 parkBlocker，线程恢复后，会消除 parkBlocker

unpark(Thread thread) 方法

当一个线程调用了 unpark 时候，如果参数 thread 线程没有只有与 LockSupport 相关联的许可证，则让 thread 线程持有。如果 thread 线程之前调用了 park() 被挂起，则调用 unpark 后会被唤醒。

读写锁 ReentrantReadWriteLock 原理

state 变量高16位表示获取读锁的线程数量，低16位表示线程获取写锁的可重入数量，通过 ThreadLocal 来保存线程获取读锁的可重入数量。先看下 ReentrantReadWriteLock 的类图。

ReentrantReadWriteLock 类图

其中，firstReader 记录第一个获取读锁的线程，firstReaderHoldCount 则记录第一个获取到读锁的线程获取读锁的可重入数。cachedHoldCounter 用来记录最后一个获取读锁的线程获取读锁的可重入次数：

static final class HoldCounter {
    int count = 0;
    // Use id, not reference, to avoid garbage retention
    final long tid = getThreadId(Thread.currentThread());
}

readHolds 是 ThreadLocal 变量，用于存放出去第一个获取读锁线程外的其它线程获取读锁的可重入次数和该线程的id。

static final class ThreadLocalHoldCounter
    extends ThreadLocal<HoldCounter> {
    public HoldCounter initialValue() {
        return new HoldCounter();
    }
}

写锁的获取和释放

写锁通过 WriteLock 来实现，写锁是独占锁

写锁的获取：

获取写锁会调用 acquire 方法，前面讲到 acquire 是 AQS 的模板方法，其中 tryAcquire 方法在子类中实现，所以只需要了解 tryAcquire 具体实现。

protected final boolean tryAcquire(int acquires) {
    /*
     * Walkthrough:
     * 1. If read count nonzero or write count nonzero
     *    and owner is a different thread, fail.
     * 2. If count would saturate, fail. (This can only
     *    happen if count is already nonzero.)
     * 3. Otherwise, this thread is eligible for lock if
     *    it is either a reentrant acquire or
     *    queue policy allows it. If so, update state
     *    and set owner.
     */
    Thread current = Thread.currentThread();
    int c = getState();
    // 低16位数值
    int w = exclusiveCount(c);
    // 写锁或读锁被某些线程获取
    if (c != 0) {
        // (Note: if c != 0 and w == 0 then shared count != 0)
        // w=0 说明有线程获取了读锁，w！=0 且当前线程不是写锁拥有者（W!=0 表示获取了写锁）
        if (w == 0 || current != getExclusiveOwnerThread())
            return false;
        // 可重入数量大于最大值
        if (w + exclusiveCount(acquires) > MAX_COUNT)
            throw new Error("Maximum lock count exceeded");
        // Reentrant acquire
        setState(c + acquires);
        return true;
    }
    // 读写锁都未被获取
    if (writerShouldBlock() ||
        !compareAndSetState(c, c + acquires))
        return false;
    setExclusiveOwnerThread(current);
    return true;
}

writerShouldBlock 方法对于非公平锁，是直接返回false，这样就会走 CAS 操作，与别的所有线程一起竞争，也就是后来的线程与先来的线程一起“插队”竞争。writerShouldBlock 方法对于公平锁，会调用 hasQueuedPredecessors 会判断是否有前驱节点，如果有则直接放回放弃进竞争，毕竟别人先来的要公平。

写锁的释放：

释放写锁会调用 release 方法，release 是 AQS 的模板方法，tryRelease 由子类实现，我们来看tryRelease。

protected final boolean tryRelease(int releases) {
    // 判断是否是写锁拥有者
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    // 获取释放锁后的 可重入 值
    int nextc = getState() - releases;
    boolean free = exclusiveCount(nextc) == 0;
    // 如果可重如值为0，就释放锁
    if (free)
        setExclusiveOwnerThread(null);
    // 写锁只有一个线程，不需要 CAS 操作
    setState(nextc);
    return free;
}tryAcquireShared

读锁的获取和释放

读锁通过 ReadLock 来实现，读锁是共享锁。

读锁的获取：

调用 AQS 的 acquireShared 方法，内部调用 ReentrantReadWriteLock 中的 Sync 重写的 tryAcquireShared 方法。

protected final int tryAcquireShared(int unused) {
    /*
     * Walkthrough:
     * 1. If write lock held by another thread, fail.
     * 2. Otherwise, this thread is eligible for
     *    lock wrt state, so ask if it should block
     *    because of queue policy. If not, try
     *    to grant by CASing state and updating count.
     *    Note that step does not check for reentrant
     *    acquires, which is postponed to full version
     *    to avoid having to check hold count in
     *    the more typical non-reentrant case.
     * 3. If step 2 fails either because thread
     *    apparently not eligible or CAS fails or count
     *    saturated, chain to version with full retry loop.
     */
    Thread current = Thread.currentThread();
    int c = getState();
    // 如果写锁被获取，且不是当前线程
    if (exclusiveCount(c) != 0 &&
        getExclusiveOwnerThread() != current)
        return -1;
    // 获取了读锁的线程数，别搞成是可重入数量
    int r = sharedCount(c);
    // 尝试获取读锁，多个线程只有一个成功，不成功的会进入下面的 fullTryAcquireShared 方法
    if (!readerShouldBlock() &&
        r < MAX_COUNT &&
        compareAndSetState(c, c + SHARED_UNIT)) {
        // 第一个获取读锁
        if (r == 0) {
            firstReader = current;
            firstReadeHoldCount = 1;
        // 是第一个获取读锁的线程
        } else if (firstReader == current) {
            firstReaderHoldCount++;
        } else {
            HoldCounter rh = cachedHoldCounter;
            // 将获取到读锁的当前线程和可重入数记录到 cachedHoldCounter 中
            if (rh == null || rh.tid != getThreadId(current))
                cachedHoldCounter = rh = readHolds.get();
            // cachedHoldCounter 为当前线程，将其保存到 readHolds 中
            else if (rh.count == 0)
                readHolds.set(rh);
            rh.count++;
        }
        return 1;
    }
    // 自旋 CAS 获取读锁
    return fullTryAcquireShared(current);
}

readerShouldBlock 方法会判断是否需要阻塞，在公平锁和非公平锁有不同的实现。

在非公平锁下，如果同步等待队列中有获取写锁的线程在排队，则获取读锁的该线程会阻塞，否则直接尝试获取读锁。

static final class NonfairSync extends Sync {
    final boolean readerShouldBlock() {
        return apparentlyFirstQueuedIsExclusive();
    }
}

final boolean apparentlyFirstQueuedIsExclusive() {
    Node h, s;
    return (h = head) != null &&
        // AQS 第一个 node 是虚拟节点
        (s = h.next)  != null &&
        !s.isShared()         &&
        s.thread != null;
}

在公平锁下，如果同步队列中有其他线程在排队，则获取读锁的该线程会阻塞，这里和写锁是一样的，先来后到~

static final class FairSync extends Sync {
    final boolean readerShouldBlock() {
        return hasQueuedPredecessors();
    }
}

读锁的释放：

直接看 tryReleaseShared 方法

protected final boolean tryReleaseShared(int unused) {
    Thread current = Thread.currentThread();
    // 先 firstReader 再 cachedHoldCounter 最后 readHolds
    if (firstReader == current) {
        // assert firstReaderHoldCount > 0;
        if (firstReaderHoldCount == 1)
            firstReader = null;
        else
            firstReaderHoldCount--;
    } else {
        HoldCounter rh = cachedHoldCounter;
        if (rh == null || rh.tid != getThreadId(current))
            rh = readHolds.get();
        int count = rh.count;
        // 为0 记得在 ThreadLocal 中 remove
        if (count <= 1) {
            readHolds.remove();
            if (count <= 0)
                throw unmatchedUnlockException();
        }
        --rh.count;
    }
    // 轮训 CAS 操作，将状态 state 更新
    for (;;) {
        int c = getState();
        int nextc = c - SHARED_UNIT;
        if (compareAndSetState(c, nextc))
            // Releasing the read lock has no effect on readers,
            // but it may allow waiting writers to proceed if
            // both read and write locks are now free.
            return nextc == 0;
    }
}

锁降级

锁降级：写锁变成读锁。锁升级：读锁变成写锁。

同一线程在没有释放读锁下去申请写锁，会阻塞，ReentrantReadWriteLock 不支持锁升级。下面代码会阻塞：

ReadWriteLock rtLock = new ReentrantReadWriteLock();
rtLock.readLock().lock();
System.out.println("get readLock");
rtLock.writeLock().lock();
System.out.println("blocking");

ReentrantReadWriteLock支持锁降级，如果线程先获取写锁，再获得读锁，再释放写锁，这样写锁就降级为读锁了。

ReadWriteLock rtLock = new ReentrantReadWriteLock();
rtLock.writeLock().lock();
System.out.println("get writeLock");
rtLock.readLock().lock();
System.out.println("get readLock");
rtLock.writeLock().unlock();
System.out.println("unWriteLock");

一些疑问

1.ReadLock 既然有了 readHolds 这个 ThreadLocal 变量，为什么还要额外的添加 firstReader 和 cachedHoldCounter 呢？

因为 ThreadLocal 变量内部是Map，这样比直接 get 一个变量是要要相对耗时的。在 fullTryAcquireShared 方法中也是先判断 firstReader 再判断 cachedHoldCounter 然后再在 readHolds 中获取的，或许 Doug Lea 大佬认为第一个获取读锁的线程后续也大概是这个线程继续获取读锁的。而且这个命名 cachedHoldCounter 也已经说明一切。

2.读锁中判断是否需要阻塞 readerShouldBlock 方法，非公平锁的实现，为什么需要判断头结点是否是获取写锁而排队呢？

看注释是为了避免无限期的写锁饥饿

synchronized 与 lock 的区别

synchronized 是通过 Monitor 监视器锁实现，而 Lock 是通过 AQS 实现。在 jdk6 之前，synchronized 是一个重量级锁。

一些疑问

为什么 AQS 需要一个虚拟 head 节点

每个节点都需要根据其前置节点 waitStatus 状态是 SINGAL 来唤醒自己，为了防止重复唤醒。但是第一个节点是没有前置节点，所以需要一个虚拟节点。

参考

java 并发编程之美（三）

[java1.8源码笔记]ReentrantReadWriteLock详解

https://www.jianshu.com/p/9d379adba98c

https://www.jianshu.com/p/396d8c5ba4c4

https://zhuanlan.zhihu.com/p/27134110

https://juejin.im/post/5ae755606fb9a07ab97942a4

2019-03-05

java进阶

java中的锁

公平锁和非公平锁

公平锁好处是等待锁的线程不会饿死，但整体效率较低。非公平锁好处是整体效率高一些，但是有些线程可能需要等待很久才能获取到锁。因为非公平锁是可以抢占的。

两者内部都维持一个 AQS 等待队列（FIFO），放置等待等待获取锁的线程。如果释放锁的时候，没有新的线程来获取锁，这时候就会从 AQS 队列头取出线程让其获取到锁。这时候公平锁和非公平锁是一样的。如果释放锁的时候，刚好有新的线程来获取锁，非公平锁就会将锁分配给这个新的线程，这就是非公平锁的抢占式。因为非公平锁中新来的线程有一定几率不会被挂起，减少了整体线程挂起的几率，所以非公平锁性能高于公平锁。

公平锁可以使用new ReentrantLock(true)实现。

自旋锁

java 的线程是映射到操作系统的，线程的阻塞和唤醒需要操作系统来完成，这就需要从用户态转换到核心态，增加了状态切换的耗时。许多应用的共享数据的锁定状态自会持续很短的时间，为了这点时间去挂起和恢复现场不值得。我们可以让请求锁的线程自旋等待，不放弃CPU时间，直到获取到锁。

自旋锁在JDK1.4.2中引入，使用-XX:+UseSpinning来开启。JDK6中已经变为默认开启，并且引入了自适应的自旋锁。自适应意味着自旋的时间不在固定了，而是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定。

自旋锁是通过 CAS 实现的，即不断重试 CAS 直到成功为止。自旋锁存在的问题如下：

占用过多 CPU 时间
死锁问题，在递归调用中，同一个线程获取到自旋锁，由再次申请获取
ABA 问题，java 中自旋锁一般是利用 CAS 操作实现

jdk 中 atomic 包下都是采用自旋锁原理

锁消除

锁消除是指 JVM 在 JIT 编译时，通过扫描上下文，去除不可能存在共享资源竞争的锁。通过锁消除，可以减少无畏的请求锁时间。

锁消除的主要判断依据是来源于逃逸分析的数据支持，如果判断在一段代码中，堆上的所有数据都不会逃逸出去从而能被其他线程访问到，那就可以把他们当做栈上数据对待，认为他们是线程私有的，同步加锁自然就无需进行。

比如下面这个代码


public String concatString(String s1, String s2, String s3) { 

    StringBuffer sb = new StringBuffer(); 

    sb.append(s1); 

    sb.append(s2); 

    sb.append(s3); 

    return sb.toString(); 

}

JIT 回去除 append 方法的加锁

锁粗化

一般情况下，都是推荐加锁范围越小越好。但是如果连续几行代码都是对同一个对象加锁解锁，甚至加锁操作出现循环体中。虚拟机遇到这样的情况，会将加锁范围扩大到整个操作序列的外部

比如下面的代码


StringBuffer sb = new StringBuffer(); 

public String concatString(String s1, String s2, String s3) { 

    StringBuffer sb = new StringBuffer(); 

    sb.append(s1); 

    sb.append(s2); 

    sb.append(s3); 

    return sb.toString(); 

}

因为 StringBuffer 定义在方法体外面，存在锁竞争，每个 append 都会加解锁，jvm 会将加锁范围扩大到整个 append 操作序列的外部

可重入锁

可重入锁也叫递归锁，同一线程可以多次获取同一个锁。可重入锁避免了死锁，synchronizez 和 ReentrantLock 都是可重入锁

类锁和对象锁


public class SynchronizedTest { 

    public static synchronized void method1() {} 

    public void method2() { 

        synchronized(LockStrategy.class) {} 

    } 

    public synchronized void method3() {} 

}

其中 method1 和 method2 都是类锁，method3 是对象锁

偏向锁、轻量级锁和重量级锁

在 jdk6 之前， synchronizez 一直是一个重量级锁，在 jdk6 中对 synchronized 做了很多优化，引入了偏向锁和轻量级锁。

对象头

锁存在于 java 对象头中，如果对象是数组类型，则虚拟机用 3 个 Word（字宽）存储对象头，如果对象是非数组类型，则用 2 字宽存储对象头。在 32 位虚拟机中，一字宽等于四字节，即 32bit。

长度	内容	说明
32/64 bit	Mark Word	HashCode，分代年龄和锁标记位
32/64 bit	Class Metadata Address	存储对象的类型指针
32/64 bit	Array length	数组的长度（如果当前对象是数组）

Class Metadata Address 用于存储对象的类型指针，该指针指向它的类元数据，JVM通过这个指针确定对象是哪个类的实例

Mark Word

Java 对象头里的 Mark Word 里默认存储对象的 HashCode，分代年龄和锁标记位。32位 JVM 的 Mark Word 存储结果如下

Mark Word 结构

其中 epoch 为偏向时间戳。

偏向锁

偏向锁是为了消除无竞争情况下的同步原语，进一步提升程序性能。

偏向锁会偏向于第一个获取到他的线程，只要没有别的线程获取该锁，那么这第一个线程将永远不需要同步。


public synchronized void method() { 

// do ... 

}

如上述代码，线程A 第一个获取到这个锁，那么线程A后续执行 method，就不需要再进行获取锁的操作（只要中途没有别的线程来获取锁）。当有线程B来执行 method 时，偏向锁宣告结束，进入轻量级锁。

实现原理：当线程请求到锁对象后，将锁对象的状态标志位改为01，即偏向模式。然后使用CAS操作将线程的ID记录在锁对象的Mark Word中。以后该线程可以直接进入同步块，连CAS操作都不需要。但是，一旦有第二条线程需要竞争锁，那么偏向模式立即结束，进入轻量级锁的状态。

优点：偏向锁可以调高有同步但是没有竞争的程序性能，但是如果锁对象同时被多个线程竞争，那么偏向锁是多余的

偏向锁可以通过 JVM 参数来关闭：-XX:-UseBiasedLocking=false

轻量级锁

使用 CAS 操作代替互斥同步，在线程请求锁时

实现原理：在线程请求锁时，判断锁对象的 Mark Word 是否是无锁状态（锁标志位为01，是否偏向为0），然后在线程的栈帧中创建一块 Lock Record 空间，并将锁对象的 Mark Word 复制到 Lock Record中，然后通过 CAS 操作将锁对象的 Mark Word 替换为指向 Lock Record 的指针，并将 Lock Record 的 owner 指针指向锁对象的 Mark Word。如下图：

获取轻量级锁过程

获取锁失败的处理：如果成功则表示获取锁成功，如果失败，首先会检查锁对象的 Mark Word 是否指向当前线程的栈帧。如果是表示获取锁成功，如果还不是表示获取锁失败。此时轻量级锁膨胀为重量级锁，当前线程会尝试用自旋获取锁，后面的线程会阻塞等待。

前提：轻量级锁比重量级锁性能高的前提是，在轻量级锁被占用期间，不会发生锁的竞争。一旦发生锁竞争，会膨胀为重量级锁，除了使用互斥量外还额外增加了 CAS 操作。

获取锁失败了，为什么要重复检查 Mark Word

因为可能是可重入锁

三者区别

重量级锁是一种悲观锁，而轻量级锁和偏向锁是乐观锁
轻量级锁是在无锁竞争情况下，使用 CAS 操作来代替互斥量使用。而偏向锁是在无锁竞争情况下，完全取消同步（只有第一次获取锁的时候会使用 CAS 操作）
轻量级锁适用场景是线程交替进入同步块，如果同一时间多个线程竞争同一把锁就会膨胀为重量级锁
一个线程重复访问同步块，轻量级锁每次都要进行 CAS 操作。而偏向锁是为了避免在无锁竞争情况下，不必要的 CAS 操作。只有第一次获取锁的时候会使用 CAS 操作
synchronized 通过监视器锁来实现同步（monitorenter 和 monitorexit），而监视器锁有依赖于底层的互斥锁，进入互斥锁需要用户态与和心态的切换，所以synchronized是重量级锁

乐观锁和悲观锁

悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。

乐观锁：假定不会发生并发冲突，只在提交操作时检测是否违反数据完整性。（使用版本号或者时间戳来配合实现）

读写锁

读写锁是数据库常见的锁，又叫共享-排它锁，S锁和X锁

共享锁：如果事务T对数据A加上共享锁后，则其他事务只能对A再加共享锁，不能加排它锁。获准共享锁的事务只能读数据，不能修改数据。

排它锁：如果事务T对数据A加上排它锁后，则其他事务不能再对A加任何类型的锁。获得排它锁的事务即能读数据又能修改数据。

读锁不能直接升级为写锁，需要重新获取写锁。

Java当中的读写锁通过ReentrantReadWriteLock实现

互斥锁

同一时刻最多只有一个线程持有锁，在JDK中synchronized和JUC的Lock就是互斥锁。

无锁

有些方法不涉及到共享数据，就不会出现线程安全问题，一定线程安全的有：

无状态编程
ThreadLocal等线程封闭方案
volatile（volatile只能保证可见性和防止重排序，并不能保证线程安全）
CAS
协程，单线程内维持多个任务的调度

分段锁

ConcurrentHashMap

闭锁

闭锁是一种同步工具类，可以延迟线程的进度直到其到达终止状态。闭锁的作用相当于一扇门：在闭锁到达结束状态之前，这扇门一直是关闭的，并且没有任何线程能通过，当到达结束状态时，这扇门会打开允许所有的线程通过。当闭锁到达结束状态后，将不会再改变状态，因此这扇门将永远保持打开状态。闭锁可以用来确保某些活动指导其他活动都完成后才继续执行。CountDownLatch就是一种灵活的闭锁实现。

死锁

多个线程因资源竞争而相互等待的现象。出现死锁必须满足4个条件：

互斥条件：一个资源一次只能被一个进程使用
请求与保持条件：一个进程因请求资源而阻塞等待，对已获取的资源保持不放
不剥夺条件：进程已获取的资源，不会被剥夺
循环等待条件：若干进程形成循环等待资源的关系。

活锁

LiveLock是一种形式活跃性问题，该问题尽管不会阻塞线程，但也不能继续执行，因为线程将不断重复执行相同的操作，而且总会失败。活锁通常发送在处理事务消息的应用程序中：如果不能成功地处理某个消息，那么消息处理机制将回滚整个事务，并将它重新放到队列的开头：如果不能成功地处理某个消息，那么消息处理机制将回滚整个事务，并将它重新放到队列的开头。如果消息处理器在处理某种特定类型的消息时存在错误并导致它失败，那么每当这个消息从队列中取出并传递到存在错误的处理器时，都会发生事务回滚。由于这条消息又被放回到队列开头，因此处理器将被反复调用，并返回相同的结果。

参考

https://www.infoq.cn/article/java-se-16-synchronized

https://www.zhihu.com/question/55075763

https://hiddenpps.blog.csdn.net/article/details/51204385

2019-03-04

计算机操作

hexo deploy 指定 git 账户

问题

hexo deploy默认使用全局的git user.name user.email，通过设置自定义 git 用户

操作

在 hexo 全局 _config.yml 中添加配置

deploy:
  type: git
  repo: <repository url>
  branch: [branch]
  message: [message]
  name: [git user]
  email: [git email]
  extend_dirs: [extend directory]

然后需要删除 .deploy_git 目录，重新 hexo deploy 生成即可

参考

https://github.com/hexojs/hexo/issues/2125

2019-02-28

java进阶

java内存模型

基础

现代计算机物理内存模型

物理内存模型

访问局部性（英语：Locality of reference）

访问局部性分为两种基本形式，一种是时间局部性，另一种是空间局部性。时间局部性指的是，程序在运行时，最近刚刚被引用过的一个内存位置容易再次被引用，比如在调取一个函数的时候，前不久才调取过的本地参数容易再度被调取使用。空间局部性指的是，最近引用过的内存位置以及其周边的内存位置容易再次被使用。空间局部性比较常见于循环中，比如在一个数列中，如果第3个元素在上一个循环中使用，则本次循环中极有可能会使用第4个元素。

指令重排序

指令重排序是为了提高程序性能做得优化，比如多次写操作，每次都要会写内存，可以在线程的 working memory 操作完成后，一起回写内存。

指令重排序包括：

编译器优化重排序
指令级并行重排序
内存系统的重排序

as-if-serial

无论如何重排序,程序执行的结果都应该与代码顺序执行的结果一致(Java编译器,运行时和处理器都会保证java在单线程下遵循as-if-serial语义).

线程的 working memory

是 cache 和寄存器的抽象，解释源于《Concurrent Programming in Java: Design Principles and Patterns, Second Edition》，而不单单是内存的某个部分

Java 内存模型（Java Memory Model）

Java内存模型(Java Memory Model)描述了Java程序中各种变量(线程共享变量)的访问规则,以及在JVM中将变量存储到内存和从内存中读取出变量这样的底层细节.

happens-before 原则

规定了 java 指令操作的偏序关系。是 JMM 制定的一些偏序关系，用于保证内存的可见性。

8大 happens-before 原则：

单线程happen-before原则：在同一个线程中，书写在前面的操作happen-before后面的操作。
锁的happen-before原则：同一个锁的unlock操作happen-before此锁的lock操作。
volatile的happen-before原则：对一个volatile变量的写操作happen-before对此变量的任意操作(当然也包括写操作了)。
happen-before的传递性原则：如果A操作 happen-before B操作，B操作happen-before C操作，那么A操作happen-before C操作。
线程启动的happen-before原则：同一个线程的start方法happen-before此线程的其它方法。
线程中断的happen-before原则：对线程interrupt方法的调用happen-before被中断线程的检测到中断发送的代码。
线程终结的happen-before原则：线程中的所有操作都happen-before线程的终止检测。
对象创建的happen-before原则：一个对象的初始化完成先于他的finalize方法调用。

内存可见性

共享变量实现可见性原理

线程1对共享变量的修改对线程2可见，需要2个步骤：

将工作内存1中修改的共享变量刷新到主内存
将主内存最新的共享变量更新到工作内存2

synchronized

JMM 关于synchronized 的两条规定：

线程解锁前，刷新共享变量到主存
线程加锁前，获取主存中共享变量最新值到工作内存

volatile

有内存栅栏（或内存屏障）和防止指令重排序

JMM 中，在 volatile 变量写操作后加入 store 栅栏（(强制将变量值刷新到主内存中去)），在读操作前加入 load 栅栏（强制从主内存中读取变量的值）

参考

https://www.jianshu.com/p/1508eedba54d
https://www.jianshu.com/p/47f999a7c280
http://ifeve.com/easy-happens-before/

Quick Start

Create a new post

Run server

Generate static files

Deploy to remote sites

概述

字符串常量池（String Pool）

常量池表（Constant Pool Table）

字面量（literal）

符号引用（Symbolic References）

常量池表的作用

运行时常量池（Runtime Constant Pool）

为什么 Java 需要设计常量池，而 C 没有？

参考

AQS 简单介绍

AQS

AQS 类简单介绍

AQS 实现同步原理

独占模式 acquire 源码分析

独占模式 release 源码分析

AQS 对于条件变量的支持

LockSupport 对于 AQS 阻塞和唤醒线程的支持

UNSAFE

parkBlockerOffset

park 相关方法

unpark(Thread thread) 方法

读写锁 ReentrantReadWriteLock 原理

写锁的获取和释放

读锁的获取和释放

锁降级

一些疑问

synchronized 与 lock 的区别

一些疑问

为什么 AQS 需要一个虚拟 head 节点

参考

公平锁和非公平锁

自旋锁

锁消除

锁粗化

可重入锁

类锁和对象锁

偏向锁、轻量级锁和重量级锁

对象头

Mark Word

偏向锁

轻量级锁

获取锁失败了，为什么要重复检查 Mark Word

三者区别

乐观锁和悲观锁

读写锁

互斥锁

无锁

分段锁

闭锁

死锁

活锁

参考

问题

操作

参考

基础

现代计算机物理内存模型

指令重排序

as-if-serial

线程的 working memory

Java 内存模型（Java Memory Model）

happens-before 原则

内存可见性

共享变量实现可见性原理

synchronized

volatile

参考

伪共享