计划:技术栈完善2-实战Java高并发程序设计-第一章




第一章

同步与异步

如图
同步是链式进行:只有当一个任务结束后才可以继续下一个
而异步则是前进->等待消息返回(同时继续前进进行其他的任务)->消息返回,继续前进.

并发(Concurrency)和并行(Parallelism)

如图
并发是以时间片为单位看似同步进行
并行是实际上的同步进行(一般为多核)

临界区

即可以有多个线程来使用它,但同一时刻只能有一个线程来使用它.
一但临界区被一个线程占用,其他线程就必须等待.

阻塞(Blocking)和非阻塞(Non-Blocking)

阻塞: 一个线程占用了临界区资源,那么其他所有需要这个资源的线程就必须在这个临界区中进行等待.
非阻塞: 任何线程都不会阻碍其他线程的执行,所有的线程都会尝试不断向前继续执行.

死锁(Deadlock)、饥饿(Starvation)和活锁(Livelock)

死锁: 如上图,在专业课程中,我们所学到的死锁经常会这样描述-

单行道(堵塞/等待):

线程A需求资源B,占用资源A(资源A最大为1个)
线程B需求资源A,占用资源B(资源B最大为1个)
他俩同时锁住了这两个资源并等待想要的资源.卡掉了.

N个同理.大家都不想放掉自己的资源,又想要别人的.

饥饿: 在每一个线程都有优先级的时候,如果一个线程的优先级始终在下面,他就永远得不到资源了,当然,不一定只有这种情况.

与死锁相比,姐还是有可能在一段时间后自行解决的

活锁: 两人互相谦让,死脑筋的想着从相同的口出/进就是活锁,本来有机会解锁的…

并发级别

由于临界区的存在,多线程之间的并发必须受到控制。根据控制并发的策略,我们可以把并发的级别进行分类,大致可以分为阻塞、无饥饿、无障碍、无锁、无等待几种.

阻塞(Blocking)

当我们使用synchronized关键字,或者重入锁时,我们得到的就是阻塞的线程.

无论哪种情况,都会在试图执行后续代码前,得到的是临界区的锁,如果得不到,都会被挂起等待,知道占用了所需资源为止.

PS:以上均未遇见,书上说在后面

无饥饿(Starvation-Free)

如果线程有优先级,而选用的线程调度算法允许插队,成为非公平,如下图,那么最下面的很大可能会产生饥饿

如果线程是公平的,就不会产生饥饿,不管来的线程优先级多么的高,要想获得资源,就必须 乖 ♂ 乖 ♂ 站 ♂ 好 ♂,所有的线程都会执行.

无障碍(Obstruction-Free)

不对临界区设任何门栏,任何线程想进就进,想出就出,如果出现数据混乱了怎么办

一旦检测到了数据改坏了,就会对自己所做的修改进行回滚.确保数据安全.如果没有竞争发生,数据就会很安全的离开临界区.

故如果有严重的错误时,所有的线程都会不断地会滚自己的操作.导致没有一个线程可以走出来,顾我们会希望至少有一个县城可以安全地走出来.

一致性标记:线程在操作之前,先读取并保存这个标记,在操作完成后,再次读取,检查这个标记是否被更改过.如果两者一致,说明资源访问没又发生冲突,安全.如果不一致,需要重试操作.而任何尝试修改数据的线程,都需要在修改前更改这个一致性标记,表示这个数据不再安全.

如下图

无锁(Lock-Free)

所有线程都可以尝试对临界区进行访问,但不同的是,无锁的并发保证必然有一个线程能够在有限步内完成操作离开临界区.

无锁是一个无穷循环。在这个循环中,线程会不断尝试修改共享变量,如果没有冲突,修改成功,则退出,否则继续尝试修改,但无论如何,无锁一定会有一个线程可以胜出.

但是无锁会出现类似于饥饿的情况.

例:

while(!atomicVar.compareAndSet(localVar,localVal+1)){
    localVar=atomicVar.get();
}

无等待(Wait-Free)

无等待是无锁++

它要求所有的线程都需要在有限步内完成,这样就不会引起饥饿问题。如果限制这个步骤上限,还可以进一步分解成有界无等待和线程数无关的无等待几种,他们之间的区别只是对循环次数的限制不同.

一种常用的方法是RCU(Read-Copy-Update)。它的基本思想是,对数据的读写可以不加控制。因此所有的读线程都是无等待的。

怎么处理数据混乱问题呢?

拿走需要修改的数据的Copy那部分,然后寻找合适的时机回写数据.

有关并行的两个重要定律

主要作用,提高性能

Amdahl定律

加速比定义:
加速比 = 优化前系统耗时 / 优化后系统耗时

加速比越高,表明优化效果越明显

T: 时间
T1: 一个处理器优化前耗时
Tn: n个处理器优化后的耗时
n: 处理器个数1
F: 程序中只能串行执行的比例

公式推导:

通俗来讲: 1/n(1-F)就是将多核时一个核的比

加速比,当n->无穷,那么加速比与系统的串行率成反比,如果系统中必须有50%的代码串行执行,那么系统的最大加速比为2.

例:


Gustafson定律

可以发现Gf定律是通过时间来推导的.

JMM

JVM是Java虚拟机
而JMM是Java的内存模型
故JMM多用于线程/进程管理

JMM是围绕着多线程的原子性,可见性和有序性来建立的

原子性

原子性是指一个程序不可中断,一旦开始执行,就不会被其他线程干扰.

值得一提的是,int是原子性的,而long在32位JVM上的读取和输入是非原子性的.


public class p11 { public static long t=0; public static class ChangeT implements Runnable{ private long to; public ChangeT(long to){ this.to=to; } @Override public void run(){ while(true){ p11.t=to; Thread.yield(); } } } public static class ReadT implements Runnable{ @Override public void run(){ while(true){ long tmp=p11.t; if(tmp!=111L && tmp!=-999L && tmp!=333L && tmp!=-444L) System.out.println(tmp); Thread.yield(); } } } public static void main(String[] args) { new Thread(new ChangeT(111L)).start(); new Thread(new ChangeT(-999L)).start(); new Thread(new ChangeT(333L)).start(); new Thread(new ChangeT(444L)).start(); new Thread(new ReadT()).start(); } }

输出:

会发现根本就不是输入的四个值中的一个,因为他们互相影响了.

可见性(Visibility)

可见性是当一个线程修改了变量后,其他线程是否能够立即知道这个修改,显然,对于船型程序而言,可见性是不存在的.因为你在任何一个操作步骤中修改了某个变量,那么在后续步骤中,读取的这个变量,一定是修改后的(临界区被占用).

但在并行程序中就不同了.有可能知道,也可能不知道.
如:

CPU2和CPU1在一开始读取了cache上的数据,但CPU2在某条路径上更快的修改了cache,而CPU1无法得知,故CPU1内还是一个旧的值.修改则一定会发生错误.

无法保证能够从一个线程中观察另一个线程的变量.

编译器的向前优化

一个复杂一点的例子

对于大部分编译器而言,可能会对线程1进行向前替换优化,也就是r5=r1.x这条指令会被直接替换成r5=r2.因为他们都读取了r1.x,又发生在同一个线程中,因此,编译器可能会认为没必要二次读取.

有序性(Ordering)

程序在执行时,会出现指令重排,重拍后的指令与原指令未必一致.
这就导致了有可能出现在前面的代码后执行,在后面的代码先执行.
如:

指令重排

可以保证与串行语义一致,但没义务保证多线程间的语义也一致.
为什么要进行指令重排呢?
指令的执行分以下几步:
– 取值 IF
– 译码和去寄存器操作数 ID
– 执行或者有效地址计算 EX
– 存储器访问 MEM
– 写回 WB

汇编指令也不是一步就可以执行完的.
ALU:算数逻辑单元,是CPU的执行单元,是CPU的核心组成部分,主要功能是进行二进制算术运算.

因为指令执行的每一步都使用不同的硬件完成,聪明的工程师就发明了流水线技术.

防止流水线中断

流水线满载时,性能很不错,但是一旦中断,所有的硬件设备都会进入一个停顿期,再次满载又需要几个周期.因此,性能的损失蛮大的.

而指令重排则是防止流水线中断的一种方式.
我们来以一个例子看看中断到底是什么意思.
下图展示的是 A=B+C 这个操作的执行过程:
LW: load LW R1,B 将B加载到R1寄存器中
ADD: 加法 ADD R3,R1,R2 将R1+R2的值放到R3寄存器中
SW: store 存储,就是将R3寄存器的值保存到变量A中.

那两个大X代表的是等待R2的值,因为R2还未MEM,WB,所以R2寄存器内还没有值,
这就是一个中断,会直接的导致后面的慢一拍.

如何防止呢?

一个更复杂的例子:

好多中断是吧.为了减少中断,我们将将对程序没有影响的代码放到中断之前,将中断代码往后移一个单位即可,即充分利用时间.

重排后的结果:

哪些指令不能重排: Happen-Before 规则

第一章结束