public static ExecutorService newFixedThreadPool(int nThreads){
    return new ThreadPoolExecutor(int corePoolSize,
                            int nThreads,	//maximumPoolSize
                            0L,		//keepAliveTime
                            TimeUnit unit,
                            BlockingQueue<Runnable> workQueue);
}

public static ExecutorService newSingleThreadExecutor(){
    return new ThreadPoolExecutor(1,
                                1,
                                0L,
                                TimeUnit unit,
                                new LinkedBlockingQueue<Runnable>());
}

public static ExecutorService newCachedThreadPool(){
    
    return new ThreadPoolExecutor(0,
                                Integer.MAX_VALUE,
                                keepAliveTime
                                TimeUnit.SECONDS,
                                new SynchronousQueue<Runnable>());
}

public E take() throws InterruptedException{
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();                                       // 1
    try{
        for( ; ; ){
            E first = q.peek();
            if(first == null){
                available.await();                                  // 2.1
            }
            else{
                long delay = first.getDelay(TimeUnit.NANOSECONDS);
                if(delay > 0){
                    long t1 = available.awaitNanos(delay);          // 2.2 
                }
                else{
                    E x = q.poll();                                 // 2.3.1
                    assert(x != null);
                    if(q.size() != 0){
                        available.signalAll();                      // 2.3.2
                    }
                    return x;
                }
            }
        }
    }finally {
        lock.unlock();                                              // 3
    }
}

public boolean offer(E e){
    final ReentrantLock lock = this.lock;
    lock.lock();                                            // 1
    try{
        E first = q.peek();
        q.offer(e);                                         // 2.1
        if(first  == null || e.compareTo(first) < 0){           
            avaiable.singalAll();                           // 2.2
        }
        return true;
    }finally {
        lock.unlock();                                      // 3
    }
}

public void execute(Runnable command){
    if(command == null){
        throw  new NullPointerException();
    }
    //如果addIfUnderCorePoolSize(command)成功,
    //表示 poolSize < corePoolSize, 在corePool线程池未满有线程可供使用
    if(poolSize >= corePoolSize || !addIfUnderCorePoolSize(command)){
        //如果线程大于等于基本线程数,或者线程创建失败, 则将当前任务刚到工作队列中.
        if(runState == RUNNING && workQueue.offer(command)){
            ensureQueueTaskHandled(command);
        }
    }
    //如果线程池不处于运行状态或任务无法加入队列, 并且当前线程数量小于最大允许的线程数量
    //则创建一个线程执行任务
    else if(!addIfUnderMaximumPoolSize(command)){
        reject(command);
    }
}

public void run(){
    try{
        Runnable task = firstTask;
        firstTask = null;
        //task  如果不是是从线程池中取出的队列
        //      那么就从工作队列(阻塞队列)中取出任务
        while(task != null || (task = getTask() != null)){
            runTask(task);
            task = null;
        }
    }finally {
        workerDone(this);
    }
}

new ThreadPoolExecutor(corePoolSize, 
                            runnableTaskQueue,
                            maximumPoolSize, 
                            keepAliveTime, 
                            TimeUnit,
                            ThreadFactory, 
                            handler)

public class EasyJoinTest {
    static volatile int Count = 0;
    static class WorkThread implements Runnable{
        int i = ++Count;
        @Override
        public void run() {
            try {
                System.out.println("Thread: " + i + " start");
                TimeUnit.SECONDS.sleep(1);
            }catch (Exception e){
            } finally {
                System.out.println("Thread: " + i +" finished");
            }
        }
    }
    public static void main(String[] args) throws InterruptedException{
        Thread t1 = new Thread(new WorkThread());
        Thread t2 = new Thread(new WorkThread());
        t1.start();
        t2.start();
        //主线程等待t1, t2线程退出才能退出
        t1.join();
        t2.join();
        System.out.println("all done");
    }
}

public class CountDownLatchTest {
    static volatile int Count = 0;
    static CountDownLatch countDownLatch  = new CountDownLatch(2);
    static class WorkThread implements Runnable{
        int i = ++Count;
        @Override
        public void run() {
            try {
                System.out.println("Thread: " + i + " start");
                TimeUnit.SECONDS.sleep(1);
            }catch (Exception e){
            } finally {
                System.out.println("Thread: " + i +" finished");
                countDownLatch.countDown();
            }
        }
    }
    public static void main(String[] args) throws InterruptedException{
        Thread t1 = new Thread(new WorkThread());
        Thread t2 = new Thread(new WorkThread());
        Thread t3 = new Thread(new WorkThread());
        t1.start();
        t2.start();
        t3.start();
        //由于countDownLatch在初始化是等待2个countDown()方法的调用
        //所以可能并不会等待线程3完成 而是先输出 all done, 再输出Thread： 3 finished
        countDownLatch.await();
        System.out.println("all done");
    }

CyclicBarrier(int parties);	//等待parties个线程到达
//在有线程到达屏障的时候执行barrierAction线程
//barrier线程在其他线程到达屏障的时候执行
CyclicBarrier(int parties, Runnable barrierAction);

public class CyclicBarrierTest {
    static CyclicBarrier barrier  = new CyclicBarrier(2, new PriorityThread());
    static class PriorityThread implements Runnable{
        @Override
        public void run() {
            System.out.println("this is priority thread");
        }
    }
    static class NormalThread implements Runnable{
        static volatile int count = 0;
        @Override
        public void run(){
            int c = ++count;
            System.out.println("thread: " + c + " is started and sleep 1s");
            try{
                TimeUnit.SECONDS.sleep(1);
                barrier.await();	//线程会被阻塞在这里
            }catch (Exception e){
            }finally {
                System.out.println("thread " + c + " is over");
            }
        }
    }
    public static void main(String[] args){
        Thread t1 = new Thread(new NormalThread());
        Thread t2 = new Thread(new NormalThread());
        t1.start();
        t2.start();
    }
}

public class SemaphoreTest {
    static Semaphore semaphore =  new Semaphore(2);
    static ThreadPoolExecutor pool = new ThreadPoolExecutor(20, 20, 20, TimeUnit.SECONDS, new ArrayBlockingQueue<Runnable>(20));
    static volatile int cnt = 0;
    static class MyThread implements Runnable{
        private int c = ++cnt;
        @Override
        public void run(){
            try{
                semaphore.acquire();
                System.out.println("task " + c + " is running, the number of waiting queue: " + semaphore.getQueueLength());
                TimeUnit.SECONDS.sleep(3);
                semaphore.release();
            }catch (Exception e){
            }
        }
    }
    public static void main(String[] args) throws InterruptedException{
        for(int i = 0; i < 20; ++i){
            Thread t = new Thread(new MyThread());
            pool.execute(t);
        }
        pool.shutdown();
    }
}

public class ExchangerTest {
    static Exchanger exchanger  = new Exchanger();
    static Random random  = new Random(47);
    static class MyThread implements Runnable{
        @Override
        public void run(){
            try {
                for( ; ;) {
                    int exchangerNumber = random.nextInt(10);
                    int i = (Integer) exchanger.exchange(exchangerNumber);
                    System.out.println("my number: " + exchangerNumber + ", your number: " + i);
                    if( i == exchangerNumber){
                        break;
                    }
                }
            }catch (Exception e){
            }
        }
    }
    public static void main(String[] args){
        int i =  0;
        Thread t1 = new Thread(new MyThread());
        Thread t2 = new Thread(new MyThread());
        t1.start();
        t2.start();
    }
}

public final int getAndIncrement(){
    for( ; ; ){
        int current = get();
        int next = current + 1;
        if(compareAndSet(current, next)){
            return current;
        }
    }
}
public final boolean compareAndSet(int expect, int update){
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

public final native boolean compareAndSwapObject(Object o, 
                                              long offset,
                                              Object expected,
                                              Object update);
public final native boolean compareAndSwapInt(Object o,
                                              long offset,
                                              int expected,
                                              int update);
public final native boolean compareAndSwapLong(Object o,
                                              long offset,
                                              long expected,
                                              long update);

static int []value = new int[]{1, 2,};
//AtomicIntegerArray内部的数组是value数组的拷贝
static AtomicIntegerArray array  = new AtomicIntegerArray(value);
public static void main(String[] args){
    System.out.println(array.getAndSet(0, 11)); //输出1
    System.out.println(array.get(0));                       //输入11
    System.out.println(value[0]);                           //输出1
}

static AtomicReference<User> reference1 = new AtomicReference<>();
static class User{
    boolean flag;
    int i;
    String s;
    public User(boolean flag, int i, String s){
        this.flag = flag;
        this.i = i;
        this.s = s;
    }
    public boolean getFlag(){ return flag; }
    public int getInt(){ return i; }
    public String getSring(){ return s; }
    public String toString(){return "flag: " + flag + ", i: " + i + ", s: " + s;}
}
public static void main(String[] args){
    User user = new User(true, 11, "Irving");
    User newUser = new User(false, 2, "Kawhi");
    reference1.set(user);
    reference1.compareAndSet(user, newUser);
    System.out.println(reference1.toString());  //输出： flag: false, i: 2, s: Kawhi

static class Player{
    public volatile int number; //变量number必须是 public属性 和 volatile
    public Player(int number){ this.number = number; }
    public int getNumber() { return number; }
}
static AtomicIntegerFieldUpdater<Player> updater = AtomicIntegerFieldUpdater.newUpdater(Player.class, "number");
public static void main(String[] args){
    Player kawhi = new Player(1);
    System.out.println(updater.getAndIncrement(kawhi)); //返回旧值1
    System.out.println(updater.get(kawhi));             //返回新值2
}

if(concurrencyLevel > MAX_SEGMENTS){
    concurrencyLevel = MAX_SEGMENTS;    //最大值为65535
}
int sshift = 0;
int ssize = 1;
while(ssize < concurrencyLevel){
    ++sshift;
    ssize <<= 1;        //最大值为65536
}
segmentShift = 32 - sshift;     //段偏移量
segmentMask = ssize -1;         //段掩码
this.segments = Segment.newArray(ssize);

if(initialCapacity > MAXIMUM_CAPACITY){
    initialCapacity = MAXIMUM_CAPACITY;
}
int c = initialCapacity / ssize;
if(c * ssize < initialCapacity){
    ++c;
}
int cap = 1;
//cap就是segment里HashEntry数组的长度 
//默认情况下 initialCapacity == 16, loadFactor == 0.75, cap == 1 
while(cap < c){
    cap <<= 1;      
}
//初始化segments[] 数组
for(int i = 0; i < this.segments.length; ++i){
    this.segments[i] = new Segment<K, V>(cap, loadFactor);
}

transient volatile int count;
volatile V value;

private transient volatile Node<E> tail = head;

private static final int HOPS = 1;
public boolean offer(E e){
    if(e == null){
        throw new NullPointerException();
    }
    //创建准备入队的节点
    Node<E> node = new Node<E>(e);
    retry:
    //死循环, 入队不成功反复入队
    for( ; ; ){
        Node<E> t = tail;   //创建一个指向tail节点的引用
        Node<E> p = t;      //p用来表示队列的尾节点, 默认情况下等于tail
        for(int hops = 0; ; hops++){
            Node<E> next = succ(p);
            // next != null说明p不是尾节点, 需要更新p后, 在将它指向next节点
            if(next != null){
                //默认情况下 HOPS == 1
                //循环了两次及其以上, 并且当前节点还是不等于尾节点
                if(hops > HOPS && t != null){
                    continue retry;
                }
                p = next;
            }
            //如果p是尾节点, 则设置p的next节点为入队节点
            //
            else if(p.casNext(null, n)){
                if(hops >= HOPS){
                    casTail(t, n);
                }
                return true;
            }
            else{
                //p有next节点, 表示p的next节点有可能是尾节点
                p = succ(p);
            }
        }
    }
}

//找p节点下一节点
//当 p == next 成立, 说明队列为空, 返回头节点即可
final Node<E> succ(Node<E> p){
    Node<E> next = p.getNext();
    return (p == next) ? head : next;
}

p.casNext(null, n)

public boolean easyUnderstandOffer(E e){
    if(e == null){
        throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    for( ; ; ){
        Node<E> t = tail;
        //每次都假设tail作为队列尾节点
        //判断失败就是有其他线程竞争, 该线程重新入队即可
        if(t.casNext(null, node) && casTail(t, node)){
            return true;
        }
    }
}

public E poll(){
    Node<E> h = head;
    // p表示头节点, 需要出队的节点
    Node<E> p = h;
    for(int hops = 0; ; ++ hops){
        E item = p.getItem();
        //如果p节点的元素不为空, 使用CAS设置p节点引用的元素为null
        //如果成功返回p节点的元素
        if(item != null && p.casItem(item, null)){
            if(hops >= HOPS){
                //将p节点一个节点设置为head节点
                Node<E> q = p.getNext();
                updateHead(h, (q != null) ? q : p);
            }
            return item;
        }
        //如果头节点元素为空或者头节点发生了变化, 说明头节点已经被另外一个线程修改了
        //那么获取p节点的一个节点
        Node<E> next = succ(p);
        //如果p的下一个节点也为空, 说为这个队列已经空了
        if(next == null){
            //更新头节点
            updateHead(h, p);
            break;
        }
        //如果下一个元素不为空, 则将头节点的一个节点设置为头节点
        p = next;
    }
    return null;
}

//访问的公平性是使用可重入锁实现的
public ArrayBlockingQueue(int capacity, boolean fair){
    if(capacity <= 0){
        throw new IllegalArgumentException();
    }
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull = lock.newConditon();
}

class DelayedItem<T> implements Delayed {
    private T t;
    private long liveTime;      //存活的时间
    private long removeTime;    //设置过期时间
    public DelayedItem(T t, long liveTime){
        this.t = t;
        this.liveTime = liveTime;
        this.removeTime = TimeUnit.NANOSECONDS.convert(liveTime, TimeUnit.NANOSECONDS) + System.nanoTime();
    }
    //返回值大于0表示还在时间以内
    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(removeTime - System.nanoTime(), unit);
    }
    @Override
    @SuppressWarnings("uncheck")
    public int compareTo(Delayed o) {
        if(o == null){
            return 1;
        }
        if(o == this){
            return 0;
        }
        if(o instanceof DelayedItem){
            DelayedItem<T> delayedItem = (DelayedItem<T>)o;
            if(liveTime > delayedItem.liveTime){
                return 1;
            }
            else if (liveTime < delayedItem.liveTime){
                return -1;
            }
            else{
                return 0;
            }
        }
        long diff = getDelay(TimeUnit.NANOSECONDS) - o.getDelay(TimeUnit.NANOSECONDS);
        return diff > 0 ? 1 : ((diff < 0) ? -1 : 0);
    }
    @Override
    public int hashCode(){
        return t.hashCode();
    }
    @Override
    public boolean equals(Object o){
        if(o instanceof DelayedItem){
            return o.hashCode() == this.hashCode();
        }
        return false;
    }
    public T getT(){
        return this.t;
    }
}
class Cache<K, V>{
    public ConcurrentHashMap<K, V> map = new ConcurrentHashMap<>();
    public DelayQueue<DelayedItem<K>> queue = new DelayQueue<>();
    public Cache(K k, V v, long liveTime){
        Thread t = new Thread(){
            @Override
            public void run(){
            }
        };
        t.setDaemon(true);
        t.start();
    }
    public void dameonCheckOverdueKey(){
        for( ; ; ){
            DelayedItem<K> delayedItem = queue.poll();
            if(delayedItem != null){
                map.remove(delayedItem.getT());
                System.out.println(System.nanoTime() + " remove " + delayedItem.getT() + " from  cache");
            }
            try{
                TimeUnit.SECONDS.sleep(1);
            }catch (Exception e){
                e.getStackTrace();
            }
        }
    }
    public void put(K k, V v, long liveTime){
        //put()返回旧值
        V v2 = map.put(k, v);
        DelayedItem<K> tmpItem = new DelayedItem<>(k, liveTime);
        if(v2 != null){
            queue.remove(v2);
        }
        queue.put(tmpItem);
    }
}

private final Condition notFull;
private final Condition notEmpty;
public ArrayBlockingQueue(int capacity, boolean fair){
    //省略其他代码
    notFull = lock.newCondition();
    notEmpty = lock.newCondition();
}
public void put(E e) throws InterruptedException{
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try{
        while(count == items.length){
            notFull.await();
        }
        insert(e);      //插入值, 并且通知notEmpty
    }finally {
        lock.unlock();
    }
}
public E take() throws InterruptedException{
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try{
        while(count == 0){
            notEmpty.await();
        }
        return dequeue();   //返回值, 并且通知notFull
    }finally {
        lock.unlock();
    }
}

package com.myConcurrent.Chapter6;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveTask;
public class CountTask extends RecursiveTask<Integer>{
    private static final int THRESHOLD = 2;     //阈值
    private int start;
    private int end;
    public CountTask(int start, int end){
        this.start = start;
        this.end = end;
    }
    @Override
    protected Integer compute() {
        int sum = 0;
        //如果任务足够小就计算任务
        boolean canCompute = (end - start) <= THRESHOLD;
        if(canCompute){
            for(int i = start; i <= end; ++i){
                sum += i;
            }
        }
        else{
            //任务大于设定的阈值, 分割任务
            int middle = (start + end) / 2;
            CountTask leftTask = new CountTask(start, middle);
            CountTask rightTask = new CountTask(middle + 1, end);
            //执行子任务
            leftTask.fork();
            rightTask.fork();
            //等待子任务执行完毕, 得到其结果
            int leftResult = leftTask.join();
            int rightResult = rightTask.join();
            sum = leftResult + rightResult;
        }
        return sum;
    }
    public static void main(String[] args){
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        CountTask countTask = new CountTask(1, 4);
        Future<Integer> result = forkJoinPool.submit(countTask);
        try{
            System.out.println(result.get());
        }catch (InterruptedException ie){
        }catch (ExecutionException ee){
        }
    }
}

abstract class CarFactory{
    public void showCar(){
        this.name();
        this.location();
    }
    protected abstract void name();
    protected abstract void location();
}
class Benzi extends  CarFactory{
    @Override
    protected void name(){
        System.out.println("benzi");
    }
    @Override
    protected void location(){
        System.out.println("tatou");
    }
}
class Bmw extends  CarFactory{
    @Override
    protected void name(){
        System.out.println("BMW");
    }
    @Override
    protected void location(){
        System.out.println("touta");
    }
}
public class Demo {
    public static void main(String[] args){
        CarFactory carFactory  = new Benzi();
        carFactory.showCar();
        Bmw bmw = new Bmw();
        bmw.showCar();
    }
}

benzi
tatou
BMW
touta

Lock lock = new ReentrantLock();
lock.lock();
try{
}catch(Exception e){
}finally{
    lock.unlock();
}

protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

//独占式获取同步状态, 实现该方法使用CAS方法
protected boolean tryAcquire(int arg)
//独占式释放同步状态
protected boolean tryRelease(int arg)
//共享式获取同步状态, 返回大于等于0的值, 表示获取成功, 反之失败
protected int tryAcquireShared(int arg)
//共享式释放同步状态
protected boolean tryReleaseShared(int arg)
//表示是否被当前线程所独占
protected boolean isHeldExclusively()

//独占式获取同步状态, 
//若当前线程获取成功,返回;
//否则线程进入同步等待队列, 调用可重写的tryAcquire(int)
void acquire(int arg)
//与acquire(int arg)一样, 但是该方法响应中断
//线程未获取锁, 进入同步等待队列, 若被中断, 方法抛出InterruptedException并返回
void acquireInterruptibly(int arg)
//在acquireInterruptibly(int arg)基础上加上超时限制
//线程在时间内获取到同步状态, 返回true, 否则返回false
boolean tryAcquireNanos(int arg, long nanos)
//共享式的获取同步状态
//与独占式的获取主要区别就是同一个时刻可以有多个线程获取到同步状态
void acquireShared(int arg)
//与acquireShared(int)一样, 并且响应中断
void acquireSharedInterruptibly(int arg)
//独占式释放同步状态
//该方法在释放同步状态之后, 还会将同步队列中的第一个节点包含的线程唤醒
boolean release(int arg)
//共享式的释放同步状态
boolean releaseShared(int arg)
//获取等待在同步队列上的线程集合
Collection<Thread> getQueueThreads()

public class MyMutex implements Lock {
    //静态内部类继承AQS
    private static class Sync extends AbstractQueuedSynchronizer{
        @Override
        protected boolean isHeldExclusively(){
            return getState() == 1;
        }
        @Override
        public boolean tryAcquire(int acquire){
            if(compareAndSetState(0, 1)){
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }
        @Override
        protected boolean tryRelease(int release){
            if(getState() == 0){
                throw  new IllegalMonitorStateException();
            }
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }
        Condition newCondition(){
            return new ConditionObject();
        }
    }//结束静态内部类
    //仅需将操作代理到Sync上既可以
    private final Sync sync = new Sync();
    public void lock() { sync.acquire(1); }
    public boolean tryLock() { return sync.tryAcquire(1); }
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return sync.tryAcquireNanos(1, unit.toNanos(time));
    }
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }
    public void unlock() { sync.release(1); }
    public Condition newCondition() { return sync.newCondition(); }
    public boolean isLocked() { return sync.isHeldExclusively(); }
    public boolean hasQueuedThreads(){ return sync.hasQueuedThreads(); }
}

//head和tail是不存线程信息的节点（只用于标识）
private transient volatile Node head;
private transient volatile Node tail;
static final class Node {
        static final Node SHARED = new Node();	//共享式同步状态, 使用同一个节点
        static final Node EXCLUSIVE = null;
        static final int CANCELLED =  1;
        static final int SIGNAL    = -1;
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;
        volatile int waitStatus;
        volatile Node prev;
        volatile Node next;
        volatile Thread thread;
        Node nextWaiter;
        final boolean isShared() {
            return nextWaiter == SHARED;
        }
	
        final Node predecessor() throws NullPointerException {
        //获取当前节点的前驱节点
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }
        Node() {    // Used to establish initial head or SHARED marker
        }
        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }
        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

public final void acquire(int arg){
    if(!tryAcquire(arg) && acquireQueued(Node.EXCLUSIVE, arg)){
        selfInterrupt();
    }
}
private Node addWaiter(Node mode){
    Node node = new Node(Thread.currentThread(), mode);
    //快速尝试在尾部添加节点
    //满足两个条件： 1.尾节点已经存在 2.没有线程竞争出现导致的问题
    Node pred = tail;
    if(pred != null){
        node.prev = pred;
        if(compareAndSetTail(pred, tail)){
            pred.next = node;
            return node;
        }
    }
    enq(node);
    return node;
}
//返回的并非新建尾节点, 而是旧的尾节点
//通过"死循环", 完成线程安全的正确设置尾节点
private Node enq(final Node node){
    for( ; ;){
        Node t = tail;
        if(t == null){
            if(compareAndSetTail(new Node())){
                tail = node;
            }
        }
        else{
            node.prev = t;
            if(compareAndSetTail(t, node)){
                t.next = node;
                return t;
            }
        }
    }
}
//每个节点(线程)在同步队列中不断地自省观察
//条件满足, 获取同步状态; 否则, 自旋并阻塞节点(线程)
final boolean acquireQueued(final Node node, int arg){
    boolean failed = true;
    try{
        boolean interrupted = false;
        for( ; ; ){
            //获取当前node的前一节点p
            //如果前驱节点是头节点, 并且满足自定义的tryAcquire条件
            //那么获取同步状态成功, 否则继续自旋, 自旋的同时判断是否有阻塞和中断信
            final Node p = node.predecessor();
            if(p == head && tryAcquire(arg)){
                setHead(node);
                p.next = null;
                failed = false;
                return interrupted;
            }
            //shouldParkAfterFailedAcquire()方法
            //Checks and updates status for a node that failed to acquire.
            //Returns true if thread should block. This is the main signal
            //control in all acquire loops.
            if(shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()){
                interrupted = true;
            }
        }
    }finally {
        //不能从自旋中获取同步状态
        if(failed){
            //Cancels an ongoing attempt to acquire.
            //取消尝试获取同步锁
            cancelAcquire(node);
        }
    }
}
public final boolean release(int arg){
    //从自定义的释放锁中返回
    if(tryRealease(arg)){
        Node h = head;
        //waitStatus == 0 标识初始状态.
        if(h != null && h.waitStatus != 0){
            unparkSuccessor(h);     //Wakes up node's successor, if one exists.
        }
        return true;
    }
    return false;
}

//共享式同步状态的获取和释放
public final void acqurireShared(int arg){
    //要求自定义的tryAcquireShared
    //第一次获取不到同步状态, 进入死循环获取同步状态
    if(tryAcqureShared(arg) < 0){
        doAcquireShared(arg);
    }
}
/*
 *  tryAcquireShared在返回 >= 0时, 表示能够获取到同步状态
 *  自旋过程中, 如果当前节点的前驱节点为头节点, 尝试获取同步状态, 返回值 >= 0, 成功
 */
private void doAcquireShared(int arg){
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try{
        boolean interrupted = false;
        for( ; ; ){
            final Node p = node.predecessor();
            if(p == head){
                int r = tryAcquireShared(arg);
                if(r >= 0){
                    setHeadAndPropagate(node, r);
                    p.next = null;
                    if(interrupted){
                        selfInterrupt();
                    }
                    failed = false;
                    return;
                }
            }
            if(shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()){
                interrupted = true;
            }
        }
    }finally {
        if(failed){
            cancelAcquire(node);
        }
    }
}
/*
 *  该方法在释放同步状态之后, 将会唤醒后续处于等待状态的节点.
 *  tryReleaseShared方法必须保证同步状态线程安全地释放, 一般通过循环和CAS保证
 *  因为释放共享同步状态的操作会来自多个线程
 */    
public final boolean releaseShared(int arg){
    if(tryReleaseShared(arg)){
        doReleaseShared();
        return true;
    }
    return false;
}

private boolean doAcquireNanos(int arg, long nanosTimeout) throws InterruptedException{
    long lastTime = System.nanoTime();
    final Node node = addWaiter(Node.EXCLUSIVE);
    boolean failed = true;
    try{
        for( ; ; ){
            final Node p = node.predecessor();
            if(p == head && tryAcquire(arg)){
                setHead(node);
                p.next = null;
                failed = false;
                return true;
            }
            //超时返回false
            if(nanosTimeout <= 0){
                return false;
            }
            //超时等待时间 > threshold(1000ns), 进入超时等待状态
            //否则, 按照进入快速自旋过程
            if(shouldParkAfterFailedAcquire(p, node) && nanosTimeout > spinForTimeoutThreshold){
                LockSupport.parkNanos(this, nanosTimeout);
            }
            //计算nanosTimeout剩余的睡眠时间
            long now = System.nanoTime();
            nanosTimeout -= now - lastTime;
            lastTime = now;
            if(Thread.interrupted()){
                throw new InterruptedException();
            }
        }
    }finally {
        if(failed){
            cancelAcquire(node);
        }
    }
}

//ReentrantLock获取锁的非公平方法
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState(); //获取当前锁的状态, [计数值]
    //该锁第一次被获取, 只要CAS成功即可获取锁
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    //判断是否, 当前线程已经获取锁, 并再次想获取该锁
    //如果锁已被其他线程锁占有, 当前线程并不能获取锁资源, 返回false
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) {
            throw new Error("Maximum lock count exceeded");
        }
        setState(nextc);
        return true;
    }
    return false;
}
//公平方法, 线程对于同步状态的获取是基于FIFO的
protected final boolean tryAcquire(int acquires){
    final Thread current = Thread.currentThread();
    int c = getState();
    if(c == 0){
        //hasQueuedPredecessors()方法, 同步队列中当前节点是否有前驱节点的判断
        //返回true, 表示有线程比该线程很早请求锁, 没有遵守FIFO规则
        //因此需要等待前面的线程获取并释放锁, 该线程才能获取
        if(!hasQueuedPredecessors() && compareAndSetState(0, acquires)){
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if(current == Thread.currentThread()){
        int nextc = c + acquires;
        if(nextc < 0){
            throw new Error("maximum lock count exceeded");
        }
        setState(nextc);
        return true;
    }
    return false;
}
//ReentrantLock的tryRelease方法
protected final boolean tryRealease(int releases){
    int c = getState() - releases;
    //当前线程并没有占有ReentrantLock, 但是尝试释放该锁, 会抛出异常
    if(Thread.currentThread() != getExclusiveOwnerThread()){
        throw new IllegalMonitorStateException();
    }
    boolean free = false;
    //当锁计数为0的, 没有线程占有该锁了
    if(c == 0){
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

/*
 * 当 读写锁中有读锁, 那么写锁不能被获取
 * 原因： 读写锁要确保写锁的操作对读锁可见,
 *       只有当所有的读线程释放了锁, 写锁才可以被当前线程获取
 *       一旦写锁被获取, 其他读写线程的后续访问都被阻塞
 */
protected final boolean tryAcqure(int acquires){
    Thread current = Thread.currentThread();
    int c = getState();
    int w = exclusiveCount(c);  //返回值为写锁的状态
    if(c != 0){
        //c != 0 && w == 0 写锁不存在, 但存在读锁; 或者出现了线程竞争
        if(w == 0 || current != Thread.currentThread()){
            return false;
        }
        if(w + exclusiveCount(acquires) > MAX_COUNT){
            throw new Error("Maximum lock count exceeded");
        }
        setState(c + acquires);
        return true;
    }
    //出现了需要阻塞写线程的情况
    if(writerShouldBlock() || !compareAndSetState(c, c+acquires)){
        return false;
    }
    //c == 0, 读写锁未被占有
    setExclusiveOwnerThread(current);
    return true;
}
protected final boolean tryRelease(int releases){
    int c = getState() - releases;
    if(Thread.currentThread() != getExclusiveOwnerThread()){
        throw  new IllegalMonitorStateException();
    }
    boolean free = false;
    // c == 0 返回 true
    // 表示没有写锁(并且已知没有读锁), 所以目前读写锁没有被获取
    if(c == 0){
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

protected final int tryAcqureShared(int unused){
    for( ; ; ){
        int c = getState();
        int nextc = c + (1 << 16);
        if(nextc < c){
            throw new Error("Maximum lock count exceeded");
        }
        //写锁存在或者出现线程竞争
        if(exclusiveCount(c) != 0 || owner != Thread.currentThread()){
            return -1;
        }
        if(compareAndSetState(c, nextc)){
            return 1;
        }
    }
}

public void processData(){
    readLock.lock();	//这里的readLock和writeLock应该要是同一把锁，分开是易于标识
    // update 是一个volatile修饰的boolean变量
    // 此时所有访问processData()方法的线程都能够感知到变化,
    // 但是只有一个线程能够获取到写锁, 其他线程的读写状态获取均被阻塞
    if(!update){
        //必须先释放读锁, 锁降级从写锁的获取开始
        readLock.unlock();	// 1
        writeLock.lock();		// 2 .   1和2操作可以设置为原子操作
        try{
            if(!update){
                //准备数据的流程(略)
                //现在数据被更新了
                update = true;
            }
            // 获取读锁, 但肯定会被阻塞
            // 目的在于在释放写锁的那一刹那, 不让其他线程获取到写锁
            readLock.lock();
        }finally {
            writeLock.unlock();
        }
    }
    try{
        //使用数据的流程(略)
    }finally {
        readLock.unlock();
    }
}

public final void await() throws InterruptedException{
    if(Thread.interrupted()){
        throw  new InterruptedException();
    }
    //当前线程加入等待队列
    Node node = addConditionWaiter();
    //当前线程从同步队列中释放, 即当前线程释放了锁
    int savedState = fullyRelease(node);
    int interruptMode = 0;
    // isOnSyncQueue 当线程在不在同步队列中, 返回false，循环
    //               一旦返回true(线程从等待队列移到同步队列), 或者被打断
    //               线程从等待队列中移除
    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){
        unlinkCancelledWaiters();    // Unlinks cancelled waiter nodes from condition queue
    }
    if(interruptMode != 0){
        reportInterruptAfterWait(interruptMode);
    }
}

  //被唤醒的线程可以从await()返回, 此时该线程已经成功地获取了锁	
//调用signal方法会唤醒等待队列中等待时间最长的节点(首节点)
//在唤醒节点之前, 会将节点移到同步队列的队尾
public final void signal(){
    //节点从等待队列移到同步队列的前置条件是
    //当前线程必须获取到了锁
    if(!isHeldExclusively){
        throw new IllegalMonitorStateException();
    }
    Node first = firstWaiter;
    if(first != null){
        doSignal(first);
    }
  
}

import java.util.concurrent.TimeUnit;
public class Daemon {
    static class DaemonRunner implements Runnable{
        @Override
        public void run(){
            try{
                TimeUnit.SECONDS.sleep(3);
            }catch (Exception e){
            }finally {
                System.out.println("finally in run()");
            }
        }
    }
    public static void main(String[] args) throws Exception{
        Thread t = new Thread(new DaemonRunner(), "...");
        //将main线程作为自己的守护线程
        t.setDaemon(true);
        t.start();
        //main线程退出, java虚拟中没有非Daemon线程, 虚拟机退出
        //DaemonRunner中的finally没有被执行.
        //下面t.join()可让finnally块执行
        //在main线程调用了t的join, 那么main线程就要等待t结束, 才能执行后续代码
//        t.join();
//        System.out.println("shit");
    }
}

private void init(ThreadGroup g, Runnable target, String name, long stackSize, AccessControlContext acc){
       if(name == null){
           throw new NullPointerException("name connot be null");
       }
       //当前线程就是新建线程的父线程
       Thread parent = Thread.currentThread();
       this.group = g;
       this.target = target;
       tid = nextThreadID();   //分配一个线程ID
       //将daemon, priority属性设置为父线程的对应属性
       this.daemon = parent.isDaemon();
       this.priority = parent.getPriority();
   }

import java.util.concurrent.TimeUnit;
public class ShutDown {
    private static class Runner implements Runnable{
        private long i;
        private volatile boolean on = true;
        public void cancel(){
            on = false;
        }
        @Override
        public void run(){
            while( on && !Thread.currentThread().isInterrupted()){
                ++i;
            }
            System.out.println("Count i: " + i);
        }
    }
    public static void main(String[] args) throws Exception{
        Runner r1 = new Runner();
        Runner r2 = new Runner();
        Thread thread1 = new Thread(r1, "countThread1");
        Thread thread2 = new Thread(r2, "countThread2");
        //main线程睡眠1秒, 然后对thread1进行中断, 使得thread1可以感知中断而结束
        thread1.start();
        TimeUnit.SECONDS.sleep(1);
        thread1.interrupt();
        //main线程睡眠1秒, 然后thread2调用cancel(), 使得thread2可以感知 on == false而结束
        thread2.start();
        TimeUnit.SECONDS.sleep(1);
        r2.cancel();
    }
}

class Pikaqiu{
    public synchronized void n(){
    }
}
public class SynchronizedLock {
    private static Pikaqiu pikaqiu = new Pikaqiu();
    public static void main(String []args){
        //普通同步方法, 锁的对象是实例对象
        pikaqiu.n();
        //静态同步方法, 锁的对象是 SynchronizedLock Class类
        m();
        //同步方法块, 锁的对象是括号里的 Pikaqiu Class类
        synchronized (Pikaqiu.class){
        }
        //同步方法块, 锁的对象是括号里的实例对象
        synchronized (pikaqiu){
        }
    }
    public static synchronized void m(){
    }
}

synchronized(对象){
	while(条件不满足){
		对象.wait()；
	}
	后续的逻辑处理；
}

synchronized(对象){
	改变条件；
	对象.notifyAll()；
}

import java.io.IOException;
import java.io.PipedReader;
import java.io.PipedWriter;
public class Piped {
    public static void main(String []args) throws Exception{
        PipedWriter out = new PipedWriter();
        PipedReader in = new PipedReader();
        //将输出和输入的流进行连接, 否则在使用时会抛出IOException
        out.connect(in);
        Thread thread = new Thread(new Print(in), "PrintThread");
        thread.start();
        int receive = 0;
        try{
            while((receive = System.in.read()) != -1){
                out.write(receive);
            }
        }catch (IOException ioe){
        }finally {
            out.close();
        }
    }
    static class Print implements Runnable{
        private PipedReader in;
        public Print(PipedReader in){
            this.in = in;
        }
        @Override
        public void run(){
            int receive = 0;
            try{
                while((receive = in.read()) != -1){
                    System.out.print((char)receive);
                }
            }catch (IOException ioe){
            }
        }
    }
}

import java.util.concurrent.TimeUnit;
public class Profiler {
    private static ThreadLocal<Long> threadLocal = new ThreadLocal<>();
    public static void begin(){
        threadLocal.set(System.currentTimeMillis());
    }
    public static Long end(){
        return System.currentTimeMillis() - threadLocal.get();
    }
    public static void main(String[] args) throws Exception{
        Profiler.begin();
        TimeUnit.SECONDS.sleep(1);
        System.out.println("cost: " + Profiler.end() + "mills");
    }
}

import java.util.concurrent.TimeUnit;
public class Join {
    static class Catalina implements Runnable{
        private Thread thread;
        public Catalina(Thread thread){
            this.thread = thread;
        }
        @Override
        public void run(){
            try{
                thread.join();
            }catch (InterruptedException e){
                e.getMessage();
            }
            System.out.println(Thread.currentThread().getName() + "terminate.");
        }
    }
    public static void main(String[] args) throws Exception{
        System.out.println("Start main");
        Thread previous = Thread.currentThread();
        for(int i = 0; i < 10; ++i){
            //每个线程拥有上一个线程的一个引用, 需要等待上一个线程的终止, 才能从等待中返回
            Thread thread = new Thread(new Catalina(previous), "Thread(" + i + ")");
            thread.start();
            previous = thread;
        }
        TimeUnit.SECONDS.sleep(2);
        System.out.println("Thread: " + Thread.currentThread().getName());
    }
}

public class FinalTest {
    int i;
    final int j;
    static FinalTest obj;
    
    public FinalTest(){             //构造函数
        i = 1;                      //写普通域
        j = 2;                      //写final域
    }
    
    public static void writer(){    //写线程A的执行
        obj = new FinalTest();   
    }
    
    public static void reader(){    //读线程B的执行
        FinalTest object = obj;     //读对象的引用
        int a = object.i;           //读普通域
        int b = object.j;           //读final域
    }
    
}

public class FinalTest {
    final int i;
    static FinalTest obj;
    public FinalTest(){             //构造函数
        i = 1;                      //1 写final域, 此时初始化未完成
        obj = this;                 //2 this引用在此"溢出"
    }
    public static void writer(){
        new FinalTest();
    }
    public static void reader(){
        if(obj != null){            //3 由于"溢出"(obj != null)
            int t = obj.i;          //4 读取未被初始化i
        }
    }
}

class Instance{
}
public class SafeDoubleCheckedLocking {                     //1
    private volatile static Instance instance;              //2
    public static Instance getInstance(){                   //3
        if(instance == null){                               //4 第一次检查
            synchronized (SafeDoubleCheckedLocking.class){  //5 加锁
                if(instance == null){                       //6 第二次检查
                    instance = new Instance();              //7 可能会出现问题的地方
                }
            }
        }
        return instance;
    }
}

instance = new Instance();
//新建一个对象Instance可分解为如下三行伪代码
memory = allocate();	//1 分配对象的内存空间
ctorInstance(memory);	//2 初始化对象
instance = memory;	    //3 设置Instance指向分配的空间

public class Solution {
    private int movingCountHelper(int threshold, int rows, int cols, boolean []isVisited, int i, int j){
		int pos = i * cols + j;
        if(i < 0 || i >= rows || j < 0 || j >= cols || isVisited[pos] || !isSafe(threshold, i, j)){
            return 0;
        }
        isVisited[pos] = true;
        return 1 + movingCountHelper(threshold, rows, cols, isVisited, i, j-1) 
            	 + movingCountHelper(threshold, rows, cols, isVisited, i, j+1) 
            	 + movingCountHelper(threshold, rows, cols, isVisited, i+1, j) 
            	 + movingCountHelper(threshold, rows, cols, isVisited, i-1, j);
    }
    
    private boolean isSafe(int threshold, int x, int y){
		int sum = 0;
        while(x != 0){
			sum += (x % 10);
            x /= 10;
        }
        while(y != 0){
            sum += (y % 10);
            y /= 10;
        }
        return sum > threshold ? false : true;
    }
        
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean []isVisited = new boolean[rows * cols];
        return movingCountHelper(threshold, rows, cols, isVisited, 0, 0);
    }
    
}