JAVA并发编程1--并发简介+任务调度算法

并发编程能够在一定程度上提升程序的运行速度，响应速度

为什么并发编程能够提高程序的运行速度？

多核处理器：

现代计算机体系结构中，多核处理器已经非常普遍。例如，服务器通常配备多个核心，通过并发编程，可以让程序的多个部分同时在不同的核心上运行。

逻辑处理器：

是一个虚拟元件（也即逻辑层面的，只有操作系统可见），又称为逻辑内核（逻辑处理器）（逻辑CPU），代表了你的CPU内核能够支持的线程数量，帮助CPU更高效地处理任务。如果该核支持超线程技术，那1颗内核可以当成2颗内核来发挥作用。每个线程都作为独立的CPU实例运行。

 内核：

是一个物理元件（也即可见可触及的实体），位于处理器（Processor）内部，用于处理繁杂的计算任务。单块CPU上能进行计算的芯片组的数量，如双核，四核等。

逻辑处理器为并发单元（线程或进程）提供执行环境，多个逻辑处理器支持多任务并发，提升程序执行速度。并发编程能充分利用逻辑处理器资源，通过合理调度提高利用率、实现负载均衡。

并发和并行：

为什么操作系统上可以同时运行多个程序而用户感觉不出来？

因为操作系统在同时运行多个进程时，通过调度算法和上下文切换的快速切换，会让用户产生多个任务同时运行的错觉。

并发和并行的区别

并发（concurrent）：并发是指在同一时间段内，多个任务都在执行，但在任意时刻，可能只有一个任务在真正运行，强调多个任务在时间上的重叠，是一种处理多个任务的能力，例如一个人在一天内要处理写报告、接听电话、回复邮件等多项任务，会在任务间快速切换，从一天看同时处理多任务，但某一时刻只能专注一项

并行（parallel）：并行是指在同一时刻，多个任务同时执行，依赖多核处理器、多台计算机等硬件资源，让多个任务在物理上同时进行，就像多个人同时分别进行写报告、接听电话、回复邮件的工作，这些任务在同一时刻都在实际进行中。

任务调度算法

参考文章：操作系统——调度算法_操作系统调度算法-CSDN博客

先来先服务(FCFS)

饥饿是进程或者作业长期得不到服务而产生的一种状态。

先来先服务(FCFS, First Come First Serve)
算法思想：从公平的角度考虑，类似于排队购物、打饭等。
算法规则：按照作业或者进程到达的先后顺序进行服务。
方法用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。
进程调度的方式：非抢占式算法。

是否会导致饥饿：不会导致饥饿。

例子：举一个 FCFS 算法的例子，如下图所示。

简单模拟时间轴表示其过程：

开始时间是上一个进程的结束时间
结束时间 = 开始时间 + 服务时间
周转时间 = 结束时间 - 到达时间
带权周转时间 = 周转时间 / 服务时间

优缺点：

优点：算法公平且实现简单；

缺点：排队在长作业或长进程后面的短作业或短进程需要等待很长的时间，带权周转时间很大，对短作业或进程的用户体验不好。所以先来先服务算法对长作业有利，对短作业不利。
 

短作业（进程）优先调度算法/最短时间优先(SJF)
 

最短时间优先(SJF, Shortest Job First)
算法思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间。
算法规则：最短的作业或者进程优先得到服务，这里的最短指的是要求服务的时间最短。
方法用于作业/进程调度：即可用于作业调度，也可以用于进程调度，用于进程调度时称为最短进程优先算法(SPF, Shortest Process First)。
进程调度的方式：最短时间优先和最短进程优先是非抢占式算法，但也有抢占式的算法——最短剩余时间优先算法。

是否会导致饥饿：会导致饥饿，如果源源不断的有短作业或短进程到来，可能会使得长作业或者长进程长时间的得不到服务，因此产生饥饿现象，如果一直得不到服务，则称为饿死。

最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)是每当有进程加入就绪队列发生改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列，此外，当一个进程完成时也需要重新调度。

例子：短进程优先算法的例子

简单模拟时间轴表示其过程：

SJF 算法默认是非抢占式的，该算法的平均等待时间、平均周转时间相对来说较短。在所有进程同时可运行时(或者所有进程几乎同时到达时)，采用 SJF 算法的平均等待时间和平均周转时间最少。

优缺点：

优点：有较短的平均等待时间和平均周转时间；

缺点：不太公平，对短作业有利，对长作业不利，可能产生饥饿现象，此外，作业或者进程的运行时间是由用户提供的，并不一定真实，所以不一定能做到真正的短作业优先。
 

最高响应比优先(HRRN)

最高响应比优先(HRRN, Highest Response Ratio Next) 算法就要综合作业或进程的运行时间和等待时间。
算法思想：综合考虑作业或进程的等待时间和要求服务的时间。
算法规则：在每次调度时先计算各个作业或进程的响应比，选择响应比最高的作业或进程为其服务。

由该公式可知，响应比一定是大于等于1的。
方法用于作业/进程调度：即可用于作业调度，也可用于进程调度。
进程调度的方式：非抢占式算法，所以只有当前运行的作业或进程主动放弃处理机时，才需要调度和计算响应比。

是否会导致饥饿：不会导致饥饿。

例子：最高响应比优先算法

（1）先执行A作业，其余再通过响应比判断执行哪个；

（2）根据响应比，执行D作业；

等待时间 = 上一个作业调入完成时间 - 该作业到达的时间

响应比高的先执行

R（B） = 1 + （6 - 3）/ 2 = 2.5
R（C） = 1 + （6 - 4）/ 4 = 1.5
R（D）= 1 + （6 - 4） / 1 = 3

（3）根据响应比，执行B作业；
R（B） = 1 + （7 - 3）/ 2 = 2
R（C） = 1 + （7 - 4）/ 4 = 0.75

（4）执行最后C作业。

优缺点：

综合考虑了等待时间和运行时间，当等待时间相同时，要求服务时间短的优先(SJF 算法的优点)；当要求服务时间相同时，等待时间长的优先(FCFS 算法的优点)。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

 

时间片轮转调度算法(RR)

时间片轮转(RR, Round-Robin)
算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
算法规则：按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
方法用于作业/进程调度：只能用于进程调度，只有作业放入内存建立了相应的进程后，才能被分配处理机时间片。
进程调度的方式：抢占式算法，由时钟装置发出时钟中断来通知 CPU 时间片已到。

是否会导致饥饿：不会导致饥饿。

例子

进程A、B、C、D需要运行的时间分别为20ms、10 ms、15 ms、5 ms，均在0时刻到达。到达的先后次序为A、B、C、D。如果时间片分别为1 ms和5ms，计算各个进程的带权周转时间和平均带权周转时间。

分析 在掌握了时间片轮转法概念的基础上，我们可以用一个执行时间图来形象地表示作进程的执行情况，帮助我们理解此题。具体如下：

根据执行时间图就可以计算各个进程的带权周转时间和平均带权周转时间了。这里要注意的是，要记住带权周转时间和平均带权周转时间的算术公式：

带权周转时间W，即：

 W = T/R

其中T为周转时间，R为实际运行时间。

平均带权周转时间为：

解：采用时间片轮转法进行调度，算法的性能指标如下：

如果在某一时刻，有一个新进程到达且有一个进程的时间片已到但是还没运行完，那在排序时，新到达的进程在前，该进程排在队尾。

时间片的大小：

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间，因此时间片不能太大。

另一方面，进程调度和切换是有代价的，如果时间片太小，会导致进程切换过于频繁，系统会花费大量的时机来处理进程切换，从而导致实际用于进程执行的时间比例减少，所以时间片也不能太小。一般来说，设计时间片时要让切换进程的开销占比不超过1%。

优缺点：

优点：公平，响应快，且适合于分时操作系统；

缺点：由于高频率的进程切换，因此有一定的系统开销，同时也不区分任务的紧急程度。
 

优先级调度

算法思想：随着计算机的发展，特别是实时操作系统系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
算法规则：每个作业或进程有各自的优先级，调度时选择优先级最高的作业或进程。
方法用于作业/进程调度：可用于作业调度，也可用于进程调度，还会用于I/O调度。
进程调度的方式：抢占式和非抢占式都有，区别在于非抢占式只需要在进程主动放弃处理机时进行调度，而抢占式的还需要在就绪队列变化时检查是否会发生抢占。

非抢占式优先级调度算法的例子

抢占式优先级调度算法的例子

通过这两个例子就可以看出两者的区别，即非抢占式优先级调度算法只需要在进程主动放弃处理机时进行调度，而抢占式优先级调度算法还需要在就绪队列变化时检查是否会发生抢占，然后再分配处理机。

合理地设置各类进程的优先级：
①系统进程优先级高于用户进程；
②前台进程优先级高于后台进程；
③操作系统更偏好 I/O 型进程(I/O 繁忙型进程)。

静态优先级和动态优先级
根据优先级是否可以动态地改变，可以将优先级分为静态优先级和动态优先级两种。静态优先级在创建进程时就已经确定，之后一直不变；动态优先级创建进程时有一个初始值，之后会根据情况动态地调整优先级。

动态优先级的调整时机：从追求公平、提升资源利用率等角度考虑。如果某进程在就绪队列中等待了很长时间，可以适当提升其优先级；如果某进程占用处理机运行了很长时间，可以适当降低其优先级；如果发现一个进程频繁地进行I/O操作，可以适当提升其优先级。
优缺点：优点是用优先级区分紧急程度、重要程度，适用于实时操作系统，可灵活地调整对各种作业或进程的偏好程度；缺点是若源源不断地有高优先级进程到来，则可能导致饥饿。
是否会导致饥饿：会导致饥饿。

多级反馈队列

算法思想：对其他调度算法的折中权衡。
算法规则：设置多级就绪队列，各级队列优先级从高到低，时间片从小到大；新进程到达时先进入第一级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经是在最下级的队列，则重新放回该队列队尾；只有第 k 级队列为空时，才会为 k+1 级队列头的进程分配时间片；被抢占处理机的进程重新放回原队列队尾。
方法用于作业/进程调度：只用于进程调度。
进程调度的方式：抢占式算法，在 k 级队列的进程运行过程中，若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾。

例子

注意

在执行的过程中，每执行完一个级别的时间片，若进程没有执行完，则该进程优先级下降，移动到下一级队列的队尾

在运行的时候，如果更高级别进入了一个新进程，即使当前运行的进程时间片还没运行完，也会被剥夺处理机，该进程在原队列队尾等待更高优先级的进程运行完成。

优缺点：

优点：

• 对于各类型进程相对公平(FCFS 的优点)；
• 每个新到达的进程都可以很快就得到响应(RR 的优点)；
• 短进程只用较少的时间就可完成(SPF 的优点)；不必实现估计进程的运行时间(避免用户作假)；
• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程 (可以将因 I/O 而阻塞的进程重新放回到原队列而不是优先级更低的下一级队列，这样 I/O 型进程就可以保持较高的优先级) 。

缺点：可能会导致饥饿。
是否会导致饥饿：被降级的进程可能会一直等待，因此会导致饥饿。

参考文章：操作系统——调度算法_操作系统调度算法-CSDN博客