25新考点¶

进程间通信–信号¶

信号的概念¶

信号是一种异步的、非阻塞的通信机制（进程不需要通过任何操作等待信号到达），用于通知接收进程某个事件已经发生。例如，SIGINT信号通常由 Ctrl+C触发，用于终止进程。
信号（Signal）也叫“用户态中断”，用于异步通知进程某个事件的发生，每个信号都有一个唯一的编号和一个对应的处理动作。当某个信号发生时，内核会向相应的进程发送该信号，并触发预设的信号处理函数或执行默认操作。Linux信号也可以称为软中断，是在软件层次上对中断机制的一种模拟。在原理上，一个进程收到一个信号与处理器收到一个中断请求可以说是一样的
信号通常用于简单的事件通知，如终止进程、暂停执行等，而不适合用于复杂的数据传输任务。
信号可以直接进行用户空间进程和内核进程之间的交互，内核进程也可以利用它来通知用户空间进程发生了哪些系统事件

信号的来源¶

硬件来源：
硬件信号触发：某些硬件操作可能会触发特定的信号。例如，浮点除零操作会触发SIGFPE信号。
硬件异常：硬件异常，如内存访问越界（段错误，SIGSEGV）或非法指令，也会导致信号的产生。
软件来源：
系统调用：通过系统提供的函数，如kill()、raise()、alarm()和setitimer()等，可以显式地向进程发送信号。
用户输入：用户通过终端输入特定的字符组合（如Ctrl+C），操作系统会向当前前台进程发送SIGINT信号。
系统事件：系统内部发生的事件，如子进程退出，会导致父进程收到SIGCHLD信号。
定时器：通过alarm()或setitimer()设置的定时器到期时，会向进程发送SIGALRM信号。

信号的特点¶

简洁性：信号是一种轻量级的进程间通信方式，不涉及复杂的数据传输。
异步性：信号可以在任何时间发送给进程，不需要进程主动去检查或等待。
可配置性：进程可以指定对信号的处理方式，包括忽略、捕获并自定义处理函数或执行默认操作。

实际应用中的使用场景：¶

程序终止：通过发送SIGTERM信号来请求进程正常退出，给予进程机会进行资源释放和状态保存。
用户交互：通过发送SIGINT信号来中断长时间运行的命令行程序，使用户能够及时终止不必要的操作。
守护进程管理：在服务管理系统中，通过发送不同信号来控制守护进程的启动、停止和重启。
错误检测与处理：利用信号来报告和处理程序运行时遇到的严重错误，如段错误（SIGSEGV）。

信号分类¶

在linux系统中，通过kill -l命令，可以查看所有的信号

常见的信号：

SIGINT：终端中断信号，通常由用户输入中断字符（如Ctrl+C）产生。
SIGKILL：强制终止信号，无法被捕获或忽略。
SIGTERM：默认的终止信号，进程可以捕获并进行清理工作。
SIGCHLD：子进程终止时，父进程收到的信号。
SIGALRM：定时器信号，由alarm函数设置。

信号传递和响应¶

在 Linux 中，信号的传递流程通常遵循以下步骤：

信号产生：信号可以由内核、操作系统或者应用程序生成。常见的信号产生方式包括用户在终端按下键盘快捷键产生的信号，以及系统调用执行过程中出现的异常情况。
信号传递：一旦信号被产生，内核会把信号传递给目标进程。目标进程可以是正在等待信号的进程，或者正在执行的进程。如果信号没有被阻塞并且未被忽略，内核将会将信号传递给进程。
信号处理：一旦进程接收到信号，内核会检查信号的处理方式。根据注册的信号处理方式，可以有以下几种情况：
忽略信号：即对信号不做任何处理，但是两个信号不能忽略: SIGKILL 以及 SIGSTOP 。
捕捉信号：当信号发生时，执行用户自定义的信号处理函数。
执行默认操作：对于大多数信号，操作系统定义了默认的行为。这些默认行为通常是终止进程，生成核心转储文件，或暂停进程执行等。当进程收到信号时，如果没有设置信号的自定义处理函数，将会执行操作系统默认的行为。
信号处理过程：如果信号的处理方式是执行自定义的信号处理函数，进程将会调用该函数来处理信号。处理函数可以完成一系列操作，比如修改全局变量、执行清理操作等。在信号处理函数执行期间，进程可能会被阻塞在信号处理函数中。
信号返回：一旦信号处理函数执行完毕，程序将会从信号处理函数中返回，程序恢复执行之前的代码。

注：信号传递不支持排队，当在很短时间内传递多个相同信号，该信号只会被处理一次。

在 Linux 中，信号的传递流程通常是由内核负责进行管理和调度，确保信号被准确传递给目标进程，并按照指定的处理方式进行处理。对于开发人员来说，可以通过信号处理函数来实现对信号的处理和响应，以应对不同的信号产生场景

信号（Signal）与其他IPC的区别¶

共享内存（Shared Memory）、管道（Pipe）、消息传递（Message Passing）、信号量（Semaphore）都是进程间通信（IPC）的机制，但它们在通信方式、数据传输能力、同步机制等方面存在显著差异。

IPC机制	类型	数据传输能力	同步机制	主要用途
信号（Signal）	异步通知	仅通知，无数据传输	无同步能力	异常处理、进程控制
共享内存（Shared Memory）	数据传输	高效的数据传输	需要额外的同步机制（如信号量）	大量数据的快速共享
管道（Pipe）	数据传输	单向数据传输	无同步能力	父子进程或无亲缘关系进程间通信
消息传递（Message Passing）	数据传输	可传输数据	提供同步机制	远程过程调用、分布式系统
信号量（Semaphore）	同步机制	不直接传输数据，主要用于同步和互斥	强大的同步能力	资源控制、复杂同步问题

信号（Signal）：

信号是一种异步通信机制，用于通知接收进程某个事件的发生5。

信号不携带数据，仅用于指示事件的发生。

信号用于异常处理、进程控制等场景。

共享内存（Shared Memory）：

共享内存允许两个或多个进程访问同一块物理内存区域。

它是最快的IPC方式，因为数据不需要在进程间复制。

但共享内存本身不提供同步机制，需要配合信号量等机制来同步对共享内存的访问。

管道（Pipe）：

管道是一种单向的数据流通道，通常用于父子进程或无亲缘关系进程间通信。

管道的读写操作没有同步机制，可能会导致数据丢失或竞争条件。

消息传递（Message Passing）：

消息传递通过发送格式化的消息来进行进程间的数据交换。

消息传递可以提供同步或异步的数据传输。

消息队列、套接字等都是消息传递的实现方式。

信号量（Semaphore）：

信号量主要用于解决进程或线程间的同步问题。

它是一个计数器，可以用来控制对共享资源的访问。

信号量本身不用于数据传输，而是用于协调不同进程或线程对共享资源的访问顺序和访问次数。

综上，信号主要用于异步事件的通知，而其他IPC机制则侧重于数据的传输和同步。

CPU调度算法¶

新大纲删除了“典型调度算法”，但是新增了“CPU调度算法”，为此下面将介绍一些其他的调度算法，仅作了解即可，主要引用自汤小丹《计算机操作系统慕课版》这本教材；

基于公平原则的调度算法¶

之前介绍的几种典型调度算法所保证的只是满足要求的进程优先运行，如优先级调度算法可以保证优先级最高的进程优先运行，但并不保证进程占用了多少处理机时间;另外也未考虑调度的公平性。本小节将介绍两种相对公平的调度算法。

保证调度算法¶

算法定义：保证调度向用户所做的并不是优先运行保证，而是明确的性能保证，该算法可以做到调度的公平性。该调度算法会根据每个进程自创建以来实际获得的 CPU 时间来决定谁应该优先获得处理机。目标是保证每个进程在长期运行中都能获得相同的处理机资源（在多进程情况下，每个进程应获得\(\frac{1}{n}\)的处理机时间）。
具体实现原理：
追踪每个进程自创建以来的 CPU 使用时间。
计算进程应获得的 CPU 时间（例如，系统有 5 个进程，理论上每个进程应该获得 20% 的 CPU 时间）。
比较进程的实际获得时间和应获得时间的比率。比如：
进程 A 的比率是 0.5（表示它获得的 CPU 时间低于预期）。
进程 B 的比率是 0.8。
进程 C 的比率是 1.2（表示它已经获得的 CPU 时间超出预期）。
选择比率最低的进程，并将 CPU 资源分配给它，直到它的比率超过下一个进程为止。
它与RR算法的区别

调度算法	时间片轮转算法	保证调度算法
调度依据	时间片轮转算法是基于“时间片”的轮转，不考虑进程的历史 CPU 使用情况。	公平调度算法则考虑进程的历史 CPU 使用情况，优先将资源分配给那些实际获得资源较少的进程。
处理公平性的方式	在短期内是公平的，但无法确保在长期内每个进程都获得相等的处理机资源。	长期公平的，保证所有进程在一个较长的周期内平均分配到相同的 CPU 时间。
性能	对于短任务（如交互式任务）可能更有利，因为每个进程都会快速轮流获得 CPU	根据历史资源分配情况调整，有时会导致某些进程不得不等待较长时间。

公平分享调度算法¶

公平分享调度算法（Fair-Share Scheduling Algorithm）的目标是为每个用户而不是进程提供公平的处理机时间分配。为了实现这一点，调度算法需要考虑每个用户的进程数量，并在分配处理机时间时确保不同用户间的公平性。

问题背景 : 在经典的时间片轮转算法（Round-Robin，RR）中，每个进程都能获得相等的时间片。如果用户 1 启动了 4 个进程，而用户 2 只启动了 1 个进程，则时间片的分配会造成用户 1 获得更多的处理机时间。即：
用户 1 的 4 个进程每个都轮到一个时间片，因此用户 1 占用系统总 CPU 时间的 80%。
用户 2 只有 1 个进程，因此它只占用 20% 的 CPU 时间。

尽管在这种情况下对进程是公平的，但对用户是不公平的，因为用户 2 的 CPU 资源远少于用户 1。

公平分享调度算法的目标：公平分享调度算法关注用户之间的公平性，而不是单独的进程。它会根据用户的进程数量进行调整，以确保每个用户的进程总体上分配到的处理机时间是公平的。例如，两个用户中的每个用户都应该获得相同的处理机时间（如果没有其他要求）。
示例解释
情况 1：用户之间平分 CPU 资源
系统中有两个用户：用户 1 有 4 个进程（A、B、C、D），用户 2 有 1 个进程（E）。
公平分享调度算法的目标是确保两个用户各自获得 50% 的处理机时间。
因为用户 1 有 4 个进程，而用户 2 只有 1 个进程，直接使用 RR 算法会导致不公平。因此，必须采用强制调度序列来保证公平性。

强制调度序列的逻辑如下：

- 让用户 1 的进程 A 先运行一次，然后用户 2 的进程 E 运行一次。
- 之后再让用户 1 的进程 B 运行，接着是用户 2 的进程 E。
- 依次让用户 1 的其他进程 C、D 运行，每次都让用户 2 的进程 E 夹在其中。

具体的调度序列就是：

A E B E C E D E A E B E C E D E……

在这种情况下，尽管用户 1 有 4 个进程，用户 2 只有 1 个进程，但在每轮调度中，两个用户的总 CPU 时间是相等的（每个用户都获得 50% 的处理机时间）。

情况 2：若需要用户 1 获得 2 倍于用户 2 的 CPU 资源
现在假设用户 1 应该获得 2 倍于用户 2 的处理机时间。
由于用户 1 有 4 个进程，用户 2 有 1 个进程，强制调度的目标是使用户 1 获得 2 倍于用户 2 的 CPU 资源。

强制调度序列的逻辑如下：

- 用户 1 的进程 A 和 B 先分别运行一次，接着用户 2 的进程 E 运行一次。
- 然后用户 1 的进程 C 和 D 分别运行，再次轮到用户 2 的进程 E。
- 这个循环持续进行，每次用户 1 都有两个进程运行，之后才轮到用户 2 的进程运行一次。

具体的调度序列为：

A B E C D E A B E C D E A B E C D E……

在这种情况下，用户 1 的进程总共占用 2/3 的处理机时间，而用户 2 的进程 E 占用 1/3 的处理机时间，从而满足用户 1 获得 2 倍 CPU 资源的要求。

实时调度算法¶

在实时系统中，任务通常被分为两类：硬实时任务（HRT, Hard Real-Time tasks）和软实时任务（SRT, Soft Real-Time tasks）。每种任务都有其特定的截止时间（Deadline），即任务必须在某个时间点之前完成。

硬实时任务（HRT）:

定义: 硬实时任务的截止时间是绝对必须满足的。如果硬实时任务没有在规定的截止时间前完成，系统的功能可能会出现严重问题，甚至导致灾难性后果。

例子: 比如控制医疗设备、航空控制系统或自动驾驶汽车中的关键部件。这些任务若没有及时完成，可能会导致安全问题或系统失败。

软实时任务（SRT）:

定义: 软实时任务的截止时间相对灵活。如果软实时任务未能在截止时间前完成，尽管可能会引起一些性能上的降低或用户体验的影响，但不会导致系统的崩溃或严重后果。

例子: 视频流媒体的播放、音频处理等，延迟可能会导致用户体验的下降，但不会引起系统崩溃。

实现实时调度的基本条件¶

提供必要的信息

为了实现实时调度，系统应向调度程序提供与任务相关的信息，包括:

①就绪时间，指某任务的状态转换为就绪状态的起始时间，在周期任务的情况下，它是事先预知的一串时间序列;
②开始截止时间和完成截止时间，对于典型的实时应用，只须知道开始截止时间或者完成截止时间;
③处理时间，一个任务从开始执行直至完成所需的时间;
④资源要求，任务执行时所需的一组资源;
⑤优先级，如果某任务的开始截止时间被错过了(势必引起故障)，则应赋予该任务“绝对”优先级;如果其开始截止时间的错过对任务的继续执行无重大影响，则可赋予其“相对”优先级以供调度程序参考。

2. 系统处理能力强

在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过来而致使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的HRT任务，它们的处理时间表示为C，周期时间表示为P，则在单处理机情况下，必须满足下式所示的限制条件，系统才可调度。顺便说明一下，该限制条件并未考虑任务切换所花费的时间，因此，当利用该限制条件时，还应适当地留有余地。

\(\sum_{i=1}^{m} \frac{C_i}{P_i} \le 1\)

提高系统处理能力的途径有二:

①采用单处理机系统，但须增强其处理能力，以显著减少对每个任务的处理时间;
②采用多处理机系统，假定系统中的处理机个数为N，则应将上式所示的限制条件改为:\(\sum_{i=1}^{m} \frac{C_i}{P_i} \le N\)
采用抢占式调度机制

在含有HRT任务的实时系统中，广泛采用抢占式调度机制，这样便可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占式调度机制，以简化调度程序和任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区代码后能及时地将自己阻塞起来，以便释放处理机并供调度程序去调度开始截止时间即将到达的任务。

采用快速切换机制

为保证HRT任务能及时运行，在系统中还应采用快速切换机制，使之能进行任务的快速切换。该机制应具有如下两方面的能力。

①对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应，要求系统具有快速硬件中断机构，此外，还应使禁止中断的时间间隔尽量短，以免耽误时机(影响其他紧迫任务的执行)。
②快速的任务分派能力。为了提高分派程序的任务切换速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时间开销。

实时调度算法分类¶

非抢占式调度算法
非抢占式轮转调度算法。由一台计算机控制若干个相同的(或类似的)对象，为每个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾进行等待，调度程序再选择下一个队首任务运行。这种调度算法可获得数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统。
非抢占式优先级调度算法。如果在系统中还含有少数具有一定要求的实时任务，则可采用非抢占式优先级调度算法，系统会为这些任务赋予较高的优先级。当这些实时任务到达时，系统会把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，再通过调度执行队首的高优先级进程。这种调度算法在做了精心的处理后，有可能使进程的响应时间减少到数百毫秒至数秒，因而可用于有一定要求的实时控制系统。

抢占式调度算法

可根据抢占发生时间的不同，将抢占式调度算法进一步分成以下两种算法。

基于时钟中断的抢占式优先级调度算法。在某实时任务到达后，如果它的优先级高于当前任务的优先级，则此时并不立即抢占当前任务的处理机，而是等到时钟中断发生后，调度程序才会剥夺当前任务的执行，将处理机分配给新到的高优先级任务。该算法能获得较好的响应效果，其调度时延可降低到几毫秒至几十毫秒，可用于大多数的实时系统。
立即抢占的优先级调度算法。在这种调度算法中，要求OS具有快速响应外部中断事件的能力。一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。该算法能获得非常快的响应，其调度时延可降低到几百微秒至几毫秒。图3-6所示为4种实时调度算法所对应的调度时间情况。

最早截止时间优先算法¶

最早截止时间优先(earliest deadline first，EDF)算法根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高，具有最早截止时间的任务排在队列的前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，并为之分配处机。EDF算法既可用于抢占式调度方式中，也可用于非抢占式调度方式中。

非抢占式调度方式用于非周期实时任务

下图所示为将EDF算法用于非抢占式调度方式之例。该例中具有4个非周期实时任务，它们先后到达。系统先调度任务1执行，在任务1执行期间，任务2、任务3又先后到达。由于任务3的开始截止时间早于任务2的，故系统在执行完任务1后先调度任务3执行。在此期间任务4又到达了，其开始截止时间仍早于任务2的，故在任务3执行完后，系统又会先调度任务4执行，最后才调度任务2执行。

抢占式调度方式用于周期实时任务

多处理机调度（这部分内容可以跟计组CPU的多处理器联动）¶

引用资料：

处理器调度：多核调度策略 [中山大学操作系统原理]

厦门大学 109.多处理器调度的特点

清华OS 8.6 多处理机调度

《操作系统概念》

这节之前我们讨论的都是单处理机系统的CPU 调度问题。如果有多个CPU，则负载分配(load sharing)成为可能，但是

调度问题就相应地更为复杂。许多可能的方法都已试过，但与单处理器调度一样，没有最好的解决方案。

这里我们讨论多处理器调度的几个问题。我们主要关注同构系统，这类系统的处理器从功能上来说相同。这样，我们可以用

任何一个处理器来运行队列内的任何进程。然而，请注意，即使同构多处理器，有时也有一些调度限制。

假设有一个系统，它有一个I/O设备与其某个处理器通过私有总线相连，希望使用该设备的进程应调度到该处理器上运行。

多处理器调度的方法¶

非对称多处理：让一个主处理器负责所有调度决定、IO处理以及其他系统活动，其他的处理器只负责执行用户代码。

优点：因为只有一个处理器访问系统数据结构（访问内存、I/O等资源），减少了数据共享的需要（减少冲突）。

缺点：主处理器故障会导致整个系统崩溃；主处理器会成为性能瓶颈；

对称多处理(Symmetric MultiProcessing，SMP)
即每个处理器运行自己的调度程序
所有进程可能处于一个共同的就绪队列中，或每个处理器都有它自己的私有就绪进程队列。不管如何，调度这样进行:每个处理器的调度程序都检查共同就绪队列，以便选择执行一个进程。
如果多个处理器试图访问和更新一个共同的数据结构，那么每个处理器必须仔细编程。必须确保两个处理器不会选择同一进程，而且进程不会从队列中丢失。（以及调度程序对共享资源的访问需要进行同步）

几乎所有现代操作系统，包括Windows、Linux 和MacOS，都支持SMP，本节余下部分讨论有关SMP系统的多个问题。

处理器亲和性¶

考虑一下，当一个进程运行在一个特定处理器上时缓存会发生些什么，由于进程最近访问的数据更新了处理器的缓存，因此，进程的后续内存访问通常通过缓存来满足。现在考虑一下，如果进程移到其他处理器上则会发生什么。

1. 原来运行的处理器缓存的内容应设为无效
2. 迁移到的处理器缓存需要重新填充

由于缓存的无效或重新填充的代价高，大多数SMP系统试图避免将进程从一个处理器移到另一个处理器，而是试图让一个进程运行在同一个处理器上。这称为处理器亲和性，即一个进程对它运行的处理器具有亲和性。

处理器的亲和性具有多种形式：

当一个操作系统试图保持进程运行在同一处理器上时(但不保证它会这么做，这个进程也可迁移到其他处理器)，这种情况称为软亲和性(soft affinity)。
相反，有的系统提供系统调用以便支持硬亲和性，从而允许某个进程运行在某个处理器子集上。
许多系统提供软的和硬的亲和性。例如，Linux实现软亲和性，但是它也提供系统调用 schedsetaffinity()以支持硬亲和性。

系统的内存架构可以影响处理器的亲和性，下图为采用非统一内存访问(NonUniform Memory Access，NUMA)的一种架构，其中一个 CPU 访问内存的某些部分会比其他部分更快。通常情况下，这类系统包括组合CPU和内存的板卡。每个板的CPU 访问本板内存快于访问其他板的内存。如果操作系统的CPU 调度和内存分配算法一起工作，那么当一个进程分配到一个特定的亲和处理器时，它应分配到同板上的内存。这个例子还说明操作系统通常不按教科书描述的那样清楚地定义与实现。

对称多处理器SMP的进程分配¶

静态进程分配	动态进程分配
进程从开始到结束都被分配到一个固定的处理机上运行	进程在执行中可分配到任意空闲处理及执行
每个处理机都有自己的就绪队列	所有处理机共享一个公共的就绪队列
调度开销小	调度开销大
各处理机可能忙闲不均（有的空闲有的忙）	各处理机的负载是均衡的
处理器亲和性好	处理器亲和性差

静态进程分配（各核心负载不均）

任务由全局调度器分配给某一个核心之后，就一直由这个核心来执行完成它，因此它是缓存友好型的；

动态进程分配

对称多处理器SMP的负载均衡¶

对于 SMP系统，重要的是保持所有处理器的负载平衡，以便充分利用多处理器的优点。否则，一个或多个处理器会空闲，而其他处理器会处于高负载状态，且有一系列进程处于等待状态。负载平衡(load balance)设法将负载平均分配到 SMP系统的所有处理器。

其实SMP的动态进程分配不止上面那种，也分为两种情况：

对于有些系统(它们的处理器具有私有的可执行进程的队列)，负载平衡是必需的；
而对于具有公共队列的系统，负载平衡通常没有必要，因为一旦处理器空闲，它立刻从公共队列中取走一个可执行进程。

同样重要的是，要注意对于大多数支持SMP的现代操作系统，每个处理器都有一个可执行进程的私有队列。

负载平衡通常有两种方法:

推迁移：一个特定的任务周期性地检查每个处理器的负载，如果发现不平衡，那么通过将进程从超载处理器推到(push)空闲或不太忙的处理器，从而平均分配负载。
拉迁移：当空闲处理器从一个忙的处理器上拉(pull)一个等待任务时，发生拉迁移。

推迁移和拉迁移不必相互排斥，事实上，在负载平衡系统中它们常被并行实现。例如，Linux 调度程序实现了这两种技术。

有趣的是，负载平衡往往会抵消处理器亲和性的好处。也就是说，保持一个进程运行在同一处理器上的好处是进程可以利用它在该处理器缓存内的数据。无论是从一个处理器向另一处理器推或拉进程，都会失去这个好处。与通常的系统工程情况一样，关于何种方式是最好的，没有绝对规则。因此，在某些系统中，空闲的处理器总是会从非空闲的处理器中拉进程;而在其他系统中，只有当不平衡达到一定程度后才会移动进程。

多核处理器¶

传统上，SMP系统具有多个物理处理器，以便允许多个线程并行运行。然而，计算机硬件的最近做法是，将多个处理器放置在同一个物理芯片上，从而产生多核处理器(multicore processor)。每个核都保持架构的状态，因此对操作系统而言它似乎是一个单独的物理处理器。采用多核处理器的 SMP系统与采用单核处理器的 SMP系统相比，速度更快，功耗更低。

多核处理器的调度问题可能更为复杂。下面我们来分析一下原因。研究人员发现，当一个处理器访问内存时，它花费大量时间等待所需数据。这种情况称为内存停顿(memory stall)，它的发生原因多种多样，如高速缓存未命中(访问数据不在高速缓冲里)。下图显示了内存停顿，在这种情况下，处理器可能花费高达50%的时间等待内存数据变得可用。为了弥补这种情况，许多最近的硬件设计都采用了多线程的处理器核，即每个核会分配到两个(或多个)硬件线程。这样，如果一个线程停顿而等待内存，该核可以切换到另一个线程。下图显示了一个双线程的处理器核，这里线程0和线程1的执行是交错的。从操作系统的角度来看，每一个硬件线程似乎作为一个逻辑处理器，以便运行软件线程。因此，在双线程双核系统中，操作系统会有4个逻辑处理器。UItraSPARCT3CPU具有16个处理器核，而每个核有8个硬件线程。从操作系统的角度，就有128个逻辑处理器。

一般来说，处理器核的多线程有两种方法:粗粒度(coarse-grained)和细粒度(fine- grainded)的多线程。

对于粗粒度的多线程，线程一直在处理器上执行，直到一个长延迟事件(如内存停顿)发生。由于长延迟事件造成的延迟，处理器应切换到另一个线程来开始执行。然而，线程之间的切换成本是高的，因为在另一个线程可以在处理器核上开始执行之前，应刷新指令流水线。一旦这个新的线程开始执行，它会开始用指令来填充流水线。
细粒度(或交错)的多线程在更细的粒度级别上(通常在指令周期的边界上)切换线程。而且，细粒度系统的架构设计有线程切换的逻辑。因此，线程之间的切换成本很小。

注意，一个多线程多核处理器实际需要两个不同级别的调度。

一个级别的调度决策由操作系统做出，用于选择哪个软件线程运行在哪个硬件线程(逻辑处理器)。对于这个级别的调度，操作系统可以选择任何调度算法，如之前提过的FCFS,多级反馈队列等调度算法。
另一个级别的调度指定每个核如何决定运行哪个硬件线程。在这种情况下，有多种策略可以采用。例如采用一个简单的轮转算法，安排8个硬件线程到每个核。另一个例子是，Intel Itanium 为双核处理器，而且每个核有两个硬件线程。每个硬件线程有一个动态的紧迫值，它的取值范围为0~7，用0表示最低的紧迫性，而7表示最高的。Itanium 有5个不同的事件，用于触发线程切换。当这些事件发生时，线程切换逻辑会比较两个线程的紧迫性，并选择紧迫性较高的线程在处理器核上执行。

页框的回收¶

内存分配的过程¶

应用程序通过 malloc函数申请内存的时候,实际上申请的是虚拟内存，此时并不会分配物理内存。
当应用程序读写了这块虚拟内存，CPU 就会去访问这个虚拟内存，这时会发现这个虚拟内存没有映射到物理内存，CPU 就会产生缺页中断，进程会从用户态切换到内核态,并将缺页中断交给内核的 Page FaultHandler (缺页中断函数)处理.
缺页中断处理函数会看是否有空闲的物理内存，如果有，就直接分配物理内存，并建立虚拟内存与物理内存之间的映射关系。
如果没有空闲的物理内存，那么内核就会开始进行回收内存(页框)的工作，回收的方式主要是两种：
后台内存回收(kswapd):在物理内存紧张的时候,会唤醒 kswapd 内核线程来回收内存，这个回收内存的过程异步的，不会阻塞进程的执行。

后台运行的守护进程kswapd会定期检查系统的内存使用情况，当发现空闲物理页面数目少于特定阈值时，会发起页面回收操作

直接内存回收(direct reclaim):如果后台异步回收跟不上进程内存申请的速度,就会开始直接回收这个回收内存的过程是同步的，会阻塞进程的执行。

5. 如果直接内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会放最后的大招了触发 OOM (Out of Memory)机制。OOM Kiler 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM Kiler 会继续杀死占用物理内存较高的进程，直到释放足够的内存位置。

页框回收的定义¶

页框回收（Page Frame Reclaiming Algorithm，PFRA）是Linux内核中用于回收物理内存页的一种算法。当系统内存不足时，内核会触发页框回收算法，从用户态进程和内核高速缓存中“窃取”页框，以补充伙伴系统的空闲块列表。

哪些页框可以被回收¶

页框回收算法按照页框所含内容的不同，将页框区分为以下几种类型，并以不同的方式处理：

不可回收页：包括空闲页、内核空间使用的页、临时锁定的页等。

可交换页：用户态进程的匿名页或与其他进程共享的页，这些页在硬盘上没有对应的区域，需要写入交换区（swap区）

可同步页：如文件映射到内存的页，这些页在硬盘中有备份，系统只需检查页是否被修改过，如果被修改过则写回硬盘

可丢弃页：如slab机制保留的未使用页、文件系统目录项等的缓存页，这些页可以直接丢弃

系统内存紧张的时候，就会进行回收内存（页框）的工作，主要有两类内存可以被回收，而且它们的回收方式也不同。

文件页(File-backed Page)：内核缓存的磁盘数据(Buffer)和内核缓存的文件数据(Cache)都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据(也就是脏页)，就得先写入磁盘，然后才能进行内存释放。所以，回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存。
匿名页(Anonymous Page)：这部分内存没有实际载体,不像文件缓存有硬盘文件这样一个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们回收的方式是通过Linux 的 Swap 机制，Swap 会把不常访问的内存先写到磁盘中,然后释放这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。

文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。

回收页框带来的性能影响¶

回收内存有两种方式

后台内存回收，也就是唤醒 kswapd 内核线程,这种方式是异步回收的,不会阻塞进程。
直接内存回收，这种方式是同步回收的，会阻塞进程，这样就会造成很长时间的延迟，以及系统的 CPU 利用率会升高，最终引起系统负荷飙高。

可被回收的内存类型有文件页和匿名页，

文件页的回收:对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先写回到磁盘再释放内存，这个操作会发生磁盘I/O 的，这个操作是会影响系统性能的。
匿名页的回收:如果开启了 Swap 机制，那么 Swap 机制会将不常访问的匿名页换出到磁盘中，下次访问时，再从磁盘换入到内存中，这个操作是会影响系统性能的。

可以看到，回收内存（页框）的操作基本都会发生磁盘I/O 的，如果回收内存的操作很频繁,意味着磁盘 I/O 次数会很多，这个过程势必会影响系统的性能，整个系统给人的感觉就是很卡。

堆及其应用¶

堆作为完全二叉树的一个特例，具有以下特性：

最底层节点靠左填充，其他层的节点都被填满。
我们将二叉树的根节点称为「堆顶」，将底层最靠右的节点称为「堆底」。
对于大顶堆（小顶堆），堆顶元素（即根节点）的值分别是最大（最小）的。

堆的实现¶

下文实现的是大顶堆。若要将其转换为小顶堆，只需将所有大小逻辑判断取逆（例如，将 \(\geq\) 替换为 \(\leq\) ）。

堆的存储与表示¶

我们在二叉树章节中的顺序存储中学习到，完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树，我们将采用数组来存储堆。

当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。

具体而言，给定索引 \(i\) ，其左子节点索引为 \(2i + 1\) ，右子节点索引为 \(2i + 2\) ，父节点索引为 \((i - 1) / 2\)（向下取整）。当索引越界时，表示空节点或节点不存在。

(从下标为0处开始存储，王道课上是从下标为1处开始存储)

我们可以将索引映射公式封装成函数，方便后续使用。

/* 获取左子节点索引 */
int left(int i) {
    return 2 * i + 1;
}
/* 获取右子节点索引 */
int right (int i) {
    return 2 * i + 2;
}
/* 获取父节点索引 */
int parent(int i) {
    return (i - 1) / 2; // 向下取整
}

访问堆顶元素：堆顶元素就是二叉树的根结点，也就是列表中的首个元素；

int peek() {
    return maxHeap[0];
}

元素入堆¶

给定元素val,入堆时首先将其添加到堆底，即数组的末尾处。添加之后，由于val可能大于它的父节点等其他元素，堆的成立条件可能已被破坏。因此，需要修复从插入节点到根节点路径上的各个结点，这个操作被称为堆化(Heapify)

堆化实现步骤：从入堆结点开始，从底到顶执行堆化。具体来说，我们比较插入节点和它的父节点的值，如果插入结点值更大，则将它们交换。然后继续执行此操作，依次修复堆中的各个结点，直到越过根节点或遇到无需交换的结点时结束。

示意图：

//元素入堆；
void push(int val) {
    maxHeap.push_back(val); //添加结点到堆底（即数组末尾）；
    siftup(maxHeap.size() - 1); //从堆底开始向上堆化；
}
//从下标为i的结点开始，从底至顶堆化；
void siftup(int i) {  
    while(true) {
        int p = parent(i);  //p为i结点的父节点下标；
        if(p < 0 || maxHeap[i] < maxHeap(p)) //当“越过根节点”或者当前元素小于其父节点，结束堆化；
            break;
        swap(nums[i],nums[p]); //否则，交换该结点与其父节点；
        i = p; //循环往上堆化，直到结束；
    }
}

设结点总数为\(n\),则树的高度为\(logn\).由此可知，堆化操作的循环次数最多为\(logn\)轮，因此元素入堆的时间复杂度为\(O(logn)\).

堆顶元素出堆¶

堆顶元素是二叉树的根节点，即列表首元素。如果直接从列表中删除该元素，那么二叉数中所有结点的索引都将发生变化，这将使得后序使用堆化修复变得困难。为了尽量减少元素索引的变动，我们一般采用下列步骤：

交换堆顶与堆底元素；（即交换根节点与完全二叉树的最右下叶结点）；
交换完成后，将堆底元素删除，此时删除的其实就是原来的堆顶元素；
从根节点开始，自顶至底执行堆化；

这里的堆化与从底至顶的堆化操作方向相反，我们将根节点的值与两个子节点的值进行对比，得出最大的那个元素的下标，然后交换两节点的值；再更新待堆化结点，循环执行该操作，直到越过叶节点或者当前结点比其两个子节点的值都大时，堆化结束。

如下动图展示了删除大顶堆 \({9, 8, 5, 6, 7, 2, 4, 1, 3}\) 堆顶元素 9 的过程（动图中出现的100表示堆顶，值为9）。

至此，堆化完成，最大堆的性质得以修复。

//元素出堆
void pop() {
    if(maxHeap.empty()){  //判空处理
        throw out_of_range("堆为空")；
    }
    swap(maxHeap[0],maxHeap[maxHeap.size()-1]);  //交换堆顶与堆底元素；（即根节点与最右下叶节点）
    maxHeap.pop_back();  //将堆底元素出堆，这里出堆的实际上就是之前的堆顶元素；
    siftdowm(0);   //从顶向底开始堆化；
}
//从结点i开始，自顶向底堆化,即”下滤”；
void siftDowm(int i) {
    while(true) {
        //判断当前结点与其左右孩子结点谁最大，maxIdx为三个结点中最大的那个元素的下标；
        int l = left(i), r = right(i), maxIdx = i;   
        //如果当前结点比其孩子结点值都要大或者已经索引l,r都已经越界，说明堆化完成，堆的性质已经恢复；
        if(l < maxHeap.size() && maxHeap[l] > maxHeap[maxIdx])
            maxIdx = l;
        if(r < maxHeap.size() && maxHeap[r] > maxHeap[maxIdx])
            maxIdx = r;
        if(maxIdx == i) 
            break;
        swap(maxHeap[i],maxHeap[maxIdx]);  //将更大的那个子节点的值与当前结点交换；
        i = maxIdx;   //继续向下执行堆化；     
    }
}

与元素入堆操作类似，因此时间复杂度也为\(Ologn\)

建堆操作¶

如果我们想要根据输入列表生成一个堆，这个过程称为建堆。

建堆有两种方式

借助入堆方法实现¶

最直接的方法是借助“元素入堆操作”实现，首先，创建一个空堆，然后将列表元素依次添加到堆中，设元素数量为\(n\),则最后一个元素入堆的时间复杂度为\(O(logn)\),在依次添加元素时，堆的平均长度为\(\frac{n}{2}\),因此这种建堆方式的总体时间复杂度为\(O(nlogn)\)

2021年真题考察的就是这种建堆操作，题目：将关键字\(6,9,1,5,8,4,7\),依次插入到初始为空的大根堆H中，得到的H是？

基于堆化操作实现¶

这种建堆方法更高效，其时间复杂度仅为\(O(n)\)。我们先将列表中的元素原封不动的添加到堆中，然后迭代地对各个结点执行“从顶到底堆化“。当然，我们不需要对叶子节点执行堆化操作，因为它们没有子节点,故其本身已满足堆序性质，也就无下滤的必要 (也不会下滤)。

如下动图是将输入数组 \({4, 6, 2, 1, 7, 9, 5, 8, 3}\) (1为最后一个非叶子结点) 堆化成大顶堆 \({9, 8, 5, 6, 7, 2, 4, 1, 3}\) 的过程。

createmaxHeap(vector<int> nums) {
    maxHeap = nums;  //// 将列表元素原封不动添加进堆
    int n = maxHeap.size();
    // 堆化除叶节点以外的其他所有节点
    for(int i = parent(n-1); i >= 0; --i) {
        siftDown(i);
    }
}

第五句：这里的 \(i\) 就是这棵完全二叉树的最后一个叶子结点的父节点，也是这棵树的最后一个非叶子结点，先将以该结点为根的子树执行自顶向底的堆化，然后向前依次对各子树执行堆化操作，直到根节点为止，从而使得这颗完全二叉树成为堆。

一句话总结堆化操作：对最后一个非叶子节点到根节点，依次执行下滤操作 (\(siftDown\)) 。

复杂度分析：

这部分内容不用掌握，知道结论即可；

为什么第二种建堆方法的时间复杂度是 \(O(n)\) ？我们来展开推算一下。

完全二叉树中，设节点总数为 \(n\) ，则叶节点数量为 \((n + 1) / 2\) ，其中 \(/\) 为向下整除。因此，在排除叶节点后，需要堆化的节点数量为 \((n - 1)/2\) ，复杂度为 \(O(n)\) 。

在从顶至底堆化的过程中，每个节点最多堆化到叶节点，因此最大迭代次数为二叉树高度 \(O(\log n)\) 。

将上述两者相乘，可得到建堆过程的时间复杂度为 \(O(n \log n)\) 。然而，这个估算结果并不准确，因为我们没有考虑到二叉树底层节点数量远多于顶层节点的特性。

接下来我们来进行更为详细的计算。为了减小计算难度，我们假设树是一个“完美二叉树”，该假设不会影响计算结果的正确性。设二叉树（即堆）节点数量为 \(n\) ，树高度为 \(h\) 。上文提到，节点堆化最大迭代次数等于该节点到叶节点的距离，而该距离正是“节点高度”

因此，我们可以将各层的“节点数量 \(\times\) 节点高度”求和，从而得到所有节点的堆化迭代次数的总和。

\( T(h) = 2^0h + 2^1(h-1) + 2^2(h-2) + \cdots + 2^{(h-1)}\times1 \)

化简上式需要借助中学的数列知识，先对 \(T(h)\) 乘以 \(2\) ，得到

\( \begin{aligned} T(h) & = 2^0h + 2^1(h-1) + 2^2(h-2) + \cdots + 2^{h-1}\times1 \newline 2 T(h) & = 2^1h + 2^2(h-1) + 2^3(h-2) + \cdots + 2^{h}\times1 \newline \end{aligned} \)

使用错位相减法，令下式 \(2 T(h)\) 减去上式 \(T(h)\) ，可得

\( 2T(h) - T(h) = T(h) = -2^0h + 2^1 + 2^2 + \cdots + 2^{h-1} + 2^h \)

观察上式，发现 \(T(h)\) 是一个等比数列，可直接使用求和公式，得到时间复杂度为

\( \begin{aligned} T(h) & = 2 \frac{1 - 2^h}{1 - 2} - h \newline & = 2^{h+1} - h - 2 \newline & = O(2^h) \end{aligned} \)

进一步地，高度为 \(h\) 的完美二叉树的节点数量为 \(n = 2^{h+1} - 1\) ，易得复杂度为 \(O(2^h) = O(n)\) 。以上推算表明，输入列表并建堆的时间复杂度为\(O(n)\)，非常高效。

`TOP-K`问题¶

leetcode上有类似面试题：面试题 17.14. 最小K个数

【2022年408真题】：现有 \(n(n>100000)\) 个数保存在一维数组 \(M\)中，需要查找\(M\)中最小的\(10\)个数，请回答下列问题。

⑴ 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。

⑵ 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

解答：下面介绍的方法先从简单直接的开始，再介绍效率更高的算法。

方法一：利用选择排序的思想，我们可以进行\(k\)轮遍历，分别在每轮中提取第\(1,2,\cdots,k\)小的元素，然后交换到数组左边的有序子序列中，时间复杂度为\(O(kn)\),因为本题中\(k=10\),因此时间复杂度为\(O(n)\),因为是原地排序，因此空间复杂度为\(O(1)\)

该方法只适用于\(k<\<n\)的情况，当\(k\)与\(n\)较为接近时，其时间复杂度趋近于\(O(n^2)\).当\(k=n\),时，这就是选择排序。

法二：对该数组进行排序，那么最左边\(k\)位的元素就是我们要找的元素，时间复杂度为\(O(nlogn)\),这种方法”超额“完成任务了，因此效率不佳。
法三：堆，我们可以基于堆这种数据结构解决该问题，流程为

先在\(M[1:10]\)原地建造大顶堆，然后原地堆化调整；

遍历\(M[11:n]\),将遍历到的每个元素\(M[i]\)与该大顶堆堆顶元素相比较，如果\(M[i]\)大于堆顶元素,什么都不要做，如果\(M[i]\)小于堆顶元素，则删除堆顶元素，将该元素入堆，并重新调整堆化为大顶堆；

遍历完成之后，该大顶堆中保存的就是最小的10个数。

为什么用大顶堆而不用小顶堆呢，因为该大顶堆每次删除的堆顶元素都是当前堆里面的元素中最大的，这样的话每次遍历就可以让更小的元素进入到堆里面，同时删除的也是原来堆内最大的元素；如果用小顶堆的话，堆顶是最小的元素，则达不到该效果，除非将该数组全部原地堆化，然后依次弹出堆顶元素，那样的话，时间复杂度就很高了，不如直接排序呢。

所以我们可以得出一个结论：找最大元素topk，用小顶堆；找最小的k个数，用大顶堆。

前10个元素原地建造大顶堆的时间复杂度为\(O(10)\),即\(O(1)\),然后执行了\(n-10\)次比较，假设执行了\(n-10\)次出堆入堆操作，那么该操作的时间复杂度为\(O(n-10)log10=O(n)\)

因为原地建堆，因此空间复杂度为\(O(1)\).

另外，该方法适用于动态数据流的使用场景。在不断加入数据时，我们可以持续维护堆内的元素，从而实现最小k个元素的动态更新。

//基于堆查找数组中最小的k个元素
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

若要找最小的\(k\)个元素的话，时间复杂度：\(O(nlog⁡k)\)，其中 \(n\)是数组 \(arr\) 的长度。由于大根堆实时维护前 \(k\) 小值，所以插入删除都是 \(O(logk)\) 的时间复杂度，最坏情况下数组里 \(n\) 个数都会插入，所以一共需要\(O(nlogk)\)的时间复杂度。

空间复杂度：\(O(k)\)，因为大根堆里最多\(k\)个数。

法四：利用快排思想

这个重要思想同样可以运用于2016年算法题！

由于题目仅要求返回最小\(k\)个元素，并没有要将它们排好顺序，因此，只需要将数组划分为最小的\(k\)个数和其他数字即可，而快速排序的哨兵划分即可完成此目标。

随便找个数，进行一轮快排
快排结束，进行数据划分，假设这个数属于第\(t\)个,
t==k,那么返回前\(t\)个就是我们要找的结果；
t>k,那么我们便将问题规模缩小到在前\(t-1\)个元素中找k个最小元素；
t<k,那么说明已经确定前面t个数属于我们要找的那k个数，但是第\(t+1\)到第\(k\)这些数还没确定，此时，问题规模缩小到从\(t+1\)到右边界找这剩下的\(k-t\)个数。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k >= arr.size()) return arr;
        return quickSort(arr, k, 0, arr.size() - 1);
    }
private:
    vector<int> quickSort(vector<int>& arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }
};

复杂度分析：本方法优化时间复杂度的本质是通过判断舍去了不必要的递归（哨兵划分）。

时间复杂度：\(O(n)\),\(n\)为数组长度，对于长度为n的数组执行哨兵划分的时间复杂度为\(O(n)\)；每轮哨兵划分后根据\(k和i\)的大小关系选择递归，由于\(i\)分布的随机性，则向下递归的平均长度为\(\frac{n}{2}\),因此平均情况下，哨兵划分操作一共有\(n+\frac{n}{2}+\frac{n}{4}+\frac{n}{n}=\frac{n-\frac{1}{2}}{1-\frac{1}{2}}=2n-1\),即总体时间复杂度为\(O(n)\)

空间复杂度：划分函数的平均递归深度为\(O(logn)\)

堆在c++中的使用方法¶

堆通常用作实现优先队列，大顶堆相当于元素按从大到小顺序出队的优先队列。从使用角度来看，我们可以将「优先队列」和「堆」看作等价的数据结构。

/* 初始化堆 */
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 初始化大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap;

/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);

/* 获取堆顶元素 */
int peek = maxHeap.top(); // 5

/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1

/* 获取堆大小 */
int size = maxHeap.size();

/* 判断堆是否为空 */
bool isEmpty = maxHeap.empty();

/* 输入列表并建堆 */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

堆的小结¶

堆是一棵完全二叉树，根据成立条件可分为大顶堆和小顶堆。大（小）顶堆的堆顶元素是最大（小）的。

优先队列的定义是具有出队优先级的队列，通常使用堆来实现。

堆的常用操作及其对应的时间复杂度包括：元素入堆\(O(\log n)\)、堆顶元素出堆\(O(\log n)\)和访问堆顶元素\(O(1)\)等。

完全二叉树非常适合用数组表示，因此我们通常使用数组来存储堆。

堆化操作用于维护堆的性质，在入堆和出堆操作中都会用到。

输入\(n\)个元素并建堆的时间复杂度可以优化至\(O(n)\)，非常高效。

Top-K 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为 \(O(n \log k)\) 。