type
status
date
slug
summary
tags
category
icon
password
考虑在内存中尽量同时驻留多个应用，这样处理器的利用率就会提高。但只有一个程序执行完毕后或主动放弃执行，处理器才能执行另外一个程序
我们把这种运行方式称为 多道程序(Multiprogramming)
  • 协作式操作系统
      • 让应用在执行 I/O 操作或空闲时，可以主动 释放处理器 ，让其他应用继续执行。当然执行 放弃处理器 的操作算是一种对处理器资源的直接管理，所以应用程序可以发出这样的系统调用，让操作系统来具体完成。这样的操作系统就是支持 多道程序 或 协作式多任务 的协作式操作系统
  • 抢占式操作系统
      • 应用程序员在编写程序时，无法做到在程序的合适位置放置 放弃处理器的系统调用请求 ，这样系统的整体利用率还是无法提高
      操作系统可进一步利用某种以固定时长为时间间隔的外设中断（比如时钟中断）来强制打断一个程序的执行，这样一个程序只能运行一段时间（可以简称为一个时间片, Time Slice）就一定会让出处理器，且操作系统可以在处理外设的 I/O 响应后，让不同应用程序分时占用处理器执行，并可通过统计程序占用处理器的总执行时间，来评估运行的程序对处理器资源的消耗。我们把这种运行方式称为 分时共享（Time Sharing） 或 抢占式多任务（Multitasking） ，也可合并在一起称为 分时多任务 
      我们可以把一个程序的一次完整执行过程称为一次 任务 (Task)，把一个程序在一个时间片（Time Slice）上占用处理器执行的过程称为一个 任务片 (Task Slice)。操作系统对不同程序的执行过程中的 任务片 进行调度和管理，即通过平衡各个程序在整个时间段上的任务片数量，就能达到一定程度的系统公平和高效的系统效率。在一个包含多个时间片的时间段上，会有属于不同程序的多个任务片在轮流占用处理器执行，这样的操作系统就是支持 分时多任务 或 抢占式多任务 的抢占式操作系统。
  • 批处理系统和支持多道程序的系统的区别
      • 对于批处理系统而言，它在一段时间内可以处理一批程序，但内存中只放一个程序，处理器一次只能运行一个程序，只有在一个程序运行完毕后再把另外一个程序调入内存，并执行。即批处理系统不能交错执行多个程序。
      对于支持多道程序的系统而言，它在一段时间内也可以处理一批程序，但内存中可以放多个程序，一个程序在执行过程中，可以主动（协作式）或被动（抢占式）地放弃自己的执行，让另外一个程序执行。即支持多道程序的系统可以交错地执行多个程序，这样系统的利用率会更高。
协作式多道程序操作系统 – CoopOS的总体结构如下图所示：
notion image
  • CoopOS进一步改进了 AppManager 内核模块，把它拆分为负责加载应用的 Loader 内核模块和管理应用运行过程的 TaskManager 内核模块
  •  TaskManager 通过 task 任务控制块来管理应用程序的执行过程，支持应用程序主动放弃 CPU 并切换到另一个应用继续执行，从而提高系统整体执行效率
  • 应用程序在运行时有自己所在的内存空间和栈，确保被切换时相关信息不会被其他应用破坏
  • 如果当前应用程序正在运行，则该应用对应的任务处于运行（Running）状态；如果该应用主动放弃处理器，则该应用对应的任务处于就绪（Ready）状态
  • 操作系统进行任务切换时，需要把要暂停任务的上下文（即任务用到的通用寄存器）保存起来，把要继续执行的任务的上下文恢复为暂停前的内容，这样就能让不同的应用协同使用处理器了
分时多任务操作系统 – TimesharingOS：
notion image
  • TimesharingOS最大的变化是改进了 Trap_handler 内核模块，支持时钟中断，从而可以抢占应用的执行
  • 并通过进一步改进 TaskManager 内核模块，提供任务调度功能，这样可以在收到时钟中断后统计任务的使用时间片，如果任务的时间片用完后，则切换任务

多道程序放置与加载

通过具体实现，可以看到多个应用程序被一次性地加载到内存中，这样在切换到另外一个应用程序执行会很快，不像前一章介绍的操作系统，还要有清空前一个应用，然后加载当前应用的过程开销。

多道程序放置

不同的是，我们对相关模块进行了调整：在第二章中应用的加载和执行进度控制都交给 batch 子模块，而在第三章中我们将应用的加载这部分功能分离出来在 loader 子模块中实现，应用的执行和切换功能则交给 task 子模块。
要一次加载运行多个程序，就要求每个用户程序被内核加载到内存中的起始地址都不同。 为此，我们编写脚本 user/build.py 为每个应用定制各自的起始地址。 它的思路很简单，对于每一个应用程序，使用 cargo rustc 单独编译， 用 -Clink-args=-Ttext=xxxx 选项指定链接时 .text 段的地址为 0x80400000 + app_id * 0x20000 。
notion image

多道程序加载

找到第i个应用程序的起始地址
在pub fn load_apps()中，通过这个循环取得第i个程序的起始地址，并把内存中第i个程序从链接后的的地址，复制到从base_i开始，长为app_start[i + 1] - app_start[i]的这一片地址空间来
因此应用程序就是从地址APP_BASE_ADDRESS: usize = 0x80400000开始，按APP_SIZE_LIMIT: usize = 0x20000这个大小分成快依次存储的

执行应用程序

当多道程序的初始化放置工作完成，或者是某个应用程序运行结束或出错的时候，我们要调用 run_next_app 函数切换到下一个应用程序。此时 CPU 运行在 S 特权级的操作系统中，而操作系统希望能够切换到 U 特权级去运行应用程序
操作系统知道每个应用程序预先加载在内存中的位置，这就需要设置应用程序返回的不同 Trap 上下文（Trap 上下文中保存了放置程序起始地址的 epc 寄存器内容）：
  • 跳转到应用程序（编号 𝑖 ）的入口点 
  • 将使用的栈切换到用户栈

任务切换

任务切换的设计与实现

本节所讲的任务切换是第二章提及的 Trap 控制流切换之外的另一种异常控制流，都是描述两条控制流之间的切换，如果将它和 Trap 切换进行比较，会有如下异同：
  • 与 Trap 切换不同，它不涉及特权级切换；
  • 与 Trap 切换不同，它的一部分是由编译器帮忙完成的；
  • 与 Trap 切换相同，它对应用是透明的。
因为任务会在某个时间中断也会在某个时间恢复执行，因此需要在栈上保存任务上下文
对于当前正在执行的任务的 Trap 控制流，我们用一个名为 current_task_cx_ptr 的变量来保存放置当前任务上下文的地址；而用 next_task_cx_ptr 的变量来保存放置下一个要执行任务的上下文的地址。利用 C 语言的引用来描述的话就是：
notion image
在上图中我们假设某次 __switch 调用要从 Trap 控制流 A 切换到 B，一共可以分为四个阶段，在每个阶段中我们都给出了 A 和 B 内核栈上的内容
  1. 在A的内核栈上，只有Trap上下文
  1. 保存任务A使用的寄存器数据，当前current_task_cx_ptr指向A的任务上下文
  1. 读取next_task_cx_ptr，指向B之前保存的任务上下文，根据B任务上下文保存的内容来恢复B的寄存器数据
  1. 寄存器数据恢复完成后，sp指向B的内核栈，让B可以从调用__switch函数时开始继续向后执行，A进入暂停状态
💡
在 RISC-V 架构中，ra 是一个特殊的寄存器，通常用于存储函数调用的返回地址。ra 是 Return Address 的缩写，它存储了函数在执行完后需要返回的地址，也就是函数调用指令的下一条指令地址。
在 RISC-V 架构中，a0 是一个通用寄存器，用途比较灵活，通常用于传递参数和存储临时数据。虽然 a0 寄存器本身只能存储一个 32 位的数值，但是在这个汇编代码中，a0 寄存器被用来存储内存地址，而不是直接存储数据。
在这个上下文中，a0 寄存器被用来作为一个基地址，通过指定偏移量来访问内存中的不同位置。例如，sd sp, 8(a0) 将当前任务的栈指针 (sp) 的值保存到地址 a0 + 8 处，sd ra, 0(a0) 将返回地址 (ra) 的值保存到地址 a0 处。而在 SAVE_SN 宏中，通过将寄存器的值保存到 a0 加上某个偏移量的地址处，来实现将多个寄存器的信息保存到内存中的目的。
__switch 函数：
定义了一个宏，意思是接收一个参数n，把sn这个寄存器的数据，存到(a0)+(n+2)*8这个地址处
保存A程序的任务上下文：
  • 将当前栈指针存到(a0)+8地址处
  • 将当前程序的返回地址（即__switch函数的下一条指令，__switch函数的返回地址）存到(a0)地址处
  • 将s0~s11存储到(a0)+2*8之后的连续12块8字节的内存空间中
恢复B程序的任务上下文：
  • 将(a1)地址处的寄存器信息加载到ra中，此时ra里面应该是B程序的函数调用返回地址，即调用__switch函数的下一条语句
  • 将s0~s11寄存器的信息加载回去
  • 将当前栈指针指向(a1)+8地址处的寄存器，即换栈，将当前栈换位B程序的栈
__switch函数return，继续执行B任务：
任务上下文结构体的定义：
保存 ra 很重要，它记录了 __switch 函数返回之后应该跳转到哪里继续执行，从而在任务切换完成并 ret 之后能到正确的位置
notion image
所以Trap的上下文是用于恢复到用户态在陷入Trap之后的指令，Task上下文是用于恢复到在Trap处理的过程中调用__switch之后的指令

管理多道程序

对 任务 的概念进行进一步扩展和延伸：形成了
  • 任务运行状态：任务从开始到结束执行过程中所处的不同运行状态：未初始化、准备执行、正在执行、已退出
  • 任务控制块：管理程序的执行过程的任务上下文，控制程序的执行与暂停
  • 任务相关系统调用：应用程序和操作系统之间的接口，用于程序主动暂停 sys_yield 和主动退出 sys_exit

yield 系统调用

外设，即输入输出(I/O, Input/Output) ：
  • CPU 会把 I/O 请求传递给外设，待外设处理完毕之后， CPU 便可以从外设读到其发出的 I/O 请求的处理结果。
  • 在 CPU 对外设发出了 I/O 请求之后，由于 CPU 速度远快于外设速度，使得 CPU 不能立即继续执行，而是要等待（忙等或睡眠等）外设将请求处理完毕并拿到完整的处理结果之后才能继续。
  • 通常外设会提供一个可读的寄存器记录它目前的工作状态，于是 CPU 需要不断原地循环读取它直到它的结果显示设备已经将请求处理完毕了，才能继续执行（这就是 忙等 的含义）。
  • 外设的计算速度和 CPU 相比可能慢了几个数量级，这就导致 CPU 有大量时间浪费在等待外设这件事情上，这段时间它几乎没有做任何事情，也在一定程度上造成了 CPU 的利用率不够理想。
notion image
上图描述了一种多道程序执行的典型情况。其中横轴为时间线，纵轴为正在执行的实体。 开始时，蓝色应用向外设提交了一个请求，外设随即开始工作， 但是它要一段时间后才能返回结果。蓝色应用于是调用 sys_yield 交出 CPU 使用权， 内核让绿色应用继续执行。一段时间后 CPU 切换回蓝色应用，发现外设仍未返回结果， 于是再次 sys_yield 。直到第二次切换回蓝色应用，外设才处理完请求，于是蓝色应用终于可以向下执行了。

任务控制块与任务运行状态

把任务上下文和任务状态都装在任务控制块结构体中
在内核中，任务控制块就是应用的管理单位

任务管理器

与之前的AppManager 一样，TaskManager里面也包括任务数量和inner，其中inner是一个UPSafeCell
它不允许多个读写同时存在，依靠RefCell提供的可变性检查，保证只有一个可变借用存在
初始化 TaskManager 的全局实例 TASK_MANAGER：
  • 首先初始化tasks数组，里面包含MAX_APP_NUM个任务控制块
  • task上下文，寄存器内容设置为全0
  • 任务状态全部设置为未初始化
  • 针对每一个任务块进行初始化，tasks.iter_mut().enumerate() 这个表达式返回一个元素为 (usize, &mut T) 类型的迭代器
  • 将其运行状态设置为Ready
  • 初始化它的任务上下文
    • 将它的任务上下文压入它的栈
    • 入口：APP_BASE_ADDRESS + app_id * APP_SIZE_LIMIT
    • 栈空间从高地址向低地址增长，因此现在第app_id个任务的栈指针应该在地址最高的地方
返回一个TaskManager实例

实现 sys_yield 和 sys_exit

  • sys_yield 的实现用到了 task 子模块提供的 suspend_current_and_run_next 接口，这个接口如字面含义，就是暂停当前的应用并切换到下个应用
  • sys_exit 基于 task 子模块提供的 exit_current_and_run_next 接口，它的含义是退出当前的应用并切换到下个应用
那么 suspend_current_and_run_next 和 exit_current_and_run_next 各是如何实现的呢？
  • suspend：
    • 修改当前任务状态为Ready
    • 运行下一个任务
  • exit：
    • 修改当前任务状态为Exit
    • 运行下一个任务
再看 run_next_task 的实现：
  • find_next_task 方法尝试寻找一个运行状态为 Ready 的应用并返回其 ID
  • 如果找到了，就修改这个任务的状态为Running，并把任务管理器inner的当前任务修改为找到的新的任务
  • 分别拿到当前应用 current_task_cx_ptr 和即将被切换到的应用 next_task_cx_ptr 的任务上下文指针
  • 在实际切换之前我们需要手动 drop 掉我们获取到的 TaskManagerInner 的来自 UPSafeCell 的借用标记
  • 调用__switch函数进行切换
notion image

第一次进入用户态

靠的主要是这个init_app_cx，它构造该任务的 Trap 上下文（包括应用入口地址和用户栈指针）并将其压入到内核栈顶
goto_restore将函数返回地址设置为__restore，sp设置为栈顶指针，这样一来函数返回时就会恢复这个任务的上下文，继续执行该任务
在 rust_main 中我们调用 task::run_first_task 来开始应用的执行
寄存器表：
notion image

分时多任务系统

现代的任务调度算法基本都是抢占式的，它要求每个应用只能连续执行一段时间，然后内核就会将它强制性切换出去。 一般将 时间片 (Time Slice) 作为应用连续执行时长的度量单位，每个时间片可能在毫秒量级。 简单起见，我们使用 时间片轮转算法 (RR, Round-Robin) 来对应用进行调度。

时钟中断与计时器

中断 (Interrupt) 和我们第二章中介绍的异常（包括程序错误导致或执行 Trap 类指令如用于系统调用的 ecall ）一样都是一种 Trap ，但是它们被触发的原因却是不同的。对于某个处理器核而言， 异常与当前 CPU 的指令执行是 同步 (Synchronous) 的，异常被触发的原因一定能够追溯到某条指令的执行；而中断则 异步 (Asynchronous) 于当前正在进行的指令，也就是说中断来自于哪个外设以及中断如何触发完全与处理器正在执行的当前指令无关。
实现调度算法需要计时。RISC-V 要求处理器维护时钟计数器 mtime，还有另外一个 CSR  mtimecmp 。 一旦计数器 mtime 的值超过了 mtimecmp，就会触发一次时钟中断。
设置x毫秒之后一个 S 特权级时钟中断就会被触发
获取以微秒为单位的当前时间
功能：获取当前的时间，保存在 TimeVal 结构体 ts 中，_tz 在我们的实现中忽略
返回值表示是否成功

抢占式调度

有了时钟中断和计时器，抢占式调度就很容易实现了：
我们只需在 trap_handler 函数下新增一个条件分支跳转，当发现触发了一个 S 特权级时钟中断的时候，首先重新设置一个 10ms 的计时器，然后调用上一小节提到的  suspend_current_and_run_next  函数暂停当前应用并切换到下一个。
Relate Posts
CS144：Introduction to Computer Networking，Winter 2024
第三阶段项目6学习记录
rCore-Tutorial-Guide 2024 春季学期
CS144—Lab5
CS144—Lab4
CS144—Lab2
数组Computer Networking Notes
  • Giscus