操作系统中的调度算法是用于决定哪个进程或作业应该被分配CPU资源以进行执行的策略。

一、先来先服务调度算法（FCFS）

• 算法思想：从“公平”的角度考虑，先到先服务。
• 算法规则：先进入系统的作业/进程优先被挑选。
• 优点：公平、算法实现简单。
• 缺点：对长作业有利，对短作业不利。排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。

二、短作业优先调度算法（SJF）

• 算法思想：追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间。
• 算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）。
• 优点：相比先来先服务算法，其平均等待时间、平均周转时间、平均带权周转时间都更低。
• 缺点：不公平。对短作业有利，对长作业不利。作业/进程的运行时间是由用户提供，并不一定真实，不一定能做到真正的短作业优先。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。

SJF有两种变体：

• 非抢占式SJF：一旦进程被分配CPU，它将一直运行到完成，除非它自愿放弃。
• 抢占式SJF（也称为最短剩余时间优先调度算法SRTF）：每当有新进程加入就绪队列或当前进程完成时，调度器都会检查并可能抢占当前运行的进程，如果新进程的剩余时间更短。

三、响应比最高者优先调度算法（HRRF）

• 算法思想：选择等待时间和要求服务时间都较短的作业/进程优先调度。
• 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。响应比=（等待时间+要求服务时间）/要求服务时间。
• 优点：既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。等待时间相同时，要求服务时间短的优先（SJF的优先，对短作业有利）。要求服务时间相同时，等待时间长的优先（FCFS的优点）。随着等待时间越来越长，其响应比也会越来越大，从而避免了长作业饥饿的问题（长作业有利）。
• 缺点：要进行响应比计算，增加了系统开销。

四、时间片轮转调度算法（RR）

• 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。

• 算法规则：调度程序每次把CPU分配给就绪队列首进程/线程使用一个时间间隔（称为时间片），就绪队列中的每个进程/线程轮流运行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

• 时间片的选取：时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。

  • 最常用的轮转法是等时间片轮转法，每个进程轮流运行相同时间片。
  • 改进的轮转法对于不同的进程分配不同的时间片，时间片的长短可以动态修改。

• 优点：公平、响应快，适用于分时操作系统。

• 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急性。

五、优先级调度算法（PSA）

• 算法思想：根据任务的紧急程度来决定处理顺序。

• 算法规则：根据确定的优先级选取进程/线程，每次总是选择就绪队列中优先级最高者运行。

• 进程/线程优先级的确定方式：根据优先级是否随时间而变，进程/线程优先级的确定有静态和动态两种方式。

  • 静态优先级：在进程/线程创建时确定，此后不再改变。优先级主要由进程类型、资源需求、时间需求和用户需求决定。
  • 动态优先级：会根据进程的执行情况和系统需求进行调整。

• 优点：能够确保紧急任务得到及时处理。

• 缺点：可能导致优先级低的进程长时间得不到执行（饥饿问题），且优先级的确定可能复杂且主观。

六、多级反馈队列调度算法（MLFQ）

• 算法规则：

  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
  2. 新进程首先进入最高优先级队列，按照FCFS+RR的方式进行执行，若进程未能在时间片内完成，则下沉到下一级队列。
  3. 只有当上一级队列的所有任务都执行过一个时间片后，才会执行下边一级队列。

• 优点：

  1. 提高了系统吞吐量和缩短了平均周转时间。
  2. 照顾了短进程，并为I/O型进程提供了较好的响应。
  3. 不必估计进程的执行时间，能够动态调节。

以下分别针对先来先服务（FCFS）、短作业优先（SJF）、高响应比优先（HRRN）这三种进程调度算法各举一个例子进行说明：

先来先服务（FCFS）

• 例子：

  • 假设有四个进程P1、P2、P3、P4，它们分别按照如下顺序和时间到达就绪队列：P1（0时刻到达，需要运行5个时间单位），P2（1时刻到达，需要运行3个时间单位），P3（2时刻到达，需要运行1个时间单位），P4（3时刻到达，需要运行2个时间单位）。
  • 使用FCFS调度算法，调度顺序为：P1→P2→P3→P4。

• 说明：

  • FCFS算法按照进程到达就绪队列的先后顺序进行调度，先到达的进程先得到服务。
  • 在这个例子中，P1最先到达，因此它首先得到服务，然后是P2、P3和P4。

短作业优先（SJF）

• 例子：

  • 假设有四个进程P1、P2、P3、P4，它们的到达时间和需要的运行时间如下：P1（0时刻到达，需要运行8ms），P2（1ms时刻到达，需要运行4ms），P3（2ms时刻到达，需要运行9ms），P4（3ms时刻到达，需要运行5ms）。
  • 使用SJF调度算法，调度顺序为：P2→P4→P1→P3。

• 说明：

  • SJF算法选择当前已到达且运行时间最短的进程进行服务。
  • 在这个例子中，P2在到达时是已到达进程中运行时间最短的，因此它首先得到服务。接着是P4（因为它比P1和P3都短），然后是P1，最后是P3。
  • SJF算法可以是抢占式的（称为最短剩余时间优先算法SRTN），也可以是非抢占式的。在这个例子中，我们假设使用的是非抢占式的SJF算法。

高响应比优先（HRRN）

• 例子：

  • 假设有四个作业J1、J2、J3、J4，它们的提交时间和需要的运行时间如下：J1（8:00提交，需要0.5小时），J2（8:30提交，需要0.1小时），J3（8:50提交，需要0.4小时），J4（9:00提交，需要0.1小时）。
  • 使用HRRN调度算法，调度次序可能为：J1→J3→J2→J4（具体调度次序还取决于每个作业的实际等待时间和要求服务时间的比值，即响应比）。

• 说明：

  • HRRN算法综合考虑了作业的等待时间和要求服务时间，选择响应比最高的作业进行服务。
  • 响应比的计算公式为：响应比=（等待时间+要求服务时间）/要求服务时间。
  • 在这个例子中，我们需要计算每个作业的响应比，并根据响应比的高低进行调度。例如，在J1运行完成后，我们可以计算J2、J3和J4的响应比，并选择响应比最高的作业进行服务。