该博客在GitHub上公开开发。如果您有任何问题或疑问，请在此处打开一个issue。您也可以在底部留下评论。这篇文章的完整源代码可以在post-12分支中找到。

多任务

多数操作系统的基本特征之一是多任务处理 ，即能够同时执行多个任务的功能。 例如，您可能在看这篇文章时打开了其他程序，例如文本编辑器或终端窗口。 即使只打开一个浏览器窗口，也可能会有各种后台任务来管理桌面窗口，检查更新或为文件建立索引。

尽管看起来所有任务都是并行运行的，但实际上一个CPU核心一次只能执行一个任务。 为了产生任务并行运行的错觉，操作系统会在活动任务之间快速切换，以便每个任务都可以向前推进。 由于计算机速度很快，因此我们大多数时候不会注意到这些切换。

单核CPU一次只能执行一个任务，而多核CPU可以真正并行地运行多个任务。 例如，具有8个内核的CPU可以同时运行8个任务。 我们将在以后的文章中解释如何设置多核CPU。 在本文中，为简单起见，我们将重点介绍单核CPU。 （值得注意的是，所有多核CPU一开始都是以单核启动，因此我们现在可以将它们视为单核CPU。）

多任务处理有两种形式： 协作多任务处理要求任务定期放弃对CPU的控制，以便其他任务可以取得进展。 抢占式多任务使用操作系统功能通过在任意时间点强行暂停线程切换线程。 在下文中，我们将更详细地探讨多任务的两种形式，并讨论它们各自的优点和缺点。

抢占式多任务

抢占式多任务处理的思想是操作系统控制何时切换任务。 为此，它利用了它在每个中断上重新获得对CPU的控制这一事实。 这样，只要系统有新输入可用，就可以切换任务。 例如，当移动鼠标或到达网络数据包时，可以切换任务。 操作系统还可以通过配置硬件计时器在该时间之后发送中断来确定允许任务运行的确切时间。

下图说明了硬件中断时的任务切换过程：

在第一行中，CPU正在执行程序A任务A1 。 所有其他任务都已暂停。 在第二行中，硬件中断到达CPU。 如硬件中断中所述，CPU立即停止执行任务A1并跳转到中断描述符表（IDT）中定义的中断处理程序。 通过此中断处理程序，操作系统现在再次具有对CPU的控制权，从而允许它切换到任务B1而不是继续执行任务A1 。

保存状态

任务在任意时间点都可能被中断，此时它们可能正在进行某些计算。 为了能够在以后继续进行运算，操作系统必须备份任务的整个状态，包括其调用堆栈和所有CPU寄存器的值。 此过程称为上下文切换 。

由于调用堆栈可能非常大，因此操作系统通常为每个任务设置单独的调用堆栈，而不是在每每次切换任务时备份整个调用堆栈的内容。 具有单独堆栈的此类任务称为线程 。 通过为每个任务使用单独的堆栈，在上下文切换时仅需要保存寄存器内容（包括程序计数器和堆栈指针）。 这种方法可以最大程度地减少上下文切换的性能开销，这非常重要，因为上下文切换通常每秒发生100次。

讨论

抢占式多任务处理的主要优点是操作系统可以完全控制任务的允许执行时间。 这样，它可以确保每个任务都能公平分配CPU时间，而无需信任任务之间的协作。 当运行第三方任务或多个用户共享系统时，这一点尤其重要。

抢占式任务调度的缺点是每个任务都需要自己的堆栈。 与共享堆栈相比，这将导致每个任务的内存使用量更高，并且通常会限制系统中的任务数量。 另一个缺点是，即使任务仅使用了寄存器中的一小部分，操作系统仍必须在每次任务切换时保存完整的CPU寄存器状态。

抢占式多任务处理和线程是操作系统的基本组件，因为它们使运行不受信任的用户空间程序成为可能。 我们将在以后的文章中详细讨论这些概念。 但是，在这篇文章中，我们将专注于协作式多任务处理，这也为我们的内核提供了有用的功能。

协作式多任务

协作式多任务处理可以使每个任务运行直到自愿放弃对CPU的控制，而不是在任意时间点强行暂停正在运行的任务。 这使任务可以在方便的时间点（例如，无论如何需要等待I/O操作时）暂停自己的运行。

协作式多任务通常在语言级别使用，例如以协程或async/await的形式。 主要想法是由程序员或编译器将yield操作插入到程序中，从而放弃对CPU的控制并允许其他任务运行。 例如，可以在复杂循环的每次迭代之后插入一个yield。

通常都是将协作式多任务与异步操作结合在一起。 如果操作尚未完成，则异步操作将返回“未就绪”状态，而不是等到操作完成并阻止此时再次执行其他任务。 在这种情况下，等待的任务可以执行yield操作以让其他任务运行。

保存状态

由于任务自己定义了暂停点，因此它们不需要操作系统来保存其状态。 相反，他们可以在暂停之前准确保存需要继续的状态，这通常可以提高性能。 例如，刚完成复杂计算的任务可能只需要备份计算的最终结果，因为它不再需要中间结果。

语言支持的协作任务实现通常甚至可以在暂停之前备份调用堆栈的所需部分。 例如，Rust的async/await实现将所有仍需要的局部变量存储在自动生成的结构中（见下文）。 通过在暂停之前备份调用堆栈的相关部分，所有任务可以共享一个调用堆栈，从而使每个任务的内存消耗大大减少。这样就可以创建几乎任意数量的协作任务，而不会耗尽内存。

讨论

协作式多任务处理的缺点是，不让出执行机会的CPU的协作任务可能会无限期地运行。 因此，恶意或有Bug的任务可能会阻止其他任务运行并减慢甚至使整个系统停止运行。 因此，仅当已知所有任务都会让出执行机会时才应使用协作式多任务处理。 作为反例，操作系统对用户级程序使用协作式多任务调度就不是一个好主意。

但是，协作多任务的强大性能和内存优势使其成为程序内使用的好方法，尤其是与异步操作结合使用时。 由于操作系统内核是与异步硬件进行交互的，性能至关重要的程序，因此协作多任务似乎是实现并发的好方法。

Rust Rust中的Async /Await

Rust语言以async/await的形式为协作式多任务提供了支持。 在探讨什么是async/await及其如何工作之前，我们需要了解futures和异步编程如何在Rust中工作。

Futures

Future代表一个可能尚不可用值。 例如，这可能是由另一个任务计算的整数，也可以是从网络下载的文件。 Future无需等到该值可用时，就可以继续执行，直到需要该值为止。

例子

最好用一个小例子来说明Futures的概念：

此序列图显示了一个main函数，该函数从文件系统读取文件，然后调用函数foo 。 此过程重复两次：一次通过同步read_file调用，一次通过异步async_read_file调用。

通过同步调用访问文件时， main函数需要等待文件系统加载完文件。 只有这样，它才能调用foo函数，这要求它再次等待结果。

通过异步async_read_file调用，文件系统直接返回一个future并在后台异步加载文件。 这允许main函数更早地调用foo ，然后foo与文件加载并行运行。 在此示例中，文件加载甚至能在foo返回之前完成，因此main可以直接处理文件，而无需在foo返回之后再等待。

Rust的Future

在Rust中，Future由Future trait表示，如下所示：

1. pub trait Future {
2. type Output;
3. fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output>;
4. }

关联类型 Output指定异步值的类型。 例如， async_read_file函数将返回Future实例，并且Output设置为File 。

poll方法允许检查该值是否已可用。 它返回一个Poll枚举，如下所示：

1. pub enum Poll<T> {
2. Ready(T),
3. Pending,
4. }

当该值已经可用时（例如，已从磁盘完全读取文件），将其包装在Ready中返回。 否则，将返回Pending，它告知调用方该值尚不可用。

poll方法采用两个参数： self: Pin<&mut Self>和cx: &mut Context 。 前者的行为类似于普通的&mut self引用，不同之处在于self值 固定在其内存位置 如果不先了解异步/等待的工作原理，就很难了解Pin以及为什么需要它。 因此，我们将在本文后面解释。

cx: &mut Context参数的目的是将Waker实例传递给异步任务，例如文件系统负载。 该Waker允许异步任务发信号通知它（或其一部分）已完成，例如，文件是从磁盘加载的。 由于主任务知道在Future准备就绪时会收到通知，因此它不需要一遍又一遍地调用poll 。 当我们实现自己的waker类型时，我们将在本文后面的部分中更详细地说明此过程。

使用futures

现在，我们知道了如何定义future并了解poll方法背后的基本思想。 但是，我们仍然不知道如何有效地使用futures。 问题在于，future代表了异步任务的结果，这可能尚不可用。 但是，实际上，我们经常直接需要这些值以进行进一步的计算。 所以问题是：我们如何在需要时有效地获取future的值？

等待future

一种可能的方法是等到future准备就绪。 可能看起来像这样：

1. let future = async_read_file("foo.txt");
2. let file_content = loop {
3. match future.poll(…) {
4. Poll::Ready(value) => break value,
5. Poll::Pending => {}, // do nothing
6. }
7. }

在这里，我们在一个循环中调用poll来积极地等待future。 poll的参数在这里无关紧要，因此我们省略了它们。 尽管这个解决方案能用，但效率很低，因为我们一直使CPU忙碌，直到该值可用为止。

一种更有效的方法可能是阻塞当前线程，直到将来数据可用。 当然，这只有在有线程的情况下才有可能，因此该解决方案不适用于我们的内核，至少目前还不能。 即使在支持阻塞的系统上，也常常不希望这样做，因为它将再次将异步任务转换为同步任务，从而抑制了并行任务的潜在性能优势。

Future组合子

等待的替代方法是使用Future的组合子。 Future组合子是类似于map方法，它允许将Future链接和组合在一起，类似于Iterator上的方法。 这些组合器不等待Future，而是自己返回一个Future，这将对poll应用映射操作。

例如，用于将Future<Output=String>转换为Future<Output=usize>的简单string_len组合器可能如下所示：

1. struct StringLen<F> {
2. inner_future: F,
3. }

5. impl<F> Future for StringLen<F> where F: Future<Output = String> {
6. type Output = usize;

8. fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<T> {
9. match self.inner_future.poll(cx) {
10. Poll::Ready(s) => Poll::Ready(s.len()),
11. Poll::Pending => Poll::Pending,
12. }
13. }
14. }

16. fn string_len(string: impl Future<Output = String>)
17. -> impl Future<Output = usize>
18. {
19. StringLen {
20. inner_future: string,
21. }
22. }

24. // Usage
25. fn file_len() -> impl Future<Output = usize> {
26. let file_content_future = async_read_file("foo.txt");
27. string_len(file_content_future)
28. }

该代码无法正常工作，因为它不处理固定问题，但是作为示例就足够了。 基本思想是string_len函数将给定的Future实例包装到新的StringLen结构中，该结构还实现了Future 。 当对打包的future进行轮询时，它将轮询内部的未来。 如果该值尚未准备好，则包装的future也返回Poll::Pending 。 如果准备好该值，则从Poll::Ready变量中提取字符串，并计算其长度。然后，将其包装在Poll::Ready并返回。

使用这个string_len函数，我们可以计算异步字符串的长度，而无需等待它。 由于该函数再次返回Future ，因此调用者无法直接对返回的值进行操作，而需要再次使用组合器函数。 这样，整个调用图就变得异步了，我们可以高效地在某个时候一次等待多个future，例如在main函数中。

手动编写组合器函数很困难，因此它们通常由库提供。 尽管Rust标准库本身还没有提供组合器方法，但半官方（和no_std兼容）的futures crate却提供了。 它的FutureExt特性提供了高级组合器方法，例如map或then ，可用于对future结果的操作。

优势

Future组合子的最大优点是它们使操作保持异步。与异步I/O接口结合使用，这种方法可以带来非常高的性能。 Future组合子是通过常规的使用struct和trait实现的，这使得编译器可以对其进行优化。 有关更多详细信息，请参阅《Rust中的零开销Future》一文，该文章宣布将Future添加到Rust生态系统中。

缺点

尽管Future组合子可以编写非常有效的代码，但是由于类型系统和基于闭包的接口，在某些情况下它们可能很难使用。 例如，考虑如下代码：

1. fn example(min_len: usize) -> impl Future<Output = String> {
2. async_read_file("foo.txt").then(move |content| {
3. if content.len() < min_len {
4. Either::Left(async_read_file("bar.txt").map(|s| content + &s))
5. } else {
6. Either::Right(future::ready(content))
7. }
8. })
9. }

在这里，我们读取文件foo.txt ，然后使用then组合器根据文件内容链接第二个future。如果内容长度小于给定的min_len ，我们将读取另一个bar.txt文件，然后使用map组合器将其附加到content 。 否则，我们仅返回foo.txt的内容。

我们需要对传递给then的闭包使用move关键字 ，因为否则将会对min_len造成生命周期错误。 使用Either包装器的原因是if和else块必须始终具有相同的类型。 由于我们在块中返回了不同类型的Future，因此必须使用包装器类型将它们统一为一个类型。 ready函数将值包装到将来立即准备好的future中。 这里需要该函数，因为Either包装器希望包装的值实现Future 。

可以想象，这会很快导致大型项目的代码非常复杂。 如果涉及借贷和不同的生存期，则变得特别复杂。 由于这个原因，为了使异步代码从根本上更易于编写，我们投入了大量工作来为Rust添加对异步/等待的支持。

Async/Await模式

async/await背后的想法是让程序员编写看起来像普通同步代码的代码，但被编译器转换为异步代码。 它基于两个关键字async和await起作用。 可以在函数签名中使用async关键字，以将同步函数转换为返回Future的异步函数：

```RustRu s async fn foo() -> u32 { 0 }

// the above is roughly translated by the compiler to: fn foo() -> impl Future { future::ready(0) }

2. 仅此关键字不会有用。 但是在`async`函数内部，可以使用`await`关键字来检索future的异步值：

4. ```Rust
5. async fn example(min_len: usize) -> String {
6. let content = async_read_file("foo.txt").await;
7. if content.len() < min_len {
8. content + &async_read_file("bar.txt").await
9. } else {
10. content
11. }
12. }

此函数是从上面使用组合子的example函数的直接翻译。 使用.await运算符，我们可以检索future的值，而无需任何闭包或Either类型。 结果，我们可以像编写普通的同步代码一样编写代码，区别在于这仍然是异步代码 。

状态机转换

编译器在此幕后所做的就是将async函数的主体转换为状态机 ，每个.await调用代表一个不同的状态。 对于上面的example函数，编译器创建具有以下四个状态的状态机：

每个状态代表该函数的不同暂停点。 “Start”和“End”状态代表函数在其执行的开始和结束时的状态。 “Waiting on foo.txt”状态表示该函数当前正在等待第一个async_read_file结果。 同样， “Waiting on bar.txt”状态表示功能在第二个async_read_file结果上等待的暂停点。

状态机通过使每个poll调用可能的状态转换来实现Future特性：

该图使用箭头表示状态切换，并使用菱形表示选择执行。 例如，如果foo.txt文件尚未准备好，则采用标记为“ no”的路径，并达到“ Waiting on foo.txt”状态。 否则，采用“yes”路径。 没有标题的红色小菱形代表example函数的if content.len() < 100分支。

我们看到，第一个poll调用启动了该函数并使它运行，直到到达尚未准备好的Future为止。 如果路径上的所有Future都准备就绪，则该函数可以运行到“ End”状态，并返回包装在Poll::Ready中的结果 。否则，状态机进入等待状态并返回Poll::Pending 。 在下一个poll呼叫中，状态机从上一个等待状态开始，然后重试上一个操作。

保存状态

为了能够从上一个等待状态继续，状态机必须在内部跟踪当前状态。 此外，它必须保存在下一个poll调用中继续执行所需的所有变量。 这是编译器真正发挥作用的地方：由于它知道何时使用哪些变量，因此它可以自动生成具有所需变量的结构。

作为示例，编译器为上述example函数生成类似于以下的结构：

1. // The `example` function again so that you don't have to scroll up
2. async fn example(min_len: usize) -> String {
3. let content = async_read_file("foo.txt").await;
4. if content.len() < min_len {
5. content + &async_read_file("bar.txt").await
6. } else {
7. content
8. }
9. }

11. // The compiler-generated state structs:

13. struct StartState {
14. min_len: usize,
15. }

17. struct WaitingOnFooTxtState {
18. min_len: usize,
19. foo_txt_future: impl Future<Output = String>,
20. }

22. struct WaitingOnBarTxtState {
23. content: String,
24. bar_txt_future: impl Future<Output = String>,
25. }

27. struct EndState {}

在“start”和“waiting on foo.txt”状态下，需要存储min_len参数，因为稍后与content.len()比较时需要使用该参数。 “waiting on foo.txt”状态还存储了一个foo_txt_future ，它表示async_read_file调用返回的future。 状态机继续运行时，需要再次轮询此future，因此需要保存它。

“waiting on bar.txt”状态包含content变量，因为在bar.txt准备就绪后，字符串拼接需要使用该变量。 它还存储了一个bar_txt_future ，它表示bar_txt_future的正在进行中的负载。该结构不包含min_len变量，因为在content.len()比较之后不再需要它。 在“End”状态下，没有存储任何变量，因为该函数已经运行完毕。

请记住，这只是编译器可能生成的代码的示例。 结构名称和字段布局是实现细节，可能有所不同。

整个状态机的类型

尽管确切的编译器生成的代码是实现细节，但有助于理解想象生成的状态机如何查找example函数。 我们已经定义了代表不同状态并包含所需变量的结构。 为了在它们之上创建一个状态机，我们可以将它们组合成一个enum ：

1. enum ExampleStateMachine {
2. Start(StartState),
3. WaitingOnFooTxt(WaitingOnFooTxtState),
4. WaitingOnBarTxt(WaitingOnBarTxtState),
5. End(EndState),
6. }

我们为每个状态定义一个单独的枚举变量，并将对应的状态结构作为字段添加到每个变量。 为了实现状态转换，编译器根据example函数生成Future trait的实现：

1. impl Future for ExampleStateMachine {
2. type Output = String; // return type of `example`

4. fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> {
5. loop {
6. match self { // TODO: handle pinning
7. ExampleStateMachine::Start(state) => {…}
8. ExampleStateMachine::WaitingOnFooTxt(state) => {…}
9. ExampleStateMachine::WaitingOnBarTxt(state) => {…}
10. ExampleStateMachine::End(state) => {…}
11. }
12. }
13. }
14. }

Output类型为String因为它是example函数的返回类型。 为了实现poll函数，我们在loop内的当前状态上使用match语句。 这个想法是我们尽可能长时间地切换到下一个状态，并在无法继续时使用显式return Poll::Pending 。

为简单起见，我们仅显示简化的代码，不处理固定 ，所有权，生命周期等。因此，此代码和以下代码应视为伪代码，不能直接使用。 当然，真正的编译器生成的代码可以正确处理所有内容，尽管可能以不同的方式进行。

为了使代码片段较小，我们将分别显示每个match分支的代码。 让我们从Start状态开始：

1. ExampleStateMachine::Start(state) => {
2. // from body of `example`
3. let foo_txt_future = async_read_file("foo.txt");
4. // `.await` operation
5. let state = WaitingOnFooTxtState {
6. min_len: state.min_len,
7. foo_txt_future,
8. };
9. *self = ExampleStateMachine::WaitingOnFooTxt(state);
10. }

在函数一开始调用时，状态机就处于Start状态。 在这种情况下，我们将执行example函数主体中的所有代码，直到第一个.await 。 为了处理.await操作，我们将self状态机的状态更改为WaitingOnFooTxt ，其中包括WaitingOnFooTxtState结构的构造。

由于match self {…}语句是在循环中执行的，因此该执行将跳转到下一个WaitingOnFooTxt：

1. ExampleStateMachine::WaitingOnFooTxt(state) => {
2. match state.foo_txt_future.poll(cx) {
3. Poll::Pending => return Poll::Pending,
4. Poll::Ready(content) => {
5. // from body of `example`
6. if content.len() < state.min_len {
7. let bar_txt_future = async_read_file("bar.txt");
8. // `.await` operation
9. let state = WaitingOnBarTxtState {
10. content,
11. bar_txt_future,
12. };
13. *self = ExampleStateMachine::WaitingOnBarTxt(state);
14. } else {
15. *self = ExampleStateMachine::End(EndState));
16. return Poll::Ready(content);
17. }
18. }
19. }
20. }

在此匹配分支中，我们首先调用foo_txt_future的poll函数。 如果其尚未准备好，则退出循环并返回Poll::Pending 。 由于在这种情况下self保持在WaitingOnFooTxt状态，因此状态机上的下一个poll调用将进入相同的匹配并再试一次。

当foo_txt_future准备就绪时，我们将结果分配给content变量，然后继续执行example函数的代码：如果content.len()小于状态struct中保存的min_len则异步读取bar.txt文件。 我们再次将.await操作转换为状态更改，这次转换为WaitingOnBarTxt状态。 由于我们是在循环内执行match ，因此执行会直接跳到新状态的匹配分支，然后轮询bar_txt_future 。

如果我们进入else分支，则不会进行进一步的.await操作。 我们到达函数的结尾，并返回包装在Poll::Ready 。 我们还将当前状态更改为End状态。

WaitingOnBarTxt状态的代码如下所示：

1. ExampleStateMachine::WaitingOnBarTxt(state) => {
2. match state.bar_txt_future.poll(cx) {
3. Poll::Pending => return Poll::Pending,
4. Poll::Ready(bar_txt) => {
5. *self = ExampleStateMachine::End(EndState));
6. // from body of `example`
7. return Poll::Ready(state.content + &bar_txt);
8. }
9. }
10. }

与WaitingOnFooTxt状态类似，我们从轮询bar_txt_future开始。 如果仍在等待处理，则退出循环并返回Poll::Pending 。 否则，我们可以执行example函数的最后一个操作：将content变量与将来的结果连接起来。 我们将状态机更新为End状态，然后返回包装在Poll::Ready的结果。

最后， End状态的代码如下所示：

1. ExampleStateMachine::End(_) => {
2. panic!("poll called after Poll::Ready was returned");
3. }

Future返回Poll::Ready之后，不应再次对其进行轮询，因此，如果在已经处于End状态的情况下调用poll ，我们将panic。

现在我们知道了编译器生成的状态机及其对Future trait的实现。 实际上，编译器以不同的方式生成代码。 （如果您有兴趣，当前的实现是基于generator的 ，但这只是实现的细节。）

难题的最后一部分是为example函数本身生成代码。 记住，函数头是这样定义的：

1. async fn example(min_len: usize) -> String

由于现在完整的功能主体是由状态机实现的，因此该功能唯一需要做的就是初始化状态机并将其返回。 为此生成的代码如下所示：

1. fn example(min_len: usize) -> ExampleStateMachine {
2. ExampleStateMachine::Start(StartState {
3. min_len,
4. })
5. }

该函数不再具有async修饰符，因为它现在显式返回ExampleStateMachine类型，该类型实现了Future特性。 如预期的那样，状态机被构造为“Start”状态，并且使用min_len参数初始化了相应的状态结构。

请注意，此功能不会启动状态机的执行。 这是Rust future的一个基本设计决策：在第一次poll之前，它们什么都不做。

固定

我们已经在这篇文章中偶然发现了多次固定 。 现在终于可以探索固定是什么以及为什么需要固定了。

自引用结构

如上所述，状态机转换将每个暂停点的局部变量存储在结构中。 对于像我们的example函数这样的小例子，这很简单，并且不会导致任何问题。 但是，当变量互相引用时，事情变得更加困难。例如，考虑以下函数：

1. async fn pin_example() -> i32 {
2. let array = [1, 2, 3];
3. let element = &array[2];
4. async_write_file("foo.txt", element.to_string()).await;
5. *element
6. }

此函数创建一个包含内容1，2和3的小array 。 然后，它创建对最后一个数组元素的引用，并将其存储在element变量中。 接下来，它将异步将转换为字符串的数字写入foo.txt文件。 最后，它返回由element引用的数字。

由于该函数使用单个await操作，因此结果状态机具有三种状态：开始，结束和“等待写入”。 该函数不带参数，因此开始状态的结构为空。 像以前一样，结束状态的结构也是空的，因为该功能已在此时完成。 “等待写入”状态的结构更有趣：

1. struct WaitingOnWriteState {
2. array: [1, 2, 3],
3. element: 0x1001a, // address of the last array element
4. }

我们需要存储array和element变量，因为返回值需要element ，而array是由element引用的。 由于element是引用，因此它存储指向所引用元素的指针 （即内存地址）。我们0x1001a在这里以内存地址为例。实际上，它必须是array字段的最后一个元素的地址，因此它的值取决于该结构在内存中的位置。具有此类内部指针的结构被称为自引用结构，因为它们对其字段之一进行引用。

自我指涉的Structs存在的问题

我们的自引用结构的内部指针会导致一个基本的问题，当我们查看其内存布局时，该问题变得显而易见：

这里的array字段从地址0x10014开始，element字段从地址0x10020开始。它指向地址0x1001a，因为最后一个数组元素位于该地址。到现在为止还看不出什么问题。但是，当我们将此结构移到其他内存地址时，会发生问题：

我们稍微移动了结构，使其现在从0x10024的地址开始。例如，当我们将struct作为函数参数传递或将其赋值给其他堆栈中的变量时，可能会发生这种情况。问题在于，即使最后一个元素现在位于0x1002a ，该element字段仍然指向0x1001a 。因此，指针现在处于悬垂状态，结果就是在下一次调用时发生未定义的行为。

可能的解决方案

有三种基本方法可以解决悬垂指针问题：

• 在移动时更新指针：想法是每当结构在内存中移动时都更新内部指针，以使其在移动后仍然有效。不幸的是，这种方法将需要对Rust进行大量更改，从而可能导致巨大的性能损失。原因是某种运行时需要跟踪所有结构字段的类型，并检查每个移动操作是否需要更新指针。
• 存储偏移量而不是自引用：为了避免更新指针的要求，编译器可以尝试将自引用存储为结构体开始处的偏移量。例如，element上面WaitingOnWriteState结构的element_offset字段可以以值8的形式存储，因为引用指向的数组元素在结构开始后的8个字节处开始。由于在移动结构时偏移量保持不变，因此不需要字段更新。

这种方法的问题在于，它要求编译器检测所有自引用。这在编译时是不可能的，因为引用的值可能取决于用户输入，因此我们将再次需要运行时来分析引用并正确创建状态结构。这不仅会导致运行时成本增加，而且还会阻止某些编译器优化，从而会再次导致较大的性能损失。 - 禁止移动该结构：如上所示，仅当我们在内存中移动该结构时，才会出现悬垂指针。通过完全禁止对自引用结构的移动操作，也可以避免该问题。这种方法的最大优点是，可以在类型系统级别上实现它，而不会增加运行时成本。缺点是它将处理移动操作的负担放在程序员的可能自引用的结构上。

由于其原则是提供零成本抽象，这意味着抽象不应施加额外的运行时成本，因此Rust选择了第三个解决方案。为此，在RFC 2349中提出了固定 API 。在下文中，我们将简要概述此API，并说明其如何与async / await和futures一起使用。

堆上的值

第一个观察结果是，堆分配的值大多数时候已经具有固定的内存地址。它们是调用allocate创建的，然后由指针类型（如Box）引用。虽然可以移动指针类型，但指针指向的堆值将保持在相同的内存地址，直到deallocate再次通过调用将其释放为止。

使用堆分配，我们可以尝试创建一个自引用结构：

1. fn main() {
2. let mut heap_value = Box::new(SelfReferential {
3. self_ptr: 0 as *const _,
4. });
5. let ptr = &*heap_value as *const SelfReferential;
6. heap_value.self_ptr = ptr;
7. println!("heap value at: {:p}", heap_value);
8. println!("internal reference: {:p}", heap_value.self_ptr);
9. }

11. struct SelfReferential {
12. self_ptr: *const Self,
13. }

我们创建一个名为SelfReferential的简单结构，其中包含单个指针字段。首先，我们使用空指针初始化此结构，然后使用将其分配到堆上Box::new。然后，我们确定堆分配的结构的内存地址，并将其存储在ptr变量中。最后，通过将ptr变量分配给self_ptr字段，使结构自引用。

在playground中执行此代码时，我们看到堆值的地址及其内部指针相等，这意味着该self_ptr字段是有效的自引用。由于heap_value变量只是指针，因此移动变量（例如，通过将其传递给函数）不会更改结构本身的地址，因此self_ptr即使指针被移动，其保持有效。

但是，仍然有一种方法可以破坏此示例：我们可以移出Box或替换其内容：

1. let stack_value = mem::replace(&mut *heap_value, SelfReferential {
2. self_ptr: 0 as *const _,
3. });
4. println!("value at: {:p}", &stack_value);
5. println!("internal reference: {:p}", stack_value.self_ptr);

在这里，我们使用该mem::replace函数用新的struct实例替换堆分配的值。这使我们可以将原始对象heap_value移到堆栈中，而self_ptrstruct 的字段现在是一个悬垂指针，该指针仍然指向旧的堆地址。当您尝试在playground中运行示例时，您会看到打印的“ value at：”和“ internal reference：”行确实显示了不同的指针。因此，堆分配值不足以使自引用安全。

导致上述破坏的根本问题是Box允许我们获得&mut T，即对堆分配值的可变引用。该&mut引用使使用mem::replace或mem::swap来使得堆分配的值无效成为可能。若要解决此问题，我们必须防止&mut创建对自引用结构的引用。

Pin<Box<T>> 和 Unpin

固定API以Pin包装器类型和Unpin标记trait的形式提供了对&mut T问题的解决方案。 这些类型背后的思想是对Pin的所有能获取包装中值的的&mut的方法，都将其转发给Unpin trait。 Unpin trait是一个自动trait，对于除明确选择不实现的类型之外，所有类型均自动实现了Unpin。 只要自引用结构明确选择不实现Unpin，就没有（safe的）方法可以从Pin<Box<T>>类型获取&mut T。 这样做的结果就是保证了它们的内部自引用保持有效。

例如，让我们更新上面的SelfReferential类型以选择取消固定：

1. use core::marker::PhantomPinned;

3. struct SelfReferential {
4. self_ptr: *const Self,
5. _pin: PhantomPinned,
6. }

我们选择强制不实现Unping，方法是添加类型为PhantomPinned的一个字段。此类型是大小为零的标记类型，其唯一目的是不实现Unpin特征。由于auto trait的工作方式，单个不Unpin的字段也会使得整个struct Unpin。

第二步是将例子中的Box<SelfReferential>类型更改为Pin<Box<SelfReferential>>类型。最简单的方法是使用Box::pin函数而不是Box::new创建堆分配的值：

1. let mut heap_value = Box::pin(SelfReferential {
2. self_ptr: 0 as *const _,
3. _pin: PhantomPinned,
4. });

除了更改Box::new为Box::pin，我们还需要在struct初始化中添加新字段_pin。由于PhantomPinned是零大小的类型，因此我们只需要使用其类型名称即可对其进行初始化。

现在，当我们尝试运行调整后的示例时，我们发现它不能编译了：

1. error[E0594]: cannot assign to data in a dereference of `std::pin::Pin<std::boxed::Box<SelfReferential>>`
2. --> src/main.rs:10:5
3. |
4. 10 |     heap_value.self_ptr = ptr;
5. |     ^^^^^^^^^^^^^^^^^^^^^^^^^ cannot assign
6. |
7. = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `std::pin::Pin<std::boxed::Box<SelfReferential>>`

9. error[E0596]: cannot borrow data in a dereference of `std::pin::Pin<std::boxed::Box<SelfReferential>>` as mutable
10. --> src/main.rs:16:36
11. |
12. 16 |     let stack_value = mem::replace(&mut *heap_value, SelfReferential {
13. |                                    ^^^^^^^^^^^^^^^^ cannot borrow as mutable
14. |
15. = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `std::pin::Pin<std::boxed::Box<SelfReferential>>`

发生这两个错误是因为Pin<Box<SelfReferential>>类型不再实现DerefMut trait。这正是我们想要的，因为DerefMut trait将返回一个&mut引用，我们希望避免这样做。这正是因为我们选择了不自动实现Unpin并更改Box::new为Box::pin。

现在的问题是，编译器不仅禁止了在第16行中移动这个类型的变量，而且还禁止了在第10行中初始化self_ptr字段。这是因为编译器无法区分&mut引用的有效使用和无效使用。为了正确初始化这个结构体，我们必须使用unsafe的 get_unchecked_mut方法：

1. // safe because modifying a field doesn't move the whole struct
2. unsafe {
3. let mut_ref = Pin::as_mut(&mut heap_value);
4. Pin::get_unchecked_mut(mut_ref).self_ptr = ptr;
5. }

该get_unchecked_mut函数在 Pin<&mut T>工作，而不是在Pin<Box<T>>上，因此我们必须先使用Pin::as_mut转换值。然后，我们可以使用get_unchecked_mut返回的可变引用来设置字段self_ptr。

现在剩下的唯一错误来源于mem::replace。此操作尝试将堆上分配的值移动到栈上，这会破坏存储在self_ptr字段中的自引用。通过选择不自动实现Unpin并使用Pin<Box<T>>，我们可以防止在编译时执行此操作，从而可以安全地使用自引用结构。如我们所见，编译器（暂时）无法证明自引用的创建是安全的，因此我们需要使用unsafe块并自己验证其正确性。

栈上的固定和Pin<&mut T>

在上一节中，我们学习了如何用Pin<Box<T>>安全地创建分配了堆的自引用值。尽管这种方法可以很好地工作并且相对safe（除了unsafe的构造），但是所需的堆分配会带来性能成本。由于Rust一直希望尽可能提供零成本的抽象，因此固定API还允许创建Pin<&mut T>指向栈上分配的值的实例。

与拥有包装值所有权的Pin<Box<T>>实例不同， Pin<&mut T>实例仅临时借用包装值。这使事情变得更加复杂，因为它要求程序员自己提供一些额外的保证。最重要的是，一个Pin<&mut T>实例必须在被引用的整个生命周期中保持固定状态，这对于基于堆栈的变量来说很难验证。为了解决这个问题，有类似pin-utils这样的crate的存在，但除非您真的知道自己在做什么，否则我仍然不建议固定在堆栈上的变量。

要进一步阅读，请查阅pin模块和Pin::new_unchecked方法的文档。

固定与Future

正如我们在本文中已经看到的那样，Future::poll方法以Pin<&mut Self>参数形式使用固定：

1. fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output>

如上所示，此方法采用非常规的self: Pin<&mut Self>而非一般的&mut self作为参数，从async/await创建的Future实例通常是自引用的。通过将Self包装入Pin并让编译器让async/await创建的含有自我指涉的Future不自动实现Unpin，它保证了Future在多次调用之间未在内存之间移动。这样可以确保所有内部引用仍然有效。

值得注意的是，在第一个poll调用之前移动Future是可以的。这是由于Future是懒惰的，在第一次被poll之前什么都不做。因此生成的状态机的start状态，只包含了函数的参数，而不会有内部引用。为了调用poll，调用者必须先将future包装到Pin，以确保future无法再在内存中移动。由于栈上的固定很难正确完成，因此我建议为此始终使用结合Box::pin和Pin::as_mut的方式。

如果你有兴趣了解如何使用栈上固定安全地实现Future的组合子函数，可以看看futurescrate中相对较短的map组合子方法的源码，以及有关投影和结构的固定的文档。

Executors 和 Wakers

使用async/await，可以以符合人的习惯却完全异步的方式处理Future。但是，正如我们从上面了解到的那样，在poll之前，Future什么都不做。这意味着我们必须在某个时候poll它们，否则异步代码将永远不会执行。

对于单一的Future，我们总是可以使用如上所述的循环手动等待每个Future。但是，这种方法效率很低，并且对于创建大量Future的程序不实用。解决此问题的最常见方法是定义一个全局Executor，该Executor负责轮询系统中的所有Future，直到完成为止。

Executor

Executor的目的是允许将Future作为独立的任务生成，通常通过某种spawn方法。然后，Executor负责轮询所有Future，直到完成为止。中心化管理所有Future的最大优势在于，每当Future返回Poll::Pending时，Executor就可以切换到另一个Future。因此，异步操作可以并行运行，并且CPU保持繁忙。

许多Executor的实现也可以利用具有多个CPU内核的系统。他们创建了一个线程池，如果有足够的可用工作，该线程池就可以利用所有内核，并使用诸如工作窃取之类的技术来平衡内核之间的负载。嵌入式系统还有一些特殊的执行器实现，它们可以优化以降低延迟和内存开销。

为了避免一遍又一遍地查询Future的开销，Executor通常还利用Rust Future支持的唤醒 API。

Wakers

Waker API背后的想法是，将特殊的Waker类型变量传递给包装在该Context类型中的每次poll调用。此Waker类型变量由Executor创建，并且异步任务可以用它来表示其（部分）完成。这样Executor在相应的Waker通知它之前，就不再需要不断在先前返回了Poll::Pending的future上调用poll了。

最好通过一个小例子来说明：

1. async fn write_file() {
2. async_write_file("foo.txt", "Hello").await;
3. }

此函数将字符串“Hello”异步写入foo.txt文件。由于硬盘写入需要一些时间，因此poll此将来的首次调用很可能会返回Poll::Pending。但是，硬盘驱动器将在内部存储poll调用中的Waker，并在文件写入磁盘时使用它来通知执行程序。这样，执行程序poll在接收唤醒通知之前，不需要浪费任何时间再次poll这个future。

在本文的实现部分中，当我们创建具有唤醒器支持的执行程序时，我们将详细了解Waker类型如何工作。

合作式多任务？

在本文的开头，我们讨论了抢先式和协作式多任务。抢占式多任务处理依靠操作系统在正在运行的任务之间进行强制切换，而协作式多任务处理则要求任务通过定期的yield操作自愿放弃对CPU的控制。协作方法的最大优点是任务可以自己保存状态，从而可以更有效地进行上下文切换，并可以在任务之间共享相同的调用堆栈。

这可能并不明显，但是future和async/await是协作式多任务处理模式的实现：

• 添加到执行器中的每个Future基本上都是一项合作任务。
• Future不使用显式的yield操作，而是通过返回

Poll::Pending（或最后的Poll::Ready）来放弃对CPU内核的控制。

• 没有什么可以强迫future放弃CPU。如果他们愿意，他们将永远无法从poll中返回，例如通过死循环。
• 由于每个future都可以阻止Executor中其他future的执行，因此我们需要相信它们不是恶意的。

• Future在内部存储了在下一次poll被调用时继续执行所需的所有状态。使用async/await，编译器会自动检测所需的所有变量，并将其存储在生成的状态机中。

• 仅保存继续所需的最小状态。

• 由于poll方法在返回时会放弃调用堆栈，因此该堆栈可用于轮询其他future。

我们看到Future和async/await非常适合协作多任务处理模式，它们只是使用一些不同的术语。因此，在下文中，我们将互换使用术语“任务”和“future”。

实现

现在，我们了解了基于Future和异步/等待的协作式多任务在Rust中的工作原理，是时候向我们的内核添加对它的支持了。由于Future trait是core库的一部分，而async/await是语言本身的功能，因此我们无需做任何特殊操作即可在#![no_std]内核中使用它。唯一的要求是我们至少使用nightly 2020-03-25 之后的Rust，因为在此之前async/await 不兼容no_std。（那以后的nightly rust版本还没有rustfmt和clippy组件，因此您可能必须将--force标志传递给rustup update，即使会删除了一些已安装的组件，使用该标志后也会执行更新。）

在使用了一个足够新的nightly Rust 版本后，我们可以开始在我们main.rs中使用async/await：

1. // in src/main.rs

3. async fn async_number() -> u32 {
4. 42
5. }

7. async fn example_task() {
8. let number = async_number().await;
9. println!("async number: {}", number);
10. }

async_number函数是一个 async fn，因此编译器将其转换为实现了Future的状态机。由于该函数仅返回42，因此生成的future将在第一次poll调用时直接返回Poll::Ready(42)。就像async_number那样，example_task函数也是async fn。它等待返回的数字async_number，然后使用println宏将其打印出来。

要运行example_task返回的future，我们需要对其进行调用poll，直到它通过返回来表示已完成Poll::Ready。为此，我们需要创建一个简单的executor类型。

任务

在开始执行执行程序之前，我们创建一个task模块，其具有以下Task类型：

1. // in src/lib.rs

3. pub mod task;

1. // in src/task/mod.rs

3. use core::{future::Future, pin::Pin};
4. use alloc::boxed::Box;

6. pub struct Task {
7. future: Pin<Box<dyn Future<Output = ()>>>,
8. }

该Task结构是一个包裹了一个堆上的，固定的，且动态派发的输出为空类型()的future输出。让我们详细研究一下：

• 我们要求与任务相关的future返回()。这意味着任务不会返回任何结果，它们只是为了副作用而执行。例如，上面定义的example_task函数没有返回值，但是它会在屏幕上显示一些副作用。
• dyn关键字表明我们存储在Box中的是一个trait对象中。这意味着Future上的方法是动态派发的，从而可以在该Task类型中存储不同类型的Future 。这很重要，因为每个async fn都有自己的类型，我们希望能够创建多个不同的任务。
• 正如我们在固定一节中所了解的那样，Pin类型可以通过将值放在堆上并防止创建对它的&mut引用来确保它不能在内存中移动。这很重要，因为async/await生成的future可能是自我指涉的，即包含指向自身的指针，这些指针在移动future时将失效。

为了允许用future创建新Task，我们创建一个new函数：

1. // in src/task/mod.rs

3. impl Task {
4. pub fn new(future: impl Future<Output = ()> + 'static) -> Task {
5. Task {
6. future: Box::pin(future),
7. }
8. }
9. }

该函数接受一个输出值为()类型的future并通过Box::pin函数将其固定在内存中。然后，将装入Box的future包装在Task结构中并返回。'static生命周期在此处是必须的，因为返回的Task可能存活任意长的时间，因此那个future也需要在那段时间内一直有效。

我们还添加了一个poll方法，使executor可以轮询存储的future：

1. // in src/task/mod.rs

3. use core::task::{Context, Poll};

5. impl Task {
6. fn poll(&mut self, context: &mut Context) -> Poll<()> {
7. self.future.as_mut().poll(context)
8. }
9. }

由于Futuretrait的poll方法希望在Pin<&mut T>类型上调用，因此我们使用Pin::as_mut方法首先转换字段self.future的类型。然后，我们在转换后的self.future字段上调用poll并返回结果。由于该Task::poll方法仅应由我们稍后创建的executor调用，因此我们将函数保留为task模块私有。

简单执行器

由于Executor可能非常复杂，因此，我们刻意从创建一个非常基本的执行程序开始，之后再实现功能更强大的Executor。为此，我们首先创建一个新的task::simple_executor子模块：

1. // in src/task/mod.rs

3. pub mod simple_executor;

1. // in src/task/simple_executor.rs

3. use super::Task;
4. use alloc::collections::VecDeque;

6. pub struct SimpleExecutor {
7. task_queue: VecDeque<Task>,
8. }

10. impl SimpleExecutor {
11. pub fn new() -> SimpleExecutor {
12. SimpleExecutor {
13. task_queue: VecDeque::new(),
14. }
15. }

17. pub fn spawn(&mut self, task: Task) {
18. self.task_queue.push_back(task)
19. }
20. }

该结构包含一个VecDeque类型的字段task_queue。VecDeque类型基本上是一个允许在两端进行推入和弹出操作的向量。使用这种类型背后的想法是，我们在spawn方法的最后插入新任务，并从前面弹出要执行的下一个任务。这样，我们得到一简单的FIFO队列（“ 先进先出”）。

Dummy Waker

为了调用该poll方法，我们需要创建一个Context，作为Waker类型的包装类型。首先，我们将创建一个不执行任何操作的Dummy唤醒器。为此，我们创建一个RawWaker实例，该实例定义了不同Waker方法的实现，然后使用Waker::from_raw函数将其转换为Waker：

1. // in src/task/simple_executor.rs

3. use core::task::{Waker, RawWaker};

5. fn dummy_raw_waker() -> RawWaker {
6. todo!();
7. }

9. fn dummy_waker() -> Waker {
10. unsafe { Waker::from_raw(dummy_raw_waker()) }
11. }

该from_raw函数是unsafe的，因为如果程序员不遵守文档中对RawWaker的要求，则会发生未定义的行为。在研究dummy_raw_waker函数的实现之前，我们首先尝试了解RawWaker类型的工作方式。

RawWaker

该RawWaker类型要求程序员明确定义一个虚函数表（vtable），该表指定了在RawWaker克隆，唤醒或删除它们时应调用的函数。此vtable的布局由RawWakerVTable类型定义。每个函数接收一个*const ()参数，该参数基本上是指向某个结构的类型被擦除掉的 &self指针，例如，堆上的内存分配。使用*const ()指针而不是适当的引用的原因是该RawWaker类型应该是非泛型的，但仍支持任意类型。传递给函数的指针值是RawWaker::new中传入的data指针值。

通常，RawWaker为包裹在Box或Arc类型中的一些堆分配的结构创建。对于此类类型，可以使用诸如Box::into_raw之类的方法将Box<T>转换为*const T指针。然后，可以将该指针转换为匿名*const ()指针并传递给RawWaker::new。由于每个vtable函数接收同样的的*const ()参数，因此这些函数可以安全地将指针强制转换回Box<T>或 &T进行操作。可以想象，此过程非常危险，很容易导致错误的不确定行为。因此，除非必要，否则不建议手动创建RawWaker。

DummyRawWaker

虽然不建议手动创建RawWaker ，但是目前没有其他方法可以创建一个不执行任何操作的dummy Waker。幸运的是，我们实际上什么也不做的事实使得实现dummy_raw_waker函数相对安全：

1. // in src/task/simple_executor.rs

3. use core::task::RawWakerVTable;

5. fn dummy_raw_waker() -> RawWaker {
6. fn no_op(_: *const ()) {}
7. fn clone(_: *const ()) -> RawWaker {
8. dummy_raw_waker()
9. }

11. let vtable = &RawWakerVTable::new(clone, no_op, no_op, no_op);
12. RawWaker::new(0 as *const (), vtable)
13. }

首先，我们定义两个名为no_op和clone的内部函数。no_op函数需要一个*const ()指针，但不执行任何操作。clone函数获取一个*const ()指针，并通过dummy_raw_waker返回一个新的RawWaker。我们使用这两个函数来创建一个最小的RawWakerVTable：clone函数用于克隆操作，no_op函数用于所有其他操作。既然RawWaker什么都不做，那么在克隆它时直接返回一个新RawWaker而不是真的克隆它也没有关系。

创建vtable之后，我们使用RawWaker::new函数创建RawWaker。传入的*const ()无关紧要，因为vtable函数均未使用它。因此，我们只传递一个空指针。

run方法

现在我们有了创建Waker实例的方法，可以使用它在executor上实现一个run方法。最简单的run方法是在循环中重复轮询所有排队的任务，直到完成所有任务。这不是很高效，因为它没有利用Waker类型的通知，但是它是让一切运行起来的简单方法：

1. // in src/task/simple_executor.rs

3. use core::task::{Context, Poll};

5. impl SimpleExecutor {
6. pub fn run(&mut self) {
7. while let Some(mut task) = self.task_queue.pop_front() {
8. let waker = dummy_waker();
9. let mut context = Context::from_waker(&waker);
10. match task.poll(&mut context) {
11. Poll::Ready(()) => {} // task done
12. Poll::Pending => self.task_queue.push_back(task),
13. }
14. }
15. }
16. }

该函数使用while let循环来处理task_queue中的所有任务。对于每个任务，它首先通过包装由我们的dummy_waker函数返回的Waker实例来创建一个Context类型。然后，它使用这个context调用方法Task::poll。如果poll方法返回Poll::Ready，则任务完成，我们可以继续下一个任务。如果任务仍然存在Poll::Pending，我们将其再次添加到队列的后面，以便在后续循环迭代中再次对其进行轮询。

试一试

使用我们的SimpleExecutor类型，我们现在可以尝试运行main.rs中example_task函数返回的任务：

1. // in src/main.rs

3. use blog_os::task::{Task, simple_executor::SimpleExecutor};

5. fn kernel_main(boot_info: &'static BootInfo) -> ! {
6. // […] initialization routines, including `init_heap`

8. let mut executor = SimpleExecutor::new();
9. executor.spawn(Task::new(example_task()));
10. executor.run();

12. // […] test_main, "it did not crash" message, hlt_loop
13. }

16. // Below is the example_task function again so that you don't have to scroll up

18. async fn async_number() -> u32 {
19. 42
20. }

22. async fn example_task() {
23. let number = async_number().await;
24. println!("async number: {}", number);
25. }

当我们运行它时，我们可以看到预期的“async number: 42”消息打印到屏幕上：

让我们总结一下此示例发生的各个步骤：

• 首先，使用一个空的task_queue创建一个我们SimpleExecutor类型的新实例。
• 接下来，我们调用异步example_task函数，该函数返回一个future。我们将这个future包装在Task类型中，将其移动到堆中并固定，然后通过spawn方法将任务添加到Executor的task_queue。
• 然后，我们调用该run方法以开始执行队列中的单个任务。

这涉及：

• 从task_queue头部弹出任务。
• 为任务创建一个RawWaker，将其转换为Waker实例，然后从中创建一个Context实例。
• 使用我们刚创建的Context实例在任务的future上调用poll方法。
• 由于example_task无需等待，因此可以直接在第一次poll调用就运行到底。也就会打印出“async number:42”。
• 由于example_task直接返回Poll::Ready，因此不会将其添加回任务队列。
• task_queue变为空后，run方法返回。我们的kernel_main功能继续执行，并且打印”It did not crash!“信息。

异步键盘输入

我们简单的executor不使用Waker通知，而是循环遍历所有任务，直到完成为止。对于我们的例子来说，这不是问题，因为我们example_task可以直接在第一次poll调用时就运行完。要观察适当Waker实现的性能优势，我们首先需要创建一个真正异步的任务，即在第一次poll调用时可能返回Poll::Pending的任务。

我们的系统中已经存在某种异步性：硬件中断。正如我们在硬件中断一文中了解到的那样，硬件中断可以在取决于某些外部设备的任意时间发生。例如，在经过一段预定义的时间后，硬件计时器将中断发送到CPU。当CPU接收到中断时，它将立即将控制权转移到在中断描述符表（IDT）中定义的相应处理程序。

下面，我们将基于键盘中断创建一个异步任务。键盘中断是一个很好的选择，因为它既不确定又对延迟至关重要。非确定性意味着无法预测下一次按键的发生时间，因为它完全取决于用户。延迟关键性意味着我们要及时处理键盘输入，否则用户会感到系统卡顿。为了以有效的方式支持此类任务，executor必须具有适当的Waker通知支持，这一点至关重要。

扫描码队列

当前，我们直接在中断处理程序中处理键盘输入。从长远来看，这不是一个好主意，因为中断处理程序应尽可能短，因为它们可能会中断重要的工作。更好的方案是，中断处理程序仅执行必要的最少工作量（例如，读取键盘扫描码），而将其余工作（例如，解释扫描码）留给后台任务。

将工作委派给后台任务的常见模式是创建某种队列。中断处理程序将工作单元推送到队列，而后台任务处理队列中的工作。应用于我们的键盘中断，这意味着中断处理程序仅从键盘读取扫描代码，然后将其推送到队列，然后返回。键盘任务位于队列的另一端，并解释和处理推入队列的每个扫描代码：

该队列的一个简单实现可以是用互斥锁保护的VecDeque。但是，在中断处理程序中使用互斥锁不是一个好主意，因为它很容易导致死锁。例如，当用户在键盘任务锁定队列时按下某个键时，中断处理程序将尝试再次获取该锁定并无限期挂起。这种方法的另一个问题是，VecDeque满时，会进行新的堆分配来自动增加其容量。这可能再次导致死锁，因为我们的分配器还在内部使用了互斥锁。更进一步的问题是，当堆碎片化时，堆分配可能会失败或花费大量时间。

为避免这些问题，我们需要更好的一个队列实现，该队列实现不需要互斥量或在push操作时分配内存。可以通过使用无锁原子操作来推送和弹出元素来实现此类队列。这样，push和pop操作仅需要&self引用，因此无需互斥即可使用。为了避免在push时分配内存，可以使用预先分配的固定大小的缓冲区来支持队列。虽然这使队列有界（即具有一个固定的最大长度），但实际上通常可以为队列长度定义合理的上限，因此这样做问题不大。

crossbeam Crate

以正确有效的方式实现这样的队列非常困难，因此我建议坚持使用经过良好测试的现有实现。有一个流行的Rust项目crossbeam实现了并发编程的各种无锁类型。它提供了一个名为ArrayQueue的类型，正是这种情况下我们需要的类型。而且我们很幸运：该类型与具有内存分配支持的no_std crate完全兼容。

要使用该类型，我们需要添加一个依赖项crossbeam-queue crate：

1. # in Cargo.toml

3. [dependencies.crossbeam-queue]
4. version = "0.2.1"
5. default-features = false
6. features = ["alloc"]

默认情况下，crate使用了标准库。为了使其与no_std兼容，我们需要禁用其默认功能，同时启用该alloc功能。（请注意，crossbeam crate在这里不能用，因为它在no_std下没有导出 queue模块。我提出了拉取请求以解决此问题，但这个版本尚未在crates.io上发布。）

队列的实现

使用该ArrayQueue类型，我们现在可以在新task::keyboard模块中创建全局扫描代码队列：

1. // in src/task/mod.rs

3. pub mod keyboard;

``` 1. // in src/task/keyboard.rs

1. use conquer_once::spin::OnceCell; 4

（本文超出站点单文档体积上限，已截断）