Java Concurrency

Intrinsic Lock: 通过 synchronized关键字实现， 非公平锁
Explicit Lock: 通过java.concurrent.locks.Lock接口的实现类（如java.concurrent.locks.ReentrantLock类）实现，既支持公平锁又支持非公平锁

ReentrantLock lock = new ReentrantLock(boolean fair) // true 表示公平锁 (默认是非公平调度)
 
锁的获得隐含着刷新处理器缓存这个动作 load from memory to cache
锁的释放隐含着冲刷处理器缓存这个动作 flush cache to memory

内存重排 ，英文为 Memory Reordering 

Reentrancy： ：一个线程在其持有一个锁的时候能否再次（或者多次）申请该锁
              如果一个线程持有一个锁的时候还能够继续成功申请该锁，那么我们就称该锁是可重入的（Reentrant），否则我们就称该锁为非可重入的（Non-reentrant）

任何一个对象都有唯一一个与之关联的锁。这种锁被称为 监视器（Monitor）或者内部锁（Intrinsic Lock）

volatile 使用场景:
1. 使用volatile变量作为状态标志。在该场景中，应用程序的某个状态由一个线程设置，其他线程会读取该状态并以该状态作为其计算的依据.
2. 使用volatile保障可见性。在该场景中，多个线程共享一个可变状态变量，其中一个线程更新了该变量之后，其他线程在无须加锁的情况下也能够看到该更新.
3. 使用volatile变量替代锁。volatile关键字并非锁的替代品，但是在一定的条件下它比锁更合适（性能开销小、代码简单)

caveat: volatile关键字只能够对数组引用本身的操作起作用，而无法对数组元素的操作（读取、更新数组元素）起作用。
        如果要使对数组元素的读、写操作也能触发volatile关键字的作用，可以使用AtomicIntegerArray 、AtomicLongArray 和 AtomicReferenceArray。

AtomicReference 对引用型变量的有条件更新：更新引用变量时确保该变量的确是我们要修改的那个，即该变量没有被其他线程修改过。

一个线程只有在持有一个object的内部锁的情况下才能够调用该object的wait方法，因此Object.wait()调用总是放在相应对象所引导的临界区之中。包含上
述模板代码的方法被称为受保护方法（Guarded Method）
由于同一个对象的同一个方法（someObject.wait()）可以被多个线程执行，因此一个对象可能存在多个等待线程

synchronized(someObject){
  while（保护条件不成立）{
    someObject.wait(); // 调用Object.wait()暂停当前线程, 释放someObject 对应的内部锁
  }
  // 代码执行到这里说明保护条件已经满足
  // 执行目标动作
  doAction();
}

synchronized(someObject){
  updateSharedState()； // 更新等待线程的保护条件涉及的共享变量
  someObject.notify(); // 唤醒其他线程  只有在持有一个对象的内部锁的情况下才能够执行该对象的notify方法
}

Object.notify()调用所在的临界区代码执行结束后才会被释放，而Object.notify()本身并不会将这个内部锁释放. 一般尽可能地将Object.notify()调用放在靠近临界区结束
的地方


java.util.concurent.locks.Condition: Condition接口可作为wait/notify的替代品来实现等待/通知, 可解决过早唤醒问题, 并解决了Object.wait(long)不能区分其返回是否是由等待超时而
导致的问题。

Condition实例也被称为条件变量（Condition Variable）或者条件队列（Condition Queue）
每个Condition实例内部都维护了一个存储等待线程的队列
cond1.signal() 会使cond1 的等待队列中的一个任意线程被唤醒。
cond1.signalAll()会使cond1的等待队列中的所有线程被唤醒，

private final Lock lock = new ReentrantLock();
private final Condition condition1 = lock.newCondition(); // condition1 由显示lock产生
private final Condition condition2 = lock.newCondition(); // 同一个lock 可以产生多个conditions 用于精确唤醒 (每个thread的保护条件不一样)

lock.lock();
try {
  while （保护条件不成立） {
    condition.await();
  }
  doAction(); // 执行目标动作
} finally {
  lock.unlock();
}

lock.lock();
try {
  changeState();   // 更新共享变量
  condition.signal();
} finally {
  lock.unlock();
}

Condition.awaitUntil (Date deadline) 返回true 表示未到最后期限


CountdownLatch: 当需要等待其他线程执行的特定操作结束即可，而不必等待这些线程终止

Blocking Queue vs Non-blocking Queue
Blocking Queue: threads need to wait for the queue's availability. Producer waits for available space, Consumer waits for available item.
Non-blocking Queue: threads don't wait because queue throws an exception or returns a special value (null or false)

Blocking:
ArrayBlockingQueue: bounded queue, has a fixed size,  a single lock for put and take.  Underlying is an array
LinkedBlockingQueue: unbounded queue (Integer.MAX_VALUE), can set capacity, put and take have separate lock. Underlying is linked list
PriorityBlockingQueue: take operation can occur simultaneously with the put operation (uses spinlock)
DelayQueue: leader thread + conditional variable + PriorityQueue + sleep.

Non-blocking:
ConcurrentLinkedQueue: add and poll are guaranteed to be thread-safe and return immediately, uses CAS instead of lock
========= 

Spinlock: 当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环
          (1) 自旋锁不会使线程状态发生切换，一直处于用户态，即线程一直active；不会使线程进入阻塞状态，减少了不必要的上下文切换，执行速度快
          (2) 非自旋锁在获取不到锁的时候会进入阻塞状态，从而进入内核态，当获取到锁的时候需要从内核态恢复，需要线程上下文切换。
              (线程被阻塞后便进入内核（Linux）调度状态，这个会导致系统在用户态与内核态之间来回切换，严重影响锁的性能）


// java 中的 Threadpool
ExecutorService executorService = Executors.newFixedThreadPool(10); // set up a thread pool with 10 threads.
Future<String> future = executorService.submit(() -> "Hello World");
String result = future.get(); // wait for task to complete

==========
java concurrent 库中经常见到如下写法
public void someMethod() {
   final ReentrantLock lock = this.lock;
   lock.lock();
   ...
}

为什么要这样做呢？

原因一 为了加快访问速度；
将全局变量赋值给方法的一个局部变量，访问的时候直接在线程栈里面取，比访问成员变量速度要快，读取栈里面的变量只需要一条指令，读取成员变量则需要两条指令；

原因二 为了安全；
如果只是为了访问速度快，那么直接使用一个普通的局部变量即可，不需要加final，加了final原因就是为了多线程下的线程安全。
final的作用，一经初始化就无法被更改，并且保证对象访问的内存重排序，保证对象的可见性，更详细内容见这里 
————————————————
CAS存在的缺点:

（1）只能保证一个共享变量的原子性
CAS不像synchronized和RetranLock一样可以保证一段代码和多个变量的同步。对于多个共享变量操作是CAS是无法保证的，这时候必须使用加锁来是实现。

（2）存在性能开销问题
由于CAS是一个自旋操作，如果长时间的CAS不成功会给CPU带来很大的开销。

（3）ABA问题
因为CAS是通过检查值有没有发生改变来保证原子性的，假若一个变量V的值为A，线程1和线程2同时都读取到了这个变量的值A，此时线程1将V的值改为了B，然后又改回了A，期间线程2一直没有抢到CPU时间片。知道线程1将V的值改回A后线程2才得到执行。那么此时，线程2并不知道V的值曾经改变过。这个问题就被成为ABA问题。
ABA问题的解决其实也容易处理，即添加一个版本号，更次更新值同时也更新版本号即可。上文中提到的AtomicStampedReference就是用来解决ABA问题的。

链接：https://juejin.cn/post/6977993272538955806
---------------------
Semaphore: We can use semaphores to limit the number of concurrent threads accessing a specific resource.
constructors:  
    Semaphore(int num)
    Semaphore(int num, boolean isFair) // permit is released to the thread that has been waiting for longest time.
how to use:
    semaphore.acquire() // try to acquire the permit
    semaphore.release()
    
    semaphore.acquire(int permits)
    semaphore.release(int permits) 

Conditional Variable:
    Lock lock = new ReentrantLock();
    Condition cv = lock.newCondition();
    cv.await();    // is always used with lock.lock()/unlock()  判断条件要被lock保护起来，不然会被提前signal而无穷等待, 详见：https://zhuanlan.zhihu.com/p/55123862
    cv.signal(); cv.signalAll();

The signal() method must not be used unless all of these conditions are met:
   (1) The Condition object is identical for each waiting thread.
   (2) All threads must perform the same set of operations after waking up, which means that any one thread can be selected to wake up and resume for a single invocation of signal().
   (3) Only one thread is required to wake upon receiving the signal.
or all of these conditions are met:
   (1) Each thread uses a unique Condition object.
   (2) Each Condition object is associated with the same Lock object.
When used securely, the signal() method has better performance than signalAll().

signalAll() is a method specific to a Condition, whereas notifyAll() is done on any object you're locking on.
signalAll() should be used when you're waiting/sleeping with Condition.await(), and notifyAll() when you're using Object.wait() inside a synchronized block.

One of the drawback of using Future is that you either need to periodically check whether task is completed or not 
e.g. by using isDone() method or wait until task is completed by calling blocking get() method. 
There is no way to receive the notification when task is completed. 
This shortcoming is addressed in CompletableFture, which allows you to schedule some execution when the task is done. 
CompletableFuture class is introduced in Java 8 and you can perform some task when Future reaches completion stage
Read more: https://javarevisited.blogspot.com/2015/01/how-to-use-future-and-futuretask-in-Java.html#ixzz6rxGbLU9c


[Notes from daily work]:
1. concurrent set allows concurrent iteration (In other words, it can safely iterate while other thread is attempting to modify this set)

[reference]: 
基础篇： http://www.10tiao.com/html/689/201804/2651581230/1.html
晋级篇： https://blog.csdn.net/gitchat/article/details/79983445
高级篇1：http://www.10tiao.com/html/689/201805/2651581519/1.html
高级篇2：http://gitbook.cn/books/5ac70a26d60a134e37dafdd7/index.html
高级篇3：https://blog.csdn.net/valada/article/details/79910098
/****************************************************************************************************************/
1. 堆是一个进程中最大的一块内存，堆是被进程中的所有线程共享的，是进程创建时候分配的，堆里面主要存放使用 new 操作创建的对象实例.
2. 方法区则是用来存放进程中的代码片段的，是线程共享的.
3. Java 中有三种线程创建方法，分别为
    (1)实现 Runnable 接口的runnable method;   // no return value
    (2)继承 Thread 类并重写 run 方法;          // no return value
    (3)使用 FutureTask 方式.                 // allows to return value
   //创任务类，类似Runable
   public static class CallerTask implements Callable<String>{        
        @Override
        public String call() throws Exception {            
            return "hello";
        }
    }  
    public static void main(String[] args) throws InterruptedException {    
        FutureTask<String> futureTask  = new FutureTask<>(new CallerTask());  // 创建异步任务      
        new Thread(futureTask).start();       //启动线程 
        try {          
            String result = futureTask.get(); //等待任务执行完毕，并返回结果
            System.out.println(result);
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
4. wait() method:
   当一个线程调用一个共享对象的 wait() 方法时候，调用线程会被阻塞挂起，直到下面几个事情之一发生才返回：
    (1)其它线程调用了该共享对象的 notify() 或者 notifyAll() 方法；
    (2)其它线程调用了该线程的 interrupt() 方法设置了该线程的中断标志，该线程会抛出 InterruptedException 异常返回
    [thread interrupted() 和 isInterrupted()的区别]:
         interrupted()除了返回中断标记之外，它还会清除中断标记(即将中断标记设为false);
         isInterrupted()仅仅返回中断标记;
         也就是说，调用interrupted()这个函数时，中断标记会暂时变为true，然后被清楚变为false.
         
5. spurious wakeup 虚假唤醒
   如果线程没有被其它线程调用 { notify(), notifyAll(),或者被中断，或者等待超时 } 而被唤醒，这种唤醒称为spurious wakup
   [防范 spurious wakeup]:
     用一个loop不停的去测试该线程被唤醒的条件是否满足，不满足则继续等待：
     synchronized (obj) {       // 注意这个obj通常采用private final修饰，不能改变: private final Object lock = new Object();
        while (条件不满足){
           obj.wait();  
        }
     }
6. void notify() method:
   会唤醒一个在该共享变量上调用 wait 系列方法后被挂起的线程，一个共享变量上可能会有多个线程在等待，具体唤醒哪一个等待的线程是随机的。
   void notifyAll() method:
   会唤醒所有在该共享变量上由于调用 wait 系列方法而被挂起的线程。
   [notify 和 notifyAll()的区别]:
       (1) 唤醒不等于执行，唤醒 -> 得到monitor -> 执行。 
       (2) 例如：thead1, thread2 都调用了obj.wait()将自己阻塞， thread3处于active的状态。
           如果调用 obj.notify(), 假如thread1被唤醒，并得到monitor后执行完毕。即使thread1执行完释放monitor，thread2仍阻塞，因为它没被唤醒
           如果调用 obj.notifyAll(), thread1和thread2都被唤醒。thread1先拿到monitor执行结束后，thread2会接着拿到monitor继续执行。

7. join() method:
   阻塞自己，等到某些thread执行完毕，才能继续往下执行
   thread1.join(); // 等待thread1执行完毕后，该线程才能执行
/****************************************************************************************************************/
1. 共享变量(shared variables)的内存不可见问题(Visibility failures)
                   Thead A         |       Thead B
             ----------------------|------------------------
                 Control Unit      |     Control Unit
                     ALU           |        ALU
                   L1 Cache        |      L1 Cache
             ----------------------|------------------------
                              L2 Cache(shared)
             -----------------------------------------------
                         Main Memory (shared variables)
             -----------------------------------------------
    Concept: 线程的工作内存 = Registers + L1 Cache + L2 Cache
    Example: 假设线程  A和 B 使用不同 CPU 进行去修改共享变量 X，假设 X 的初始化为0，并且当前两级 Cache 都为空的情况，具体看下面分析:
            (1)假设线程 A 首先获取共享变量 X，由于两级Cache都没有命中，所以到主内存加载了X=0，然后会把X=0的值缓存到两级缓存，假设线程 A 修改 X=1, 写入到两级 Cache，并且刷新到主内存（注：如果没刷新会主内存也会存在内存不可见问题）。
            (2)这时候线程 A 所在的 CPU 的两级 Cache 内和主内存里面 X 的值都是1；
            (3)然后假设线程 B 这时候获取 X 的值，首先一级缓存没有命中，然后看二级缓存，二级缓存命中了，所以返回 X=1；然后线程 B 修改 X 的值为2；然后存放到线程2所在的一级 Cache 和共享二级 Cache，最后更新主内存值为2；
            (4)然后假设线程 A 这次又需要修改 X 的值，获取时候一级缓存命中获取 X=1，到这里问题就出现了，明明线程 B 已经把 X 的值修改为了2，为啥线程 A 获取的还是1呢？
            这就是共享变量的内存不可见问题，也就是线程 B 写入的值对线程 A 不可见.
            
2. Synchronized:
   Synchronized块是Java提供的一种原子性内置锁, Java中每个对象都可以当做一个同步锁的功能来使用. 这些 Java 内置的使用者看不到的锁被称为内部锁, 也叫做监视器锁(monitor)
   Synchronized块释放锁的3种情形：
   (1) 正常退出同步代码块
   (2) 异常抛出后
   (3) 同步块内调用了该内置锁资源的 wait() 方法
   
   Synchronized 如何解决内存不可见的？
   (1) 线程进入Synchronized块, 会把Synchronized块内用到的变量从线程的工作内存中清除，当使用该变量时候就不会从线程的工作内存中获取了，而是直接从主内存中获取；
   (2) 退出Synchronized块时, 会把 Synchronized 块内对共享变量的修改刷新到主内存;
   
   remark: Synchronized 关键字会引起线程上下文切换和线程调度的开销; Synchronized 可以解决内存不可见问题 和 实现原子性操作
   
   对于Synchronized，Java中的每个对象都可以作为锁，具体有以下3种形式：
   (1) synchronized 普通 method, 锁是当前instance对象
   (2) synchronized static method, 锁是当前类Class对象
   (3) synchronized 代码块, 锁是Synchronized括号里配置的对象
   (4) synchronized 代码块, 比如 synchronized (PersonService.class)形式, 锁是Synchronized括号里class的所有对象
   
3. Volatile:
   一旦一个变量被 volatile 修饰了，当线程获取这个变量值的时候会首先清空线程工作内存中该变量的值，然后从主内存获取该变量的值；

4. sleep 和 wait的异同：
   相同点：sleep和wait都释放出cpu的使用权
   不同点：sleep不释放锁，而wait释放锁，使得其他线程可以使用同步方法或者同步控制块
          wait，notify和notifyAll只能在同步控制方法或者同步控制块里面使用，而sleep可以在任何地方使用（使用范围）

5. 什么是伪共享,为何会出现，以及如何避免
6. 什么是可重入锁、乐观锁、悲观锁、公平锁、非公平锁、独占锁、共享锁。
7. Reentrant Lock 和 Syncronized 的区别

/****************************************************************************************************
*                            《Java 并发编程实战》                                                     *
*****************************************************************************************************/
第2章 线程安全性：
 1. 无状态对象（stateless）一定是线程安全的
 2. compound operation：比如 “读取-修改-写入”，再比如“先检查后执行”
 3. 要保证状态的一致性，就需要在单个原子操作中更新所有相关的状态变量
 4. Java 内置锁：同步代码块（synchronized block）= 锁的对象引用 + 锁保护的代码块
    每个Java对象都可以作为锁， 被称为 monitor lock 或 intrinsic lock
 5. 重入
    Java 内置锁是可重入的。如果一个线程试图获得一个已经由它自己持有的锁，那么请求会成功。
    “重入” 意味着获取锁的颗粒度是thread而不是invoke，每个锁关联着计数值和所有者线程。 同一个线程再次获得锁，计数值递增；当线程退出同步代码块时，计数值递减，当等于0时，释放锁
 6. 在执行时间较长的计算或操作时（例如：网络I/O，操作台I/O）， 一定不要持有锁
 
第3章 对象的共享
  1. 可见性（memory visibility）: 确保多个线程对写入操作的结果是可见的，必须使用同步机制
  2. 重排序（reordering）: 在没有同步时，编译器、处理器可能对执行的顺序进行意想不到的调整
  3. 非原子的64位操作: JVM 允许将64位的读写操作拆成两个32位的操作。如果对64位的读写操作分别在两个线程中，则会读到某个值的高32位和另一个值的低32位
  4. 访问volatile变量不会执行加锁操作，也不会线程阻塞，所以是比synchronized更轻量级的同步机制
  5. 加锁的含义不局限于互斥，还包括内存可见性。为确保所有线程看到共享变量的最新值，所有执行读写操作的线程都必须在同一个锁上同步
  6. 加锁既可以确保可见性，又可以确保原子性。 而volatile只能保证可见性
     当前仅当满足以下所有条件时，才应该使用volatile变量：
     (1)变量写入操作不依赖变量的当前值
     (2)该变量不会和其他状态变量纳入不变性条件
     (3)访问变量时不需要加锁
  7. Publish(发布): 是对象可以在当前作用域之外的代码块使用
     Escape(逸出): 当某个不应该发布的对象被发布
     
/****************************************************************************************************
*                            《Java 并发编程艺术》                                                     *
*****************************************************************************************************/
1. Context Switch 测量工具：
   （1）Lmbench3可以上下文切换的时长；
   （2）vmstat可以测量上下文切换的次数；
   
2. Java的对象头
    synchronize 用的锁是存在Java对象头里的。
    <1> 数组类型，JVM用3个字长（word）存储对象头 (Mark Word, Class Metadata Address, ArrayLength)
    <2> 非数组类型，JVM用2个字长(word)存储对象头 (Mark Word, Class Metadata Address)
    
    Mark Word 存储：(1)HashCode, (2)分代年龄, (3)锁标记位
    
3. 锁的升级
   无锁状态 --> 偏向锁状态(Biased Lock) --> 轻量级锁状态 --> 重量级锁状态 
   (1) 随着竞争情况逐渐升级
   (2) 锁可以升级，不能降级
    
4. 几个概念
   （1）cache line      //缓存的最小操作单位，也是缓存可以分配的最小存储单元
   （2）memory barriers //一组处理器指令，用于内存操作顺序(order)的限制
   （3）memory order violation //内存顺序冲突，由假共享(false sharing)引起. 出现内存顺序冲突时，CPU必须清空流水线
   （4）false sharing   //伪共享，指多个CPU同时修改同一个cache line的不同部分，而引起其中一个CPU的操作无效
   （5）CAS = Compare And Swap // 需要两个数值<期望值/旧值，更新值>. 比较期望值和当前值是否一致，一致则替换为更新值；否则，不替换. 这由一条机器指令完成

5. 有两种方式实现多处理器之间的原子操作
   (1)总线加锁
   (2)缓存加锁

6. ReentrantReadWriteLock
线程进入读锁的前提条件： 同时满足 (1)没有其他线程的写锁, (2)没有写请求或者有写请求，但调用线程和持有锁的线程是同一个
线程进入写锁的前提条件： 同时满足 (1)没有其他线程的读锁, (2)没有其他线程的写锁
ReadLock 和 WriteLock的性质：
     (a).重入方面其内部的WriteLock可以获取ReadLock，但是反过来ReadLock想要获得WriteLock则永远都不要想。 
     (b).WriteLock可以降级为ReadLock，顺序是：先获得WriteLock再获得ReadLock，然后释放WriteLock，这时候线程将保持Readlock的持有。反过来ReadLock想要升级为WriteLock则不可能，为什么？参看(a). 
     (c).ReadLock可以被多个线程持有并且在作用时排斥任何的WriteLock，而WriteLock则是完全的互斥。这一特性最为重要，因为对于高读取频率而相对较低写入的数据结构，使用此类锁同步机制则可以提高并发量。 
     (d).不管是ReadLock还是WriteLock都支持Interrupt，语义与ReentrantLock一致。 
     (e).WriteLock支持Condition并且与ReentrantLock语义一致，而ReadLock则不能使用Condition，否则抛出UnsupportedOperationException异常
Q: 为什么ReadLock重入时不能获得WriteLock?
A: 因为ReadLock是共享锁，可能被当前线程之外的另个线程持有。注意写锁的前提之一是 (1)没有其他线程的读锁。设想一下，如果当前线程得到写锁，而别的线程
   持有读锁的情况下，会发生inconsistent

(java 的各种锁，请参考美图技术团队的博客 https://tech.meituan.com/2018/11/15/java-lock.html )