xv6实验-抢占式多任务调度(文档篇)

介绍

这个实验会实现多个活动用户环境的抢占式多任务处理

Part A会添加JOS的多处理器支持，实现循环调度(round-robin)，添加基本环境管理系统调用(创建和销毁环境，分配和映射内存)

Part B会实现类Unix的fork
，使用用户环境创建副本

Part C添加进程间通信(IPC)的支持，让不同的用户模式环境交互和同步。还会添加硬件时钟中断抢占的支持

开始

老规矩，切换到lab4
的分支，然后合并lab3
的代码。新增的代码：

• kern/cpu.h
  多处理器支持的内核私有定义
• kern/mpconfig.c
  读取多处理器配置
• kern/lapic.c
  每个处理器驱动本地APIC单元的内核代码
• kern/mpentry.c
  非启动CPU的汇编语言入口代码
• kern/spinlock.h
  实现自旋锁内核代码
• kern/sched.c
  将要实现的调度器骨架

实验要求

这部分就不翻译了，没有意义

Part A: 多处理器支持和协作式多任务

这个实验的第一部分，扩展JOS运行在一个多处理器系统上，然后实现一些JOS内核系统调用，让用户级别环境创建额外新的环境。将要实现写作式(cooperative)循环调度，当当前环境自愿放弃CPU的时候，允许内核从一个环境切换到另一个环境。在Part C会实现抢占式(preemptive)调度，这将允许内核在一定时间后直接拿回CPU的控制权

多处理器支持

将让JOS支持对称多处理器(SMP)，在一个多处理器模型中，所有的CPU都有系统相同的权限，比如内存和I/O总线。虽然所有在SMP中，所有的CPU功能都相同，但是在启动的时候，处理器会分成两类：引导处理器(BSP)负责初始化系统和引导操作系统；应用处理器(APs)是在操作系统启动且运行之后，由BSP激活。硬件和BIOS决定哪个处理器是BSP。到目前为止，所有的JOS代码都运行在BSP上

在一个SMP系统中，每个CPU都附带本地的APIC(LAPIC)单元，LAPIC单元负责在整个系统中传递中断。LAPIC还为连接的CPU提供了唯一的标识。这个实验，使用LAPIC单元下面基本功能(kern/lapic.c
)：

• 读取LAPIC标识来辨别当前代码运行在哪个CPU上(参考cpunum()
  )
• 把STARTUP
  处理器间中断(IPI)从BSP发送给APs，来唤醒其他的CPU(参考lapic_startap()
  )
• 在Part C， 编写LAPIC的内建定时器来触发始终中断，从而支持抢占式多任务(参考apic_init()
  )

一个处理器使用内存映射I/O(MMIO)来获取LAPIC。在MMIO中，一部分物理内存硬连接到I/O设备的寄存器，所以，通常用户访问内存的加载/保存指令也能用来访问设备寄存器。你已经知道物理内存地址0xA000
处有一个I/O洞(用来输出VGA显示)。LAPIC位于从物理地址0xFE000000
开始的洞中。对于我们来说，使用直接映射到KERNBASE
的方式去访问，实在是太高了。JOS虚拟内存地址映射留了一个4MB的间隙在MMIOBASE
的位置，所以我们有一个位置来像这样映射设备。由于后面的实验有更多MMIO区域的指令，所以你将写一个简单的函数来从这些区域分配空间并将设备内存映射过去

进行练习1

应用处理器引导

在启动APs之前，BSP应该首先收集关于多核处理器系统信息，比如CPU总数，APIC的ID以及LAPIC的MMIO地址。kern/mpconfig.c
里面的mp_init
函数通过读取保存在BIOS的MP配置表来检索这些信息

boot_aps
函数(在kern/init.c
)驱动AP引导程序。APs在实模式启动，跟在boot/boot.S
中的引导程序类似，所以boot_aps()
复制AP入口代码(kern/mpentry.S
)到实模式内存地址。不像引导程序，可以控制AP开始执行代码的位置；复制入口代码到0x7000
位(MPENTRY_PADDR
),但是任何未使用的，低于640KB页面对齐的物理地址都可以使用。

之后，boot_aps
通过发送IPIs
给LAPIC单元来一个个激活APs，同时初始化CS:IP
地址为AP应该开始运行的入口地址(在这个实验中是MPENTRY_PADDR
)。kern/mpentry.S
的入口代码与boot/boot.S
非常类似。在简短设置之后，通过页面启动的方式把AP放到保护模式，然后调用C启动协程mp_main
(也在kern/init.c
)。在继续唤醒下一个之前，boot_aps
等待AP发送一个CPU_STARTED
信号给struct CpuInfo
结构的cpu_status
变量

进行练习2

单CPU状态和初始化

当写一个多处理器操作系统时，区分单CPU状态(对每个处理器是私有的)和全局状态(整个系统共享的)是非常重要的。kern/cpu.h
定义了大多数单CPU状态，包括保存了单CPU变量的struct CpuInfo
。cpunum()
总是返回调用的CPU的ID，可以看作是cpus
数组的下标。thiscpu
宏是当前CPU结构体struct CpuInfo
的简写

下面是你需要注意的单CPU状态：

• 单CPU内核栈 .
  因为多CPU能够同时陷入内核，所以对每个处理器都需要一个单独内核栈，防止干扰彼此的运行。数组percpu_kstacks[NCPU][KSTKSIZE]
  保存了NCPU的内核栈

  在lab2中，映射了物理地址，仅仅把低于KSTACKTOP
  的bootstack
  指向了BSP的内核栈。相似的，在这个lab中，将映射每个CPU的内核栈道这个带有保护页面的区域，保护页面的功能是作为缓存使用。CPU 0栈仍然从KSTACKTOP
  向下生长；CPU 1栈将从CPU 0栈的底部开始KSTKGAP
  字节，依此类推，inc/memlayout.h
  有映射布局

• 单CPU的TSS和TSS描述符 .
  一个单CPU任务状态段(TSS)也是必须的，以便于指定每个CPU的内核栈的位置。CPU 的TSS保存在cpus[i].cpu_ts
  ，与GDT入口gdt[(GD_TSS0 >> 3)]
  定义的TSS描述符相关联。在kern/trap.c
  中定义的全局ts
  变量不再使用了

• 单CPU当前环境指针 .
  因为每一个CPU能同时运行不同的用户进程，所以重新定义了curenv
  指向cpus[cpunum()].cpu_env
  (或thiscpu->cpu_env
  )，指向环境当前正在执行执行的CPU(代码正在运行的CPU)

• 单CPU系统寄存器所有寄存器，包括系统寄存器对CPU来说都是私有的。因此初始化这些寄存器的指令(如lcr3()
  , ltr()
  , lgdt()
  , lidt()
  )必须扩展到每一个CPU。函数env_init_percpu()
  和trap_init_percpu()
  就是这个目的

  此外，对于之前实验中挑战代码，还需要添加额外的单CPU状态或额外的CPU指定初始化(例如，在CPU寄存器中进行位操作)

  进行练习3

  进行练习4

锁

在mp_main
初始化AP之后，当前的代码就在自旋。让AP运行其他之前，当多CPU同时运行内核代码的时候，需要定位竞争条件。最简单的做饭就是用一个大内核锁。大内核锁是一个单个全局锁，当环境进入内核代码时，就获取锁，当环境回到用户模式时，就释放锁。这种模型下，用户模式的环境能并发在任何有效的CPU上，但是只能有一个用户环境进入内核；任何尝试进入内核模式的环境都会被强制等待

kern/spinlock.h
声明了一个大内核锁，称为kernel_lock
。它提供了lock_kernel
和unlock_kernel
方法，简单来说就是获取和释放锁。你应该在4个地方用到大内核锁：

• 在i386_init()
  中，BSP唤醒其他CPU之前获取锁
• 在mp_main()
  中，初始化AP之后获取锁，然后调用shed_yield()
  开始在这个AP上运行环境
• 在trap()
  中，当从用户模式陷入的时候，获取锁。为了确定trap是在用户模式还是在内核模式下发生的，检查tf_cs
  的低位就可以了
• 在env_run()
  中，刚刚要切换到用户模式之前，释放锁。不要太早也不要太晚，否则会遭遇竞争或死锁

进行练习5

轮询调度

这个实验的下一个任务是修改JOS内核，以便于它可以以轮询的方式在多个环境之间循环。JOS的轮询调度工作原理如下：

• kern/sched.c
  里面的sched_yield()
  负责选择一个环境运行。它在envs[]
  里面循环搜索，从上个运行的环境(或者如果没有上一个运行的环境，就从数组的起始位置)开始，选择第一个状态为ENV_RUNNABLE
  的环境，然后调用env_run()
  跳转到环境运行
• sched_yield()
  不能同时在两个CPU运行同一个环境。它可以分辨某个环境当前运行在某个CPU上(有可能是当前CPU)，因为那个环境的状态会是ENV_RUNNING
  
• sys_yield()
  是一个已经实现的系统调用，用户环境可以调用它来调用内核的sched_yield()
  ，从而自愿将CPU给不同的环境

进行练习6

创建环境的系统调用

尽管现在内核能够运行和切换多个用户级别的环境，但是仍然只能运行由内核初始化设置的环境。现在要实现JOS系统调用，允许用户环境创建和开始一个新用户环境

Unix提供了fork()
系统调用作为进程创建的原语。Unix的fork()
复制调用进程(父进程)的地址空间来创建一个新进程(子进程)。两者唯一的区别是进程ID(getpid
)和父进程ID(getppid
)。在父进程中，fork()
返回子进程ID，然而在子进程中，fork()
返回0。默认的，每个进程有自己私有的地址空间，彼此对进程内存的修改都不可见。

你将提供一个不同的，更原始的创建用户模式环境的JOS系统调用集。通过这些系统调用，你能在用户空间实现一个类Unix的fork
。新的系统调用如下：

• sys_exofork
  : 这个系统调用创建一个几乎空白的新环境:地址空间的用户部分没有映射任何东西也不能运行。在调用sys_exofork
  的时候，新环境和父环境有相同的寄存器状态。在父环境中，sys_exofork
  返回新环境的envid_t
  (或创建失败为负数),在子环境中，返回0.(因为子环境一开始被标记为不可以运行，sys_exofork
  不会在子环境中返回，直到父环境通过明确标记子环境允许运行)
• sys_env_set_status
  : 设置指定环境的状态为ENV_RUNNABLE
  或者ENV_NOT_RUNNABLE
  。这个系统调用时典型用来标记一个新环境准备运行了，一旦它的地址空间和寄存器状态被初始化了
• sys_page_alloc
  : 分配一页物理内存，并映射到环境地址空间给定的虚拟地址
• sys_page_map
  : 将页面映射(不是页面内容)从一个环境地址空间复制到另一个地址空间，保留内存共享，以便于新和旧的映射同时指向相同的物理内存页
• sys_page_unmap
  : 在给定的环境中，取消给定虚拟内存的映射

所有的系统调用接受一个环境ID参数，JOS内核支持0代表当前环境的公约。这个公约由kern/env.c
的envid2env()
实现

已经提供了一个类Unix的fork()
原语实现，实现位于测试程序user/dumbfork.c
。这个测试程序使用上面的系统调用来创建和运行子环境，通过复制自己的地址空间。父环境在10次迭代后，然而子环境存在于20次

进行练习7

写时复制的fork

正如前面提到的，Unix提供了fork()
系统调用作为主要进程创建原语。fork()
系统调用复制调用者地址空间来创建一个新进程

xv6 Unix通过从父进程页面复制所有数据到分配给子进程的新页面，来实现了fork()
。这基本上与dumbfork()
采用的方法相同。复制父进程地址空间到子进程开销是很大的。

然而，在调用fork()
之后，子进程的exec()
几乎紧随其后，exec()
调用会新程序替换子进程的内存。在这种情况下，复制父进程地址空间消耗是非常巨大的，因为子进程在调用exec()
之前使用的内存是非常少的

由于这个原因，Unix后面的版本利用了虚拟内存硬件，允许父进程和子进程共享映射到他们地址空间的内存，直到一个进程实际修改了它。这个技术被称为写时复制(copy-on-write)。为了做到这一点，内核在fork()
时，复制的是地址空间的映射，而不是映射页的内容，同时暂时共享的页面标记为只读的。基于这一点，Unix内核知道页面是"虚拟的"或"写时复制"，所以它会为页面创建一个私有的，可写的页面复制。这样，单个页面的内容直到写入的时候，才会被复制。这个优化让fork()
之后再运行exec()
的开销变小了很多:在执行exec()
之前，子进程只需要复制一个页面(当前栈页面).

这个实验的下一节，会实现一个合适的类Unix的写时复制fork()
，作为用户空间库。实现支持用户空间的fork()
和写时复制有利于内核保持简洁。也可以让用户模式程序定义自己的fork()
语义。

用户级别错误处理

用户级别的写时复制fork()
需要知道在写保护页面上的页面错误，所以，这个是首先要实现的。写时复制是用户级别页面错误处理众多可能用途中的一种

设置一个地址空间是很常见的，以便于页面错误指明何时需要执行某些动作。例如，大多数Unix内核最开始只在一个新进程栈区域映射一个单独的页面，然后当进程栈消耗增加且导致没有映射到栈地址上的页面错误的时候，分配和映射额外的栈页面。当一个页错误发生在进程空间的每个区域的时候，一个典型的Unix内核必须跟踪要采取的操作。例如在栈区域发生的错误将分配和映射一个新的物理内存页。在程序BBS区域发生的错误会分配一个新页面，并用0填充然后映射。在需要页面执行的系统中，发生在text区域的错误会从磁盘读取相关的页面，然后映射

内核需要跟踪的信息有很多。不是采取传统的Unix方法，你将决定在用户空间的页面错误时要做什么，其中错误破坏性非常小。这个设计让程序在定义它们内存空间时有更好的灵活性；你使用用户级别页面错误映射和从磁盘获取文件。

设置页面错误处理

为了处理页面错误，用户环境需要用JOS内核保存一个页面错误处理入口。用户环境通过sys_env_set_pgfault_upcall
系统调用来保存页面错误入口。

进行练习8

用户环境正常和异常栈

在正常执行期间，JOS的用户环境运行在正常用户栈上:ESP
寄存器开始指向USTACKTOP
，入栈数据保存在USTACKTOP-PGSIZE
到USTACKTOP - 1
之间。当用户模式下发生页面错误时，内核将重启运行在不同栈上用户级别页面错误处理的用户环境，名为用户异常栈。本质上，会让JOS内核代表用户环境实现自动"栈切换"，在某种程度上说，这与x86处理器在从用户模式切换到内核时，代表JOS实现的切换栈相类似

JOS用户异常栈也是一页大小为单位的，栈顶定义了UXSTACKTOP
的虚拟地址。所以用户异常栈有效字节是从UXSTACKTOP - PGSIZE
到UXSTACKTOP - 1
。当运行在这个异常栈的时候，用户级别页面错误处理是用JOS的常规系统调用来映射新页面或调整映射，以便于修复无论什么页面错误造成的问题。然后用户级别页面错误处理通过汇编语言stub
返回到原始栈错误代码处理处。

每个想支持用户级别页面处理错误的用户环境需要为它们分配自己的异常栈，异常栈通过Part A中介绍的sys_page_alloc()
系统调用分配。

调用用户页面错误处理程序

你需要修改kern/trap.c
中页面错误处理代码来处理下面用户模式的页面错误。把用户环境发生错误时间的状态称为trap-time
状态

如果没有注册页面错误处理程序，JOS内核跟前面一样会销毁用户环境。否则内核在异常栈上设置trap frame
，定义在inc/trap.h
的struct UTrapframe

                    <-- UXSTACKTOP
trap-time esp
trap-time eflags
trap-time eip
trap-time eax       start of struct PushRegs
trap-time ecx
trap-time edx
trap-time ebx
trap-time esp
trap-time ebp
trap-time esi
trap-time edi       end of struct PushRegs
tf_err (error code)
fault_va            <-- %esp when handler is run

复制

然后内核通过运行在带有stack frame
异常栈上的页面错误处理程序，来为用户环境恢复运行；你必须要理解这是怎么发生的。fault_va
是造成页面错误的虚拟地址

如果当异常发生的时候，用户环境已运行在用户异常栈上，那么页面错误处理程序本身就有错误。这种情况下，你应该在当前的tf->tf_esp
(而不是UXSTACKTOP
)下面开始新的stack frame
。你应该首先压入一个32位的字，然后才是struct UTrapframe

测试tf->tf_esp
是否已经在用户异常栈上，包括检查是否在UXSTACKTOP-PGSIZE
到UXSTACKTOP - 1
之间

进行练习9

用户模式页面错误入口

接下来，你需要实现调用C页面错误处理和恢复原始错误指令的汇编程序。汇编程序是通过由内核注册的sys_env_set_pgfault_upcall()
处理程序

进行练习10

最后，需要实现C用户库代码

进行练习11

实现写时复制fork

你已经在用户空间拥有完整实现写时复制fork
的内核工具

我们已经提供了一个fork
的骨架在lib/fork.c
中。就像dumbfork()
一样，fork()
应该创建一个环境，然后扫描父环境的整个地址空间并在子环境中设置相关页面的映射。不同点是dumbfork()
是复制页面，fork()
最开始仅仅复制页面映射。fork()
仅仅会在环境尝试写的时候才会复制页面

fork()
的基本流程如下:

1. 父环境使用set_pgfault_handler()
   注册pgfault()
   作为C级别的页面错误处理
2. 父环境调用sys_exofork()
   创建一个子环境
3. 对于每个在低于UTOP
   地址空间的可写或写时复制页面，父环境调用duppage
   ，这个调用会映射写时复制页面到子环境地址空间，然后remap
   写时复制页面到自己地址空间。[注意：这里顺序有影响(例如标记页面为写时复制时，子页面优先)。可以考虑一下为什么]。duppage
   设置两个PTEs
   包含PTE_COW
   来区分写时复制页面和只读页面，以便于页面不可写。然而这种情况下，异常栈不会重映射。你需要在异常栈里为子环境分配一个新的页面。因为页面错误处理程序会真正复制，同时运行在异常栈上，所以异常栈没有做成写时复制。
4. 父环境为子环境设置页面错误处理程序的入口
5. 子环境准备运行了，所以父环境将其标记为可运行的

每次环境要写一个写时复制的页面时，会发出一个页面错误。下面是页面错误处理程序流程：

1. 内核传播页面错误给_pgfault_upcall
   ，这个会调用fork()
   的pgfault()
   处理程序。
2. pgfault()
   检测错误是写(检测FEC_WR
   错误码)且页面的PTE
   被标记为PTE_COW
   ，如果不是的话，就panic
3. pgfault()
   分配映射到一个临时位置的新页面并且复制错误页面的内容到这个新页面。然后错误处理函数在合适的位置映射新页面，页面包含读写权限。

进行练习12

Part C: 抢占式多任务调度和进程间通信(IPC)

lab4的最后，需要修改内核，进行抢占式调度和允许环境之间交换信息

时间中断和抢占

运行user/spin
的测试程序。这个测试程序复制了一个子环境，子环境一旦拿到CPU控制权，就一直自旋。父进程和内核都无法拿到CPU的控制权。对于保护系统环境而言，这显然不是一个理想的环境，因为任何用户模式环境都能无限获取CPU的控制权。为了允许内核抢占运行环境，强制拿到CPU的控制权，必须扩展JOS内核支持时钟硬件中断

中断原则

扩展中断(比如设备中断)指向IRQs，有16个IRQs，从0-15排序。从IRQ序号到IDT入口的映射不是固定的。在picirq.c
中的pic_init
映射了IRQs 0-15到IDT的入口(从IRQ_OFFSET
到IRQ_OFFSET+ 15
)

在inc/trap.h
中，IRQ_OFFSET
被定义成十进制32，因此IDT入口32-47与IRQs的0-15关联。例如，时钟中断是IRQ 0。因此在内核中，IDT[IRQ_OFFSET+0]
包含了时钟中断处理函数的入口地址。IRQ_OFFSET
存在是为了不让设备中断和处理器异常重叠，实际上早期的MS-DOS系统中，IRQ_OFFSET
是0，经常会有奇怪的错误产生。

相比于xv6，在JOS中，我们做了一个关键的简化。在内核中，额外的设备中断总是被禁用(与xv6类似，在用户空间才会启用)。额外中断由eflags
寄存器的FL_IF
控制位控制的(参考inc/mmu.h
)。当被置位时，额外的中断会启用。这个位有多种方式修改，因为简化过，当进入和离开用户模式的时候，恢复和修改eflags
的FL_IF

必须确保FL_IF
标志位在用户环境被置位了，以便于中断到达的时候，可以传递给处理器然后处理中断代码。否则中断被覆盖了，或者忽略了直到中断再次启用。在引导程序指令中，忽略了中断，目前为止也没有再次启用它

进行练习13

处理时钟中断

在user/spin
程序中，子环境运行之后，一直自旋，内核永远也拿不到控制权。需要硬件周期性生成时钟中断，这样可以强制让内核拿到控制权，然后交给不同的用户环境

lapic_init
和pic_init
的调用已经写好了设置始终和中断控制器来生成终端。需要写代码来处理这些中断

进行练习14

进程间通信(IPC)

之前一直专注于操作系统隔离方面，它提供了一种错觉，每个程序独占一台机器。操作系统另一个重要的服务是允许进程间相互通信。Unix管道是一个典型的例子

有很多进程间通信的模型。甚至今天也没办法证明哪种模型是最好的。也不打算去证明。我们打算实现一个简单的IPC机制，并且尝试理解它

JOS的IPC

你会实现一些JOS系统调用来实现一个简单的进程间通信机制。你实现两个系统调用sys_ipc_recv
和sys_ipc_try_send
，然后实现两个库包装ipc_recv
和ipc_send

用户环境能够通过JOS的IPC机制发送给对方的消息是由两个部分组成：一个单个32位值和可选的单页面映射。允许环境传递页面映射提供了更方便的方式来传递更多的信息，同时也让环境设置共享内存更容易

发送和接收消息

为了接收消息，环境调用sys_ipc_recv
。这个系统调用取消调度当前环境并且直到信息接收才会再次运行。当环境在等待接收信息时，任何其他的环境都能发送消息。换句话说，在Part A中实现的权限校验不会应用到IPC中，因为IPC系统调用为了安全而设计的：通过发送消息，一个环境能够造成另一个环境故障(除非目标环境也有bug)

为了发送消息，环境调用sys_ipc_try_send
，并带有接收者环境id和需要发送的内容。如果环境真的接收了，然后发送给发送者消息并返回0.否则会发送-E_IPC_NOT_RECV
表明目标环境没有接收到消息

用户空间ipc_recv
库函数调用sys_ipc_recv
,然后在当前环境strcut Env
中查找接收到信息的

相似的，ipc_send
库函数调用sys_ipc_try_send
直到发送成功

转换页面

当环境使用有效的dstva
参数（低于UTOP
）调用sys_ipc_recv
时，环境表明它愿意接收页面映射。如果发送方发送一个页面，那么该页面应该映射到接收方地址空间中的dstva
。如果接收方已经在dstva
上映射了一个页面，则该前一个页面将被取消映射。

当环境使用有效的srcva
（低于UTOP
）调用sys_ipc_try_send
时，这意味着发送方希望将当前映射在srcva
的页面发送给接收方，并且权限为perm
。IPC 成功后，发送方在其地址空间中的srcva
处保留其原始页面的映射，但接收方也在接收方地址空间中在接收方最初指定的dstva
处获得同一物理页面的映射。因此，此页面在发送方和接收方之间共享。

如果发送方或接收方未指示应传送页面，则不传送页面。在任何 IPC 之后，内核将接收者的 Env
结构中的新字段 env_ipc_perm
设置为接收到的页面的权限，如果没有接收到页面，则设置为零

进行练习15