如何套用别人网站做页面高级搜索百度

并发编程

三大问题

• 在并发编程中，原子性、有序性和可见性是三个重要的问题，解决这三个问题是保证多线程程序正确性的基础。
• 原子性: 指的是一个操作不可分割, 要么全部执行完成, 要么不执行, 不存在执行一部分的情况.
• 有序性: 有序性是指程序的执行顺序与程序中代码的顺序一致。在多线程环境下，由于线程的交替执行和指令重排等因素，可能会导致代码的执行顺序与预期不一致
• 可见性: 可见性是指当一个线程修改了共享变量的值时，其他线程能够立即看到这个修改。在多核处理器和多级缓存系统中，线程对共享变量的修改可能被缓存到CPU的本地缓存中，而其他CPU上的线程无法立即看到这个修改，从而导致数据不一致的问题。
• 原子性问题, 可以用 synchronized 关键字解决, JDK 也提供了 ReentrantLock 等机制, 也能解决;
• 有序性和可见性, 可以由 volatile 解决;

原子性问题, 就不多说了, 下面重点介绍一下如何解决有序性和可见性问题;

HappensBefore原则

• 它是一种顺序保证，确保在并发环境下的有序性和可见性;
• 例如, 该规则规定同一个线程内的每个操作, 都 happens-before 于该线程中的任意后续操作;
• 例如, 一个监视器锁上一次的解锁操作, happens-before于下一次的加锁操作;
• 例如, 如果线程A调用线程B的start()方法来启动线程B，则start()操作Happens-Before于线程B中的任意操作。
• 如果 A happens before B, 那么 A 应该在 B 之前执行, 且 A 的结果应该对 B 可见;

原则固然好, 问题是怎么实现呢? 主要就是 synchronized + volatile, synchronized已经介绍过, 这里介绍 volatile, 让我们先从缓存开始说起;

缓存行

• 现代计算机为了缓和 CPU 速度和内存速度之间的差异, 会在内存与CPU之间设置多级缓存, 缓存的速度比内存快;

• 当 CPU 读缓存未命中时, 会从内存读取数据并放入到缓存中, 以后就可以直接从缓存中读取, 提高了速度;

• 从内存往 CPU Cache 读的时候, 根据程序局部性原理, 会按块(在缓存里也叫缓存行)读取, 大小为64B;

• 如果你有一个特别热点的变量, 那应该让他尽量独占一个缓存行, 怎么做? 在前后填充无意义数据, 前后都填充 7 * 8B, 这样就保证热点变量一定独占一个缓存行;

• 现在 CPU 一般都是多核的, 每个核相当于一个独立的 CPU;

• 现在的 CPU 缓存一般是三级缓存, 一二级在 CPU 核心内部, 三级共享;

• 补充: 超线程

  一个CPU内有一套ALU计算单元, 两套程序计数器PC和寄存器, 这样就可以同时保存两个线程的上下文, 切换时只需要让ALU切换一下数据来源即可;

  这样提高了线程切换效率, 8核16线程就是这么来的;

英特尔X86 - MESI

• 每个CPU内核有自己的 cache, 为了解决不同 CPU内核的 Cache 之间以及 Cache 与主存之间的一致性问题, 引入了串行总线 + MESI协议的解决方式;

• 将 Cache 中缓存的数据分为四种状态;

  1. **Exclusive（E）：**当某个缓存数据仅存在于一个CPU核内, 并且与内存中的值一致时, 该缓存行的状态为 Exclusive。
  2. Modified（M）： 在E的基础上, 如果内核修改了缓存, 使得与内存不一致, 该缓存行的状态为 Modified;
  3. Shared（S）： 当一个缓存行被多个CPU内核缓存，并且缓存中的数据与内存中的数据一致时，该缓存行的状态为 Shared;
  4. Invalid（I）： 在S的基础上, 某个内核修改自己的缓存时, 其它内核的缓存将被失效, 状态变为 Invalid

• 举例

  1. CPU0 读变量a, a 从主存缓存到CPU0, 状态为 E;

  2. CPU0 写变量a, 缓存状态改为 M;

  3. CPU1 读变量a, 发现 CPU0 有变量a的缓存, 那么拿到自己的缓存里来, 并将缓存的最新值写入内存, 缓存的状态变为S, CPU0和1现在都有a的缓存, 且状态都是 S;

  4. CPU0 再次修改a, 这会将 CPU1 的缓存失效, 状态改为 I; 并将最新值写入内存, CPU0自己的缓存状态改为 E;

• 当CPU内核去查询其它CPU内核是否有相同缓存, 以及通知其它CPU缓存失效等操作时, 为了避免这些操作发生混乱, 总线是串行的;

• 补充: 如果数据非常大, 一个缓存行放不下, 怎么保证一致性? 直接到内存中访问, 并且访问时锁总线;

store buffer & invalidate queue

• 因为总线是串行的, 所以效率较低, 为此引入了store buffer和invalidate queue; 以下简称 SB 和 IQ;

• 每个 CPU 都有自己 SB 和 IQ ;

• 前面讲过, 当一个 CPU 要读某个数据时, 会向其它 CPU 查询是否有该数据的缓存, 如果有, 拿过来, 如果没有, 去内存拿; 这个过程是锁总线的, 是串行的, 过程中所有 CPU 都不能使用总线;

• 当一个 CPU 要失效其它 CPU 中的数据时也是一样, 其它 CPU 要等待通知, 然后失效对应的缓存, 这个过程中不能去使用总线;

• 现在引入 SB 后, 当 CPU 要读取数据时, 由 SB 与其它 CPU 交互, 得到的结果暂存到 SB 中, CPU 此时可以去执行其它指令;

• IQ 也是一样, 当有失效通知到来时, 先缓存到 IQ 中, CPU再异步地进行处理;

指令重排

指令重排通常出现在以下两个阶段：

编译器优化阶段：编译器在生成字节码或机器码时，为了提高执行效率，可能会对源代码中的指令进行重新排序。例如，编译器可能会将没有依赖关系的指令提前执行，以充分利用 CPU 的流水线能力。

处理器优化阶段：处理器为了最大化硬件资源的利用率，可能会在执行指令时重新调整指令的顺序。例如，在处理器的流水线中，如果某个指令的执行依赖于之前指令的结果，而该结果尚未准备好，处理器可能会先执行其他指令。

比如 SB 和 IQ 的引入, 就会导致修改不能立即可见以及指令重排的问题;

// 假设一开始 flag 值为true, 在线程 1 和线程 2都有缓存;
// 线程1先执行, 这将导致线程2的缓存失效, 但是因为invalidQueue, 线程2并不会立即收到这一信息;
{flag = false;
}// 线程二可能还没来得及处理IQ中的失效通知, 导致还是能通过 if 判断;
if(flag){// 导致还能进来;i++;
}// 明明我先把一个值改为 false 了, 其它线程却还是判断为 true, 这就发生了不可见;
// 本来应该 flag = false 然后 i++ 不执行, 现在却变成了相当于线程二先通过判断并执行 i++, 线程一再 flag = false
// 这就发生了指令重排;

指令重排问题举例: new对象

一次完整的 new 对象并执行构造方法的过程, 其字节码如下

new #2 <T>
dup
invokespecial #3 <T.<init>>
astore_1
return

• new 分配空间, 并将该引用压到操作数栈; 分配以后所有成员都是默认值;

  分配空间的时候有两种方式: 指针碰撞和空闲链表;

  首先, 不考虑逃逸分析的话, 新对象的创建都在堆上;

  Eden 区放得下, 就在 Eden 区分配; 如果是超大对象, 还有可能直接在老年代分配;

  指针碰撞: 用一个指针指向当前空闲区域的起始位置;

  适用于不会产生碎片的垃圾回收算法, 比如 Parallel Scavenge, 基于复制算法; 所以, 新生代上 new 对象, 一般适用指针碰撞;

  空闲链表: 维护空闲链表, 每个元素对应一个空闲块; 适用于会产生碎片的垃圾回收算法; 比如CMS;

  如何解决多线程同时分配内存的安全问题?

  可以用 CAS;

  可以用 TLAB; 每个线程初始化的时候, 分配一个 在分配内存权限上私有的 一块Buffer; 满了再申请; 分配是私有的, 访问不是;

• dup 将栈顶的值复制一份再次入栈;

• invokespecial 弹出栈顶, 作为 this 传给构造方法;

• astore, 将弹出栈顶, 保存到当前方法的局部变量表中;

• return, 返回;

• 由于指令重排, 有可能还没调用构造方法, 就放到局部变量表里了, 这时候去使用它, 用的是一个没有经过构造方法初始化的对象, 很危险;

指令重排问题举例: 单例模式

如何做一个线程安全的懒加载单例类? 大多数人的回答是DCL, 即 double check lock

private static singleton;
public static Singleton get(){// 外层的if 保证效率, 已经创建了单例对象的时候不会进入synchronized;if(singleton == null){synchronized(Singleton.class){// 内层保证多线程安全if(singleton == null)singleton = new Singleton();else{return singleton;}}}else{return singleton;}
}

• 正确的回答要在 DCL 的基础上, 给 singleton 引用加 volatile, 如果不加volatile, DCL也没用

  private volatile static singleton;
  

• 因为new对象是个过程, 假设没有加volatile, 因为指令重排, 使得astore指令在 invokespecial 指令前执行; 那么线程一 new 对象 new 到一半, 所有成员还是默认值的情况下, 就把引用保存了, 这时如果线程2到来, 进行外层判断, singleton != null, 会直接把这个没有执行invokespecial的对象返回;

• 如果是一个初值为1000的账户, 那现在初始金额只有0;

volatile 如何解决可见性与有序性问题?

1. 在源码中加volatile关键字, 编译为 class 文件后, 对应 ACC_VOLATILE 指令;

2. CPU 提供了内存屏障指令, 上层应用可以在合适的地方添加内存屏障指令来避免指令重排;

   JVM 会自动对 volatile 变量的读写操作添加对应的内存屏障;

   比如对 volatile 修饰的变量 x 进行写操作:

   JVM 自动在写操作之前加 StoreStore 屏障, 表示前面的对普通变量的写操作完成, 当前的写操作才能执行;

   后面加 StoreLoad, 表示当前的写操作执行完了, 后面对普通变量的读操作才能执行;

3. 读写屏障在底层使用 lock 汇编指令, 通过对总线或者缓存行加锁的方式, 禁用 SB 和 IQ, 将对缓存的修改强制立即写入主存, 进而解决了可见性和有序性问题;

4. 需要注意, volatile 并不保证原子性; 不过, 在一些场景下, 比如 CAS 操作一个变量, 通过 CAS 和 volatile 是可以同时解决三大问题的, 性能比synchronized 要好;