【红黑树】先提前备点儿干货......
～再谝Java中的原子性～
～可见性～
～有序性～
⚠️⚠️⚠️指令重排序不会影响单个线程的执行，但是会影响到线程并发执行的正确性
要想并发程序正确地执行，必须要保证原子性、可见性以及有序性。只要有一个没有被保证，就有可能会导致程序运行不正确。
～Java有序性～
在Java内存模型中，允许编译器和处理器对指令进行重排序，但是重排序过程不会影响到单线程程序的执行，却会影响到多线程并发执行的正确性。
即不需要通过任何手段就能够得到保证的有序性，这个通常也称为 happens-before 原则。如果两个操作的执行次序无法从happens-before原则推导出来，那么它们就不能保证它们的有序性，虚拟机可以随意地对它们进行重排序。
①程序次序规则：一个线程内按照代码顺序，书写在前面的操作先行发生于书写在后面的操作
②锁定规则：一个unLock操作先行发生于后面对同一个锁的lock操作
③volatile变量规则：对一个变量的写操作先行发生于后面对这个变量的读操作
④传递规则：如果操作A先行发生于操作B，而操作B又先行发生于操作C，则可以得出操作A先行发生于操作C
⑤线程启动规则：Thread对象的start()方法先行发生于此线程的每个一个动作
⑥线程中断规则：对线程interrupt()方法的调用先行发生于被中断线程的代码检测到中断事件的发生
⑦线程终结规则：线程中所有的操作都先行发生于线程的终止检测，我们可以通过Thread.join()方法结束、Thread.isAlive()的返回值手段检测到线程已经终止执行
⑧对象终结规则：一个对象的初始化完成先行发生于他的finalize()方法的开始
⚠️针对第①条虚拟机可能会对程序代码进行指令重排序。虽然进行重排序，但是最终执行的结果是与程序顺序执行的结果一致的，它只会对不存在数据依赖性的指令进行重排序。在单个线程中，程序执行看起来是有序执行的。事实上，这个规则是用来保证程序在单线程中执行结果的正确性，但无法保证程序在多线程中执行的正确性。
～是不是叒想到了volatile？～ 那就顺便谝一哈volatile.......
1. volatile保证可见性
一个共享变量（类的成员变量、类的静态成员变量）被volatile修饰之后，就具备了两层语义：
保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。
禁止指令重排序。
【死循环】每个线程在运行过程中都有自己的工作内存，那么线程1在运行的时候，会将stop变量的值拷贝一份放在自己的工作内存当中。当线程2更改了stop变量的值之后，但是还没来得及写入主存当中，线程2转去做其他事情了，那么线程1由于不知道线程2对stop变量的更改，因此还会一直循环下去。
【解决方案】用volatile关键字修饰，如volatile boolean stop = false; 那有啥不一样：
第一：使用volatile关键字会强制将修改的值立即写入主存；
第二：若使用volatile关键字。当线程2进行修改时，会导致线程1的工作内存中缓存变量stop的缓存行无效（反映到硬件层的话，就是CPU的L1或者L2缓存中对应的缓存行无效）；
第三：由于线程1的工作内存中缓存变量stop的缓存行无效，所以线程1再次读取变量stop的值时会去主存读取。～是不是又想起了CAS呢？
⚠️⚠️⚠️～Volatile只能保证可见性，保证不了原子性！！！～
如自增 i++ 操作不是原子性操作，而且volatile也无法保证对变量的任何操作都是原子性的。
解决方案：可以通过synchronized、lock进行加锁，来保证操作的原子性。也可以通过AtomicInteger（Atomic是利用CAS来实现原子性操作的（Compare And Swap），CAS实际上是利用处理器提供CMPXCHG指令实现的，而处理器执行CMPXCHG指令是一个原子性操作）.
2. volatile禁止指令重排序
1）当程序执行到volatile变量的读操作or写操作时，在其前面的操作的更改肯定全部已经进行，且结果已经对后面的操作可见；在其后面的操作肯定还没有进行；
2）在进行指令优化时，不能将再对volatile变量的读操作或者写操作的语句放在其后面执行，也不能把volatile变量后面的语句放到其前面执行。
例子～
处理器为了提高处理速度（为啥会有缓存？答：速度不匹配）不直接和内存进行交互，而是将系统内存的数据独到内部缓存后再进行操作，但操作完后不知什么时候会写到内存。 如果对声明了volatile变量进行写操作时，JVM会向处理器发送一条Lock前缀的指令，将这个变量所在缓存行的数据写会到系统内存。 这一步确保了如果有其他线程对声明了volatile变量进行修改，则立即更新主内存中数据。 |
Lock前缀指令实际上相当于一个内存屏障/栅栏MemoryFence，它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面；即在执行到内存屏障这句指令时，在它前面的操作已经全部完成。 |
～适合哪些场景使用？
1）对变量的写操作不依赖于当前值。
2）该变量没有包含在具有其他变量的不变式中。DCL～Double Check Lock双重锁校验
～为什么要使用 volatile修饰 instance？
因为 instance = new Singleton() 不是一个原子操作。执行的流程：
1.给 instance 分配内存
2.调用 Singleton 的构造函数来初始化成员变量～半初始化状态，即成员变量是默认初始值，
3.将instance对象指向分配的内存空间（执行完这步 instance 就为非 null 了）。
但是在JIT/即时编译器中存在指令重排序的优化。第2步和第3步的顺序是不能保证的，最终的执行顺序可能是 1-2-3 or 1-3-2。如果是后者，则在第3步执行完毕、第2步未执行之前，被线程2抢占了，这时instance已经是非null了（但却没有初始化），所以线程2会直接返回instance，此时使用报错。