后端必备知识

进程、线程、协程

进程

(1)进程状态

1.创建状态(new) :进程正在被创建,尚未到就绪状态。
2.就绪状态(ready) :进程已处于准备运行状态,即进程获得了除了处理器之外的一切所需资源,一旦得到处理器资源(处理器分配的时间片)即可运行。
3.运行状态(running) :进程正在处理器上上运行(单核CPU下任意时刻只有一个进程处于运行状态)。
4.阻塞状态(waiting) :又称为等待状态,进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲,该进程也不能运行。
5.结束状态(terminated) :进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

(2)进程调度方式

  • 非抢占方式 : 把处理机分配给某进程后,就一直让它运行下去,直至完成。或者发生阻塞时(比如 I/O操作引起的阻塞,或者执行了block阻塞原语),才把处理机分配给其它进程。
  • 抢占方式:优先权原则、短进程优先原则、时间片原则

抢占方式又细分为:
轮转调度算法: 基于时间片的轮转。(当CPU时间片用完后,或者进程执行完后,开始切换下一个进程 )
优先级调度算法: 将处理机分配给就绪队列中优先级最高的进程。也分为抢占式 和 非抢占式。抢占式可以中断正在运行的低级进程,运行新来的优先级高的进程。非抢占式不会中断正在运行的低优先级的进程。
多队列调度算法: 多个就绪队列。
多级反馈队列调度算法

(3)进程调度算法

1、时间片轮转调度算法(RR):给每个进程固定的执行时间,根据进程到达的先后顺序让进程在单位时间片内执行,执行完成后便调度下一个进程执行,时间片轮转调度不考虑进程等待时间和执行时间,属于抢占式调度。优点是兼顾长短作业;缺点是平均等待时间较长,上下文切换较费时。适用于分时系统。

2、先来先服务调度算法(FCFS):根据进程到达的先后顺序执行进程,不考虑等待时间和执行时间,会产生饥饿现象。属于非抢占式调度,优点是公平,实现简单;缺点是不利于短作业。

3、优先级调度算法(HPF):在进程等待队列中选择优先级最高的来执行。

4、多级反馈队列调度算法:将时间片轮转与优先级调度相结合,把进程按优先级分成不同的队列,先按优先级调度,优先级相同的,按时间片轮转。优点是兼顾长短作业,有较好的响应时间,可行性强,适用于各种作业环境。

5、高响应比优先调度算法:根据“响应比=(进程执行时间+进程等待时间)/ 进程执行时间”这个公式得到的响应比来进行调度。高响应比优先算法在等待时间相同的情况下,作业执行的时间越短,响应比越高,满足段任务优先,同时响应比会随着等待时间增加而变大,优先级会提高,能够避免饥饿现象。优点是兼顾长短作业,缺点是计算响应比开销大,适用于批处理系统。

线程

(1)线程状态

1.NEW:新建状态,Mythread thread=new MyThread();此时thread的状态
2.RUNNABLE:运行状态,thread.start();此时thread的状态,但是处于这个状态的线程并不一定真正执行,可能会存在在等待资源,因此网上也有人将这个状态分为就绪状态和执行状态两种
3.TERMINATED:结束状态,线程执行完之后的状态

异常状态3种:
1.BLOCKED:阻塞状态,通常出现在synchronized语句块中,代表着一个线程等待锁
2.WAITING:等待状态,通常出现在Object.wait()Thread.join()LockSupport.park()语句前后
3.TIMED_WAITING:限时等待状态,当前线程的等待时间是有限制的,时间一到线程就会被唤醒,通常出现Thread.sleep(long)Object.wait(long)Thread.join(long)LockSupport.parkNanos()LockSupport.parkUntil()

(2)ThreadLocal

往ThreadLocal中set值就是存入了当前线程对象的threadLocals属性里,而threadLocals的类型是ThreadLocalMap。ThreadLocalMap 可以理解为 ThreadLocal 类实现的定制化的 HashMap。

Java的四种引用(强弱软虚)

跟ThreadLocal有关的有两个引用: 强引用弱引用。这两个引用就是内存泄漏的重点,ThreadLocalMap中的Entry对象继承了WeakReference弱引用类,并且在Entry的构造方法中,会以key作为参数传入到父类构造方法,key是以弱引用指向ThreadLocal,这时候垃圾回收器线程运行,发现弱引用就回收,key被回收。ThreadLocalMap里对应的Entry的key会变成null。而ThreadLocalMap里对应的Entry的value则无法被访问到,value作为一个强引用垃圾回收不到也不能被访问,即造成了内存溢出。注意:主动调用remove方法

  • 强引用(StrongReference): 当JVM的内存空间不足时,宁愿抛出OutOfMemoryError使得程序异常终止也不愿意回收具有强引用的存活着的对象。

  • 弱引⽤(WeakReference):在GC的时候,不管内存空间足不足都会回收这个对象。

  • 软引用(SoftReference):如果内存空间足够,垃圾回收器就不会回收它,如果内存空间不足了,就会回收这些对象的内存。只要垃圾回收器没有回收它,该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。

  • 虚引用(PhantomReference):与其他几种引用都不同,虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用,那么它就和没有任何引用一样,在任何时候都可能被垃圾回收。

虚引用主要用来跟踪对象被垃圾回收的活动。虚引用与软引用和弱引用的一个区别在于:虚引用必须和引用队列(ReferenceQueue)联合使用。当垃 圾回收器准备回收一个对象时,如果发现它还有虚引用,就会在回收对象的内存之前,把这个虚引用加入到与之关联的引用队列中。程序可以通过判断引用队列中是 否已经加入了虚引用,来了解被引用的对象是否将要被垃圾回收。程序如果发现某个虚引用已经被加入到引用队列,那么就可以在所引用的对象的内存被回收之前采取必要的行动。

1.线程模型

参考阅读:线程的实现
线程是CPU调度执行的基本单位,多个线程共享系统为进程分配的资源,又可以被系统独立调度执行。

(1)内核线程模型(Kernel-Level Thread ,KLT),即一对一线程模型
(2)用户线程模型(User Thread),即1:N 模型
(3)混合线程模型- 用户线程 + 轻量级进程混合实现, 即N:M 模型

(1)内核线程模型

即完全依赖操作系统内核提供的内核线程(Kernel-Level Thread ,KLT)来实现多线程。在此模型下,线程的切换调度由系统内核完成,系统内核负责将多个线程执行的任务映射到各个CPU中去执行。
在这里插入图片描述

用户进程使用系统内核提供的接口———轻量级进程(Light Weight Process,LWP)来使用系统内核线程。
在此种线程模型下,由于一个用户线程对应一个LWP,因此某个LWP在调用过程中阻塞了不会影响整个进程的执行。

缺点:

  • 由于是基于内核线程实现的, 所以各种线程操作,如创建、析构及同步,都需要进行系统调用。而系统调用的代价相对较高,需要在用户态(User Mode)和内核态(Kernel Mode)中来回频繁切换,消耗较大
  • 基于1:1的关系,每个LWP都需要一个内核线程来支持执行用户代码,因此轻量级进程要消耗一定的内核资源(如内核线程的栈空间)内核内存空间,因此一个系统支持轻量级进程的数量是有限的

(2)用户线程模型

用户线程模型完全建立在用户空间的线程库上,不依赖于系统内核,用户线程的创建、同步、切换和销毁等操作完全在用户态执行,不需要切换到内核态。
在这里插入图片描述

缺点:
在此种线程模型下,线程的各种操作以及切换消耗很低,但线程的所有操作都需要在用户态实现,线程的调度实现起来异常复杂,处理器映射更是无法实现。

(3)混合线程模型

混合线程模型是前述两种模型的混合版本,用户线程仍然是在用户态中创建,用户线程的创建、切换和销毁的消耗很低,用户线程的数量不受限制。而LWP在用户线程和内核线程之间充当桥梁,就可以使用操作系统提供的线程调度和处理器映射功能。
在这里插入图片描述

(3)Java线程内存模型

参考:Java线程模型

Java线程内存模型划分为两部分:主内存和线程工作内存,主内存是多个线程共享的内存,线程工作内存是每个线程独享的内存。
在这里插入图片描述
Java线程调度方式:分别是协同式线程调度(Cooperative Threads-Scheduling)和抢占式线程调度

Java内存模型定义了8种原子操作来实现上图中的线程内存交互:

原子性、可见性和有序性

  • 原子性
    Java内存模型定义了8中原子操作,此外Java内存模型还保证了对于基本数据类型(char、boolean、int等)的操作是原子性的。对于其他类型的数据如若需要更灵活的原子性操作,Java内存模型提供了lock和unlock操作。JVM中使用的两个字节码指令monitorenter和monitorexit即是通过lock和unlock操作来实现的,常使用的synchronized关键字转换成字节码指令后即由monitorenter和monitorexit构成。

  • 可见性
    可见性是指当一个线程修改了主内存中变量的值,其他线程可以立即获取这个修改后的新值。只要在工作内存中修改变量之后立即存储到主内存,以及读取一个变量之前强制从主内存刷新变量的值即可保证可见性。volatile关键字即通过上述方法保证多线程操作变量时的可见性,读写直接是主内存。

  • 有序性
    有序性是指在同一个线程中的所有操作都是有序执行的,但由于编译器和处理器都可能对指令进行重排序等行为会导致指令执行的顺序不一定是按照代码中的先后顺序执行的,提高程序执行的速度,在多线程中对一个变量的操作就可能会受到指令重排序的影响。volatile关键字包含有禁止指令重排序的作用,因此使用volatile关键字修饰的变量可以保证多线程之间对该变量操作的有序性,保证自己的读写前后插入屏障,使得不会发生指令重排。

2.多线程&线程池

(1)为什么要引入线程池?

每开一个线程都要新建一个Thread对象来处理,这种操作会造成哪些后果呢?

1、系统执行多任务时,会为每个任务创建对应的线程,当任务执行结束之后会销毁对应的线程,在这种情况下对象被频繁的创建和销毁。
2、当对线程象被频繁时会占用大量的系统资源,在并发的过程中会造成资源竞争出现问题。大量的创建线程还会造成混乱,没有一个统一的管理机制,容易造成应用卡顿。
3、大量线程对象被频繁销毁,将会频繁出发GC机制,从而降低性能。

引入线程池的好处:
1、重用线程池中的线程,避免因频繁创建和销毁线程造成的性能消耗。
2、更加有效的控制线程的最大并发数,防止线程过多抢占资源造成的系统阻塞。
3、对线程进行有效的管理。

(2)为什么不推荐使用executors创建?

public static ExecutorService newFixedThreadPool(int nThreads) {
    return new ThreadPoolExecutor(nThreads, nThreads,
                                  0L, TimeUnit.MILLISECONDS,
                                  new LinkedBlockingQueue<Runnable>());
}

public static ExecutorService newSingleThreadExecutor() {
    return new FinalizableDelegatedExecutorService
        (new ThreadPoolExecutor(1, 1,
                                0L, TimeUnit.MILLISECONDS,
                                new LinkedBlockingQueue<Runnable>()));
}

public static ExecutorService newCachedThreadPool() {
    return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                  60L, TimeUnit.SECONDS,
                                  new SynchronousQueue<Runnable>());
}

public static ExecutorService newScheduledThreadPool(int corePoolSize) {
    return super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
          new DelayedWorkQueue());
}

FixedThreadPoolSingleThreadPool都使用了LinkedBlockingQueue。
CachedThreadPoolScheduledThreadPool允许的创建线程数量为 Integer.MAX_VALUE, 可能会创建大量的线程,从而导致 OOM。

Java中的阻塞队列BlockingQueue主要有两种实现,分别是ArrayBlockingQueue 和 LinkedBlockingQueue。

ArrayBlockingQueue //是一个用数组实现的有界阻塞队列,必须设置容量。

LinkedBlockingQueue //是一个用链表实现的有界阻塞队列,容量可以选择进行设置,不设置的话,将是一个无边界的阻塞队列,最大长度为Integer.MAX_VALUE。

SynchronousQueue //是同步队列,它不会保存提交的任务,而是将直接新建一个线程来执行新来的任务。

DelayedWorkQueue // 核心数据结构是二叉最小堆的优先队列,队列满时会自动扩容,不过是将优先级队列和DelayQueue的实现过程迁移到本身方法体中

这里的问题就出在:“不设置的话,将是一个无边界的阻塞队列,最大长度为Integer.MAX_VALUE”。也就是说,如果我们不设置LinkedBlockingQueue的容量的话,其默认容量将会是Integer.MAX_VALUE。

而newFixedThreadPool中创建LinkedBlockingQueue时,并未指定容量。此时,LinkedBlockingQueue就是一个无边界队列,对于一个无边界队列来说,是可以不断的向队列中加入任务的,这种情况下就有可能因为任务过多而导致内存溢出问题。

拒绝策略
当线程池已经关闭或达到最大线程(队列都已满)状态时,新提交的任务将会被拒绝。 ThreadPoolExecutor 定义了四种拒绝策略:

AbortPolicy:默认策略,在需要拒绝任务时抛出RejectedExecutionException;
CallerRunsPolicy:直接在 execute 方法的调用线程中运行被拒绝的任务,如果线程池已经关闭,任务将被丢弃;
DiscardPolicy:直接丢弃任务;
DiscardOldestPolicy:丢弃队列中等待时间最长的任务,并执行当前提交的任务,如果线程池已经关闭,任务将被丢弃。

3.IO模型

参考:
LinuxIO模型
Linux五种IO模型

通常用户进程中的一个完整IO分为两阶段:用户进程空间<–>内核空间、内核空间<–>设备空间(磁盘、网络等)
IO分类:内存IO、网络IO和磁盘IO三种,通常所说指的是后两者

IO这里涉及到基本概念:

同步和异步:
阻塞与非阻塞:
同步阻塞/同步非阻塞:
同步阻塞:一个线程必须等待一个方法调用完毕才能继续执行接下来的任务, 但是等待过程中自己处于挂起状态
同步非阻塞:一个线程必须等待一个方法调用完毕才能继续执行接下来的任务, 且在等待过程中还可以执行其他方法
异步阻塞/异步非阻塞:
数据由 socket 设备到用户态经过两次拷贝: 用户进程在读/写外存(socket 设备)上的数据时, 数据先从 socket 拷贝到内核空间, 然后再从内核空间拷贝到用户空间

(1)阻塞

阻塞IO, 就是指当调用读取数据的函数(比如 read),这个函数不立马返回结果,而是阻塞当前进程,直到数据被复制到用户进程空间或者是超时出错才解除阻塞,并返回结果。
缺点: 几乎所有的IO接口 ( 包括socket接口 ) 都是阻塞型的。这给网络编程带来了一个很大的问题,如在调用 recv(1024) 的同时,线程将被阻塞,在此期间,线程将无法执行任何运算或响应任何的网络请求。

(2)非阻塞

在非阻塞 IO 中,用户在调用 read 方法后,进程没有被阻塞。内核会立马返回数据给进程,这个数据可能是error提示,也可能是最终的结果。如果要得到最终的结果,就需要用户进程主动的多次调用 read 方法。
缺点: 轮询调用 read 是很费CPU资源的

(3)IO多路复用(select,poll,epoll)

IO 多路复用的好处就在于单个进程就可以同时处理多个网络连接的IO。它的基本原理就是不再由应用程序自己监视连接,取而代之由内核替应用程序监视文件描述符。

  • 与传统的多线程/多进程模型比,I/O多路复用的最大优势是系统开销小,系统不需要创建新的额外进程或者线程,也不需要维护这些进程和线程的运行,降底了系统的维护工作量,通过减少无效的系统调用,减少了对 CPU 资源的消耗。
  • 适用高并发服务应用开发、一个进程/线程响应多个请求

(4)信号驱动(SIGIO)

信号驱动式IO就是指进程预先告知内核、向内核注册一个信号处理函数、然后用户进程返回不阻塞、当内核数据就绪时会发送一个信号给进程、用户进程便在信号处理函数中调用IO读取数据. 实际IO内核拷贝到用户进程的过程还是阻塞的、信号驱动式IO并没有实现真正的异步、因为通知到进程之后、依然是由进程来完成IO操作

  • 在信号驱动式IO模型中、依然不符合POSIX描述的异步IO、只能算是半异步、并且实际中并不常用、
  • 回调机制、实现、开发应用难度大

(5)异步IO(POSIX的aio_函数和lio函数)

工作机制是:告知内核启动某个操作、并让内核在整个操作完成后通知我们、这种模型与信号驱动的IO区别在于、信号驱动IO是由内核通知我们何时可以启动一个IO操作, IO操作由用户自定义的信号函数来实现; 而异步IO模型是由内核告知我们IO操作何时完成.

  • 异步IO真正实现了POSIX描述的异步IO、是五种IO模型中唯一的异步模型

阻塞IO和非阻塞IO的区别在哪?

阻塞IO会一直阻塞住对应的进程直到操作完成、而非阻塞IO在内核还没准备数据的情况下会立刻返回, 阻塞和非阻塞关注的是进程在等待调用结果时的状态、阻塞是指调用结果返回之前、当前进程会被挂起、调用进程只有在得到结果才会返回; 非阻塞调用指不能立刻得到结果、该调用不会阻塞当前进程、

同步IO和异步IO区别在哪?

同异步IO的根本区别在于、同步IO主动的调用recvfrom来将数据拷贝到用户内存、而异步则完全不同、它就像是用户进程将整个IO操作交给了他人(内核)完成、然后他人做完后发信号通知、在此期间、用户进程不需要去检查IO操作的状态、也不需要主动的去拷贝数据

信号驱动式IO和异步IO的区别?

信号驱动IO与异步IO的区别在于启用异步IO意味着通知内核启动某个IO操作、并让内核在整个操作(包括数据从内核复制到用户缓冲区)完成时通知我们、也就是说、异步IO是由内核通知我们IO操作何时完成、即实际的IO操作也是异步的、信号驱动IO是由内核通知我们何时可以启动一个IO操作、这个IO操作由用户自定义的信号函数来实现

Java中的三种IO模型:

BIO: 同步阻塞IO,应用程序发起read调用后,会一直阻塞,直到在内核把数据拷贝到用户空间中。数据的读取写⼊必须阻塞在⼀个线程内等待其完成
NIO: JDK1.4 中引入,对应 java.nio 包,提供了Channel, SelectorBuffer等抽象。NIO 中的 N 可以理解为 Non-blocking,不单纯是 New。它支持面向缓冲的,基于通道的 I/O 操作方法。 对于高负载、高并发的(网络)应用,应使用 NIO 。Java 中的 NIO 可以看作是 I/O 多路复用模型。
AIO: JDK7 中引⼊了 NIO 的改进版 NIO 2,它是异步⾮阻塞的 IO 模型。异步 IO 是基于事件和回调机制实现的,也就是应⽤操作之后会直接返回,不会堵塞在那⾥,当后台处理完成,操作系统会通知相应的线程进⾏后续的操作。AIO 是异步 IO 的缩写,虽然 NIO 在⽹络操作中,提供了⾮阻塞的⽅法,但是 NIO 的 IO ⾏为还是同步的。

4.进程通信

参考:Linux进程通信

(1)本地进程

  • (1)匿名管道(pipe):

管道是一个固定大小的缓冲区,在Linux中,限制为4KB
特点:
半双工的通信方式;
只能在父子进程能通讯;
速度慢,容量有限

  • (2)命名管道(FIFO):

任何进程间都能通讯,但速度慢;

  • (3)消息队列(msgQueue):

消息队列是链表,具有特定的格式,存放在内存中并由消息队列标识符标识, 其优势是对每个消息指定特定的消息类型,接收的时候不需要按照队列次序,而是可以根据自定义条件接收特定类型的消息。 可以把消息看做一个记录,具有特定的格式以及特定的优先级。
管道和消息队列的通信数据都是先进先出的原则,与管道(无名管道:只存在于内存中的文件;命名管道:存在于实际的磁盘介质或者文件系统)不同的是消息队列存放在内核中,只有在内核重启(即,操作系统重启)或者显示地删除一个消息队列时,该消息队列才会被真正的删除。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。
消息队列克服了信号承载信息量少,管道只能承载无格式字 节流以及缓冲区大小受限等缺点。
缺点: 容量受到系统限制,且要注意第一次读的时候,要考虑上一次没有读完数据的问题;

  • (4)共享内存(Shared memory):

使得多个进程可以访问同一块内存空间,不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作,如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
能够很容易控制容量,速度快,但要保持同步,比如一个进程在写的时候,另一个进程要注意读写的问题;

  • (5)信号(Signal):

信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生; 信号就是一个内核对象,或者说是一个内核数据结构。只有在父子进程或者是共享内存中,才可以发送字符串消息;
比如:
(1)默认情况下,如果不指定信号,kill 等价于kill -15,kill -15时系统会发送一个SIGTERM的信号给对应的程,只是通知对应的进程要进行"安全、干净的退出",程序接到信号之后,退出前一般会进行一些"准备工作",如资源释放、临时文件清理等等,如果准备工作做完了,再进行程序的终止;
(2)kill -9,系统会发出SIGKILL(9)信号,该信号不允许忽略和阻塞,所以应用程序会立即终止

SIGHUP:用户从终端注销,所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。
SIGINT:程序终止信号。程序运行过程中,按Ctrl+C键将产生该信号。
SIGQUIT:程序退出信号。程序运行过程中,按Ctrl+\键将产生该信号。
SIGBUS和SIGSEGV:进程访问非法地址。
SIGFPE:运算中出现致命错误,如除零操作、数据溢出等。
SIGKILL:用户终止进程执行信号。shell下执行kill -9发送该信号。
SIGTERM:结束进程信号。shell下执行kill 进程pid发送该信号。
SIGALRM:定时器信号。
SIGCLD:子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号,则子进程退出后将形成僵尸进程。

  • (6)信号量(Semaphores):

信号量是一个计数器,用于多进程对共享数据的访问,信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。不能传递复杂消息,只能用来同步。用于实现进程间的互斥与同步,而不是用于存储进程间通信数据。

(2)不同机器进程

  • 套接字(Socket): (ip地址+端口号)

5.锁和并发

参考:Java中的15中锁
在这里插入图片描述

(1)ConcurrentHashMap实现并发的关键

jdk7:

数据结构:ReentrantLock+HashEntry,一个Segment中包含一个HashEntry数组,每个HashEntry又是一个链表结构。
元素查询:二次Hash,第一次Hash定位到Segment,第二次Hash定位到元素所在的链表的头部。
锁:Segment分段锁 Segment继承了ReentrantLock,锁定操作的Segment,其他的Segment不受影响,并发度为Segment个数,可以通过构造函数指定,数组扩容不会影响其他的Segment。
get方法无需加锁,volatile保证

jdk8:
数据结构:synchronized+CAS+Node+红黑树,Node的val和next都用volatile修饰,保证可见性。
查找,替换,赋值操作都使用CAS
锁:锁链表的head节点,不影响其他元素的读写,锁粒度更细,效率更高,扩容时,阻塞所有的读写操作、并发扩容。
读操作无锁:Node的val和next使用volatile修饰,读写线程对该变量互相可见; 数组用volatile修饰,保证扩容时被读线程感知

(2)锁有哪几种?

  • 公平锁 / 非公平锁
  • 可重入锁 / 不可重入锁

任意线程在获取到锁之后能够再次获取该锁而不会被锁所阻塞

  • 独享锁 / 共享锁
  • 互斥锁 / 读写锁
  • 乐观锁 / 悲观锁

乐观锁实现:版本号、CAS

  • 分段锁

ConcurrentHashMap中的segment实现

  • 偏向锁 / 轻量级锁 / 重量级锁

为什么要引入偏向锁?
因为经过HotSpot的作者大量的研究发现,大多数时候是不存在锁竞争的,常常是一个线程多次获得同一个锁,因此如果每次都要竞争锁会增大很多没有必要付出的代价,为了降低获取锁的代价,才引入的偏向锁。
为什么要引入轻量级锁?
轻量级锁考虑的是竞争锁对象的线程不多,而且线程持有锁的时间也不长的情景。因为阻塞线程需要CPU从用户态转到内核态,代价较大,如果刚刚阻塞不久这个锁就被释放了,那这个代价就有点得不偿失了,因此这个时候就干脆不阻塞这个线程,让它自旋这等待锁释放。

  • 自旋锁

自旋锁(spinlock):是指当一个线程在获取锁的时候,如果锁已经被其它线程获取,那么该线程将循环等待,然后不断的判断锁是否能够被成功获取,直到获取到锁才会退出循环。

(3)synchronized的锁升级状态变化

参考:锁升级的过程
synchronized的基本原理是基于对象头当中的监视器,也叫做监视器锁。
头部有一个moniter_enter命令和一个moniter_exit命令,前者是将对象头当中的计数器加1,后者是将计数器减1

  • 无锁 -> 偏向锁 -> 轻量级锁 -> 自旋锁 -> 重量级锁
    在这里插入图片描述
  1. 偏向锁的升级

当线程1访问代码块并获取锁对象时,会在java对象头和栈帧中记录偏向的锁的threadID,因为偏向锁不会主动释放锁,因此以后线程1再次获取锁的时候,需要比较当前线程的threadID和Java对象头中的threadID是否一致,如果一致(还是线程1获取锁对象),则无需使用CAS来加锁、解锁;如果不一致(其他线程,如线程2要竞争锁对象,而偏向锁不会主动释放因此还是存储的线程1的threadID),那么需要查看Java对象头中记录的线程1是否存活,如果没有存活,那么锁对象被重置为无锁状态,其它线程(线程2)可以竞争将其设置为偏向锁;如果存活,那么立刻查找该线程(线程1)的栈帧信息,如果还是需要继续持有这个锁对象,那么暂停当前线程1,撤销偏向锁,升级为轻量级锁,如果线程1 不再使用该锁对象,那么将锁对象状态设为无锁状态,重新偏向新的线程。

  1. 轻量级锁什么时候升级为重量级锁?

线程1获取轻量级锁时会先把锁对象的对象头MarkWord复制一份到线程1的栈帧中创建的用于存储锁记录的空间(称为DisplacedMarkWord),然后使用CAS把对象头中的内容替换为线程1存储的锁记录(DisplacedMarkWord)的地址;
如果在线程1复制对象头的同时(在线程1CAS之前),线程2也准备获取锁,复制了对象头到线程2的锁记录空间中,但是在线程2CAS的时候,发现线程1已经把对象头换了,线程2的CAS失败,那么线程2就尝试使用自旋锁来等待线程1释放锁。
但是如果自旋的时间太长也不行,因为自旋是要消耗CPU的,因此自旋的次数是有限制的,比如10次或者100次,如果自旋次数到了线程1还没有释放锁,或者线程1还在执行,线程2还在自旋等待,这时又有一个线程3过来竞争这个锁对象,那么这个时候轻量级锁就会膨胀为重量级锁。重量级锁把除了拥有锁的线程都阻塞,防止CPU空转。

  • 锁粗化

按理来说,同步块的作用范围应该尽可能小,仅在共享数据的实际作用域中才进行同步,这样做的目的是为了使需要同步的操作数量尽可能缩小,缩短阻塞时间,如果存在锁竞争,那么等待锁的线程也能尽快拿到锁。
但是加锁解锁也需要消耗资源,如果存在一系列的连续加锁解锁操作,可能会导致不必要的性能损耗。
锁粗化就是将多个连续的加锁、解锁操作连接在一起,扩展成一个范围更大的锁,避免频繁的加锁解锁操作。

  • 锁消除

Java虚拟机在JIT编译时(可以简单理解为当某段代码即将第一次被执行时进行编译,又称即时编译),通过对运行上下文的扫描,经过逃逸分析,去除不可能存在共享资源竞争的锁,通过这种方式消除没有必要的锁,可以节省毫无意义的请求锁时间

(4)CAS

是一种非阻塞的轻量级的乐观锁,非阻塞式是指一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。
CAS(compare and swap),比较并交换。可以解决多线程并行情况下使用锁造成性能损耗的一种机制.CAS 操作包含三个操作数—内存位置(V)、预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。一个线程从主内存中得到num值,并对num进行操作,写入值的时候,线程会把第一次取到的num值和主内存中num值进行比较,如果相等,就会将改变后的num写入主内存,如果不相等,则一直循环对比,知道成功为止。
优点: 解决变量原子性问题
缺点: 带来ABA问题;CPU开销较大;CAS机制所保证的只是一个变量的原子性操作,而不能保证整个代码块的原子性;
解决:通过版本号解决,每次执行数据的修改操作时都会带上一个版本号,在预期版本号和内存中版本号相同时,执行修改操作,并对版本号+1,否则不操作。因为版本号是递增的,所以不会出现ABA问题。例:java原子类中的AtomicStampedReferenceAtomicMarkableReference

6.JVM内存空间

在这里插入图片描述
方法区和堆内存就是主内存区域,而虚拟机栈、本地方法栈以及程序计数器则属于每个线程独享的工作内存

7.垃圾收集器有哪些

1.1 新生代

新生代采用复制算法,主要的垃圾收集器有三个,Serial、Parallel New 和 Parallel Scavenge,特性如下:

  • Serial:单线程收集器,串行方式运行,GC 进行时,其他线程都会停止工作。在单核 CPU 下,收集效率最高。
  • Parallel New:Serial 的多线程版本,新生代默认收集器。在多核 CPU 下,效率更高,可以跟CMS收集器配合使用。
  • Parallel Scavenge:多线程收集器,更加注重吞吐量,适合交互少的任务,不能跟 CMS 配合使用。

1.2 老年代

  • Serial Old:采用标记-整理(压缩)算法,单线程收集。
  • Parallel Old:采用标记-整理(压缩)算法,可以跟 Parallel Scavenge 配合使用
  • CMS:Concurrent Mark Sweep,采用标记-清除算法,收集线程可以跟用户线程一起工作。
    CMS缺点:吞吐量低、无法处理浮动垃圾、标记清除算法会产生大量内存碎片、并发模式失败后会切到Serial old。

1.3 整堆回收

G1:把堆划分成多个大小相等的Region,新生代和老年代不再物理隔离,多核 CPU 和大内存的场景下有很好的性能。新生代使用复制算法,老年代使用标记-压缩(整理)算法。主要用于多处理器、大内存的场景,它有五个属性:分代、增量、并行(大多时候可以并发)、stop the word、标记整理。

8.跳表和二叉树

跳跃表、红黑树、B+树、AVL树特性比较

(1)AVL树:

适合查找,对插入删除不频繁的场景,利用其高度平衡的特性,AVL还是优于红黑的
高度平衡,有稳定的logn的高度,因此有很好的查找性能O(logn)

(2)红黑树:

平衡二叉树,适合查找,它不要求绝对平衡,所以他的查找性能略逊于AVL,但是它却因此可以获得较好的插入删除性能O(logn)
应用:
(1)epoll在内核中的实现,用红黑树管理事件块
(2)C++的STL中。map和set都是用红黑树实现的
(3)nginx中,用红黑树管理timer等
(4)Java的TreeMap实现
(5)linux进程调度用红黑树管理进程控制块

(3)B+树

更加稳定,数据全部存储在叶子节点, 查询时间复杂度固定为 O(log n)
应用:
主要用在文件系统以及数据库中做索引(MySQL的innodb引擎B+树索引)等,B+树的叶子节点的数据都是使用链表连接起来的,更适合范围查询

(4)跳跃表:

查询、插入、删除有log(n)的复杂的, 空间代价较大。跳跃表的优势在于实现简单,而且在并发场景下加锁粒度更小,从而可以实现更高的并发性
应用:
redis的有序集合sortset实现

红黑树和跳跃表比较:
对并发和性能有要求的情况下,如何选择合适的数据结构(这里是跳跃表和红黑树)?

(1)如果单纯比较性能,跳跃表和红黑树可以说相差不大,但是加上并发的环境就不一样了,
(2)如果要更新数据,跳跃表需要更新的部分就比较少,锁的东西也就比较少,所以不同线程争锁的代价就相对少了,而红黑树有个平衡的过程,牵涉到大量的节点,争锁的代价也就相对较高了。性能也就不如前者了。
(3)在并发环境下skiplist有另外一个优势,红黑树在插入和删除的时候可能需要做一些rebalance的操作,这样的操作可能会涉及到整个树的其他部分,而skiplist的操作显然更加局部性一些,锁需要盯住的节点更少,因此在这样的情况下性能好一些。

为什么 MongoDB 索引选择B-树,而 Mysql 索引选择B+树?

(1)MongoDB 是文档型的数据库,是一种 nosql,它使用类 Json 格式保存数据, 性能要求高,B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1),尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库,而 B-树恰好 key 和 data 域聚合在一起。
(2)B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。B+树的查询效率更加稳定,数据全部存储在叶子节点,查询时间复杂度固定为 O(log n)。
(3)B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

9.分布式

ACID 是数据库事务完整性的理论,CAP 是分布式系统设计理论,BASE 是 CAP 理论中 AP 方案的延伸。

理论

1. CAP理论?

CAP 理论中分区容错性 P 是一定要满足的,在此基础上只能满足可用性 A 或者一致性 C。
因此,分布式系统理论上不可能选择 CA 架构,只能选择 CP 或者 AP 架构。 比如 ZooKeeper、HBase 就是 CP 架构,Cassandra、Eureka 就是 AP 架构,Nacos 不仅支持 CP 架构也支持 AP 架构。

为啥不可能选择 CA 架构呢? 举个例子:若系统出现“分区”,系统中的某个节点在进行写操作。为了保证 C, 必须要禁止其他节点的读写操作,这就和 A 发生冲突了。如果为了保证 A,其他节点的读写操作正常的话,那就和 C 发生冲突了。

选择 CP 还是 AP 的关键在于当前的业务场景,没有定论,比如对于需要确保强一致性的场景如银行一般会选择保证 CP 。

另外,需要补充说明的一点是: 如果网络分区正常的话(系统在绝大部分时候所处的状态),也就说不需要保证 P 的时候,C 和 A 能够同时保证。

Consistency(一致性):所有节点访问同一份最新的数据副本
Availability(可用性):非故障的节点在合理的时间内返回合理的响应
Partition Tolerance(分区容错性):分布式系统出现网络分区的时候,仍然能够对外提供服务

2. BASE理论?

BASE 理论本质上是对 CAP 的延伸和补充,更具体地说,是对 CAP 中 AP 方案的一个补充。

BASE 理论是对 CAP 中一致性 C 和可用性 A 权衡的结果,其来源于对大规模互联网系统分布式实践的总结,是基于 CAP 定理逐步演化而来的,它大大降低了我们对系统的要求。
核心思想: 即使无法做到强一致性,但每个应用都可以根据自身业务特点,采用适当的方式来使系统达到最终一致性。
也就是牺牲数据的一致性来满足系统的高可用性,系统中一部分数据不可用或者不一致时,仍需要保持系统整体“主要可用”。
因此,AP 方案只是在系统发生分区的时候放弃一致性,而不是永远放弃一致性。在分区故障恢复后,系统应该达到最终一致性。这一点其实就是 BASE 理论延伸的地方。

Basically Available(基本可用):
Soft-state(软状态):
Eventually Consistent(最终一致性):

3. 2PC?

参考地址:2PC和3PC参考

为了解决这种分布式一致性问题, 提出的典型的协议和算法, XA协议是一个基于数据库的分布式事务协议,其分为两部分:事务管理器和本地资源管理器。事务管理器作为一个全局的调度者,负责对各个本地资源管理器统一号令提交或者回滚。二阶提交协议(2PC)和三阶提交协议(3PC)就是根据此协议衍生出来而来。如今Oracle、Mysql等数据库均已实现了XA接口。

通过协调者给每一个参与者发送Prepare消息,执行本地数据脚本但不提交事务。
如果协调者收到了参与者的失败消息或者超时,直接给每个参与者发送回滚(Rollback)消息;否则,发送提交(Commit)消息;
参与者根据协调者的指令执行提交或者回滚操作,释放所有事务处理过程中被占用的资源,显然2PC做到了所有操作要么全部成功、要么全部失败。

两段提交(2PC)的缺点:

二阶段提交看似能够提供原子性的操作,但它存在着严重的缺陷

(1) 网络抖动导致的数据不一致: 第二阶段中协调者向参与者发送commit命令之后,一旦此时发生网络抖动,导致一部分参与者接收到了commit请求并执行,可其他未接到commit请求的参与者无法执行事务提交。进而导致整个分布式系统出现了数据不一致。
(2) 超时导致的同步阻塞问题:2PC中的所有的参与者节点都为事务阻塞型,当某一个参与者节点出现通信超时,其余参与者都会被动阻塞占用资源不能释放。
(3) 单点故障的风险: 由于严重的依赖协调者,一旦协调者发生故障,而此时参与者还都处于锁定资源的状态,无法完成事务commit操作。虽然协调者出现故障后,会重新选举一个协调者,可无法解决因前一个协调者宕机导致的参与者处于阻塞状态的问题。

4. 3PC?

三段提交(3PC)是对两段提交(2PC)的一种升级优化,3PC在2PC的第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前,各参与者节点的状态都一致。同时在协调者和参与者中都引入超时机制,当参与者各种原因未收到协调者的commit请求后,会对本地事务进行commit,不会一直阻塞等待,解决了2PC的单点故障问题,但3PC 还是没能从根本上解决数据一致性的问题。

3PC 的三个阶段分别是CanCommit、PreCommit、DoCommit
CanCommit:协调者向所有参与者发送CanCommit命令,询问是否可以执行事务提交操作。如果全部响应YES则进入下一个阶段。
PreCommit:协调者向所有参与者发送PreCommit命令,询问是否可以进行事务的预提交操作,参与者接收到PreCommit请求后,如参与者成功的执行了事务操作,则返回Yes响应,进入最终commit阶段。一旦参与者中有向协调者发送了No响应,或因网络造成超时,协调者没有接到参与者的响应,协调者向所有参与者发送abort请求,参与者接受abort命令执行事务的中断。
DoCommit: 在前两个阶段中所有参与者的响应反馈均是YES后,协调者向参与者发送DoCommit命令正式提交事务,如协调者没有接收到参与者发送的ACK响应,会向所有参与者发送abort请求命令,执行事务的中断。

相对于2PC,3PC主要解决的单点故障问题,并减少阻塞,因为一旦参与者无法及时收到来自协调者的信息之后,他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题,因为,由于网络原因,协调者发送的abort响应没有及时被参与者接收到,那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

6. ZAB协议?

ZAB协议,全称 Zookeeper Atomic Broadcast(Zookeeper 原子广播协议)。它是专门为分布式协调服务——Zookeeper,设计的一种支持崩溃恢复和原子广播的协议。
从设计上看,ZAB协议和 Raft 很类似。ZooKeeper集群中,只有一个Leader节点,其余均为Follower节点

Zab 协议包括两种基本的模式:
崩溃恢复 :一旦 Leader 服务器出现崩溃或者由于网络原因导致 Leader 服务器失去了与过半 Follower 的联系,那么就会进入崩溃恢复模式,崩溃恢复具有两个阶段:Leader 选举与初始化同步。当完成 Leader 选 举后,此时的 Leader 还是一个准 Leader,其要经过初始化同步后才能变为真正的 Leader。

恢复模式的两个原则: 1. 已被处理过的消息不能丢 2. 被丢弃的消息不能再现

消息广播:当集群中的 Learner 完成了初始化状态同步,那么整个 zk 集群就进入到了正常工作模式 了。

整个ZAB协议一共定义了三个阶段:

发现: 要求zookeeper集群必须选举出一个 Leader 进程,同时 Leader 会维护一个 Follower 可用客户端列表。将来客户端可以和这些 Follower节点进行通信。
同步: Leader 要负责将本身的数据与 Follower 完成同步,做到多副本存储。这样也是提现了CAP中的高可用和分区容错。Follower将队列中未处理完的请求消费完成后,写入本地事务日志中
广播: Leader 可以接受客户端新的事务Proposal请求,将新的Proposal请求广播给所有的 Follower。
三个阶段执行完为一个周期,在Zookeeper集群的整个生命周期中,这三个阶段会不断进行,如果Leader崩溃或因其它原因导致Leader缺失,ZAB协议会再次进入阶段一。

Zab协议的核心:定义了事务请求的处理方式
所有的事务请求必须由一个全局唯一的服务器来协调处理,这样的服务器被叫做 Leader服务器。其他剩余的服务器则是 Follower服务器。
Leader服务器 负责将一个客户端事务请求,转换成一个 事务Proposal,并将该 Proposal 分发给集群中所有的 Follower 服务器,也就是向所有 Follower 节点发送数据广播请求(或数据复制)
分发之后Leader服务器需要等待所有Follower服务器的反馈(Ack请求),在Zab协议中,只要超过半数的Follower服务器进行了正确的反馈后(也就是收到半数以上的Follower的Ack请求),那么 Leader 就会再次向所有的 Follower服务器发送 Commit 消息,要求其将上一个 事务proposal 进行提交。

7. Raft协议?

raft 算法保证在给定的一个任期最少要有一个 Leader。

raft 使用心跳机制来触发 Leader 的选举。

如果一台服务器能够收到来自 Leader 或者 Candidate 的有效信息,那么它会一直保持为 Follower 状态,并且刷新自己的 electionElapsed,重新计时。

Leader 会向所有的 Follower 周期性发送心跳来保证自己的 Leader 地位。如果一个 Follower 在一个周期内没有收到心跳信息,就叫做选举超时,然后它就会认为此时没有可用的 Leader,并且开始进行一次选举以选出一个新的 Leader。

为了开始新的选举,Follower 会自增自己的 term 号并且转换状态为 Candidate。然后他会向所有节点发起 RequestVoteRPC 请求, Candidate 的状态会持续到以下情况发生:(1)赢得选举 (2)其他节点赢得选举 (3)一轮选举结束,无人胜出
赢得选举的条件是: 一个 Candidate 在一个任期内收到了来自集群内的多数选票(N/2+1),就可以成为 Leader。

8. Paxos算法?

Paxos 算法是兰伯特在 1990 年提出了一种分布式系统共识算法。
兰伯特当时提出的 Paxos 算法主要包含 2 个部分:Basic Paxos 算法和Multi-Paxos 思想。
Raft 算法、ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进而来。

提议者(Proposer):也可以叫做协调者(coordinator),提议者负责接受客户端发起的提议,然后尝试让接受者接受该提议,同时保证即使多个提议者的提议之间产生了冲突,那么算法都能进行下去;
接受者(Acceptor):也可以叫做投票员(voter),负责对提议者的提议投票,同时需要记住自己的投票历史;
学习者(Learner):如果有超过半数接受者就某个提议达成了共识,那么学习者就需要接受这个提议,并就该提议作出运算,然后将运算结果返回给客户端。

区块链系统使用的共识算法需要解决的核心问题是 拜占庭将军问题 ,这和我们日常接触到的 ZooKeeper、Etcd、Consul 等分布式中间件不太一样。

9.分布式锁

分布式锁主要用于在分布式环境中保护跨进程、跨主机、跨网络的共享资源实现互斥访问,以达到保证数据的一致性。

redis实现思路:
如下是基本的算法,还有一种是redis官网提供的基于redLock算法实现的分布式锁,此处就不作介绍了算法
一、获取当前时间戳与锁的过时时间相加后获得锁要过时的时间,把这个要过时的时间设置为value,锁做为key。调用setnx方法,若是返回1证实锁不存在,能够成功获取锁,获取成功后,设置expire超市时间。返回获取锁apache
二、若是setnx返回0,证实原来锁存在,没有获取成功。而后调用get方法,获取第一步中存入的过时时间。与当前时间戳比较,若是当前时间大于过时时间,则证实锁已过时,调用getset方法,把新的时间存进去,返回获取锁成功。这里进行时间比较主要是应对expire执行失败,或服务重启状况下出现的没法释放锁的状况

  • Zookeeper分布式锁
    Zookeeper分布式锁参考
    在这里插入图片描述
    左边的整个区域表示一个Zookeeper集群,locker是Zookeeper的一个持久节点,node_1、node_2、node_3是locker这个持久节点下面的临时顺序节点。client_1、client_2、client_n表示多个客户端,Service表示需要互斥访问的共享资源。

思路:

在获取分布式锁的时候在locker节点下创建临时顺序节点,释放锁的时候删除该临时节点。客户端调用createNode方法在locker下创建临时顺序节点,然后调用getChildren(“locker”)来获取locker下面的所有子节点,注意此时不用设置任何Watcher。客户端获取到所有的子节点path之后,如果发现自己在之前创建的子节点序号最小,那么就认为该客户端获取到了锁。如果发现自己创建的节点并非locker所有子节点中最小的,说明自己还没有获取到锁,此时客户端需要找到比自己小的那个节点,然后对其调用exist()方法,同时对其注册事件监听器。之后,让这个被关注的节点删除,则客户端的Watcher会收到相应通知,此时再次判断自己创建的节点是否是locker子节点中序号最小的,如皋是则获取到了锁,如果不是则重复以上步骤继续获取到比自己小的一个节点并注册监听。当前这个过程中还需要许多的逻辑判断。

核心流程:

客户端A要获取分布式锁的时候首先到locker下创建一个临时顺序节点(node_n),然后立即获取locker下的所有(一级)子节点。
此时因为会有多个客户端同一时间争取锁,因此locker下的子节点数量就会大于1。对于顺序节点,特点是节点名称后面自动有一个数字编号,先创建的节点数字编号小于后创建的,因此可以将子节点按照节点名称后缀的数字顺序从小到大排序,这样排在第一位的就是最先创建的顺序节点,此时它就代表了最先争取到锁的客户端!此时判断最小的这个节点是否为客户端A之前创建出来的node_n,如果是则表示客户端A获取到了锁,如果不是则表示锁已经被其它客户端获取,因此客户端A要等待它释放锁,也就是等待获取到锁的那个客户端B把自己创建的那个节点删除。此时就通过监听比node_n次小的那个顺序节点的删除事件来知道客户端B是否已经释放了锁,如果是,此时客户端A再次获取locker下的所有子节点,再次与自己创建的node_n节点对比,直到自己创建的node_n是locker的所有子节点中顺序号最小的,此时表示客户端A获取到了锁!


版权声明:本文为feiyanaffection原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>