什么是上下文切换

CPU 利用时间片轮询来为每个任务都服务一定的时间，然后把当前任务的状态保存下来，继续服务下一个任务。任务的状态保存及再加载的过程叫做线程的上下文切换。

进程：指一个运行中的程序的实例。在一个进程内部可以有多个线程同时运行，并与创建它的进程共享同一地址空间（一段内存区域）和其他资源。

上下文：指线程切换时 CPU 寄存器和程序计数器所保存的当前线程的信息

寄存器：指 CPU 内存容量较小但速度很快的内存区域（与之对应的是 CPU 外部相对较慢的 RAM 主内存）。寄存器通过对常用值（通常是运行的中间值）的快速访问来加快计算机程序运行的速度。

程序计数器：是一个专用的寄存器，用于表明指令序列中 CPU 正在执行的位置，存储的值为正在执行的指令的位置或者下一个将被执行的指令的位置，这依赖于特定的系统。

上下文切换：指的就是内核（操作系统的核心）在 CPU 上对进程或者线程进程切换。上下文切换过程中的信息被保存在进程控制块（PCB-Process Control Block）中，PCB 又被称作切换帧（SwitchFrame）。上下文切换的信息会一直被保存在 CPU 的内存中，直到被再次使用。

1. 挂起一个线程，将这个线程在 CPU 中的状态（上下文信息）存储与内存的 PCB 中。
2. 在 PCB 中检索下一个线程的上下文并将其在 CPU 的寄存器中恢复。
3. 跳转到程序计数器所指向的位置（即跳转到线程被中断时的代码行）并恢复该线程。
   

引起上下文切换的原因

1. 当前正在执行的任务完成，系统的 CPU 正常调度下一个任务
2. 当前正在执行的任务遇到 I/O 等阻塞操作，调度器挂起此任务，继续调度下一个任务。
3. 多个任务并发抢占锁资源，当前任务没有抢到锁资源，被调度器挂起，继续调度下一个任务。
4. 用户的代码挂起当前任务，比如线程执行的 sleep 方法，让出 CPU。
5. 硬件中断。

上下文切换带来的问题

上下文切换会导致额外的开销，常常表现为高并发执行时速度会慢串行，因此减少上下文切换次数便可以提高多线程程序的运行效率。

● 直接消耗：指的是CPU寄存器需要保存和加载, 系统调度器的代码需要执行, TLB实例需要重新加载, CPU 的pipeline需要刷掉

● 间接消耗：指的是多核的cache之间得共享数据, 间接消耗对于程序的影响要看线程工作区操作数据的大小

如何减少上下文切换

减少上下文切换的方法有无锁的并发编程、CAS算法、使用最少线程和使用协程。

1. 无锁并发编程，多线程处理数据时，可以用一些办法来避免使用锁，如将数据的ID按照Hash取模分段，不同的线程处理不同段的数据
2. CAS算法，Java的Atomic包使用CAS算法来更新数据，而不需要加锁
3. 使用最少线程
4. 协程，单线程里实现多任务的调度，并在单线程里维持多个任务间的切换

合理设置线程数目既可以最大化利用CPU，又可以减少线程切换的开销。

高并发，低耗时的情况，建议少线程。
低并发，高耗时的情况：建议多线程。
高并发高耗时，要分析任务类型、增加排队、加大线程数

Java中的线程调度

在实现上下文切换的时候，就要考虑 Java 的线程调度问题。
所有的Java虚拟机都有一个线程调度器，用来确定那个时刻运行那个线程。

线程调度主要包含两种：抢占式线程调度器和协同式线程调度器。

抢占式调度

抢占式调度指每个线程都以抢占的方式获取 CPU 资源并快速执行，在执行完毕后立刻释放 CPU 资源，具体哪些资源能抢占到 CPU 资源时由操作系统来做决定的，在抢占式调度模式下，每个线程对 CPU 资源的申请地位都是相等的，从概率上讲每个线程都是有机会获得同样的 CPU 执行时间片并发执行的。抢占式调度适用于多线程并发执行的情况，在这种机制下一个线程的堵塞不会导致整个进程性能的下降。

协同式调度

协同式调度指的是某一个线程在执行完后主动通知操作系统将 CPU 资源切换到另一个线程上执行。线程对 CPU 的持有时间是由线程自身控制的，线程切换更加透明，更适合多个线程交替执行某些任务的情况。

协同式调度有一个缺点：如果某一个线程因为外部原因（可能是磁盘 I/O 阻塞、网络 I/O 阻塞、请求数据库等待）运行阻塞，那么可能导致整个系统阻塞甚至崩溃。

Java中使用的线程调度：抢占式

在 Java 当中，采用的是抢占调度的方式来实现内部的线程调度，Java 会为每个线程都按照优先级高低分配不同的 CPU 时间片，且优先级高的线程优先执行。优先级低的线程只是获取 CPU 时间片的优先级被降低，但不会永久分配不到 CPU 时间片。 Java 的线程调度在保障效率的前提下尽可能保障线程调度的公平性。

线程让出 CPU 的情况

1. 当前运行的线程主动放弃 CPU，例如运行中的线程调用 yield() 方法放弃 CPU 的使用权。
2. 当前运行的线程进入阻塞状态，例如调用文件读取 I/O 操作，锁等待、Socket 等待。
3. 当前线程运行结束，即运行完 run() 里面的任务。

进程调度算法

进程调度算法包括优先调度算法、高优先权优先调度算法和基于时间片的轮转调度算法。
其中：
优先调度算法分为先来先服务调度算法和短作业优先调度算法；

高优先权优先调度算法分为非抢占式优先权算法、抢占式优先权调度算法和高响应比优先调度算法；

基于时间片的轮转调度算法分为时间片轮转算法和多级反馈队列调度算法。

优先调度算法

优先调度算法包含了先来先服务调度算法和短作业优先调度算法。

先来先服务调度算法

先来先服务调度算法是指每次调度时都从队列中选择一个或多个最早进入该队列的作业。为其分配资源，创建进程和放入就绪队列。调度算法在获取到可用的 CPU 资源时会从就绪队列中选择一个最早进入队列的进程，为其分配 CPU 资源并运行，该算法优先运行最早进入的任务，实现简单且相对公平。

短作业优先调度算法

短作业优先调度算法是指每次调度的时候都从对列中选择一个或若干个预估运行时间最短的作业，为其分配资源、创建线程和放入就绪队列。调度算法在获取到可用的 CPU 资源时，就会从就绪队列中选出一个预估运行时间最短的进程，为其分配 CPU 资源并运行。该算法优先运行短时间作业，以提高 CPU 整体的利用率和系统运行效率，某些大任务可能会出现长时间得不到调度的情况。

高优先级优先调度算法

高优先级优先调度算法在定义任务的时候为每个任务都设置了不同的优先权，在进行任务调度时优先权最高的任务首先被调度，这样资源的分配将更加灵活，具体包含非抢占式优先调度算法、抢占式优先调度算法和高响应比优先调度算法。

非抢占式优先调度算法

非抢占式优先调度算法在每次调度的时都从队列中选择一个或多个优先权最高的作业，为其分配资源、创建进程和放入就绪队列中，调度算法在获取到可用的 CPU 资源的时候会从就绪队列中选出一个优先权最高的进程，为其分配 CPU 资源并运行。进程在运行的过程中一旦持有该 CPU，直到进程执行完毕或者发生异常而放弃该 CPU。
该算法优先运行优先权高的作业，一旦将 CPU 分配给某个进程，就不会主动回收 CPU 资源，直到任务主动放弃。

抢占式优先调度算法

抢占式优先调度算法首先把 CPU 资源分配给优先权最高的任务并运行，但如果在运行过程中出现比当前允许任务优先权更高的任务，调度算法就会暂停运行该任务并回收 CPU 资源，为其分配新的优先权更高的任务。该算法真正保障了 CPU 在整个运行过程当中是完全按照任务的优先权分配资源的，这样如果临时加入一个紧急的作业，也可以保障这个作业会在第一时间被执行。

高响应比优先调度算法

高响应比优先调度算法使用了动态优先权的感念，即任务的执行时间越短，其优先权越高，任务的等待时间越长，优先权越高。
这样既保障了快速、并发地执行短作业，也保障了优先权低但长时间等待的任务也有被调度的可能性。

优先权变化规律：
● 在作业的等待时间相同时，运行时间越短，优先权越高，在这种情况下遵循的是短作业优先原则。
● 在作业的运行时间相同时，等待时间越长，优先权越高，在这种情况下遵循的是先来先服务原则。
● 作业的优先权随作业等待时间的增加而不断提高，加大了长作业获取 CPU 资源的可能性。

高响应比优先调度算法在保障效率（短作业优先能在很大程度上提高 CPU 的使用率和系统性能）的基础上尽可能的提高了调度的公平性（随着任务等待时间的增加，优先权提高，遵循了先来先到原则）

时间片的轮转调度算法

时间片的轮转调度算法将 CPU 资源分为不同的时间片，不同的时间片为不同的任务服务，具体包括时间片轮转法和多级反馈队列调度算法。

时间片轮转法

时间片轮转法指按照先来先服务原则从就绪队列中取出一个任务，并为该任务分配一定的 CPU 时间片区运行，在进程使用完 CPU 时间片后由一个时间计时器发出时钟计数器发出时钟中断请求，调度器在收到时钟中断请求信号停止该进程的运行并将该进程放入就绪队列的队尾，然后从就绪队列的对首取出一个任务并为其分配 CPU 时间片区执行。这样，就绪队列中的任务就将轮流获取一定的 CPU 时间片去运行。

多级反馈队列调度算法

多级反馈队列调度算法是在时间片轮询算法上设置多个就绪队列，并为每个就绪队列都设置不同的优先权。队列的优先权越高，队列中的任务被分配的时间片越大。默认第一个队列优先权最高，其他次之。

多级反馈队列调度算法的调度流程为：
在系统收到新的任务后，首先将其放入一个就绪队列的队尾，按先来先服务算法排队等待调度。若该进程在规定的 CPU 时间片内运行完成或者运行过程中出现错误，则退出进程并从系统中移除该任务；如果该进程在规定的 CPU 时间片内未运行完成，则将该进程转入第 2 队列的队尾调度执行；如果该进程在第 2 队列中运行一个 CPU 时间片后仍未完成，则将其放入第 3 队列，以此类推，在一个长作业从第 1 队列依次降到第 n 队列后，在第 n 队列中便以时间片轮转的方式运行。

在多级反馈队列调度算法中遵循以下原则：
● 仅在第一个队列为空的时候，调度器才调度第 2 队列中的任务。
● 仅在第 1~（n-1）队列均为空的时候，调度器才会调度第 n 队列中的进程
● 如果处理器正在为第 n 队列中的某个进程服务，此时有新进程进入优先权较高的队列（第 1 ~（n-1）中的任何一个队列），则此时新进程井抢占正在运行的进程的处理器，即调度器停止正在运行的进程并将其放回第 n 队列的末尾，把处理器分配给新来的高优先权进程。

多级反馈调度算法相对来说是比较复杂的，它充分考虑了先来先服务调度算法和时间轮询算法的优势，使得对进程的调度更加的合理。