引言

本章导读

本章展现了操作系统一系列功能：

  • 通过提前加载应用程序到内存，减少应用程序切换开销

  • 通过协作机制支持程序主动放弃处理器，提高系统执行效率

  • 通抢占机制支持程序被动放弃处理器，提高不同程序对处理器资源使用的公平性，也进一步提高了应用对I/O事件的响应效率

上一章，我们实现了一个简单的批处理系统。首先，它能够自动按照顺序加载并运行序列中的每一个应用，当一个应用运行结束之后无需操作员的手动替换；另一方面，在硬件提供的特权级机制的帮助下，运行在更高特权级的它不会受到有意或者无意出错的应用的影响，可以全方位监控运行在用户态特权级的应用的执行，一旦应用越过了硬件所设置特权级界限或主动申请获得操作系统的服务，就会触发 Trap 并进入到批处理系统中进行处理。无论原因是应用出错或是应用声明自己执行完毕，批处理系统都只需要加载序列中的下一个应用并进入执行。可以看到批处理系统的特性是：在内存中同一时间最多只需驻留一个应用。这是因为只有当一个应用出错或退出之后，批处理系统才会去将另一个应用加载到相同的一块内存区域。

而计算机硬件在快速发展，内存容量在逐渐增大，处理器的速度也在增加，外设IO性能方面的进展不大。这就使得以往内存只能放下一个程序的情况得到很大改善，但处理器的空闲程度加大了。于是科学家就开始考虑在内存中尽量同时驻留多个应用，这样处理器的利用率就会提高。但只有一个程序执行完毕后或主动放弃执行，处理器才能执行另外一个程序。这种运行方式称为 多道程序 。

协作式操作系统

早期的计算机系统大部分是单处理器计算机系统。当处理器进一步发展后，它与IO的速度差距也进一步拉大。这时计算机科学家发现，在 多道程序 运行方式下，一个程序如果不让出处理器，其他程序是无法执行的。如果一个应用由于IO操作让处理器空闲下来或让处理器忙等，那其他需要处理器资源进行计算的应用还是没法使用空闲的处理器资源。于是就想到，让应用在执行IO操作时，可以主动 释放处理器 ，让其他应用继续执行。当然执行 放弃处理器 的操作算是一种对处理器资源的直接管理，所以应用程序可以发出这样的系统调用，让操作系统来具体完成。这样的操作系统就是支持 多道程序 协作式操作系统。

抢占式操作系统

计算机科学家很快发现，编写应用程序的科学家（简称应用程序员）来自不同的领域，他们不一定有友好互助的意识，也不了解其他程序的执行情况，很难（也没必要）有提高整个系统利用率上的大局观。在他们的脑海里，整个计算机就应该是为他们自己的应用准备的，不用考虑其他程序的运行。这导致应用程序员在编写程序时，无法做到在程序的合适位置放置 放弃处理器的系统调用请求 ，这样系统的整体利用率还是无法提高。

所以，站在系统的层面，还是需要有一种办法能强制打断应用程序的执行，来提高整个系统的效率，让在整个系统中执行的多个程序之间占用计算机资源的情况相对公平一些。根据计算机系统的硬件设计，为提高I/O效率，外设可以通过硬件中断机制来与处理机进行I/O交互操作。这种硬件中断机制·可随时打断应用程序的执行，并让操作系统来完成对外设的I/O响应。

而操作系统可进一步利用某种以固定时长为时间间隔的外设中断（比如时钟中断）来强制打断一个程序的执行，这样一个程序只能运行一段时间（可以简称为一个时间片, Time Slice）就一定会让出处理器，且操作系统可以在处理外设的I/O响应后，让不同应用程序分时占用处理器执行，并可通过程序占用处理器的总执行时间来评估运行的程序对处理器资源的消耗。

我们可以把一个程序在一个时间片上占用处理器执行的过程称为一个 任务 (Task)，让操作系统对不同程序的 任务 进行管理。通过平衡各个程序在整个时间段上的任务数，就达到一定程度的系统公平和高效的系统效率。在一个包含多个时间片的时间段上，会有属于不同程序的多个任务在轮流占用处理器执行，这样的操作系统就是支持 分时多任务 的抢占式操作系统。

本章所介绍的多道程序和分时多任务系统都有一些共同的特点：在内存中同一时间可以驻留多个应用。所有的应用都是在系统启动的时候分别加载到内存的不同区域中。由于目前计算机系统中只有一个处理器，则同一时间最多只有一个应用在执行，剩下的应用则处于就绪状态，需要内核将处理器分配给它们才能开始执行。一旦应用开始执行，它就处于运行状态了。

本章主要是设计和实现建立支持 多道程序 的二叠纪“锯齿螈”初级操作系统、支持多道程序的三叠纪“始初龙”协作式操作系统和支持 分时多任务 的三叠纪“腔骨龙”抢占式操作系统，从而对可支持运行一批应用程序的多种执行环境有一个全面和深入的理解，并可归纳抽象出 任务 ， 任务切换 等操作系统的概念。

注解

读者也许会有疑问：由于只有一个 处理器，即使这样做，同一时间最多还是只能运行一个应用，还浪费了更多的内存来把所有 的应用都加载进来。那么这样做有什么意义呢？

读者可以带着这个问题继续看下去。后面我们会介绍这样做到底能够解决什么问题。

实践体验

多道程序 (Multiprogramming) 和 分时多任务 (Time-Sharing Multitasking) 对于应用的要求是不同的，因此我们分别为它们编写了不同的应用，代码也被放在两个不同的分支上。对于它们更加深入的讲解请参考本章正文，我们在引言中仅给出运行代码的方法。

获取多道程序的代码：

  1. $ git clone https://github.com/rcore-os/rCore-Tutorial-v3.git
  2. $ cd rCore-Tutorial-v3
  3. $ git checkout ch3-coop

获取分时多任务系统的代码：

  1. $ git clone https://github.com/rcore-os/rCore-Tutorial-v3.git
  2. $ cd rCore-Tutorial-v3
  3. $ git checkout ch3

在 qemu 模拟器上运行本章代码：

  1. $ cd os
  2. $ make run

将 Maix 系列开发板连接到 PC，并在上面运行本章代码：

  1. $ cd os
  2. $ make run BOARD=k210

多道程序的应用分别会输出一个不同的字母矩阵。当他们交替执行的时候，以 k210 平台为例，我们将看到字母行的交错输出：

  1. [rustsbi] Version 0.1.0
  2. .______       __    __      _______.___________.  _______..______   __
  3. |   _  \     |  |  |  |    /       |           | /       ||   _  \ |  |
  4. |  |_)  |    |  |  |  |   |   (----`---|  |----`|   (----`|  |_)  ||  |
  5. |      /     |  |  |  |    \   \       |  |      \   \    |   _  < |  |
  6. |  |\  \----.|  `--'  |.----)   |      |  |  .----)   |   |  |_)  ||  |
  7. | _| `._____| \______/ |_______/       |__|  |_______/    |______/ |__|
  9. [rustsbi] Platform: K210
  10. [rustsbi] misa: RV64ACDFIMSU
  11. [rustsbi] mideleg: 0x222
  12. [rustsbi] medeleg: 0x1ab
  13. [rustsbi] Kernel entry: 0x80020000
  14. [kernel] Hello, world!
  15. AAAAAAAAAA [1/5]
  16. BBBBBBBBBB [1/2]
  17. CCCCCCCCCC [1/3]
  18. AAAAAAAAAA [2/5]
  19. BBBBBBBBBB [2/2]
  20. CCCCCCCCCC [2/3]
  21. AAAAAAAAAA [3/5]
  22. Test write_b OK!
  23. [kernel] Application exited with code 0
  24. CCCCCCCCCC [3/3]
  25. AAAAAAAAAA [4/5]
  26. Test write_c OK!
  27. [kernel] Application exited with code 0
  28. AAAAAAAAAA [5/5]
  29. Test write_a OK!
  30. [kernel] Application exited with code 0
  31. [kernel] Panicked at src/task/mod.rs:97 All applications completed!
  32. [rustsbi] reset triggered! todo: shutdown all harts on k210; program halt

分时多任务系统应用分为两种。编号为 00/01/02 的应用分别会计算质数 3/5/7 的幂次对一个大质数取模的余数，并会将结果阶段性输出。编号为 03 的 应用则会等待三秒钟之后再退出。以 k210 平台为例，我们将会看到 00/01/02 三个应用分段完成它们的计算任务，而应用 03 由于等待时间过长总是 最后一个结束执行。

  1. [rustsbi] RustSBI version 0.1.1
  2. .______       __    __      _______.___________.  _______..______   __
  3. |   _  \     |  |  |  |    /       |           | /       ||   _  \ |  |
  4. |  |_)  |    |  |  |  |   |   (----`---|  |----`|   (----`|  |_)  ||  |
  5. |      /     |  |  |  |    \   \       |  |      \   \    |   _  < |  |
  6. |  |\  \----.|  `--'  |.----)   |      |  |  .----)   |   |  |_)  ||  |
  7. | _| `._____| \______/ |_______/       |__|  |_______/    |______/ |__|
  9. [rustsbi] Platform: K210 (Version 0.1.0)
  10. [rustsbi] misa: RV64ACDFIMSU
  11. [rustsbi] mideleg: 0x22
  12. [rustsbi] medeleg: 0x1ab
  13. [rustsbi] Kernel entry: 0x80020000
  14. [kernel] Hello, world!
  15. power_3 [10000/200000]
  16. power_3 [20000/200000]
  17. power_3 [30000/200000power_5 [10000/140000]
  18. power_5 [20000/140000]
  19. power_5 [30000/140000power_7 [10000/160000]
  20. power_7 [20000/160000]
  21. power_7 [30000/160000]
  22. ]
  23. power_3 [40000/200000]
  24. power_3 [50000/200000]
  25. power_3 [60000/200000]
  26. power_5 [40000/140000]
  27. power_5 [50000/140000]
  28. power_5 [60000/140000power_7 [40000/160000]
  29. power_7 [50000/160000]
  30. power_7 [60000/160000]
  31. ]
  32. power_3 [70000/200000]
  33. power_3 [80000/200000]
  34. power_3 [90000/200000]
  35. power_5 [70000/140000]
  36. power_5 [80000/140000]
  37. power_5 [90000/140000power_7 [70000/160000]
  38. power_7 [80000/160000]
  39. power_7 [90000/160000]
  40. ]
  41. power_3 [100000/200000]
  42. power_3 [110000/200000]
  43. power_3 [120000/]
  44. power_5 [100000/140000]
  45. power_5 [110000/140000]
  46. power_5 [120000/power_7 [100000/160000]
  47. power_7 [110000/160000]
  48. power_7 [120000/160000200000]
  49. power_3 [130000/200000]
  50. power_3 [140000/200000]
  51. power_3 [150000140000]
  52. power_5 [130000/140000]
  53. power_5 [140000/140000]
  54. 5^140000 = 386471875]
  55. power_7 [130000/160000]
  56. power_7 [140000/160000]
  57. power_7 [150000/160000/200000]
  58. power_3 [160000/200000]
  59. power_3 [170000/200000]
  60. power_3 [
  61. Test power_5 OK!
  62. [kernel] Application exited with code 0
  63. ]
  64. power_7 [160000/160000]
  65. 7180000/200000]
  66. power_3 [190000/200000]
  67. power_3 [200000/200000]
  68. 3^200000 = 871008973^160000 = 667897727
  69. Test power_7 OK!
  70. [kernel] Application exited with code 0
  72. Test power_3 OK!
  73. [kernel] Application exited with code 0
  74. Test sleep OK!
  75. [kernel] Application exited with code 0
  76. [kernel] Panicked at src/task/mod.rs:98 All applications completed!
  77. [rustsbi] reset triggered! todo: shutdown all harts on k210; program halt. Type: 0, reason: 0

输出结果看上去有一些混乱，原因是用户程序的每个 println! 往往会被拆分成多个 sys_write 系统调用提交给内核。有兴趣的同学可以参考 println! 宏的实现。

另外需要说明的是一点是：与上一章不同，应用的编号不再决定其被加载运行的先后顺序，而仅仅能够改变应用被加载到内存中的位置。

本章代码树

  1.  1
  2.  2
  3.  3
  4.  4
  5.  5
  6.  6
  7.  7
  8.  8
  9.  9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  1. ./os/src
  2. Rust        16 Files   481 Lines
  3. Assembly     3 Files    84 Lines
  5. ├── bootloader
  6. │   ├── rustsbi-k210.bin
  7. │   └── rustsbi-qemu.bin
  8. ├── LICENSE
  9. ├── os
  10. │   ├── build.rs
  11. │   ├── Cargo.toml
  12. │   ├── Makefile
  13. │   └── src
  14. │       ├── batch.rs(移除：功能分别拆分到 loader 和 task 两个子模块)
  15. │       ├── config.rs(新增：保存内核的一些配置)
  16. │       ├── console.rs
  17. │       ├── entry.asm
  18. │       ├── lang_items.rs
  19. │       ├── link_app.S
  20. │       ├── linker-k210.ld
  21. │       ├── linker-qemu.ld
  22. │       ├── loader.rs(新增：将应用加载到内存并进行管理)
  23. │       ├── main.rs(修改：主函数进行了修改)
  24. │       ├── sbi.rs(修改：引入新的 sbi call set_timer)
  25. │       ├── syscall(修改：新增若干 syscall)
  26. │       │   ├── fs.rs
  27. │       │   ├── mod.rs
  28. │       │   └── process.rs
  29. │       ├── task(新增：task 子模块，主要负责任务管理)
  30. │       │   ├── context.rs(引入 Task 上下文 TaskContext)
  31. │       │   ├── mod.rs(全局任务管理器和提供给其他模块的接口)
  32. │       │   ├── switch.rs(将任务切换的汇编代码解释为 Rust 接口 __switch)
  33. │       │   ├── switch.S(任务切换的汇编代码)
  34. │       │   └── task.rs(任务控制块 TaskControlBlock 和任务状态 TaskStatus 的定义)
  35. │       ├── timer.rs(新增：计时器相关)
  36. │       └── trap
  37. │           ├── context.rs
  38. │           ├── mod.rs(修改：时钟中断相应处理)
  39. │           └── trap.S
  40. ├── README.md
  41. ├── rust-toolchain
  42. ├── tools
  43. │   ├── kflash.py
  44. │   ├── LICENSE
  45. │   ├── package.json
  46. │   ├── README.rst
  47. │   └── setup.py
  48. └── user
  49.    ├── build.py(新增：使用 build.py 构建应用使得它们占用的物理地址区间不相交)
  50.    ├── Cargo.toml
  51.    ├── Makefile(修改：使用 build.py 构建应用)
  52.    └── src
  53.       ├── bin(修改：换成第三章测例)
  54.       │   ├── 00power_3.rs
  55.       │   ├── 01power_5.rs
  56.       │   ├── 02power_7.rs
  57.       │   └── 03sleep.rs
  58.       ├── console.rs
  59.       ├── lang_items.rs
  60.       ├── lib.rs
  61.       ├── linker.ld
  62.       └── syscall.rs

本章代码导读

本章的重点是实现对应用之间的协作式和抢占式任务切换的操作系统支持。与上一章的操作系统实现相比，有如下一些不同的情况导致实现上也有不同：

  • 多个应用同时放在内存中，所以他们的起始地址是不同的，且地址范围不能重叠

  • 应用在整个执行过程中会暂停或被抢占，即会有主动或被动的任务切换

对于第一个不同，需要对应用程序的地址空间布局进行调整，每个应用的地址空间都不相同，且不能重叠。这并不要修改应用程序本身。通过一个脚本 build.py 来让编译器在编译不同应用时用到的链接脚本 linker.ld 中的 BASE_ADDRESS 都不同，且有足够大的地址间隔。这样就可以让每个应用所在的内存空间是不同的。

对于第二个不同，需要实现任务切换，这就需要在上一章的 trap 上下文切换的基础上，再加上一个 task 上下文切换，才能完成完整的任务切换。这里面的关键数据结构是表示应用执行上下文的 TaskContext 和具体完成上下文切换的汇编语言编写的 __switch 函数。一个应用的执行需要被操作系统管理起来，这是通过 TaskControlBlock 数据结构来表示应用执行上下文的动态过程和动态状态（运行态、就绪态等）。再加上让应用程序第一次执行的前期初始化准备而建立的 TaskManager 数据结构的全局变量实例 TASK_MANAGER ，形成了本章的难点部分。

当然，但应用程序可以在用户态执行后，还需要有新的系统调用 sys_yield 的实现来支持应用自己的主动暂停；还要添加对时钟中断的处理，来支持抢占应用执行的抢占式切换。有了时钟中断，就可以在一定时间内打断应用的执行，并主动切换到另外一个应用，这部分主要是通过对 trap_handler 函数中进行扩展，来完成在时钟中断产生时可能进行的任务切换。 TaskManager 数据结构的成员函数 run_next_task 来实现基于任务控制块的切换，并会具体调用 __switch 函数完成硬件相关部分的任务上下文切换。

如果理解了上面的数据结构和相关函数的关系和访问情况，那么就可以比较容易理解本章改进后的操作系统。