操作系统构建Part8：调度机制

 Posted on April 24, 2025

8.1 前言

        本章的内容，是介绍dummyxv6系统的调度机制。本章先会略过许多代码细节，从高层次阐述调度机制的流程，再展示dummyxv6支撑调度机制的其他细节。在本章配套的代码中，内核运行在只有一个CPU核心的虚拟设备上，内核初始化阶段会创建两个用户进程，这个用户进程将会运行一段无限循环指令，然后通过定时器中断来触发进程切换，最后实现任务调度机制。

8.2 调度机制运作流程

        本节将开始阐述调度机制的运作流程，调度机制调度的目标就是任务，在dummyxv6中，任务调度本质就是用户进程的调度。在完成kernel/start.c里，start函数的逻辑之后，每个RISC-V CPU的核心就会跳转到kernel/main.c里的main函数里执行初始化逻辑和进程调度指令，其代码如下所示：

// kernel/main.c
1  static volatile int is_initialized = 0;
2 
3  void main() {
4      if (cpuid() == 0) {
5          uartinit();
6          printfinit();
7 
8          printf("dummyxv6 booting!\n");
9          printf("start to initialize the kernel.\n");
10         kinit();
11 
12         kvminit();
13         kvmhartinit();
14 
15         procinit();          // struct proc数组初始化
16         prochartinit();      // 设置内核中断处理事件
17 
18         test_userinit();     // 分配用户进程，并加载用户进程指令和分配用户栈空间等
19         
20         // printf("CPU%d initialize success.\n", cpuid());
21 
22         __sync_synchronize();
23 
24         is_initialized = 1;
25     } 
26     else {
27         while (is_initialized == 0);
28 
29         printf("CPU%d starts initializing.\n", cpuid());
30 
31         // test kalloc
32         void *p = kalloc();
33         strcpy(p, "hello, world!\n");
34         printf("CPU%d: %s", cpuid(), p);
35         kfree(p); 
36 
37         printf("Initialization of CPU%d complete.\n", cpuid());
38     }
39 
40     scheduler(); // 执行调度逻辑
41 }

代码片段1
        main函数里，第4行到第25行代码，只会在core 0执行。这段代码执行的是各种初始化逻辑。第27行到第38行代码，则在其他核心内执行。所有的核心最终都会执行scheduler函数，这个函数负责调度机制的运行。
        函数中，有几个地方是本章需要重点讨论的，它们分别是第15行procinit函数，第16行prochartinit函数，第18行test_userinit函数和第40行scheduler函数。它们具体的逻辑注释已经标明，后续将对它们逐一进行详细解释。

8.2.1 用户进程的概念

        为了能够充分理解任务调度机制，首先要了解的是用户进程的概念。本节开始介绍用户进程的概念，在dummyxv6操作系统中，用户进程是一个资源单位，它有自己的内存模型，同时它也是一个执行单位，因为dummyxv6的用户进程不支持多线程，一个用户进程内的代码，同时只能在一个CPU核心里执行。

8.2.1.1 用户进程的内存布局

        dummyxv6的用户进程内存布局，在第7章中有详细介绍，这里不作过多的赘述，读者可以回到《7.4 dummyxv6的用户进程内存布局》进行回顾。

8.2.1.2 用户空间代码运行流程

        dummyxv6用户进程的虚拟内存地址是从0x0开始的，在创建用户进程阶段，进入用户态，除了页表会切换到用户进程的页表以外，pc寄存器会赋值为0x0，这样CPU核心就是从用户进程的第一个指令开始执行。在用户态执行用户进程的指令时，使用的是用户进程的用户栈空间（user stack）。如果在用户空间运行过程中，有动态开辟内存的需求，则从堆空间（heap）中开辟内存。

8.2.1.3 内核空间代码运行流程

        当有中断或异常事件发生时，处在用户态运行的用户进程，会从用户态切换到内核态，此时需要保存用户态的各种寄存器的值，这些寄存器的值会保存到trapframe空间中，然后执行中断异常处理事件。这些保存寄存器的操作指令，位于内核的trampoline空间中。前面章节也提到过，用户进程的trampoline和内核空间的trampoline是共享的。在内核态运行内核代码期间，使用的栈空间是内核栈空间（kstack）。

8.2.1.4 用户进程与内核内存空间之间的关系

        如图1所示，右边是用户进程的虚拟内存空间展示，使用的是虚拟内存空间。中间的是内核内存空间展示，显示的是物理内存。左边展示的是用户进程的数据结构展示。关于内核的物理地址为何是从0x80000000开始的，这个在之前的章节有提到过，这里再提一次，由于dummyxv6是一个运行在qemu模拟的虚拟设备之上，其内核的物理地址是从0x80000000开始的，并非真实设备的物理内存。 image图1
        在dummyxv6中，表示用户进程的结构体是struct proc，内核中的.data段包含了一个struct proc结构的数组，数组的尺寸是64。struct proc结构的定义如下所示：

// kernel/proc.h
struct proc {
    uint64_t pid;                // Process ID
    struct cpu* cpu;
    uint64_t sz;                 // Size of process memory (bytes)
    pagetable_t pagetable;       // Page table

    uint64_t kstack;
    int state;                   // process state

    struct context context;
    struct trapframe* trapframe; // Trap frame for current interrupt

    struct spinlock lock;
};

代码片段2
        pid是内核每次创建用户进程时生成的唯一id。每次回收后，再次分配，会获得新的pid，而不会重复。
        cpu指针指向CPU核心对应的struct cpu实例，这个结构在第5章有介绍过，用来记录为了禁止中断事件而调用push_off函数的次数（noff变量），以及调用push_off函数之前，是否允许中断（intena变量）。它在本章中新增了两个结构体变量（context和proc）：

// kernel/proc.h
// context switch 
struct context {
    uint64_t ra; // Return address
    uint64_t sp; // Stack pointer

    // Callee-saved registers
    uint64_t s0; // frame pointer
    uint64_t s1;
    uint64_t s2;
    uint64_t s3;
    uint64_t s4;
    uint64_t s5;
    uint64_t s6;
    uint64_t s7;
    uint64_t s8;
    uint64_t s9;
    uint64_t s10;
    uint64_t s11;
};
    
struct cpu {
    int intena; // Saved interrupt enable bit
    int noff;   // Depth of push_off() nesting
    struct context context;
    struct proc* proc; // The process running on this cpu
};

代码片段3
上述代码的struct context是用来记录寄存器值的，而且只是记录ra、sp和callee-saved类型的寄存器的值，至于为什么是记录这些值，文后会详细解释。context主要是在发生任务调度时，用来存内核和用户进程当前上下文信息的结构体。这里的上下文信息，实质上就是上述寄存器的值。
        sz字段用来保存内核一共给用户进程分配了多少物理内存，单位是字节，一般是4K的倍数。
        pagetable字段存的是用户进程的页表根节点地址，每个用户进程都有独立的页表。
        kstack字段保存了用户进程关联的内核栈地址。当正在运行的用户进程发生中断或者异常事件时，会从用户态切到内核态，用户进程下一个要执行的指令地址（pc寄存器的值）、用户栈栈顶的地址（sp寄存器）、返回地址（ra寄存器）、caller-saved寄存器的值、callee-saved寄存器的值和页表地址等，也会在切换时存入trapframe内存块中，这个保存到trapframe内存块的逻辑指令，是保存在trampoline内存段中，完成上下文保存之后，trampoline中的逻辑会调用usertrap函数处理具体的中断或者异常事件。在运行这些指令时，使用的是内核栈，这个内核栈的栈底地址就是kstack变量指向的地址，kstack是struct proc结构体实例在初始化时，从物理内存中分配。
        state字段保存的是当前用户进程所处的状态，目前实现的状态主要有以下几种：

  • UNUSED：不可用状态，它表示struct proc结构体实例未初始化，处在这个状态的struct proc结构体实例，不可被分配。
  • USED：可用状态，它表示struct proc结构体实例已经完成初始化，处在这个状态的struct proc结构体实例，可以作为用户进程分配。
  • RUNNABLE：可运行状态，处在可运行状态的用户进程，一般是完成分配准备被运行，或定时器中断事件触发时，被暂停执行的用户进程所处的状态。
  • RUNNING：运行状态，用户进程处在用户态时的状态。

目前暂时没有实现其他状态，本章只聚焦在最基础的调度机制这块。
        context字段，任务调度时，用来保存和读取上下文信息的地方。
        trapframe字段，用户进程被分配时，从物理内存中申请的一页内存数据。每个用户进程都有独立的trapframe内存空间，并且访问它的虚拟地址都一样。当从用户态切入内核态时，用户态上下文信息（主要是寄存器的值）会存入这个内存页中，然后再切换为内核空间的页表，并执行trap事件（异常或者中断事件），完成之后，从内核态返回用户态时，将trapframe内的值恢复到寄存器中。trapframe结构的定义如下所示：

// kernel/trap.h

struct trapframe {
    uint64_t kernel_satp; // kernel page table
    uint64_t kernel_sp;   // top of process's kernel stack
    uint64_t kernel_trap; // user trap number
    uint64_t kernel_hartid; // core number

    uint64_t epc;         // exception program counter

    uint64_t ra; // Return address
    uint64_t sp; // Stack pointer

    uint64_t gp; // Global pointer
    uint64_t tp; // Thread pointer

    uint64_t t0; // Temporaries
    uint64_t t1;
    uint64_t t2;

    uint64_t s0; // frame pointer
    uint64_t s1;
    
    uint64_t a0; // Arguments
    uint64_t a1;
    uint64_t a2;
    uint64_t a3;
    uint64_t a4;
    uint64_t a5;
    uint64_t a6;
    uint64_t a7;

    uint64_t s2; // Saved registers
    uint64_t s3;
    uint64_t s4;
    uint64_t s5;
    uint64_t s6;
    uint64_t s7;
    uint64_t s8;
    uint64_t s9;
    uint64_t s10;
    uint64_t s11;

    uint64_t t3; // Temporaries
    uint64_t t4;
    uint64_t t5;
    uint64_t t6;
};

代码片段4
trapframe结构包含了riscv cpu所有的通用寄存器，相当于保存了用户态运行时的方方面面的数据。当从内核态返回用户态时，要将trapframe里保存的值还原到cpu的寄存器中。
        lock字段，这个是自旋锁变量，调度器会在多个核心同时运行，可能会同时访问到同一个struct proc结构体实例，因此需要加自旋锁来保证对proc实例的原子操作，所以需要一个自旋锁。
        在完成用户进程结构体–struct proc的介绍之后，回顾一下图1，它展示了用户进程概念内存模型、struct proc结构体和内核内存模型的关系。首先是用户进程的各种内存段，均是分布在内核空间之中。内核的.data段包含一个尺寸为64的struct proc结构体数组，每一个槽位代表一个用户进程，用户进程被分配之后，用户进程内存空间就和内核内存空间实现关联了。

8.2.2 调度机制运行流程

        本节将结合源码对调度机制进行论述。

8.2.2.1 用户进程的初始化

        内核初始化阶段，会在第0个CPU核心执行所有的初始化流程，也就是代码片段1（上述main函数）的第4行到第25行代码。完成之后其他核心才能开始自己的初始化操作，kernel/main.c中的main函数会在每一个CPU的核心独立执行，不过全局的初始化操作只在第0个核心执行。
        用户进程的初始化，就是在第0个核心进行的，它执行的逻辑很简单，就是将前面提到的struct proc数组中的结构体实例的状态state设置成UNUSED状态，然后为每一个struct proc实例分配kstack内存块。如图2所示，用户进程的kstack实际是一个物理内存页，是内核通过kalloc函数分配出来的内存页。dummyxv6最多可以同时运行64个用户进程，每个用户进程都会被分配一个唯一的内核栈虚拟地址，这个虚拟地址会通过页表映射到实际的物理内存地址之上。与此同时，每个用户进程的自旋锁变量也会在这个阶段完成初始化。这些操作会在上述main函数的第15行–procinit函数里执行。

// kernel/proc.c
1  static void initcpus() {
2      for (int i = 0; i < NCPU; i++) {
3          cpus[i].noff = 0;
4          cpus[i].intena = 0;
5          memset(&cpus[i].context, 0, sizeof(cpus[i].context));
6      }
7  }
8  
9  void procinit() {
10     initlock(&alloclock, "proc_alloc");
11 
12     initcpus();
13 
14     for (int i = 0; i < NPROC; i ++) {
15         struct proc* p = &procs[i];
16         p->state = UNUSED;
17         p->kstack = (uint64_t)KSTACK((uint64_t)(p - procs));
18         initlock(&p->lock, "proc");
19         memset(&p->context, 0, sizeof(p->context));
20     }
21 }

代码片段5
        最终，procinit函数执行的结果，如图2所示。 image图2
        这个阶段的用户进程实例，只是状态和内核栈完成初始化。它现在既没有申请到物理内存用于存放用户进程的执行指令和数据，也没有为trapframe申请内存，用于用户态切换到内核态，或从内核态返回用户态的上下文存取。
        接下来，就是允许内核响应异常和中断，并为其设置处理响应事件。这个逻辑在代码片段1的第16行代码执行–prochartinit函数里执行。实际上就是向stvec寄存器写入响应函数的地址。

// kernel/proc.c
1 void prochartinit() {
2     w_stvec((uint64_t)kernelvec); 
3 }

代码片段6
kernelvec的地址位于kernel/kernelvec.S，当CPU处于内核态的时候，响应中断和异常的函数地址，就是这个kernelvec指定，文后笔者会介绍这个流程，现在暂时略过。
        接下来要执行的函数是代码片段1里的第18行代码：调用test_userinit函数。这个函数会创建两个执行相同逻辑的用户进程，除了执行一个死循环以外，不会执行其他代码，这样可以最大限度简化用例。test_userinit函数调用两次useinit函数来创建用户进程，其逻辑如下所示：

// kernel/proc.c
1 void test_userinit() {
2     printf("test_userinit\n");
3 
4     initproc = userinit();
5     initproc2 = userinit();
6 }

代码片段7
        userinit函数执行的内容是，分配一个用户进程，并往这个用户进程填入执行指令，然后设置该用户进程中，设置从内核态返回用户态的函数地址。在开始更多的userinit函数论述前，先要看看用户进程分配函数的逻辑。
        一般而言，操作系统会在内核初始化阶段，创建和分配第一个用户进程，然后通过这个用户进程fork出其他进程。本章的目标是实现定时器中断驱动的用户进程调度机制，因此，在本章对应的代码中，内核初始化阶段会先创建两个用户进程，这里就需要从已经初始化好的struct proc数组中，分配两个用户进程出来。单个用户进程的分配的逻辑如下所示：

  • 第1步：按顺序遍历struct proc数组，查找一个状态为UNUSED的用户进程实例p，如果找到进入下一步，找不到，则流程终止。
  • 第2步：将p的状态设置为USED，并为其分配一个唯一的进程id。
  • 第3步：为p创建页表。
  • 第4步：为p的trapframe分配物理页，并将trapframe物理地址，映射到TRAPFRAME的虚拟地址上。
  • 第5步：将内核的trampoline段的起始地址，映射到p的虚拟地址空间的TRAMPOLINE地址值上。

第2步到第5步为原子操作，最后得到图3的结果。通过图3可以直观地看到，分配后的用户进程，只是对trampoline和trapframe内存段进行虚拟地址空间到物理地址空间的映射，此时用户栈和用户进程要运行的指令和数据也是未分配的。struct proc结构体内的很多字段，比如state、kstack、context、pagetable等，对用户进程是完全透明的。
image图3
        上述流程，实际上是在kernel/proc.c文件中的allocproc函数里执行，其逻辑实现如下所示：

// kernel/proc.c
1  struct proc *allocproc()
2  {
3   // 按顺序遍历struct proc数组，查找一个状态为UNUSED的用户进程实例p
4      struct proc *p = NULL;
5      for (int i = 0; i < NPROC; i++)
6      {
7          p = &procs[i];
8          acquire(&p->lock);
9          if (p->state == UNUSED) {
10          // 将p的状态设置为USED
11             p->state = USED;
12             goto found;
13         }
14         else {
15             release(&p->lock);
16         }
17     }
18 
19     return NULL;
20 found:
21  // 为其分配一个唯一的进程id
22     p->pid = allocpid();
23 
24     // 为p创建页表
25     p->pagetable = uvmcreate();
26     if (p->pagetable == 0) {
27         panic("fail to uvmcreate");
28     }
29 
30     // 为p的trapframe分配物理页，并将trapframe物理地址，映射到TRAPFRAME的虚拟地址上
31     p->trapframe = (struct trapframe*)kalloc();
32     if (p->trapframe == 0) {
33         panic("fail to kalloc trapframe");
34     }
35 
36     memset(p->trapframe, 0, sizeof(struct trapframe));
37     if (!mappages(p->pagetable, TRAPFRAME, PGSIZE, (uint64_t)p->trapframe, PTE_R | PTE_W)) {
38         panic("fail to mappages trapframe");
39     }
40 
41     // 将内核的trampoline段的起始地址，映射到p的虚拟地址空间的TRAMPOLINE地址值上
42     if (!mappages(p->pagetable, TRAMPOLINE, PGSIZE, (uint64_t)trampoline, PTE_R | PTE_X)) {
43         panic("fail to mappages trampoline");
44     }
45     
46     return p;
47 }

代码片段8
        在完成用户进程的分配之后，就要将用户进程要执行的逻辑和数据，加载到用户进程空间上。尔后还要为其分配用户栈空间，在dummyxv6中，所有的用户进程栈的大小一律是4KB，栈底位于高地址，栈顶位于低地址。在本章的例子中，内核初始化阶段，会分配两个用户空间，两个用户空间的执行的指令是一样的，就是执行一段死循环代码：

spin:
    j spin;

这段代码编译成RISC-V的机器指令后，如下所示：

0x6f, 0x00, 0x00, 0x00  // j 0x0

现在为刚刚分配的用户进程，再从内核中申请一页物理内存，并将上述机器码填入，得到图4的结果。图4的用户进程虚拟空间，虚拟地址从0x0开始，并且指令、数据和用户栈同属一页内存，为什么会这样呢？因为物理内存是按页分配的，本例中的指令和数据很少，根本占不到一页内存，为了避免内存浪费，所以将栈顶设置到该页的结束地址处。这页内存被设置为可读、可写和可执行。
image图4
        上述逻辑均是在userinit函数里执行，但是userinit函数做的事情还不止这些，它还对已经完成分配的用户进程结构体中的context字段进行了一些赋值操作，其实就是将context->ra赋值为forkret函数地址，将context->sp赋值为用户进程对应的kstack地址。这个forkret函数，就是负责将用户进程从内核态返回到用户态。现在来看一下userinit函数的实现。

// kernel/proc.c
1   static char initcode[] = {
2       0x6f, 0x00, 0x00, 0x00  // j 0x0
3   };
4   
5   struct proc* userinit() {
6       struct proc* p = allocproc();
7       if (p == NULL) {
8           panic("fail to allocproc");
9       }
10  
11      void* mem = kalloc();
12      if (mem == 0) {
13          panic("fail to kalloc");
14      }
15  
16      memset(mem, 0, PGSIZE);
17      memcpy(mem, initcode, sizeof(initcode));
18  
19      if (!mappages(p->pagetable, 0, PGSIZE, (uint64_t)mem, PTE_W | PTE_R | PTE_X | PTE_U)) {
20          panic("fail to mappages initcode");
21      }
22  
23      p->trapframe->epc = 0;
24      p->trapframe->sp = PGSIZE;
25  
26      p->sz = PGSIZE;
27      p->context.ra = (uint64_t)forkret;
28      p->context.sp = p->kstack + PGSIZE;
29      p->state = RUNNABLE;
30  
31      release(&p->lock);
32  
33      return p;
34  }

代码片段9
代码实现很清晰：

  • 第6行到第9行，对应前面的用户内存分配逻辑。
  • 第11行到第21行，对应图4中，将用户进程指令填充到用户空间的逻辑。
  • 第23行指明，返回用户态后执行的指令地址（用户空间的虚拟地址），第24行代码则指明返回用户态之后的栈顶地址。
  • 第26行代码，指明实际分配给用户进程的内存页只有一页。
  • 第27行代码，在context.ra中存了forkret函数的地址。调度器选中一个用户进程后，为了执行用户空间内的指令，首先要执行从内核态返回用户态的逻辑（在usertrapret函数内），forkret函数通过调用usertrapret函数实现这一点。
  • 第29行代码，设置用户进程的状态为RUNNABLE。
  • 第31行代码，释放用户进程锁，因为p->lock在allocproc函数中加锁了，所以返回前要解锁。

        截止到现在，关于用户进程的初始化流程，就完成论述了。

8.2.2.2 用户进程的状态与切换

        截止到目前为止，用户进程一共有4种状态，分别是UNUSED、USED、RUNNABLE和RUNNING。每一个用户进程实例，初始状态就是UNUSED状态。完成初始化（kstack的分配）之后，切换到USED状态。当被分配成为运行时的用户进程时，会切换到RUNNABLE状态，此时等待调度器调度。最后调度器会遍历struct proc数组，并切换到第一个遍历到的，处于RUNNABLE状态的用户进程。只有当中断事件发生时，才会打断当前运行的用户进程。其切换流程如图5所示。
image图5
        

        目前dummyxv6实现的状态就只有这4中，后续章节会持续增加新的状态。

8.2.2.3 调度流程

        本节要讨论的是代码片段1中的地40行，运行scheduler函数，这个函数就是前面提到的调度器，实际上就是一个用于执行调度逻辑的函数。
        在完成了用户进程的初始化，以及分配了用户进程之后，调度器就开始运作了。调度器本质是在一个无限for循环里执行的逻辑，它的源代码如下所示：

// kernel/proc.c
/*
 * The scheduler function implements a simple round-robin scheduler for xv6.
 * It runs continuously, searching for RUNNABLE processes in the process table.
 * When a runnable process is found, it switches to that process's context and
 * lets it execute. If no runnable process exists, the CPU enters sleep state
 * using WFI (Wait For Interrupt) instruction.
 *
 * The scheduler holds the per-process lock while examining the process state,
 * and releases it before moving to the next process. This ensures atomicity
 * during process state transitions.
 */
1 void scheduler()
2 {
3     struct proc *p = NULL;
4     struct cpu *c = mycpu();
5     c->proc = NULL;
6 
7     for (;;) {
8         intr_on();
9 
10         int found = 0;
11         for (int i = 0; i < NPROC; i++) {
12             p = &procs[i];
13             acquire(&p->lock);
14             if (p->state == RUNNABLE) {
15                 found = 1;
16 
17                 p->state = RUNNING;
18                 c->proc = p;
19 
20                 // Test printf
21                 printf("scheduler: switch to pid %d in core %d\n", p->pid, cpuid());
22                 swtch(&c->context, &p->context);
23 
24                 c->proc = NULL;
25             }
26             release(&p->lock);
27         }
28 
29         if (found == 0) {
30             intr_on();
31             asm volatile("wfi");
32         }
33     }
34 }

代码片段10
代码中第4行获取了与运行中的CPU核心对应的struct cpu结构体实例，第7行开始进入无限循环语句。第8行允许运行中的核心开启中断响应。第11到第27行是从struct proc结构体列表中，查找一个处于RUNNABLE状态的用户进程，并且通过swtch函数，将上下文保存到c->context中，并且从p->context中读取对应的值到当前的寄存器。swtch函数的实现在swtch.S中，其实现逻辑如下所示：

// kernel/swtch.S
# Perform the function of context switch.
# The caller(scheduler) calls the swtch function,
# and saves the caller-save registers,
# so, the swtch only needs to store the callee-save registers.

.global swtch

# The address of old context is in a0
# The address of new context is in a1
1  swtch:
2      # store values into old context
3      sd ra, 0(a0)
4      sd sp, 8(a0)
5      sd s0, 16(a0)
6      sd s1, 24(a0)
7      sd s2, 32(a0)
8      sd s3, 40(a0)
9      sd s4, 48(a0)
10     sd s5, 56(a0)
11     sd s6, 64(a0)
12     sd s7, 72(a0)
13     sd s8, 80(a0)
14     sd s9, 88(a0)
15     sd s10, 96(a0)
16     sd s11, 104(a0)
17 
18     # load values from new context
19     ld ra, 0(a1)
20     ld sp, 8(a1)
21     ld s0, 16(a1)
22     ld s1, 24(a1)
23     ld s2, 32(a1)
24     ld s3, 40(a1)
25     ld s4, 48(a1)
26     ld s5, 56(a1)
27     ld s6, 64(a1)
28     ld s7, 72(a1)
29     ld s8, 80(a1)
30     ld s9, 88(a1)
31     ld s10, 96(a1)
32     ld s11, 104(a1)
33 
34     ret

代码片段11
这段代码中，sd指令是将寄存器的值，存入制定地址的内存。ld指令是将内存中的值读取到寄存器中。其中c->context的地址保存在a0寄存器，p->context的地址保存在a1寄存器中。这段逻辑是将当前CPU的ra、sp和callee-saved寄存器存入c->context结构体中，然后从p->context中读取值到ra、sp和callee-svaed寄存器中。为什么swtch中只保存了callee-saved寄存器？因为swtch在代码片段10中，是被scheduler函数调用的，因此编译器会生成保存caller-saved寄存器到栈空间的指令，因此就不需要程序员自己处理了，而swtch函数是RISC-V汇编指令，因此callee-saved寄存器context结构体中读写的逻辑，要程序员自己实现。相关的介绍，在第一章有解释，读者有兴趣可以回顾一下。
        现在回头来看swtch代码段，前文提到过，此时p->context.ra的值是forkret函数的地址，p->context.sp指向了p->kstack的结束地址，在执行了代码片段11的第34行时，pc寄存器会更新到p->context.ra所指向的地址，然后此时CPU就从代码片段10的第22行代码，直接跳转到forkret函数处：

// kernel/proc.c
1 void forkret() {
2     struct proc* p = myproc();
3     release(&p->lock);
4 
5     usertrapret();
6 }

代码片段12
进入forkret函数之后，首先会获取当前选中的用户进程实例，此时需要先解锁，因为在代码片段10中，调度器对该进程加锁了。接着调用usertrapret函数，这个函数的作用就是让用户进程从内核态切换回用户态。

// kernel/trap.c
/*
 * Return to user space after handling a trap.
 * Switches from kernel mode to user mode by:
 * 1. Setting up trap vector and userret trampoline
 * 2. Saving kernel context in trapframe
 * 3. Configuring status register for user mode
 * 4. Restoring user program counter
 * 5. Switching to user page table
 * Must be called with interrupts disabled
 */
1  void usertrapret()
2  {
3      // Disable interrupt while running usertrapret
4      intr_off();
5  
6      // Set up trap vector and userret trampoline
7      w_stvec((uint64_t)(TRAMPOLINE + (uservec - trampoline)));
8      uint64_t trampoline_userret = TRAMPOLINE + (userret - trampoline);
9  
10     struct proc* p = myproc();
11     p->trapframe->kernel_satp = r_satp();           // save kernel page table
12     p->trapframe->kernel_sp = p->kstack + PGSIZE;   // save kernel stack pointer
13     p->trapframe->kernel_trap = (uint64_t)usertrap; // save usertrap function address
14     p->trapframe->kernel_hartid = r_tp();           // save hart id 
15     
16     uint64_t sstatus = r_sstatus();
17     sstatus = (sstatus & ~SSTATUS_SPP_MASK);   // return to user mode
18     sstatus = sstatus | SSTATUS_SPIE_MASK;     // enable interrupts in user mode
19     w_sstatus(sstatus);
20 
21     w_sepc(p->trapframe->epc); // restore user program counter
22 
23     uint64_t satp = MAKE_SATP((uint64_t)p->pagetable);
24     ((void (*)(uint64_t))trampoline_userret)(satp); // jump to userret trampoline
25 }

代码片段13
usertrapret函数的执行流程如下所示：

  • 第4行，禁止中断响应，避免usertrapret的流程被打断，此时CPU只能执行usertrapret函数内的指令。
  • 第7行，将kernel/trampoline.S中的uservec处的地址，赋值给stvec寄存器，这是用户态处理中断或异常事件的入口地址。这个流程，后文在讨论定时器中断时，会详细论述。
  • 第8行，获取从内核态返回用户态进行上下文恢复的逻辑的起始地址。
  • 第10行到第14行，将当前内核页表根节点的地址存入trapframe的kernel_satp字段，将内核栈kstack的栈底地址保存到trapframe的kernel_sp字段，将处理用户态切换到内核态的usertrap函数的地址保存到trapframe的kernel_trap字段，最后保存RISC-V CPU的hartid到kernel_hartid字段中。这些值在用户态发生异常或中断事件时要用到。
  • 第17行，清掉sstatus寄存器的SPP比特，这样，下一次调用sret指令时，能够让CPU返回用户模式。关于RISC-V的特权架构，读者们如果印象模糊可以返回到第二章查阅。
  • 第18行，设置sstatus寄存器的SPIE为1，这样返回用户态的时候，能够恢复允许中断响应。
  • 第21行，从trapframe中取出epc字段，并写入spec寄存器，这样下次调用sret指令返回用户态时，sepc的值会赋值给pc寄存器，该值是上次用户进程从用户态切入内核态时，下一个要执行的用户空间指令的地址，其初始值是0x0，也就是从用户空间的第1个指令开始执行。
  • 第23行和第24行，先获取用户进程的页表地址，并且作为参数传入userret函数中，然后跳转到该函数内执行，执行内核态到用户态的切换操作。

        userret函数是完全使用RISC-V汇编实现，其实现如下所示：

// kernel/trampoline.S
...

.global userret
1  userret:
2      # switch to user's pagetable
3      sfence.vma zero, zero
4      csrw satp, a0
5      sfence.vma zero, zero
6  
7      li a0, TRAPFRAME
8  
9      ld ra, 40(a0)
10     ld sp, 48(a0)
11     ld gp, 56(a0)
12     ld tp, 64(a0)
13     ld t0, 72(a0)
14     ld t1, 80(a0)
15     ld t2, 88(a0)
16     ld s0, 96(a0)
17     ld s1, 104(a0)
18 
19     ld a1, 120(a0)
20     ld a2, 128(a0)
21     ld a3, 136(a0)
22     ld a4, 144(a0)
23     ld a5, 152(a0)
24     ld a6, 160(a0)
25     ld a7, 168(a0)
26 
27     ld s2, 176(a0)
28     ld s3, 184(a0)
29     ld s4, 192(a0)
30     ld s5, 200(a0)
31     ld s6, 208(a0)
32     ld s7, 216(a0)
33     ld s8, 224(a0)
34     ld s9, 232(a0)
35     ld s10, 240(a0)
36     ld s11, 248(a0)
37 
38     ld t3, 256(a0)
39     ld t4, 264(a0)
40     ld t5, 272(a0)
41     ld t6, 280(a0)
42 
43     ld a0, 112(a0)
44 
45     sret

代码片段14
        在上述userret的汇编指令中，第3行到第5行实现的功能，是往satp寄存器写入用户进程的页表根地址，并且刷新TLB缓存。第7行到第43行指令，是从用户进程的trapframe中恢复之前从用户态切换到内核态时，保存的上下文信息。这里用到了RISC-V中所有的32个通用寄存器，原因是中断和异常对用户进程时无感的，所以当它们触发时，需要保存那一刻CPU所有寄存器的值，本质就是保存发生中断或异常那一刻的用户态上下文信息，然后从内核态返回用户态时再恢复，这样用户进程可以完全无视中断和异常事件，好像它们没发生一样，所有的陷入和恢复操作，对用户进程都是透明的。
        最后执行第45行，通过调用sret指令，让CPU从内核态返回用户态，此时pc寄存器存的是用户空间的0x0地址，sp寄存器指向图4中的“bottom of the user stack”，也就是用户栈栈底。最后运行0x0处的无限循环指令。在没有中断或异常事件发生前，用户进程会一直执行这段指令。

8.2.2.4 定时器中断事件

        接着上一节的内容，此时CPU核心运行的是用户空间的无限循环指令。当定时中断触发时，此时的CPU能够响应该事件，并且将stvec寄存器保存的值赋值给PC寄存器，尔后则跳转到stvec寄存器指向的地址空间执行指令。上一节提到，在执行usertrapret时，已经将trampoline内的uservec函数的地址存到stvec中，那么此时将会触发uservec对应的指令，其实现如下所示：

// kernel/trampoline.S
.global uservec
1  uservec:
2      csrw sscratch, a0
3      li a0, TRAPFRAME
4  
5      sd ra, 40(a0)
6      sd sp, 48(a0)
7      sd gp, 56(a0)
8      sd tp, 64(a0)
9      sd t0, 72(a0)
10     sd t1, 80(a0)
11     sd t2, 88(a0)
12     sd s0, 96(a0)
13     sd s1, 104(a0)
14     sd a1, 120(a0)
15     sd a2, 128(a0)
16     sd a3, 136(a0)
17     sd a4, 144(a0)
18     sd a5, 152(a0)
19     sd a6, 160(a0)
20     sd a7, 168(a0)
21     sd s2, 176(a0)
22     sd s3, 184(a0)
23     sd s4, 192(a0)
24     sd s5, 200(a0)
25     sd s6, 208(a0)
26     sd s7, 216(a0)
27     sd s8, 224(a0)
28     sd s9, 232(a0)
29     sd s10, 240(a0)
30     sd s11, 248(a0)
31     sd t3, 256(a0)
32     sd t4, 264(a0)
33     sd t5, 272(a0)
34     sd t6, 280(a0)
35 
36     # load usertrap
37     ld t0, 16(a0)        
38     
39     # save a0 into the trapframe
40     csrr t1, sscratch
41     sd t1, 112(a0) 
42 
43     # kernel stack
44     ld sp, 8(a0)
45 
46     ld t2, 0(a0)
47     
48     ld tp, 24(a0)
49 
50     sfence.vma zero, zero 
51     csrw satp, t2
52     sfence.vma zero, zero
53 
54     # call usertrap
55     jr t0

...

代码片段15

  • 第2行指令，将a0寄存器的值，保存到CSR寄存器sscratch寄存器中暂存，然后将TRAPFRAME的虚拟地址读取到a0寄存器中，后续对a0指向地址空间的操作，都会通过用户进程的页表，找到对应的物理地址，这个过程是CPU里的MMU组件自动完成的。
  • 第5行到第34行指令，将除了a0寄存器以外的其他31个通用寄存器的值，保存到用户进程的trapframe空间中，这就是传说中的保存用户态上下文操作。
  • 第37行指令，从trapframe中，读出usertrap函数的地址，并存入t0寄存器。
  • 第40行到第41行，从sscratch寄存器中读取原a0寄存器的值，并且存入trapframe对应的位置。
  • 第44行，读取内核栈地址，并存入sp寄存器。
  • 第46行，读取内核页表根地址到t2寄存器中。
  • 第48行，读取hartid到tp寄存器中。
  • 第50行到第52行，从用户进程的页表切换到内核页表中，并清空TLB缓存。
  • 第55行指令，跳转到usertrap函数。

        uservec指令的逻辑，除了保存上下文操作，还进行了页表切换，以及进入到内核的usertrap函数，这个函数内将处理中断和异常事件，其实现逻辑如下所示：

// kernel/trap.c
/*
 * Handle trap from user space.
 * Checks if trap originated from user mode and handles different trap causes:
 * - System calls (scause = 8): Enables interrupts and calls syscall handler
 * - Device interrupts: Handles via devintr()
 * - Timer interrupts (which_dev = 2): Yields CPU
 * Panics on unexpected trap causes or if trap not from user mode.
 * Saves trap state and returns to user mode via usertrapret().
 */
1  void usertrap()
2  {
3      struct proc *p = myproc();
4  
5      uint64_t sstatus = r_sstatus();
6      if ((sstatus & SSTATUS_SPP_MASK) != 0) {
7          panic("usertrap: not from user mode");
8      }
9  
10     if (intr_get() != 0) {
11         panic("usertrap: interrupts enabled");
12     }
13 
14     uint64_t sepc = r_sepc();
15     p->trapframe->epc = sepc;
16 
17     w_stvec((uint64_t)kernelvec);
18 
19     int which_dev = 0;
20     uint64_t scause = r_scause();
21     if (scause == 8) {
22         // system call
23         intr_on();
24         syscall();
25     }
26     else if ((which_dev = devintr(scause)) == 0) {
27         printf("usertrap(): unexpected scause %p pid=%d\n", scause, p->pid);
28         panic("usertrap: unexpected scause");
29     }
30 
31     if (which_dev == 2) {
32         // test printf
33         printf("usertrap():: pid:%d before yield in core %d\n", p->pid, cpuid()); 
34         yield();
35         printf("usertrap():: pid:%d after yield in core %d\n", p->pid, cpuid()); 
36     }
37         
38     usertrapret();
39 }

代码片段16
现在开始深入分析这个函数。

  • 第5行到第8行，从sstatus寄存器中，读取SPP比特，必须是0，0代表从用户态切入内核态，usertrap函数只响应发生于用户态时的异常或中断事件。
  • 第10行到第12行，判断当前是否禁止中断，当中断或异常事件发生时，RISC-V的CPU会将sstatus的允许中断的使能位设置为0，避免在进行处理中断事件的时候，CPU响应新的中断，从而导致无限套娃。
  • 第14行到第15行，读取sepc寄存器的值，并且写入用户进程的trapframe中，这样做的原因是uservec中没有将epc保存到trapframe中，所以需要在usertrap里进行。
  • 第17行，将处于内核态时的异常中断响应事件设置为kernelvec。当CPU处于内核态运行内核指令时，中断响应在kernel/kernelvec.S中的kernelvec中处理。
  • 第19行到第25行，获取异常/中断的原因（scause），当其值为8时，代表是system call类型，此时转入处理system call的逻辑。在进入处理system call之前，要把sstatus寄存器中允许中断的使能位打开，因为system call可能会进行io操作，所以需要允许响应中断事件，这也是为什么需要kernelvec的原因。
  • 第26行到第29行，在devintr中处理中断事件，并将结果赋值给which_dev变量，如果是定时器中断，则返回2。在devintr函数内处理中断响应时，会设置下一次触发定时器中断的时间（一般是100ms）。
  • 第31行到第36行，当中断事件时定时器中断时，通过调用yield函数挂起当前进程。
  • 第38行，调用usertrapret返回用户态，这里就要参考代码片段13了。一般来说，执行到代码片段16的第36行时，当前进程的运行就会暂停，并且切换到代码片段10的第24行，并继续执行后续的逻辑。

        现在来详细看看yield函数的逻辑，这个函数非常重要，它是实现用户进程调度的关键。

// kernel/proc.c
1  void yield() {
2      struct proc* p = myproc();
3      acquire(&p->lock);
4      p->state = RUNNABLE;
5      sched();
6      release(&p->lock);
7  }
8  
9  void sched() {
10     struct cpu* c = mycpu();
11     struct proc* p = c->proc;
12 
13     if (c->noff != 1) {
14         panic("sched locks");
15     }
16 
17     if (p->state == RUNNING) {
18         panic("sched running");
19     }
20 
21     if (intr_get()) {
22         panic("sched interruptible");
23     }
24 
25     int intena = c->intena;
26     swtch(&p->context, &c->context);
27     c->intena = intena;
28 }

代码片段17
逻辑比较简单，就是先对进程加锁，然后将其改成RUNNABLE状态，最后做一些合法性判断后，调用swtch保存用户进程上下文信息（内核态运行的上下文，不是用户态，用户态的上下文信息保存在trapframe中），然后读取调度器的上下文（恢复从scheduler函数切换到用户空间时的指令地址、栈顶地址，以及callee-saved寄存器信息）。此时，CPU的运行流，就会从代码片段17的第27行，跳转到代码片段10的地24行，继续scheduler函数的调度逻辑。
        而当scheduler函数，再次调度到之前yield起的用户进程时，当调度器执行到代码片段10的第22行时，就会直接跳转到代码片段17的第26行（而不是之前的forkret函数了）。接着完成解锁后，返回到代码片段16（usertrap函数），并调用后续的第38行，继续执行usertrapret函数返回用户态。
        这里需要注意的是，运行scheduler函数，用的栈空间是stack0数组空间（在kernel/start.c中定义，每个核心根据自己的hartid，对应stack0数组的某个连续的页，读者可以到对应的文件查阅）。运行usertrap和kerneltrap时，用到的栈空间是内核栈（用户进程对应的kstack空间），而运行用户进程的用户栈，是分配进程时，从内核申请的物理内存页，它会被映射到对应的用户进程虚拟地址空间之中。

8.3 结束语

        本章介绍了dummyxv6的调度机制，首先介绍了CPU进入调度逻辑前的初始化流程，尔后介绍了用户进程的概念，以及内核空间与用户空间的关联，最后通过两个运行无限循环的用户进程，来梳理调度机制的流程。到这里，内容结束。

let us build an os