Java Concurrency

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) {             
        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 )