第四讲 多道程序与分时多任务

第二节 实践：多道程序与分时多任务操作系统

〇 回顾

系统调用与应用程序的交互

从课程的起始，我们便重点讨论了系统调用的重要性。系统调用是应用程序获取操作系统服务的桥梁。通过介绍如读写文件等基本系统调用，帮助大家理解这一机制。对于开发者来说，这些内容相对容易从用户和应用程序的角度理解。

裸机编程与操作系统的基础

进入到课程的第二阶段，我们的学习内容开始与常规的应用开发有所不同。这时，你需要了解如何进行裸机编程，也就是直接与硬件交互的开发方式。我们关注了三个主要的知识点：

  1. 硬件与软件的启动过程：理解计算机系统是如何从硬件电源开启到加载操作系统的。
  2. 函数调用的底层实现：虽然这与编译原理课程中的内容略有不同，但同样重要，需要深入理解。
  3. 操作系统与更底层软件的关系：介绍了SBI（Supervisor Binary Interface）等软件，它们为操作系统提供服务，形成一个层次更深的软件架构。

多应用支持与特权模式

第三次课程中，我们讨论了操作系统如何支持多个应用程序同时运行。引入了特权级的概念，区分了用户态和内核态，这两者虽然相互隔离，但并非完全独立，它们之间需要通过系统调用进行通信。这种通信实现了特权级的切换，不同于常规的函数调用切换，这种特权集切换涉及到更为复杂的上下文保存与恢复操作。

应用程序的加载与执行环境构建

我们还需要掌握的是，在支持多应用的环境下，操作系统如何管理、加载并执行这些应用程序。这包括了如何在内存中构建应用的映像（image），并在需要时将它们加载至运行状态。这不仅涉及内存拷贝，还包括从特权态到用户态的状态切换。此外，操作系统还需要为每个应用程序构建和准备其执行环境，确保它们可以从初始指令开始正确执行。

一 实验目标和步骤

1.1 实验目标

  • MultiprogOS目标
    • 进一步提高系统中多个应用的总体性能和效率
  • BatchOS目标
    • 让APP与OS隔离，提高系统的安全性和效率
  • LibOS目标
    • 让应用与硬件隔离，简化应用访问硬件的难度和复杂性

多应用内存管理与调度策略

为了提高应用的资源效率，操作系统在内存中同时运行多个应用程序。关键在于确保这些应用程序能够公平且有效地共享处理器资源。我们讨论了两种基本的调度方法：

  1. 协作调度：在这种模式下，每个应用程序在执行完必要的任务后，会主动释放CPU，通过特定的系统调用让操作系统切换到另一个程序。这要求应用程序通过合作的方式，主动告诉操作系统它们已经完成了当前的任务，并准备好让出处理器。

  2. 任务上下文与线程上下文：任务切换是多任务操作系统中的一个核心功能，它涉及到任务上下文的保存与恢复。任务上下文包括了程序的所有状态信息，如寄存器、内存状态等，以保证程序可以在之后的某个时刻从同一点继续执行。这与线程上下文不同，后者更多关注于线程的执行状态。

系统级特性的实现复杂性

操作系统的设计复杂性主要体现在处理多个应用程序和任务的能力上，尤其是在它们的上下文切换处理。这包括特权级切换、任务切换和内存地址空间的管理。这些底层和复杂的处理确保了系统能够高效地在多个应用间切换，维护稳定性和安全性。

多道程序与分时多任务操作系统

  • 多道程序操作系统：在这类系统中，应用程序需要主动放弃CPU，以便操作系统可以调度其他程序执行。这种方式依赖于程序的协作性，是一种较为简单的调度策略。

  • 分时操作系统：分时系统通过时间片来实现多任务处理，自动按时间间隔切换正在执行的程序，不依赖程序的自主协作。这提高了CPU的使用效率，允许多个用户或多个程序看似同时运行。

总体思路

  • 编译：应用程序和内核独立编译，合并为一个镜像
  • 编译：应用程序需要各自的起始地址
  • 构造：系统调用服务请求接口，进程的管理与初始化
  • 构造：进程控制块，进程上下文/状态管理
  • 运行：特权级切换，进程与OS相互切换
  • 运行：进程通过系统调用/中断实现主动/被动切换

多应用性能提升策略

在操作系统的设计中，我们的目标不是提升单个应用的性能，而是提升多个应用共同执行时的整体性能。一种基本的方法是将多个应用加载到内存中，以支持它们的并发执行。这种方法相较于早期只支持单个应用的操作系统，表现在能够同时处理多个应用的能力上。

任务抽象与调度

为了便于管理不同应用的分时执行，我们引入了“任务”这一抽象概念。任务抽象允许操作系统将应用的执行过程切分为不同的段，便于按时间片分配处理器资源。这有助于形成如多道程序操作系统和分时多任务操作系统这样的两种不同类型的系统模型。

多应用内存管理与地址空间

在多应用并发的环境下，每个应用都必须在内存中有独立的地址空间。这要求操作系统在编译时将多个应用及内核编译成一个统一的镜像，并在物理地址上进行适当的管理和隔离。由于现在我们处理的是多个应用，不同应用的起始地址必须不同，以确保它们能够在物理地址空间中正确执行，这与早期单应用的操作系统有显著不同。

系统调用与任务控制

为了支持应用的主动放弃处理器资源，我们需要设计新的系统调用接口来管理这一行为。这些系统调用通过进程控制块（Process Control Block, PCB）来实现，PCB负责管理程序执行的特定阶段和状态，包括保存和恢复任务上下文。任务上下文的切换通常在内核态中完成，这涉及到在内核态完成特权级切换后，进一步进行任务级切换，以允许其他程序执行。

任务的主动与被动切换

除了通过系统调用实现的主动任务切换外，操作系统还可以通过中断方式强制打断当前处理器的执行，实现任务的被动切换。这意味着无论应用是否愿意，都可能被操作系统强制切换，以响应可能的高优先级任务或处理突发事件。

通过上述探讨，我们了解到操作系统如何通过精细的内存管理、任务调度和系统调用设计，支持高效的多应用执行。这些系统级的设计不仅仅是理论上的讨论，它们是构建强大、灵活的现代操作系统所必需的实际技术实现。

bg right:53% 90%

历史背景

尽管我们今天讨论的操作系统的设计思想起源于20世纪60年代，这些理念仍然具有现实意义和应用价值。例如，早期的计算机如Libra 3已经实现了支持多个程序顺序执行的批处理系统。这些历史上的设计不仅没有过时，反而在某些特定的应用场景中依然适用。

1.2 实践步骤

在现代操作系统教学与实践中，第一步通常是重构应用程序，确保其可以在多任务环境下正确执行。具体步骤包括：

  1. 修改应用的链接脚本：这是为了使应用能在内存中被正确地定位和执行。链接脚本（LD脚本）指定了应用程序在内存中的加载地址，是由连接器在编译过程中处理的。

  2. 加载与执行多个任务：这是操作系统的基本职责，要确保多个程序可以被有效地加载和执行。在教学中，通常会提供代码的分支供学生下载和实践。

  3. 使用系统调用进行任务切换：在没有分时系统的环境下，操作系统依靠yield这类系统调用来实现任务之间的切换。每个程序执行一定的计算后，会主动通过系统调用放弃CPU，从而允许其他程序执行。这种方式要求程序是“友好”的，即能主动分享处理器资源。

实践步骤（基于BatchOS）

  • 修改APP的链接脚本(定制起始地址)
  • 加载&执行应用
  • 切换任务

bg right 100%

三个应用程序交替执行

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

包含三个应用程序，大家谦让着交替执行

user/src/bin/
├── 00write_a.rs # 5次显示 AAAAAAAAAA 字符串
├── 01write_b.rs # 2次显示 BBBBBBBBBB 字符串
└── 02write_c.rs # 3次显示 CCCCCCCCCC 字符串

运行结果

#![allow(unused)]
fn main() {
[RustSBI output]
[kernel] Hello, world!
AAAAAAAAAA [1/5]
BBBBBBBBBB [1/2]
....
CCCCCCCCCC [2/3]
AAAAAAAAAA [3/5]
Test write_b OK!
[kernel] Application exited with code 0
CCCCCCCCCC [3/3]
...
[kernel] Application exited with code 0
[kernel] Panicked at src/task/mod.rs:106 All applications completed!
}

二 多道批处理操作系统设计

应用程序的构建与链接

在多任务操作系统的环境下，为了确保每个应用程序能在其专有的地址空间运行而不互相干扰，必须对应用程序的构建过程进行特定的修改。具体操作包括：

  1. 定制链接脚本的生成：通过工具如 builder.py 为每个应用程序生成定制的链接脚本，确保每个程序的起始地址不同。
  2. 修改构建系统：调整 Makefile，以支持自动生成的链接脚本，确保在链接阶段各应用程序正确地被定位。

这些改动不仅涉及到应用程序的编译过程，还涉及到整个构建环境的调整，从而为多任务操作系统的运行打下基础。

操作系统结构的调整

对操作系统自身的改动更为复杂，主要集中在任务的加载和管理上：

  1. 模块分离：将任务加载（Loader）和任务管理（Task Manager）分为两个子模块，使得功能更加分明且易于管理。
  2. 系统调用的增加和支持：引入新的系统调用如 yield，来支持任务的主动放弃CPU，需要在操作系统中增加相应的处理逻辑，以支持状态的保存、恢复和任务切换。

汇编程序与任务切换

在实现任务切换的过程中，由于涉及到底层的寄存器操作，通常需要通过汇编语言来实现：

  1. 任务切换的汇编实现：switch.S 是一个关键的汇编程序，用于实现任务上下文的保存与恢复。这是因为高级语言难以直接操作寄存器等硬件资源。
  2. 核心数据结构：任务控制块（Task Control Block, TCB）作为核心的数据结构，存储在 task.s 中，是任务管理的基础。

硬件需求与操作系统升级

关于硬件需求，实现一个多程序操作系统并不需要对现有硬件进行功能上的增加：

  1. 利用现有硬件特性：通过充分利用现有硬件的特权级等特性，可以在不增加新硬件的前提下升级和优化操作系统，使其支持多任务处理。

这些改动说明了现代操作系统如何通过软件架构的优化和底层编程来支持更高级的多任务功能，而无需依赖于硬件的改进。

代码结构：应用程序

构建应用

└── user
    ├── build.py(新增：使用 build.py 构建应用使得它们占用的物理地址区间不相交)
    ├── Makefile(修改：使用 build.py 构建应用)
    └── src (各种应用程序)

代码结构：完善任务管理功能

改进OS：Loader模块加载和执行程序

├── os
│   └── src
│       ├── batch.rs(移除：功能分别拆分到 loader 和 task 两个子模块)
│       ├── config.rs(新增：保存内核的一些配置)
│       ├── loader.rs(新增：将应用加载到内存并进行管理)
│       ├── main.rs(修改：主函数进行了修改)
│       ├── syscall(修改：新增若干 syscall)

代码结构：进程切换

改进OS：TaskManager模块管理/切换程序的执行

├── os
│   └── src
│       ├── task(新增：task 子模块，主要负责任务管理)
│       │   ├── context.rs(引入 Task 上下文 TaskContext)
│       │   ├── mod.rs(全局任务管理器和提供给其他模块的接口)
│       │   ├── switch.rs(将任务切换的汇编代码解释为 Rust 接口 __switch)
│       │   ├── switch.S(任务切换的汇编代码)
│       │   └── task.rs(任务控制块 TaskControlBlock 和任务状态 TaskStatus 的定义)

三 应用程序设计

任务抽象和进程概念的引入

在现代操作系统中，引入了任务抽象概念，这是后来进程概念的前身。任务代表了一个程序的执行过程，包括其运行时的各种状态，这些都需要操作系统进行管理。从操作系统的角度来看，任务是一个动态的实体，其状态随着程序的执行而变化。

应用程序的地址空间管理

对于应用程序而言，它们看起来与常规应用程序相似，但实际上它们的起始地址在系统中是动态分配的。为了确保每个应用有其独立的物理空间，操作系统通过设定不同的起始地址来隔离各个程序。这通常通过在程序地址中加入特定的前缀（如0x0102等）来实现，确保每个应用在内存中占据的空间不会相互冲突。这种设计限制了应用程序的最大大小，通常为2MB，超出这个范围可能会导致内存覆盖问题。

系统调用的封装与使用

系统调用是操作系统提供给应用程序的接口，如 yield 调用，它允许应用程序主动放弃CPU，以让其他程序得以执行。这种系统调用通常被封装在用户级库中，如 lib 库，以简化应用程序的编码工作。例如，yield 函数是对底层 syscall 的封装，使得开发者无需直接编写汇编代码，而可以通过高级语言直接调用。

应用程序与内核的集成

在操作系统的设计中，一个重要的方面是如何将应用程序与内核集成成一个单一的镜像，这简化了系统的加载和执行过程。在编写应用程序时，开发者需要了解如何通过系统调用与内核交互，以及如何在编码中利用操作系统提供的各种服务。

这部分内容主要从应用程序的角度探讨了如何利用操作系统的服务，特别是通过系统调用来实现任务管理和CPU资源的共享。同时，也解释了操作系统如何管理各个应用程序的地址空间，确保它们在独立的空间内安全运行，以及如何通过封装系统调用来简化应用程序的开发过程。这些都是构建高效且安全操作系统的关键技术。

应用程序项目结构

没有更新 应用名称有数字编号

user/src/bin/
├── 00write_a.rs # 5次显示 AAAAAAAAAA 字符串
├── 01write_b.rs # 2次显示 BBBBBBBBBB 字符串
└── 02write_c.rs # 3次显示 CCCCCCCCCC 字符串

应用程序的内存布局

  • 由于每个应用被加载到的位置都不同，也就导致它们的链接脚本 linker.ld 中的 BASE_ADDRESS 都是不同的。

  • 写一个脚本定制工具build.py ，为每个应用定制了各自的链接脚本

    • 应用起始地址 = 基址 + 数字编号 \* 0x20000

yield系统调用

//00write_a.rs
fn main() -> i32 {
    for i in 0..HEIGHT {
        for _ in 0..WIDTH {
            print!("A");
        }
        println!(" [{}/{}]", i + 1, HEIGHT);
        yield_(); //放弃处理器 
    }
    println!("Test write_a OK!");
    0
}

  • 应用之间是相互不知道的

  • 应用需要主动让出处理器

  • 需要通过

    新的系统调用

    实现

    • const SYSCALL_YIELD: usize = 124;
const SYSCALL_YIELD: usize = 124;
pub fn sys_yield() -> isize {
    syscall(SYSCALL_YIELD, [0, 0, 0])
}
pub fn yield_() -> isize {
    sys_yield()
}

四 LibOS：支持应用程序加载

应用程序加载过程

在操作系统的工作流程中，加载应用程序是一个核心任务，特别是在系统初始启动时或当操作系统需要运行新程序时。这一过程主要由操作系统的加载器（loader）完成，其基本步骤包括：

  1. 识别镜像位置：确定操作系统镜像已经加载到模拟器或真实硬件的内存中。
  2. 从镜像中提取应用：加载器负责从内存中的镜像定位并提取各个应用程序。
  3. 计算应用大小：通过比较连续两个应用的起始地址，使用地址差计算出每个应用程序的大小。
  4. 内存拷贝：将应用程序从镜像位置拷贝到指定的物理地址。这通常涉及到基于应用程序标识符（APPID）计算出的地址，每个应用有固定大小（如2MB）的空间。

这个过程确保了每个应用都被正确地加载到其预定的内存区域，为接下来的执行做好准备。

bg right:57% 100%

应用程序的执行

一旦应用程序被加载到内存中，操作系统接下来的任务是执行这些程序。执行应用程序的关键在于确定何时以及如何启动这些程序：

  1. 初始化时执行第一个程序：操作系统在启动后首先运行第一个加载的应用程序。
  2. 运行下一个应用程序：在当前运行的应用程序执行完毕或需要进行任务切换时，操作系统会选择并运行下一个程序。
    • 调用 run_next_app 函数切换到第一个/下一个应用程序
      • 跳转到编号i的应用程序编号i的入口点 entry(i)
      • 将使用的栈切换到用户栈stack(i)
  3. 执行函数：操作系统通过专门的函数来管理应用程序的运行，这些函数负责初始化程序执行的环境，并触发程序的开始。

这个执行机制不仅涉及到程序的启动，还包括在多任务环境中管理程序间切换的逻辑，确保系统资源被高效利用，同时保持系统的响应性和稳定性。

bg right:55% 90%

上下文切换和状态恢复

操作系统的上下文切换是一个关键过程，它涉及到从内核态到用户态以及从用户态到内核态的转换。这种转换通常涉及到所谓的“陷阱上下文”（trap context），其中包括保存和恢复程序状态的重要步骤。

初始化陷阱上下文

对于系统中的第一个程序，其陷阱上下文在初始时并不存在，因此需要特别构造一个。这一步骤是确保应用程序能够从正确的位置开始执行至关重要的。

  1. 入口点确定（SEPC）：在构造陷阱上下文时，一个关键的步骤是设置程序的入口点。这通常通过设置SEPC寄存器来实现，该寄存器存储了应用程序由用户态切换到内核态时的异常地址。在操作系统重新将控制权交给应用程序时，它通过特权指令SRET读取SEPC，从而跳转到程序的正确执行点。

  2. 构造堆栈（Stack）：编译器通常不会预先设置应用程序的堆栈，因此操作系统必须在陷阱上下文的创建过程中手动构造堆栈。这包括为应用程序分配一个堆栈空间，并设置堆栈指针（SP）到一个通用寄存器。当程序控制权通过SRET跳转到入口点时，堆栈指针已经就位，确保了程序的正常运行。

应用程序的执行环境

操作系统不仅需要处理程序的代码和数据段的加载到适当的内存位置，还需要确保环境完整，以便程序可以无误执行。

  1. 代码段和数据段的加载：这些通常在应用程序加载过程中已完成。操作系统将应用程序的代码和数据从镜像复制到分配的物理地址空间。

  2. 堆栈的设置：堆栈的正确设置对于应用程序的稳定运行至关重要。操作系统需要确保每个应用程序都有足够的堆栈空间，并且堆栈指针正确指向这个空间的起始位置。

通过上述步骤，操作系统确保在执行任何应用程序之前，其执行环境是完备的。这包括程序的入口点、代码、数据、以及堆栈的准备，这些都是通过系统的陷阱上下文管理和恢复过程完成的。这样的机制使得多任务操作系统能够高效而安全地管理多个应用程序的执行。

五 BatchOS：支持多道程序协作调度

5.1 任务切换

任务管理与上下文切换

为了有效支持操作系统中的yield操作，需要进一步完善任务管理和上下文切换的机制。在简单的OS中，已经实现了应用程序的加载和执行，但缺乏对任务状态的保存和恢复，这对于支持yield操作是不够的。

任务上下文和保存

  1. 任务上下文：任务上下文是指任务在执行过程中的状态信息，包括通用寄存器等。在操作系统中，任务上下文的保存和恢复是非常重要的，特别是在任务切换时。

  2. 任务控制块（TCB）：TCB是管理任务的关键数据结构，其中包括了任务的状态信息、寄存器值、堆栈指针等。通过保存和恢复TCB，操作系统可以实现任务的切换和状态的管理。

  3. 任务切换时的保存和恢复：当一个任务被打断时，需要保存其当前的上下文信息。这包括将当前的通用寄存器值保存到该任务的TCB中，以便之后恢复。当任务重新被调度执行时，需要从其TCB中恢复先前保存的上下文信息，以确保任务能够从被打断的地方继续执行。

bg right:54% 90%

任务切换过程

  1. 任务打断：任务可能因为系统调用或时钟中断而被打断，此时需要保存当前任务的上下文并选择下一个要执行的任务。

  2. 保存当前任务的上下文：将当前任务的通用寄存器值等保存到其TCB中。

  3. 选择下一个任务：根据调度算法选择下一个要执行的任务。

  4. 恢复下一个任务的上下文：从下一个任务的TCB中恢复其上下文信息。

  5. 任务恢复执行：恢复的任务将从之前打断的地方继续执行。

通过这样的任务管理和上下文切换机制，操作系统能够实现多任务的管理和调度，支持任务的切换和yield操作，从而更有效地利用系统资源。

任务状态与调度

操作系统中任务的管理涉及到对任务运行状态的精细控制，以及在不同状态之间进行切换的能力。这对于实现有效的多任务处理至关重要。

任务状态的定义

任务在操作系统中可以处于多种状态，其中最核心的包括：

  1. Running（运行状态）：当任务正在CPU上执行时，它处于此状态。这是任务实际占用处理器资源进行操作的时段。
  2. Ready（就绪状态）：当任务准备好执行但因为CPU被其他任务占用而不能执行时，它处于此状态。就绪状态的任务在等待CPU变得可用，以便可以切换到运行状态。
  3. Blocked（阻塞状态） 或 Sleep（睡眠状态）：任务因等待某些事件（如输入/输出操作完成、接收到特定信号等）而不能执行时，会被置于阻塞状态。在事件完成后，任务可以转回就绪状态，等待重新获得CPU时间。

在一个时间片内的应用执行情况

  • running
  • ready
#![allow(unused)]
fn main() {
pub enum TaskStatus {
    UnInit,
    Ready,
    Running,
    Exited,
}
}

状态转换与任务调度

从一个应用的执行过程切换到另外一个应用的执行过程

  • 暂停一个应用的执行过程（当前任务）
  • 继续另一应用的执行过程（下一任务）

操作系统的任务调度器负责管理这些状态的转换，以及决定哪个任务应该获得CPU资源。关键的状态转换包括：

  1. 从Running到Ready：当一个正在运行的任务执行完毕其时间片或主动释放CPU（如执行yield系统调用）时，它应从运行状态转为就绪状态，等待下一次获得处理器时间。

  2. 从Running到Blocked：当任务等待外部事件（如I/O操作）时，会从运行状态转为阻塞状态。一旦外部事件处理完成，任务可以被唤醒并转移到就绪状态。

  3. 从Blocked到Ready：当阻塞的条件被满足（如读取操作完成），任务状态应从阻塞转为就绪，等待重新调度。

  4. 从Ready到Running：调度器选择一个就绪状态的任务并分配CPU资源给它，使其从就绪状态转为运行状态。

这些状态及其转换是操作系统设计的核心部分，确保了任务公平且有效地共享处理器资源，同时响应系统和用户的需求。通过管理任务的运行状态，操作系统能够提供强大的多任务处理能力，优化系统性能和响应性。

bg right:65% 100%

不同类型上下文

上下文的分类和重要性

在操作系统中，主要有两种上下文：陷阱上下文（Trap Context）和任务上下文（Task Context）。这两种上下文的管理对于任务切换至关重要。

  1. 陷阱上下文（Trap Context）：

    • 保存涉及从用户态到内核态的切换所必需的信息。
    • 包含返回地址（Return Address，即RA）、栈指针（SP），以及其他关键寄存器。
    • SP在陷阱上下文中通常指向内核栈，因为当异常发生时，处理器已经在内核模式下运行。

  2. 任务上下文（Task Context）：

    • 专门用于任务之间切换时保存任务的状态。
    • 包含一组重要的寄存器，这些寄存器在函数调用中由调用者（caller）和被调用者（callee）共同管理。例如，S0到S11寄存器在callee保存和恢复。
    • 当任务恢复执行时，操作系统从任务上下文中恢复这些寄存器的值。

  3. 任务上下文和trap上下文数据结构

#![allow(unused)]
fn main() {
// os/src/task/context.rs
pub struct TaskContext {
    ra: usize,
    sp: usize,
    s: [usize; 12],
}
}
#![allow(unused)]
fn main() {
// os/src/trap/context.rs
pub struct TrapContext {
    pub x: [usize; 32],
    pub sstatus: Sstatus,
    pub sepc: usize,
}
}

切换过程的详细说明

任务切换过程不仅涉及保存当前运行任务的状态，还包括准备下一个任务的执行环境：

  1. 保存当前任务的状态：当任务执行yield或由于时间片结束等原因需要被暂停时，当前任务的状态（如寄存器内容）被保存到其任务上下文中。

  2. 选择下一个任务：调度器根据特定的策略（如轮转、优先级调度等）选择下一个要执行的任务。

  3. 恢复下一个任务的状态：从选定任务的任务上下文中恢复寄存器等状态信息，准备该任务的执行。

  4. 切换栈指针：如果任务切换涉及从一个任务的内核栈切换到另一个任务的内核栈，操作系统需要调整栈指针（SP）指向正确的内核栈。

  5. 执行任务恢复：通过执行如SRET指令来从内核态恢复到用户态，继续执行新任务。

通过这一复杂的保存和恢复过程，操作系统确保每个任务能够在适当的时候接续其执行，而不会互相干扰，从而维护系统的稳定性和响应性。

理解不同上下文

在操作系统中，理解上下文切换是关键。我们通常会遇到三种类型的上下文：

  1. 函数上下文：函数调用的上下文涉及函数所需的状态和寄存器。
  2. Trap上下文：在操作系统内核中，当发生系统调用或中断时，执行系统级别的上下文切换。
  3. 任务上下文：任务上下文切换涉及不同的进程或线程之间的切换。

函数上下文

  • 函数上下文是控制流的最小单位。当一个函数调用另一个函数时，会产生一个新的函数上下文，保存当前函数的状态。
  • 函数A调用B时，A的上下文被保存并切换到B的上下文；当B调用C时，切换到C的上下文。这样每个函数上下文保持独立，形成嵌套。
  • 所有这些嵌套的函数调用上下文都属于同一个应用程序，是编译器生成的控制流。在这个层面上，程序执行是一个完整的控制流。

Trap上下文

  • Trap上下文在系统调用或中断时出现。
  • 当用户态的应用程序执行系统调用指令（如ecall），会发生从用户态到内核态的切换。
  • 用户应用程序和操作系统内核有各自独立的控制流，因此系统调用是一次不同控制流间的切换。
  • 用户应用程序的控制流切换到内核的控制流，内核完成相关的系统服务后，再切换回用户态。

任务上下文

  • 任务上下文涉及不同任务的切换，例如不同的进程或线程。
  • 操作系统通过调度器，利用某种方式切换两个任务，使它们能够交替占用处理器执行。
  • 调度器在任务间切换时，会保存当前任务的上下文，包括寄存器、内存映射等信息，并切换到下一个任务的上下文。
  • 这种切换允许多个应用程序各自运行在独立的任务上下文中，共享处理器资源。

bg right:60% 90%

OS 中的任务上下文和内核上下文

操作系统涉及到两种关键的上下文类型：任务上下文和内核上下文。让我们深入探讨它们的区别和运作原理。

任务上下文

  • 任务上下文与特权级切换无关。它只保存12个通用寄存器，因为编译器规定了这些寄存器需要在函数调用时被保存和恢复。
  • 当函数switch用于上下文切换时，它负责保存和恢复这12个寄存器的值，但我们希望它以一种“巧妙”的方式操作，使函数返回时切换到另一个任务的上下文。
  • 除通用寄存器外，还涉及两个特殊寄存器：
    • RA（返回地址寄存器）：指向函数的返回地址。
    • SP（栈指针寄存器）：指向栈的位置。
  • 这两个寄存器标记了两个任务的返回地址和栈空间。因为内核有其专属的栈，所以切换到另一个任务的栈空间时，需要保存并恢复更多内容。应用程序的栈通常不会与其他任务共享栈空间。

内核上下文

  • 内核上下文切换涉及到操作系统特权级别的改变，例如在执行系统调用或中断时。
  • 用户应用程序无法直接察觉到内核上下文的变化，因为它是对用户透明的，所有相关的操作都是在内核中执行的。
  • 内核上下文切换通常用于处理系统调用的服务或中断处理，以确保用户任务继续以受控且安全的方式运行。

控制流

任务切换本质上是两个不同应用程序在操作系统内核的Trap控制流之间进行的切换。为了更好地理解任务切换的概念，我们需要先了解什么是控制流。

控制流的定义

  • 编译中的控制流：

    • 编译器处理的对象是程序本身，不论是高级语言代码还是汇编语言代码，编译器都是针对程序的。
    • 程序的控制流指的是一组程序指令、语句或基本块按顺序执行，形成的执行序列即称为控制流。

  • 计算机组成中的控制流：

    • 在计算机组成原理中，关注的对象是CPU（中央处理器）。
    • 处理器的控制流是指程序计数器（PC，Program Counter）的指令转移序列，或每条机器指令的执行流。

  • 操作系统中的控制流：

    • 操作系统把应用程序和内核的控制流统筹考虑。
    • 在《计算机系统概论》（CS:APP）一书中，从程序员的角度看，应用程序员所看到的控制流只是应用程序自身的控制流，并不涉及不同应用或应用与OS之间的切换。
    • 对于操作系统而言，控制流不仅仅是单个应用的执行流，还包括多个应用的流，以及操作系统自身的控制流。操作系统还需要负责管理各个应用的控制流。

普通控制流：从应用程序员的角度来看控制流

  • 普通控制流 (CCF，Common Control Flow) 是指程序中的常规控制流程,比如顺序执行、条件判断、循环等基本结构。是程序员编写的程序的执行序列，这些序列是程序员预设好的。
    • 普通控制流是可预测的。
    • 普通控制流是程序正常运行所遵循的流。

异常控制流：从操作系统程序员的角度来看控制流

  • 在OS中，从应用程序切换到内核，通过中断或系统调用、CPU 异常等情况发生的控制流被称为异常控制流（ECF, Exception Control Flow）。
  • 从应用程序的角度来看，这种切换是异常的，因为它脱离了应用程序本身的执行控制。
  • 这种异常控制流的机制允许操作系统管理和控制应用程序，实现任务间的切换与资源管理。
  • 这种“突变”的控制流称为异常控制流。
    • 在RISC-V场景中，异常控制流 == Trap控制流

不同类型的控制流与上下文

普通控制流的上下文

  • 普通控制流上下文就是函数上下文。
  • 在函数调用过程中，程序控制流在不同函数之间切换，保存和恢复相应的函数上下文。

Trap和任务控制流的上下文

  • Trap控制流上下文：

    • Trap控制流上下文属于异常控制流上下文，保存了被打断的应用程序的状态。
    • 当系统调用或中断发生时，应用程序的普通控制流被打断，系统进入异常控制流，并且上下文由内核的Trap机制管理。

  • 任务控制流上下文：

    • 任务上下文的控制流在内核中运行，是内核的普通控制流上下文，而不是异常控制流。
    • 任务上下文属于内核中的函数上下文，通常是某个特殊函数（如switch）用于在不同任务之间进行切换。
    • switch是一个用汇编语言实现的特殊函数，在执行时会切换两个不同任务的上下文，因此它是一个特殊的内核函数上下文。

区别与总结

  • 普通函数上下文：

    • 包含应用程序的普通函数调用和返回。
    • 应用程序通过高级语言进行开发并生成相应的函数。

  • 内核函数上下文：

    • 包含内核中的函数，上下文之间可能涉及不同任务的切换。
    • 内核函数通常是高级语言或汇编语言编写的。

  • Trap上下文：

    • 属于异常控制流，保存被打断应用的状态。
    • 系统调用和中断是异常控制流的主要来源。

理解这些不同的上下文类型，有助于深入掌握操作系统的任务切换和控制流管理。

5.2 Trap控制流切换

任务切换的设计与实现

任务切换涉及多个数据结构和关键点，理解它们的工作原理对于设计操作系统至关重要。

关键点

  1. 数据结构的位置：

    • Trap上下文：保存被打断应用的状态。通常，Trap上下文会被放置在每个应用的内核栈（kernel stack）顶部。
    • 任务上下文：不同于Trap上下文，它可以放置在栈中或全局数据结构中。具体位置取决于实现方式。

  2. 切换的方式：

    • 任务切换通过__switch() 函数完成，用于在任务间保存和恢复状态。
    • 任务切换的逻辑可能发生在不同情况下，包括中断、系统调用或内核调度。

  3. 何时切换：

    • 调度器决定何时发生任务切换，例如时间片耗尽、I/O完成或外部事件发生等。
    • 切换的触发条件决定了调度器的调度策略。

  4. 切换的可逆性：

    • 任务切换需要支持切换回原任务，以保证应用程序的状态可以恢复。

内核栈和数据结构

  • 每个应用程序都有其专属的内核栈。例如，应用1的内核栈存放应用1的Trap上下文和函数调用信息。
  • __switch() 函数执行任务切换，确保在函数返回时切换到另一个任务。
  • Trap上下文通常保存在内核栈顶部，但任务上下文可能保存在全局数据结构中，以确保独立管理。

多种实现方式

  • 操作系统的设计并非只有一种实现方式，有许多实现方法可以选择。
  • 概念和实现之间存在联系，但操作系统中的概念不像数学那么精确，通常可以通过多种途径实现。
  • 理解概念与实现的关系是关键，设计能够自圆其说的实现方案才是最重要的。

学习建议

  • 理解操作系统的设计需要找到概念和实现之间的联系，确保它们相互对应。
  • 学习过程中，保持开放的心态接受多样化的实现方式，理解操作系统的灵活性。
bg right 95%

Trap 和 Task 上下文的切换

为了实现多任务操作系统的切换，需要掌握 trap 和 task 上下文的结构和切换方法。

数据结构位置

  • Trap 上下文：保存在每个应用的内核栈底部，包含系统调用或中断的上下文。
  • Task 上下文：保存于全局变量中，用于在不同任务之间切换时恢复任务状态。

系统调用 yield 和上下文切换

  • yield 系统调用是多道程序 OS 切换任务的入口，触发调度器切换到另一个任务。
  • 内核检测到 yield 请求后，会调用特殊的 __switch() 函数，完成任务切换。

__switch() 函数的作用

  • switch 是用汇编语言编写的特殊函数，执行任务切换的核心逻辑。
  • 它将当前任务的上下文状态保存到 Task 上下文结构中，并从下一个任务的 Task 上下文结构中恢复新的状态。
  • 关键是改变内核栈，使得控制流返回到下一个任务。

__switch() 函数的参数

  • __switch() 函数通常接收两个参数：
    • Current：当前正在执行的任务的 Task 上下文指针，表示当前状态。
    • Next：下一个任务的 Task 上下文指针，表示需要切换到的任务。

切换过程

  1. Current 指针指向当前任务的 Task 上下文，Next 指针指向下一个任务的 Task 上下文。
  2. __switch() 函数保存当前任务的上下文，包括返回地址（RA）、栈指针（SP）和通用寄存器到当前 Task 上下文结构中。
  3. __switch() 函数加载 Next 中的上下文，将新的返回地址、栈指针和寄存器加载到 CPU 中。
  4. 改变内核栈，使得控制流返回到 Next 任务的内核栈，并继续执行下一个任务的代码。

结论

  • __switch() 函数的关键工作是更改内核栈，并确保当前 CPU 状态与要切换的任务保持一致。
  • 切换的过程需要确保当前任务的上下文被妥善保存，以便在将来可以无缝恢复。

w:800

__switch() 函数的四个步骤

__switch() 函数用于在任务之间切换，操作复杂且涉及多个关键步骤。以下是任务切换的四个主要步骤：

第一步：初始状态

  • 在进入内核并执行内核代码之前，当前任务 A 的内核栈上只包含其 Trap 上下文和相关的 Trap 处理器函数信息。
  • 被切换出的任务 B 的上下文在全局变量中独立存储，暂未使用。

第二步：保存当前任务 A 的上下文

  • __switch() 函数在任务 A 的上下文结构中保存当前 CPU 的寄存器状态，包括返回地址（RA）、栈指针（SP）和其他通用寄存器。
  • 当前任务 A 的内核栈仍在使用，而任务 B 的内核栈暂时没有用到。

第三步：恢复任务 B 的上下文

  • __switch() 函数读取 next_task_cx_ptr 指向的 B 任务上下文，将下一个任务 B 的上下文指针作为参数传递，以便找到任务 B 的寄存器快照，恢复 ra 寄存器、s0~s11 寄存器以及 sp 寄存器。
  • 函数将任务 B 上下文中的寄存器值（包括 RA 和 SP）复制到 CPU 中，准备恢复任务 B 的执行状态。
  • 此时，CPU 寄存器已经更换为任务 B 的上下文内容，但尚未执行 return。
  • 这一步做完后， __switch() 才能做到一个函数跨两条控制流执行，即 通过换栈也就实现了控制流的切换 。

第四步：执行 return 并切换到任务 B

  • __switch() 函数执行 return 指令，使得 CPU 根据新的返回地址（RA）跳转到任务 B 的代码位置。
  • 同时，栈指针（SP）已经更改为任务 B 的栈指针。
  • 一旦 ret 执行，CPU 将完全切换到任务 B，并开始在任务 B 的内核栈上执行代码，任务 B 可以从调用 __switch() 的位置继续向下执行。
  • 原任务 A 的上下文已被保存并将暂停执行，直到被再次调度。
  • __switch()通过恢复 sp 寄存器换到了任务 B 的内核栈上，实现了控制流的切换，从而做到一个函数跨两条控制流执行。

结论

  • __switch() 函数是任务切换的核心，它通过保存和恢复上下文确保任务之间的无缝切换。
  • 任务 A 的上下文被妥善保存，以备后续恢复，而任务 B 的上下文被正确恢复，以开始其执行流程。

任务切换与用户态的可行性

  • 任务切换通常在内核完成，因为它涉及到特权操作和对系统资源的管理。
  • 理论上，用户程序可以使用特定的编译器和汇编技巧模拟任务切换，但这通常是有限制的，因为用户态缺乏直接操作系统资源的权限。
  • 多数情况下，用户态的任务切换不如内核态切换有效，因为内核拥有对资源的完全控制权。

__switch() 函数的实现难点

  • __switch() 函数有两个参数：当前任务和下一个任务的 Task 上下文。
  • 汇编代码中划分为四个阶段，依次保存和恢复相关寄存器状态，并通过 return 指令切换任务。
  • 学生在课后应仔细查看代码，理解每个阶段的功能。实现这种代码可能需要指导，因为它对寄存器和内核栈的操作较复杂。

__switch()的接口

#![allow(unused)]
fn main() {
// os/src/task/switch.rs

global_asm!(include_str!("switch.S"));

use super::TaskContext;

extern "C" {
    pub fn __switch(
        current_task_cx_ptr: *mut TaskContext,
        next_task_cx_ptr: *const TaskContext
    );
}
}

__switch()的实现

__switch:
   # 阶段 [1]
   # __switch(
   #     current_task_cx_ptr: *mut TaskContext,
   #     next_task_cx_ptr: *const TaskContext
   # )
   # 阶段 [2]
   # save kernel stack of current task
   sd sp, 8(a0)
   # save ra & s0~s11 of current execution
   sd ra, 0(a0)
   .set n, 0
   .rept 12
       SAVE_SN %n
       .set n, n + 1
   .endr

   # 阶段 [3]
   # restore ra & s0~s11 of next execution
   ld ra, 0(a1)
   .set n, 0
   .rept 12
       LOAD_SN %n
       .set n, n + 1
   .endr
   # restore kernel stack of next task
   ld sp, 8(a1)
   # 阶段 [4]
   ret

5.3 协作式调度

任务控制块

操作系统管理控制进程运行所用的信息集合

pub struct TaskControlBlock {
    pub task_status: TaskStatus,
    pub task_cx: TaskContext,
}
  • 任务管理模块
struct TaskManagerInner {
    tasks: [TaskControlBlock; MAX_APP_NUM],
    current_task: usize,
}

任务调度

  • 任务调度 是一种策略，决定何时切换任务，以充分利用 CPU 资源。
  • 任务切换 则是具体的实现方法，用于在不同任务之间切换状态。

协作式调度

  • 协作式调度依赖应用程序主动触发，例如通过 yield 或 exit 系统调用。
  • 这种调度方式较为简单，被动等待应用程序请求，不主动进行调度策略的选择。
  • 在这种模式下，操作系统只是根据用户请求执行相应操作。

任务切换步骤

  • Suspend 当前任务：调用 __switch() 函数，将当前任务的上下文保存，标记其为暂停。
  • Run Next：通过 context switch 切换到下一个任务的上下文，恢复其 Trap 上下文和 Task 上下文。

任务的上下文

  • 每个任务在内核中拥有独立的上下文，包括：
    • Trap 上下文：保存被打断的用户态程序状态。
    • Task 上下文：保存任务本身的状态，用于在任务间切换。

协作式调度实现

sys_yield和sys_exit系统调用

#![allow(unused)]
fn main() {
pub fn sys_yield() -> isize {
    suspend_current_and_run_next();
    0
}
pub fn sys_exit(exit_code: i32) -> ! {
    println!("[kernel] Application exited with code {}", exit_code);
    exit_current_and_run_next();
    panic!("Unreachable in sys_exit!");
}
}
#![allow(unused)]
fn main() {
// os/src/task/mod.rs

pub fn suspend_current_and_run_next() {
    mark_current_suspended();
    run_next_task();
}

pub fn exit_current_and_run_next() {
    mark_current_exited();
    run_next_task();
}
}
fn run_next_task(&self) {
   ......
   unsafe {
       __switch(
           current_task_cx_ptr, //当前任务上下文
           next_task_cx_ptr,    //下个任务上下文
       );
   }

内核程序设计与进入用户态

内核态到用户态的第一次切换

  • 初始状态：操作系统在启动时一直在内核态运行，需要进行初始化工作。
  • 用户任务的准备：
    • Task 上下文：准备任务的 Task 上下文，以便在任务切换时恢复。
    • 内核栈：为任务分配独立的内核栈，用于处理 Trap 和系统调用。
    • 用户栈：为任务分配用户栈，用于应用程序的普通执行。
    • Trap 上下文：保存系统调用或中断发生时的应用程序状态。
  • 程序加载：
    • 使用 loader 将应用程序代码和数据加载到合适的内存区域。
    • 完成内存、栈和上下文的初始化，为任务配置正确的入口地址。
  • 进入用户态：
    • 在上述准备完成后，通过特定的汇编指令（如 SRET）切换到用户态并执行用户任务。

六 MultiprogOS：分时多任务OS

MultiprogOS的基本思路

  • 设置时钟中断
  • 在收到时钟中断后统计任务的使用时间片
  • 在时间片用完后，切换任务

时钟中断与任务切换

  • 时钟中断：是一种硬件中断，用于周期性打断当前执行的任务。
  • 中断处理：
    • 时钟中断产生时，系统会从用户态或内核态切换到内核态的中断处理程序。
    • 中断处理程序会统计当前任务的执行时间，判断时间片是否已耗尽。
  • 任务切换：
    • 如果时间片耗尽，则需要切换任务，暂停当前任务并调度下一个任务。
    • 调用任务切换函数 switch 或调度器函数进行任务切换。
  • 简单策略：这种切换策略是固定的，只要时钟中断触发，便立即进行任务切换。这种策略简单明了，方便理解和实现。

bg right:58% 100%

多任务操作系统的定时器和中断

设置定时器

  • 定时器设置：

    • 为了实现任务的时间片调度，必须设置定时器。
    • 使用 SBI（Supervisor Binary Interface）接口中的 set_timer 函数，设置下一个中断触发的时间点。
    • 设置完成后，还需要启用时钟中断。

  • 启用时钟中断：

    • 在系统初始化时，时钟中断通常是被禁用的。
    • 启用时钟中断后，可以确保系统定期收到中断信号并触发调度。

时钟中断的处理

  • 中断处理：
    • 当时钟中断触发时，系统会立即进入内核的中断处理程序。
    • 在中断处理程序中，重新设置下一个中断触发时间，确保定时器定期触发。
    • 处理任务切换逻辑，根据调度策略选择下一个任务执行。

时钟中断与计时器实现

  • 设置时钟中断
#![allow(unused)]
fn main() {
// os/src/sbi.rs
pub fn set_timer(timer: usize) {
     sbi_call(SBI_SET_TIMER, timer, 0, 0);
 }
// os/src/timer.rs
pub fn set_next_trigger() {
    set_timer(get_time() + CLOCK_FREQ / TICKS_PER_SEC);
}
pub fn rust_main() -> ! {
    trap::enable_timer_interrupt();
    timer::set_next_trigger();
}    
}

抢占式调度

#![allow(unused)]
fn main() {
// os/src/trap/mod.rs trap_handler函数
......
match scause.cause() {
    Trap::Interrupt(Interrupt::SupervisorTimer) => {
        set_next_trigger();
        suspend_current_and_run_next();
    }
}
}

多任务 OS 的要点

  • 多道程序设计：

    • 多个程序同时驻留在内存中，通过主动或被动方式共享处理器资源。
    • 这种多任务设计使得系统能够分时共享 CPU，有效提高资源利用率。

  • 协作式与抢占式调度：

    • 协作式调度需要应用程序主动放弃 CPU，而抢占式调度通过时钟中断进行任务切换。

  • 任务切换的概念与实现：

    • 任务切换涉及任务的上下文、内核栈、Trap 上下文等多个部分。
    • 实验中，任务切换需要综合考虑内核和用户态的设计。

  • 中断机制：

    • 中断机制在调度中扮演重要角色，通过设置定时器和启用中断实现定期的任务切换。
    • 中断使得系统能够主动调度任务，实现抢占式的多任务操作。

课程实验一

  • 实验任务：增加一个系统调用

    sys_task_info()

  • 实验提交要求

    • 在自己的已创建实验仓库中提交完整的代码和文档；
    • 提交实验一报告链接和commit ID；
    • 实验截止时间：布置实验任务后的第13天；