MIT6.828学习之Lab4: Preemptive Multitasking

在这个lab中，你会在多个同时

active

的用户模式环境中实现

preemptive multitasking

(抢占多任务处理)

在Part A，你会向JOS加入

multiprocessor support

(多处理器支持)，实现

round-robin scheduling

(轮转调度)，并且添加基础的

environment management system calls

(这个调用能创建和destroy环境，还能分配/映射内存)。

在Part B，你会实现一个像Unix里一样的

fork()

函数，它会允许用户模式环境创建自身的

副本

。

最后在Part C中，你将为

inter-process communication

(IPC 进程间通信)添加支持，允许不同的用户模式环境

显式

地彼此进行交流与同步。你也将为

hardware clock interrupts

(硬件时钟中断)和

preemption

(抢占)添加支持。

从MIT6.828/lab4中fetch下来lab4所需地文件，这次我要好好浏览下这些新增的文件。lab3就是没有预先浏览导致不知道很多有用的函数的存在，走了很多弯路。

kern/cpu.h			多处理器支持的内核私有定义
	Cpu状态值、CpuInfo-每个cpu状态结构体、一些函数定义
	
kern/mpconfig.c		读取多处理器配置(configuration)的代码
	mp结构体、mpconf-配置表头结构体、mpproc-处理器表条目结构体
	mpsearch1()、mpsearch()、mpconfig()、mp_init()
	
kern/lapic.c		驱动每个处理器中local APIC (中断控制)单元的内核代码
	很多宏定义、lapicw()、lapic_init()、cpunum()、lapic_eoi()承认中断、
	microdelay()里面空着、lapic_startap()主要函数、lapic_ipi()
	
kern/mpentry.S		非引导cpu的入口代码的汇编语言

kern/spinlock.h		spin locks (自旋锁)的内核私有定义，包括大内核锁

kern/spinlock.c		实现自旋锁的内核代码
	get_caller_pcs()记录caller的eip在pcs[]中、holding()检查thiscpu、
	__spin_initlock()、spin_lock()、spin_unlock()
	
kern/sched.c		要实现的scheduler (调度程序)的代码框架
	sched_yield()使用轮换调度选择一个用户环境去运行、sched_halt()中止没事干的CPU
           

Part A: Multiprocessor Support and Cooperative Multitasking

实验过程点此处

实验要点

1

.symmetric multiprocessing, SMP

中所有cpu都具有对系统资源(如内存和I/O总线)的

等效访问权

。SMP中的cpu分为BSP与Aps。

BSP

负责初始化系统、引导启动操作系统并激活应用程序处理器

APs

2.每个CPU都有一个LAPIC。

LAPIC单元

负责在整个系统中

传输中断

并为其连接的CPU提供

唯一的标识符

。所有 LAPIC 都连接到一个 I/O APIC 上，形成一个一对多的结构，所有的

外部中断

通过

I/O APIC

接收后转发给对应的 LAPIC。但是由于Part A并未涉及I/O APIC编程，所以不太明白其怎么运作

3.使用

大内核锁

的主要原因是在

JOS中每次只能有一个CPU能执行内核代码

。在本部分中，其他申请大内核锁的CPU会简单通过pause指令等待，直到大内核锁被释放

4.Part A部分有三个重点。第一是用

BSP激活所有APs

，找到MP配置表，初始化lapic，找到AP的入口地址以及每个AP的初试栈地址，一个一个启动CPU；第二是实现

轮转调度程序sched_yield()

，在整个用户环境空间中找到一个可执行的程序，如果找不到，就halted当前CPU；第三是实现最简单的

fork的相关系统调用

，允许进程通过这些系统调用创建一个子环境，子环境与父环境有着几乎完全一致的

上下文以及内存空间

(这里是说内容一致，下面Part是说映射一致)，不同的只是返回值用以区分，但是这样的

fork花销很大

，因为往往子进程立马调用exec()替换内存空间，之前复制的就浪费掉了。

代码运行流程简述(从i386_init里开始)

1. 进入mp_init()，通过mpconfig()找到

   MP configuration table

   与MP，根据MP configuration table了解cpu的总数、它们的APIC IDs和LAPIC单元的MMIO地址等配置信息
2. 进入lapic_init()，根据MP配置表找到的lapic的

   MMIO地址

   ，完成

   lapic的初始化

   操作(感觉这里完成的是BSP的lapic的初始化)
3. BSP申请大内核锁，然后进入

   boot_aps()

   去启动其他CPU。在boot_aps中，找到

   AP的入口地址

   ，以及

   AP的初始栈地址

   。
4. 进入lapic_startap()，将

   STARTUP IPIs

   (处理器之间中断)以及一个

   初始CS:IP地址

   即AP入口地址发送到相应AP的LAPIC单元
5. 进入

   mpentry.S

   完成相应CPU的寄存器初始化，启动分页机制，初始化栈，并调用mp_main
6. 进入

   mp_main

   。完成当前CPU的lapic、用户环境、trap的初始化，就算该CPU启动完成。然后想通过

   sched_yield()

   调度一个进程而

   申请大内核锁

   ，但此时

   BSP还保持着大内核锁

   ，所以其他CPU都

   pause

   等待。
7. BSP启动所有CPU后，

   继续执行i386_init

   中的代码，开始创建环境，然后执行轮转调度程序sched_yield()，从刚创建的进程中调度一个进程执行，并

   释放大内核锁

8. BSP释放大内核锁后，其他pause的CPU就

   有一个可以申请

   到大内核锁，调度一个进程执行，其他接着pause。等该CPU在

   env_run中释放大内核锁

   后就又可以有一个CPU申请到大内核锁，就这样一个一个开始执行进程。
9. 当CPU没有环境可执行时，就会进入

   sched_halted()

   里被halted，当最后那个CPU进入这个函数时，不会被halted，而是开始

   执行monitor

   。

Part B: Copy-on-Write Fork

实验过程点此处

实验要点

一、如果将父进程内存空间完全复制给子进程，而子进程通常很快会调用

exec

得到新进程内存，那么之前的复制就是极大的浪费(花销大)。所以Unix的后续版本利用虚拟内存硬件，允许

父进程和子进程共享映射

到各自地址空间的内存，直到其中一个进程实际修改它。这种技术称为“

copy-on-write

”(写时复制)很秀1。

二、在正常执行期间，JOS中的用户环境将运行在

正常的用户堆栈

上:它的

ESP寄存器

从指向USTACKTOP开始，它推送的堆栈数据驻留在

USTACKTOP- PGSIZE到USTACKTOP-1

的页面上。然而，当页面错误在用户模式下发生时，内核将重新启动用户环境，在另一个堆栈上运行指定的

用户级页面错误处理程序

，即

用户异常堆栈

，其有效字节来自

UXSTACKTOP- PGSIZE到UXSTACKTOP-1

。

三、

用户级页面错误处理程序

的调用流程(其中

栈的切换

已经

eip的处理

很秀2)：

1. 当向

   COW页面

   写入时，会产生page fault陷入

   内核

   ，
2. 在trapentry.S–>trap()–>trap_dispatch()–>page_fault_handler()
3. 在page_fault_handler()中完成

   UTrapframe入用户异常栈

   ，将用户进程从普通栈切换到用户异常栈(

   tf->esp指向UXSTACKTOP

   )，设置用户进程下一条指令

   tf->eip=_pgfault_upcall

   。env_run(curenv)回到当前用户进程
4. 此时eip指向_pgfault_upcall，esp指向UXSTACKTOP。所以开始进入pfentry.S/_pgfault_upcall–>

   handler()

   。handler里会分配新的物理页，复制COW页面的内容，并映射到对应内存空间
5. 回到pfentry.S，UTrapframe出栈，很秀的是将

   trap-time eip

   入原栈

   trap-time esp-=4

   处。这样等

   pop esp实现栈切换

   (可能切回用户普通栈，可能是递归页面错误转到用户异常栈靠上方位置。不管怎么说，都在用户空间，所以

   SS不用变

   )。这样再

   ret指令

   就会读到trap-time eip回到发生页面错误处继续往下执行。

四、既然把复制页面映射成COW，那

权限设置与检查

就非常重要，但这是用户空间下的fork，不能通过page_walk来获得

pde，pte

。所以用了个很秀3的映射技巧

uvpt，uvpd

。由于

“no-op”箭头

被巧妙地插入到页目录表中(

页目录表中条目V指向页目录表自身

)，因此我们可以在虚拟地址空间中找到

page directory

和

page tables

的

页面

(通常是不可见的)。

五、

copy-on-write fork

的工作就是

1. 调用

   exofork()

   。分配一个新环境，除了子进程eax设0外，父子进程

   上下文信息tf

   完全一致。就好像子进程也是从0开始运行到了当前位置。
2. 子进程

   虚拟内存空间初始化

   。

   UTOP以上

   的空间在env_alloc中设好了，所有进程该部分都跟内核的该部分内存空间相同。UTOP之下=UXSTACKTOP(一个PGSIZE大小)+USTACKTOP以下。

   UXSTACKTOP

   会分配新物理页，因为UTrapframe跟handler()都在该页面上运行，

   USTACKTOP以下

   的空间就通过

   duppage()

   来复制映射，父子进程内存空间

   共享

   物理内存。
3. 为子进程设置好

   用户级页面错误处理程序

   。调用sys_env_set_pgfault_upcall()
4. 设置子进程状态为

   ENV_RUNNABLE

   。至此子进程完全可以独立运行了。

代码运行流程(以forktree为例)

//forktree.c/umain()
forktree("")

进程 "":
-->forkchild(cur, '0');
	-->r=fork() 完成后父子进程的下一条指令都是if(r==0)
		-->set_pgfault_handler(pgfault);设好用户级页面错误处理程序
		-->who = sys_exofork();此时有两个进程，'上下文信息'基本一样,且下一条语句都是if(who==0)
			分配一个env，'UTOP以上的内存空间'与'内核该部分空间'一样。(所有进程这部分都一样)
			新进程env_tf与父进程完全一样，包括eip即下一条指令也一样，除了reg_eax即返回值不同
			新进程状态设为ENV_NOT_RUNNABLE，所以还不能运行，继续父进程
		-->for (i： 0~ PGNUM(USTACKTOP) duppage(who, i);
			将父进程'内存空间USTACKTOP以下的页面'都'复制映射'给子进程(UTOP以下=USTACKTOP以下+UXSTACKTOP)
			如果页面是可写或者COW的，则复制映射给子进程也是COW的，并重新把父进程的也映射成COW
				(当要往里面写时再调用'用户级页面错误处理程序'分配一个物理页，并重新映射到该处)
			否则就单纯复制映射就行(注意，复制映射不是复制内容)
		-->sys_page_alloc(who, (void *)(UXSTACKTOP-PGSIZE), PTE_W|PTE_U);为子进程用户异常栈分配物理页('必须')。
		-->sys_env_set_pgfault_upcall(who, _pgfault_upcall);注意此时的'who是子进程的id'
		-->sys_env_set_status(who, ENV_RUNNABLE);子进程内存空间、页面错误处理程序都设好了，可以mark它可运行了
		-->return who;父进程里返回的是子进程id
-->forkchild(cur, '1');
	同上述操作一样

此时整个用户环境空间有三个可运行的环境：父进程"",子进程"0",子进程"1"
具体CPU运行哪一个，按轮转调度程序sched_yield()

子进程"0"（或进程"1"）:
-->if(r==0){...}假设此时fork()的返回值是r，r确实为0
	-->forktree("0");操作同上面的forktree
		-->forkchild('0', '0');
		-->forkchild('1', '1');
	所以又会fork出两个新进程，进程"00"，进程"01" （或者进程"10"，进程"11"）
	
父进程""：因为r!=0，所以退出forkchild()，退出forktree(),退出umain()
-->exit() exit gracefully!

当cur长度等于3时，就不会再fork出新子进程了。而完成两次forkchild()的进程都会eixt()
当所有进程都exit()后，CPU就会进入monitor
-->sched_yield() 
-->sched_halted()
-->monitor()

           

Part C: Preemptive Multitasking and Inter-Process communication (IPC)

实验过程点此处

抢占多任务处理

这个其实设置好

时钟中断

(属于设备中断or外部中断)。为每个在CPU上执行的进程分配好时间片。如果时间片用完进程还没主动放弃CPU，那么

时钟中断处理程序

就要调用轮询调度程序

sched_yield()

将CPU给其他进程。要注意

lapic

的管理，以及外部中断入口是

IDT 32-47

进程间通信IPC(以sendpage执行流程为例)

首先说下，

IPC

是Inter-Process Communication。

PIC

是Programmable Interrupt Control。

这里非常秀的是两个系统调用

sys_ipc_try_send()和sys_ipc_recv()

之间的配合，真的是国民老公与傲娇老婆的完美搭配。或者就是一对好基友。

curenv进入接收状态(设好

dstva

，

from=0

证明还没环境发送成功，

recving=1，stats=ENV_NOT_RUNABLE

锁住直到接到"消息")，并让出CPU。要注意的是，除非发生error，否则sys_ipc_recv()是

没有返回值

的。也就是说curenv的%eax将会没有返回值，那怎么办呢？这老婆够傲娇！

不用担心，sys_ipc_try_send为你解决一切烦恼。在对自己进行

详细审查

后才准备发"消息"，如果sendenv

发送“消息”成功

了，它会贴心的帮recvenv设置好

env_ipc_*

，并让

recvenv->env_status=ENV_RUNNABLE

，甚至给

recvenv的%eax赋值0

提醒recvenv它收到"消息"了，真是国民好老公啊！

直接从进入sendpage.c/umain()开始说起。怎么进入的请看Lab3:User Environments

//sendpage.c/umain()
//只启动了一个CPU
父进程：who=fork(),产生子进程，两个进程基本一样，
		-->下一条语句都是if(who==0){...}
		
-->父进程：
-->sys_page_alloc(thisenv->env_id, TEMP_ADDR, PTE_P | PTE_W | PTE_U);
-->memcpy(TEMP_ADDR, str1, strlen(str1) + 1);
-->ipc_send(who, 0, TEMP_ADDR, PTE_P | PTE_W | PTE_U);此时who是子进程id
	-->r=sys_ipc_try_send(to_env, val, pg, perm);
	-->由于子进程不是接收状态，得到r=-E_IPC_NOT_RECV
	-->sys_yield()主动放弃CPU，所以子进程得到CPU

-->子进程进入if循环：
-->ipc_recv(&who, TEMP_ADDR_CHILD, 0); 此时who是from_env，是父进程id
	-->r=sys_ipc_recv(pg);进入接收状态并让出CPU
	设好'dstva'，'from=0'证明还没环境发送成功，'recving=1，stats=ENV_NOT_RUNABLE'锁住直到接到"消息"

-->父进程此时还在轮询sys_ipc_try_send()：
	-->r=sys_ipc_try_send(to_env, val, pg, perm);
	发现子进程进入接收状态，在对自己进行`详细审查`后才准备发"消息"，
	发送"消息"成功了，它会贴心的帮recvenv设置好'env_ipc_*'，
	并让'recvenv->env_status=ENV_RUNNABLE'，甚至给`recvenv的%eax赋值0`提醒recvenv它收到"消息"了
	-->发送成功，返回0，退出ipc_send()
-->ipc_recv(&who, TEMP_ADDR, 0);
	-->r=sys_ipc_recv(pg);进入接收状态并让出CPU

-->子进程还在ipc_recv()里。不过此时已经接收"页面"并映射到TEMP_ADDR_CHILD了,并由父进程的sys_ipc_try_send修复好了状态
	-->*from_env_store=父进程id
	-->*perm_store=perm
-->cprintf("%x got message: %s\n", who, TEMP_ADDR_CHILD);打印处接收到的信息
-->cprintf("child received correct message\n");验证信息是否正确
-->memcpy(TEMP_ADDR_CHILD, str2, strlen(str2) + 1);向TEMP_ADDR_CHILD写入新内容str2
-->ipc_send(who, 0, TEMP_ADDR_CHILD, PTE_P | PTE_W | PTE_U);
将TEMP_ADDR_CHILD对应页面发给父进程。此时的who由子进程的ipc_recv()赋值了父进程id
并且此时父进程已经由ipc_recv()进入了接收状态，所以子进程可以直接发送成功，不用让出CPU
-->return
-->exit()那子进程到这就exit gracefully了，寿终正寝

-->父进程还在ipc_recv()里:也已经收到子进程的信息了，所以退出ipc_recv()，且此时who又指向了子进程id
-->cprintf("%x got message: %s\n", who, TEMP_ADDR_CHILD);打印处接收到的信息
-->cprintf("child received correct message\n");验证信息是否正确
-->return
-->exit()至此，父进程也完成任务exit gracefully

-->monitor()CPU由于没有进程可执行，在sched_halted里进入monitor