• 1. 进程和线程
  • 1.1 并发和并行
  • 1.2 进程
    • 1.2.1 进程的状态
    • 1.2.2 进程的控制结构
      • 1.2.2.1 包含的信息
      • 1.2.2.2 如何组织
    • 1.2.3 进程的控制
      • 1.2.3.1 创建进程
      • 1.2.3.2 终止进程
      • 1.2.3.3 阻塞进程
      • 1.2.3.4 唤醒进程
    • 1.2.4 进程的上下文切换
      • 1.2.4.1 CPU 上下文
      • 1.2.4.2 CPU 上下文切换
      • 1.2.4.3 进程的上下文切换
      • 1.2.4.4 发生切换的场景
  • 1.3 线程
    • 1.3.1 优缺点
    • 1.3.2 进程和线程
    • 1.3.3 线程的上下文切换
    • 1.3.4 线程的实现
      • 1.3.4.1 用户线程
      • 1.3.4.2 内核线程
      • 1.3.4.3 轻量级进程
  • 1.4 调度
    • 1.4.1 调度时机
    • 1.4.2 调度原则
    • 1.4.3 单核 CPU 系统调度算法
      • 1.4.3.1 先来先服务调度算法
      • 1.4.3.2 最短作业优先调度算法
      • 1.4.3.3 高响应比优先调度算法
      • 1.4.3.4 时间片轮转调度算法
      • 1.4.3.5 最高优先级调度算法
      • 1.4.3.6 多级反馈队列调度算法

1. 进程和线程

小林coding

1.1 并发和并行

1.2 进程

通过编译后就会生成二进制可执行文件，当我们运行这个可执行文件后，它会被装载到内存中，接着 CPU 会执行程序中的每一条指令，那么这个运行中的程序，就被称为进程（Process）。

1.2.1 进程的状态

各种状态：

• 运行状态（Running）：正在被执行，该时刻进程占用CPU
• 就绪状态（Ready）：可运行，由于其它进程处于运行状态而暂时停止运行
• 阻塞状态（Blocked）：该进程正在等待某一事件的发生（例如等待输入/输出操作的完成）而暂时停止运行，此时即便给它 CPU 控制权，也无法运行
• 创建状态（new）：进程正在被创建
• 结束状态（Exit）：进程正在被销毁

还有一个状态来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态：

• 阻塞挂起状态（Suspended）：进程在外存（硬盘）并等待某个事件的出现；
• 就绪挂起状态（Suspended）：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

导致进程挂起的原因主要有以下几种情况：

• 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程；
• 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程；
• 挂起阻塞状态的进程，避免浪费物理内存。

1.2.2 进程的控制结构

在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

1.2.2.1 包含的信息

进程描述信息：

• 进程标识符：每个进程都有唯一的标识符
• 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务

进程控制和管理信息：

• 进程的状态
• 进程的优先级：进程抢占 CPU 时的优先级

资源分配清单：

• 有关内存地址空间或虚拟地址空间信息
• 打开的文件列表
• 使用的 I/O 设备信息

CPU 相关信息：

• CPU 中各个寄存器的值：当进程被切换时，CPU 的状态信息都会被保存到相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

1.2.2.2 如何组织

通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

• 把所有处于就绪状态的进程链在一起，称为就绪队列；
• 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
• 对于运行队列在单核 CPU 系统中只有一个运行指针，因为单核 CPU 在某个时间，只能运行一个程序。

除了链接的组织方式，还有索引方式。将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。

一般会选择链表，因为可能面临进程创建，销毁等调度导致进程状态发生变化，所以链表能够更加灵活的插入和删除。

1.2.3 进程的控制

1.2.3.1 创建进程

操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源。

创建进程的过程如下：

• 申请一个空白的 PCB，并向 PCB 中填写一些描述、控制和管理进程的信息，比如进程的唯一标识等；
• 为该进程分配运行时所必需的资源，比如内存资源；
• 将 PCB 插入到就绪队列，等待被调度运行；

1.2.3.2 终止进程

有 3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。

• 当子进程被终止时，其在父进程处继承的资源应当还给父进程。
• 而当父进程被终止时，该父进程的子进程就变为孤儿进程，会被 1 号进程收养，并由 1 号进程对它们完成状态收集工作。

过程如下：

• 查找需要终止的进程的 PCB
• 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程
• 如果还有子进程，则应将子进程交给 1 号进程接管
• 将该进程所拥有的全部资源归还给操作系统
• 将其从 PCB 所在的队列中删除

1.2.3.3 阻塞进程

当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。

过程如下：

• 找到将要被阻塞进程标识号所对应的 PCB
• 如果该进程为运行状态，则保护其现场，将状态转换为阻塞状态，停止运行
• 将该 PCB 插入到阻塞队列中

1.2.3.4 唤醒进程

如果某进程正在等待阻塞事件的完成，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。

过程如下：

• 在该事件的阻塞队列中找到相应进程的 PCB
• 将其从阻塞队列中移出，并置其状态为 就绪状态
• 把该 PCB 插入到就绪队列中，等待调度程序调度

1.2.4 进程的上下文切换

一个进程切换到另一个进程运行，称为进程的上下文切换。

1.2.4.1 CPU 上下文

大多数操作系统都是多任务，通常支持大于 CPU 数量的任务同时运行。实际上，这些任务并不是同时运行的，只是因为系统在很短的时间内，让各个任务分别在 CPU 运行，于是就造成同时运行的错觉。

在每个任务运行前，CPU 需要知道任务从哪里加载，又从哪里开始运行。

所以，操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器。

• CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存（缓存）。
• 程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。

所以说，CPU 寄存器和程序计数是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。

1.2.4.2 CPU 上下文切换

大多数操作系统都是多任务，通常支持大于 CPU 数量的任务同时运行。实际上，这些任务并不是同时运行的，只是因为系统在很短的时间内，让各个任务分别在 CPU 运行，于是就造成同时运行的错觉。

在每个任务运行前，CPU 需要知道任务从哪里加载，又从哪里开始运行。

所以，操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器。

• CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存（缓存）。
• 程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。

所以说，CPU 寄存器和程序计数是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。

CPU 上下文切换就是把先前一个任务的 CPU 上下文（CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文，最后再跳转到程序计数器所指的新位置，运行新任务。

内核会存储保存下来的上下文信息，当任务再次分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来是连续运行的。

可以根据任务的不同，把 CPU 上下文切换分成：

• 进程上下文切换
• 线程上下文切换
• 中断上下文切换

1.2.4.3 进程的上下文切换

进程是由内核管理和调度的，所以进程的切换只能发生在内核态。

所以，进程的上下文切换不仅包含了 虚拟内存、栈、全局变量 等 用户空间 的资源，还包括了 内核堆栈、寄存器 等 内核空间 的资源。

通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后加载到 CPU 中，这使得这个进程可以执行。

1.2.4.4 发生切换的场景

• 分配给进程的时间片耗尽了。

  CPU 时间被划分为一段段的时间片，这些时间片被轮流分配给各个进程，以保障所有进程都可以得到公平的调度。时间片耗尽后，进程变为就绪状态

• 进程运行时遇到系统资源不足（比如内存不足）需要等待时。

  当进程要等待满足资源条件才能运行时，会被挂起，由系统调度其他进程运行

• 进程主动将自己挂起。

  比如通过 sleep 函数

• 当有优先级更高的进行运行时。

  为了保证高优先级进程的运行，当前现场会被挂起，运行高优先级的进程

• 发生硬件中断时。

  CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序

  1.3 线程

线程（Thread）是是进程当中的一条执行流程，是比进程更小的能独立运行的基本单位。

同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

1.3.1 优缺点

优点：

• 一个进程可以同时存在多个线程
• 各个线程之间可以并发执行
• 各个线程之间可以共享地址空间和文件等资源

缺点：

当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java 语言中的线程奔溃不会造成进程崩溃，具体分析原因可以看这篇：线程崩溃了，进程也会崩溃吗？）。

1.3.2 进程和线程

• 进程是资源（包括内存、打开的文件等）分配的基本单位，线程是 CPU 调度的基本单位；这是它们最大的区别。
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
• 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
• 线程能减少并发执行的时间和空间开销；

线程相比进程能减少开销，体现在：

• 线程的创建时间比进程快

  因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；

• 线程的终止时间比进程快

  因为线程释放的资源相比进程少很多；

• 同一个进程内的线程切换比进程切换快

  因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；

• 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

1.3.3 线程的上下文切换

线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。

所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

对于线程和进程，我们可以这么理解：

• 当进程只有一个线程时，可以认为进程就等于线程；
• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

线程上下文切换：

• 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
• 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据（栈、寄存器等）等不共享的数据；

所以，线程的上下文切换相比进程，开销要小很多。

1.3.4 线程的实现

线程的实现方式：

• 用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，由用户态的线程库来完成线程的管理
• 内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程
• 轻量级进程（LightWeight Process）：在内核中支持用户线程

用户线程和内核线程的三种对应关系：

• 多对一，多个用户线程对应一个内核线程
• 一对一，一个用户线程对应一个内核线程
• 多对多，多个用户线程对应多个内核线程

1.3.4.1 用户线程

用户线程是基于用户态的线程管理库来实现的，那么线程控制块（Thread Control Block, TCB） 也是在库里面来实现的，对于操作系统而言是看不到这个 TCB 的，它只能看到整个进程的 PCB。

所以，用户线程的整个线程管理和调度，操作系统不参与，由用户级线程库来完成线程的管理，包括线程的创建、终止、同步和调度等。

用户级线程的模型，也就类似前面提到的多对一的关系，即多个用户线程对应同一个内核线程，如下图所示：

优点：

• 每个进程都需要有它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统；
• 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快；

缺点：

• 由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了。
• 当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的。
• 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢；

1.3.4.2 内核线程

内核线程是由操作系统管理的，线程对应的 TCB 自然是放在操作系统里的，这样线程的创建、终止和管理都是由操作系统负责。

内核线程的模型，也就类似前面提到的一对一的关系，即一个用户线程对应一个内核线程，如下图所示：

优点：

• 在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行；
• 时间片分配给线程，多线程的进程获得更多的 CPU 运行时间；

缺点：

• 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB；
• 线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大；

1.3.4.3 轻量级进程

**轻量级进程（Light-weight process，LWP）是内核支持的用户线程，一个进程可以有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，而且 LWP 由内核管理并像普通进程一样被调度。

在大多数系统中，LWP 和普通进程的区别在于它只有一个最小的执行上下文和调度程序所需的统计信息。一般来说，一个进程代表程序的一个实例，而 LWP 代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息，所以 LWP 也不带有这样的信息。

在 LWP 之上也是可以使用用户线程的，那么 LWP 与用户线程的对应关系就有三种：

• 1 : 1，即一个 LWP 对应 一个用户线程；
• N : 1，即一个 LWP 对应多个用户线程；
• M : N，即多个 LWP 对应多个用户线程；

下图是 LWP 模型：

1 : 1 模式

一个用户线程对应到一个 LWP 再对应到一个内核线程，如上图的进程 4，属于此模型。

• 优点：实现并行，当一个 LWP 阻塞，不会影响其他 LWP；
• 缺点：每一个用户线程，就产生一个内核线程，创建线程的开销较大。

N : 1 模式

多个用户线程对应一个 LWP 再对应一个内核线程，如上图的进程 2，线程管理是在用户空间完成的，此模式中用户的线程对操作系统不可见。

• 优点：用户线程要开几个都没问题，且上下文切换发生在用户空间，切换的效率较高；
• 缺点：一个用户线程如果阻塞了，则整个进程都将会阻塞，另外在多核 CPU 中，是没办法充分利用 CPU 的。

M : N 模式

根据前面的两个模型混搭一起，就形成 M:N 模型，该模型提供了两级控制，首先多个用户线程对应到多个 LWP，LWP 再一一对应到内核线程，如上图的进程 3。

• 优点：综合了前两种优点，大部分的线程上下文发生在用户空间，且多个线程又可以充分利用多核 CPU 的资源。

组合模式

如上图的进程 5，此进程结合 1:1 模型和 M:N 模型。开发人员可以针对不同的应用特点调节内核线程的数目来达到物理并行性和逻辑并行性的最佳方案。

1.4 调度

选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序（scheduler）。

说明：本小节的进程指只有主线程的进程。

1.4.1 调度时机

进程状态的变化会触发操作系统的调度：

• 就绪态变成运行态
• 运行态变成阻塞态
• 运行态变成结束态

因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给 CPU 运行，或者是否让当前进程从 CPU 上退出来而换另一个进程运行。

另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：

• 非抢占式调度算法，挑选一个进程，然后让该进程一直运行，直到被阻塞或退出，才会调用另外一个进程，不理会时钟中断。
• 抢占式调度算法，挑选一个进程，然后让该进程只运行某段时间，若时间片耗尽之后，其仍在运行，那么就把它挂起，接着从就绪队列挑选另一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。此时也会触发调度任务。

1.4.2 调度原则

1. 为了提高 CPU 利用率，在发送 I/O 事件这种致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。
2. 有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着 CPU，会造成系统吞吐量（CPU 在单位时间内完成的进程数量）的降低。要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。
3. 从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间。进程的周转时间越小越好，如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。
4. 处于就绪队列的进程，也不能等太久，当然希望这个等待的时间越短越好，这样可以使得进程更快的在 CPU 中执行。所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则。
5. 对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则就会影响用户体验了。所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。

针对上面的五种调度原则，总结成如下：

• CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
• 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
• 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
• 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

1.4.3 单核 CPU 系统调度算法

以下是单核 CPU 系统中常见的调度算法。

1.4.3.1 先来先服务调度算法

非抢占式的先来先服务（First Come First Serve, FCFS）算法。

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

FCFS 对长作业有利，不利于短作业。适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

1.4.3.2 最短作业优先调度算法

最短作业优先（Shortest Job First, SJF）调度算法，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

1.4.3.3 高响应比优先调度算法

高响应比优先 （Highest Response Ratio Next, HRRN）调度算法，每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。权衡了短作业和长作业。

• 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行；
• 如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；

Note

一个进程要求服务的时间是不可预估的。所以，高响应比优先调度算法是「理想型」的调度算法，现实中是实现不了的。

1.4.3.4 时间片轮转调度算法

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

• 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程；
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

时间片的长度是一个很关键的点：

• 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
• 如果设得太长又可能引起对短作业进程的响应时间变长。

因此，在时间片轮转调度算法中，选择合适的时间片大小需要综合考虑系统的特点、作业的类型和需求。

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。

1.4.3.5 最高优先级调度算法

最高优先级（Highest Priority First，HPF）调度算法，调度程序能从就绪队列中选择最高优先级的进程进行运行。

进程的优先级可以分为：

• 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
• 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

1.4.3.6 多级反馈队列调度算法

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

• 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
• 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

如何工作：

• 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
• 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
• 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
• priority boost（优先级提升）机制。ChatGPT【基本思想是周期性地提升处于低优先级队列中的进程的优先级。通过优先级提升机制，长时间等待的进程可以在一段时间后获得更高的优先级，这样它们有更大的机会被调度执行，从而减少等待时间并提高响应性。】也可以防止防止一直来新的任务让低优先级的长任务饿死。

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。