吃着土豆坐地铁的博客
0%

MIT-6.828-JOS 笔记 - Lab 4: Preemptive Multitasking

发表于 分类： ， 阅读次数：
本文字数： 21k 阅读时长 ≈ 19 分钟

本实验将开启多处理器、实施多进程管理并提供进程间通讯机制。

本实验代码：https://github.com/epis2048/MIT_6.828_2018/tree/lab4

一、多处理器支持和协作式多任务：

1. 多处理器支持

我们将使JOS支持”symmetric multiprocessing” (SMP)，这是一种所有CPU共享系统资源的多处理器模式。在启动阶段这些CPU将被分为两类：

  1. 启动CPU（BSP）：负责初始化系统，启动操作系统。
  2. 应用CPU（AP）：操作系统启动后由BSP激活。

哪一个CPU是BSP由硬件和BISO决定，到目前位置所有JOS代码都运行在BSP上。
在SMP系统中，每个CPU都有一个对应的local APIC（LAPIC），负责传递中断。CPU通过内存映射IO(MMIO)访问它对应的APIC，这样就能通过访问内存达到访问设备寄存器的目的。LAPIC从物理地址0xFE000000开始，JOS将通过MMIOBASE虚拟地址访问该物理地址。

Exercise 1
实现mmio_map_region()，该函数调用boot_map_region()，将MMIO区域映射到物理地址。用法参见kern/lapic.c中的lapic_init()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// kern/pmap.c
// Your code here:
// 将size以页为单位向上取整
size = ROUNDUP(pa+size, PGSIZE);
pa = ROUNDDOWN(pa, PGSIZE);
size -= pa;	
// Err
if(base + size >= MMIOLIM){
	panic("mmio_map_region: Out of memory\n");
}
// 做映射
boot_map_region(kern_pgdir, base, size, pa, PTE_PCD | PTE_PWT | PTE_W);
// 更新base
base += size;
return (void*)(base - size);

2. AP启动

注意到i386_init()中先调用了mp_init()，这个函数用于从BIOS中读取CPU的信息，并初始化cpus数组，ncpu，bootcpu指针等。
真正启动AP是在boot_aps()中，该函数遍历cpus数组，对每个AP执行mpentry.S中的代码（类似boot.S），并对其初始化。
page_init()中还需要进行一些修改，在最后把MPENTRY_PADDR从空闲列表中删除。

Exercise 2
修改page_init()，避免MPENTRY_PADDR被加入free_list。
代码直接添加到函数最后即可，完整函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// kren/pmap.c
void
page_init(void)
{
// LAB 4:
// Change your code to mark the physical page at MPENTRY_PADDR
// as in use
// 初始化pages数组，建立page_free_list链表
// 已使用的物理页包括如下几部分：
// 1）第一个物理页是IDT所在
// 2）[IOPHYSMEM, EXTPHYSMEM)称为IO hole的区域
// 3）EXTPHYSMEM是内核加载的起始位置，终止位置由boot_alloc(0)给出（boot_alloc()分配的内存是内核的最尾部）
size_t i;
size_t io_hole_start_page = (size_t)IOPHYSMEM / PGSIZE;
size_t kernel_end_page = PADDR(boot_alloc(0)) / PGSIZE;	//boot_alloc返回的是虚拟地址，需要转为物理地址

for (i = 0; i < npages; i++) {
	if (i == 0) {
		pages[0].pp_ref = 1;
		pages[0].pp_link = NULL;
	}
	else if (i >= io_hole_start_page && i < kernel_end_page) {
		pages[i].pp_ref = 1;
		pages[i].pp_link = NULL;
	}
	else {
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
}
// 把MPENTRY_PADDR这块地址也在空闲列表里面删除。
uint32_t range_mpentry = PGNUM(MPENTRY_PADDR);
pages[range_mpentry+1].pp_link=pages[range_mpentry].pp_link;
pages[range_mpentry].pp_link=NULL;
}

3. CPU的状态和初始化

cpunum()总是返回调用它的CPU的ID，宏thiscpu提供了更加方便的方式获取当前代码所在的CPU对应的CpuInfo结构。
每个CPU如下信息是当前CPU私有的：

  1. 内核栈：从内核线性地址空间看CPU 0的栈从KSTACKTOP开始，CPU 1的内核栈将从CPU 0栈后面KSTKGAP字节处开始，以此类推。
  2. TSS和TSS描述符，指定该CPU对应的内核栈。
  3. 进程结构指针，即Env指针。
  4. 系统寄存器：比如cr3, gdt, ltr这些寄存器都是每个CPU私有的。

Exercise 3
修改mem_init_mp()，将内核栈线性地址映射到percpu_kstacks处的物理地址处。 解决：本质上是修改kern_pdir指向的页目录和页表，按照inc/memlayout.h中的结构进行映射即可。

1
2
3
4
5
6
7
8
9
10
11
// kern/pmap.c
// LAB 4: Your code here:
for(size_t i = 0; i < NCPU; i++) {
	boot_map_region(
		kern_pgdir,
		KSTACKTOP - KSTKSIZE - i * (KSTKSIZE + KSTKGAP), 
		KSTKSIZE, 
		PADDR(percpu_kstacks[i]), 
		PTE_W
	);
}

Exercise 4
修改trap_init_percpu()，初始化TSS和TSS描述符，将单CPU代码修改为支持多CPU的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// kern/trap.c
void
trap_init_percpu(void)
{
// LAB 4: Your code here:
// 照着以前代码写即可，主要是把ts用thiscpu->cpu_ts代替
int i = thiscpu->cpu_id;
thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);
thiscpu->cpu_ts.ts_ss0 = GD_KD;
thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

gdt[(GD_TSS0 >> 3) + i] = SEG16(STS_T32A, (uint32_t) (&(thiscpu->cpu_ts)),
				sizeof(struct Taskstate) - 1, 0);
gdt[(GD_TSS0 >> 3) + i].sd_s = 0;

ltr(GD_TSS0 + 8 * i);

lidt(&idt_pd);
}

4. 锁

多个CPU执行内核代码，需要处理竞争条件。简单的办法是将整个内核枷锁，保证只有一个CPU执行内核代码。根据kern/spinlock.h中的定义，这是一种自旋锁，即无限循环等待锁释放。同时，要保证加锁和释放锁的操作是原子的。
此外，还有一种睡眠锁，即当无法获取锁的时候将进程block。在这里JOS没有使用睡眠锁。

Exercise 5
以下四个地方需要获取或释放内核锁：
i386_init()：BSP先获得大内核锁然后再启动其余的CPU。

1
2
3
4
5
6
7
8
9
10
// kern/init.c
// Lab 4 multitasking initialization functions
pic_init();

// Acquire the big kernel lock before waking up APs
// Your code here:
lock_kernel();

// Starting non-boot CPUs
boot_aps();

mp_main()：在初始化AP后获得大内核锁，然后调用sched_yield()开始在这个AP上运行用户环境。

1
2
3
// kern/init.c
// Your code here:
lock_kernel();

trap()：从用户态陷入到内核态必须获得大内核锁，通过检查tf_cs的低位确定这个陷入发生在用户态还是在内核态。

1
2
3
4
5
6
7
8
// kern/trap.c
if ((tf->tf_cs & 3) == 3) {
	// Trapped from user mode.
	// Acquire the big kernel lock before doing any
	// serious kernel work.
	// LAB 4: Your code here.
	lock_kernel();
	assert(curenv);

env_run()：在切换到用户态之前释放大内核锁，不要太早也不要太晚，否则就会体验一把竞争或者死锁的情况。

1
2
3
4
5
6
7
8
9
10
11
12
// kern/env.c
// LAB 3: Your code here.
if(curenv != NULL && curenv->env_status == ENV_RUNNING){ //如果当前有运行的Env，则挂起
	curenv->env_status = ENV_RUNNABLE;
}
curenv = e;
e->env_status = ENV_RUNNING;
e->env_runs++;
lcr3(PADDR(e->env_pgdir)); // 加载当前Env的线性地址到分页寄存器
// Lab4: 释放内核
unlock_kernel();
env_pop_tf(&e->env_tf); // 从栈中取tf结构

5. 轮转调度（RR）

现要JOS内核需要让CPU能在进程之间切换。目前先实现一个非抢占式的进程调度，需要当前进程主动让出CPU，其他进程才有机会在当前CPU运行。

Exercise 6
实现sched_yield()，该函数选择一个新的进程运行，从当前运行的Env的下一个Env开始，寻找一个能运行的Env，如果一个都找不到，那就继续运行当前的，如果自己也运行不了，那当前CPU就停机吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// kern/sched.c
void
sched_yield(void)
{
struct Env *idle;
// LAB 4: Your code here.
// 从当前运行的Env的下一个Env开始
int nextEnvID = 0;
if(curenv) {
	nextEnvID = ENVX(curenv->env_id);
}
// 寻找一个能运行的Env
for(int i = 0; i < NENV; i++){
	if(envs[(nextEnvID + i) % NENV].env_status == ENV_RUNNABLE){
		envs[(nextEnvID + i) % NENV].env_cpunum = cpunum();
		env_run(&envs[(nextEnvID + i) % NENV]);
	}
}
// 如果一个都找不到，那就继续运行当前的
if(curenv && curenv->env_status == ENV_RUNNING){
	curenv->env_cpunum = cpunum();
	env_run(curenv);
}
// 如果自己也运行不了，那当前CPU就停机吧

// sched_halt never returns
sched_halt();
}

实现了sched_yield我们还需要在系统调用里面使用他，不然就不会从一个环境里面出来。
修改syscall()，增加一个系统调用：

1
2
3
4
// kern/syscall.c
	case SYS_yield:
		sys_yield();
		break;

此外，还要记得在mp_main()中注释掉无限循环并调用该函数。

1
2
3
4
// kern/init.c
// Remove this after you finish Exercise 6
//for (;;);
sched_yield();

6. 创建进程相关的系统调用

现在我们的系统已经能够在多进程之间切换，但是还是不能由用户创建进程，在unix中我们用的fork函数创建进程，所以我们现在要实现一个简单fork函数及一些系统调用。注意这里要仔细检查用户程序提供的数据。
sys_exofork()：创建一个新的进程，用户地址空间没有映射，不能运行，寄存器状态和父环境一致。在父进程中sys_exofork()返回新进程的envid，子进程返回0。
sys_env_set_status()：设置一个特定进程的状态为ENV_RUNNABLE或ENV_NOT_RUNNABLE。
sys_page_alloc()：为特定进程分配一个物理页，映射指定线性地址va到该物理页。
sys_page_map()：拷贝页表，使指定进程共享当前进程相同的映射关系。本质上是修改特定进程的页目录和页表。
sys_page_unmap()：解除页映射关系。本质上是修改指定用户环境的页目录和页表。
注意：修改以上函数时均应在syscall中增加相应的判断，不要忘了。

Exercise 7
实现上述所有系统调用。
sys_exofork()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// kern/syscall.c
// 创建一个新进程，用户地址空间不做映射，寄存器状态copy父进程
static envid_t
sys_exofork(void)
{
// LAB 4: Your code here.
struct Env * e;
int ret = env_alloc(&e, curenv->env_id);
if(ret < 0){
	return ret;
}
e->env_tf = curenv->env_tf; // 复制寄存器
e->env_status = ENV_NOT_RUNNABLE; // 进程状态
e->env_tf.tf_regs.reg_eax = 0; // 新的进程从sys_exofork()的返回值应该为0
return e->env_id;
// panic("sys_exofork not implemented");
}

sys_env_set_status()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// kern/syscall.c
// 设置一个特定进程的状态为ENV_RUNNABLE或ENV_NOT_RUNNABLE。
static int
sys_env_set_status(envid_t envid, int status)
{
// LAB 4: Your code here.
if(status != ENV_NOT_RUNNABLE && status != ENV_RUNNABLE) return -E_INVAL;
struct Env * e;
int ret = envid2env(envid, &e, 1);
if(ret < 0){
	return ret;
}
e->env_status = status;
return 0;
//panic("sys_env_set_status not implemented");
}

sys_page_alloc()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// kern/syscall.c
// 为特定进程分配一个物理页，映射指定线性地址va到该物理页。
static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
// LAB 4: Your code here.
struct Env * e;
int ret = envid2env(envid, &e, 1);
if(ret < 0){
	return ret;
}
// 判定va合法性
if ((va >= (void*)UTOP) || PGOFF(va)) return -E_INVAL;
// 判定权限
int flag = PTE_U | PTE_P;
if ((perm & ~(PTE_SYSCALL))!=0 || (perm & flag) != flag) return -E_INVAL;
// 分配物理页
struct PageInfo * pp = page_alloc(1);
if(pp == NULL) return -E_NO_MEM;
ret = page_insert(e->env_pgdir, pp, va, perm);
if(ret < 0){ // page_insert错误
	page_free(pp);
	return ret;
}
return 0;
// panic("sys_page_alloc not implemented");
}

sys_page_map()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// kern/syscall.c
// 拷贝页表，使指定进程共享当前进程相同的映射关系。本质上是修改特定进程的页目录和页表。
static int
sys_page_map(envid_t srcenvid, void *srcva,
     envid_t dstenvid, void *dstva, int perm)
{
// LAB 4: Your code here.
struct Env * se, * de;
int ret = envid2env(srcenvid, &se, 1);
if(ret) return ret; // 错误的Env
ret = envid2env(dstenvid, &de, 1);
if(ret) return ret; // 错误的Env

// 如果两个地址越界或者不是页对齐的，则返回错误
if (srcva >= (void*)UTOP || dstva >= (void*)UTOP || 
	ROUNDDOWN(srcva,PGSIZE) != srcva || ROUNDDOWN(dstva,PGSIZE) != dstva) 
	return -E_INVAL;

// 如果源页没有映射给源进程，则返回错误
pte_t *pte;
struct PageInfo *pg = page_lookup(se->env_pgdir, srcva, &pte);
if (pg == NULL) return -E_INVAL;

// 如果页权限不允许，则返回错误
int flag = PTE_U|PTE_P;
if ((perm & ~(PTE_SYSCALL)) != 0 || (perm & flag) != flag) return -E_INVAL;

// 如果权限为可写而源地址权限为只读，则返回错误
if (((*pte&PTE_W) == 0) && (perm&PTE_W)) return -E_INVAL;

// 如果内存不够生成页表也返回错误
ret = page_insert(de->env_pgdir, pg, dstva, perm);
return ret;
// panic("sys_page_map not implemented");
}

sys_page_unmap()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// kern/syscall.c
// 解除页映射关系。本质上是修改指定用户环境的页目录和页表。
static int
sys_page_unmap(envid_t envid, void *va)
{
// LAB 4: Your code here.
struct Env *env;
int ret = envid2env(envid, &env, 1);
if (ret) return ret;

if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL;
page_remove(env->env_pgdir, va);
return 0;
// panic("sys_page_unmap not implemented");
}

最后还要修改syscall()，将下列系统调用填进去。

1
2
3
4
5
6
7
8
9
10
11
// kern/syscall.c
	case SYS_exofork:
          	return sys_exofork();
	case SYS_env_set_status:
          	return sys_env_set_status((envid_t)a1, (int)a2);
	case SYS_page_alloc:
          	return sys_page_alloc((envid_t)a1, (void *)a2, (int)a3);
      	case SYS_page_map:
          	return sys_page_map((envid_t)a1, (void *)a2, (envid_t)a3, (void *)a4, (int)a5);
      	case SYS_page_unmap:
          	return sys_page_unmap((envid_t)a1, (void *)a2);

二、写时拷贝

父进程将自己的页目录和页表复制给子进程，这样父进程和子进程就能访问相同的内容。只有当一方执行写操作时，才复制这一物理页。这样既能做到地址空间隔离，又能节省了大量的拷贝工作。

1. 用户级别页错误处理

一个用户级写时拷贝的fork函数需要知道哪些page fault是在写保护页时触发的，写时复制只是用户级缺页中断处理的一种。

1.1 设置缺页中断处理程序

首先，处理缺页中断，实现sys_env_set_pgfault_upcall()。该系统调用为指定的用户环境设置env_pgfault_upcall，缺页中断发生时，会执行env_pgfault_upcall指定位置的代码。

Exercise 8
实现sys_env_set_pgfault_upcall()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// kern/syscall.c
// 指定的用户环境设置env_pgfault_upcall，缺页中断发生时，会执行env_pgfault_upcall指定位置的代码。
static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
// LAB 4: Your code here.
struct Env * e;
int ret = envid2env(envid, &e, 1);
if(ret < 0){
	return -E_BAD_ENV;
}
e->env_pgfault_upcall = func;
return 0;
// panic("sys_env_set_pgfault_upcall not implemented");
}

此外，还需要修改sys_call()，增加这一系统调用。

1
2
3
// kern/syscall.c
	case SYS_env_set_pgfault_upcall:
		return sys_env_set_pgfault_upcall(a1,(void *)a2);

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

缺页中断发生时会进入内核的trap()，然后调用page_fault_handler()来处理缺页中断。在该函数中应该做如下几件事：

  1. 判断curenv->env_pgfault_upcall是否设置，如果没有设置也就没办法修复，直接销毁该进程。
  2. 修改esp，切换到用户异常栈。
  3. 在栈上压入一个UTrapframe结构。
  4. 将eip设置为curenv->env_pgfault_upcall，然后回到用户态执行curenv->env_pgfault_upcall处的代码。

Exercise 9
按照上面的描述实现page_fault_handler()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// kern/trap.c
// LAB 4: Your code here.
if(curenv->env_pgfault_upcall){
	struct UTrapframe *utr;
	// 如果已经有了异常栈，我们就直接在后面添加一个UTrapframe，否则就先把跳到异常栈。 这是为了处理多级中断
	if (tf->tf_esp >= UXSTACKTOP-PGSIZE && tf->tf_esp < UXSTACKTOP) {
		// 异常模式下陷入
		utr = (struct UTrapframe *)(tf->tf_esp - sizeof(struct UTrapframe) - 4);
	}
	else {
		// 非异常模式下陷入
		utr = (struct UTrapframe *)(UXSTACKTOP - sizeof(struct UTrapframe));	
	}
	// 检查异常栈是否溢出
	user_mem_assert(curenv, (const void *) utr, sizeof(struct UTrapframe), PTE_P|PTE_W);
	utr->utf_fault_va = fault_va;
	utr->utf_err = tf->tf_trapno;
	utr->utf_regs = tf->tf_regs;
	utr->utf_eip = tf->tf_eip;
	utr->utf_eflags = tf->tf_eflags;
	utr->utf_esp = tf->tf_esp; // UXSTACKTOP栈上需要保存发生缺页异常时的%esp和%eip
	// 设置eip，回到用户态
	curenv->env_tf.tf_eip = (uintptr_t)curenv->env_pgfault_upcall;
	curenv->env_tf.tf_esp = (uintptr_t)utr;
	env_run(curenv); // 重新进入用户态
}
else{
	// Destroy the environment that caused the fault.
	cprintf("[%08x] user fault va %08x ip %08x\n",
		curenv->env_id, fault_va, tf->tf_eip);
	print_trapframe(tf);
	env_destroy(curenv);
}

1.3 用户模式页面错误入口点

为了向用户提供该函数，需要修改lib/pfentry.S和lib/pgfault.c中的代码，提供这一调用能力。

Exercise 10
实现lib/pfentry.S中的_pgfault_upcall函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// lib/pfentry.S
 	// Struct PushRegs size = 32 
 	addl $8, %esp                 // esp+8 -> PushRegs   over utf_fault_va utf_err
movl 0x20(%esp), %eax         // eax = (esp+0x20 -> utf_eip )
subl $4, 0x28(%esp)           // for trap time eip 保留32bit,   esp+48 = utf_esp
movl 0x28(%esp), %edx         // %edx = utf_esp-4  
movl %eax, (%edx)             // %eax = eip ----> esp-4  以至于ret可以直接读取其继续执行的地址

popal              // after popal esp->utf_eip

addl $4, %esp      // esp+4 -> utf_eflags
popfl

popl %esp

ret                   // 这里十分巧妙， ret会读取esp指向的第一个内容， 也就是我们第一步写入的eip

Exercise 11
完成lib/pgfault.c中的set_pgfault_handler()。

1
2
3
4
5
6
7
// lib/pgfault.c
	// LAB 4: Your code here.
	r = sys_page_alloc(0, (void *)(UXSTACKTOP-PGSIZE), PTE_W | PTE_U | PTE_P); //为当前进程分配异常栈
	if (r < 0) {
		panic("set_pgfault_handler:sys_page_alloc failed");;
	}
	sys_env_set_pgfault_upcall(thisenv->env_id, _pgfault_upcall); //系统调用，设置进程的env_pgfault_upcall属性

坑：user_mem_check()中的cprintf()需要去掉，不然faultregs这个测试可能会过不了。

2. 实现写时拷贝fork

前面我们有一个测试程序，user/dumbfork.c，这个里面已经有了模板，我们现在要做的就是实现一个差不多的fork。
他的基本流程是：
到目前已经可以实现用户级别的写时拷贝fork函数了。fork流程如下：

  1. 使用set_pgfault_handler()设置缺页处理函数。
  2. 调用sys_exofork()系统调用，在内核中创建一个Env结构，复制当前用户环境寄存器状态，UTOP以下的页目录还没有建立，新创建的进程还不能直接运行。
  3. 拷贝父进程的页表和页目录到子进程。对于可写的页，将对应的PTE的PTE_COW位设置为1。
  4. 为子进程设置_pgfault_upcall。
  5. 将子进程状态设置为ENV_RUNNABLE。

缺页处理函数pgfault()流程如下：

  1. 如果发现错误是因为写造成的（错误码是FEC_WR）并且该页的PTE_COW是1，则进行执行第2步，否则直接panic。
  2. 分配一个新的物理页，并将之前出现错误的页的内容拷贝到新的物理页，然后重新映射线性地址到新的物理页。

Exercise 12
实现lib/fork.c中的fork, duppage and pgfault。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// lib/fork.c
envid_t
fork(void)
{
// LAB 4: Your code here.
envid_t cenvid;
   unsigned pn;
   int r;
set_pgfault_handler(pgfault); //设置 缺页处理
if ((cenvid = sys_exofork()) < 0){ //创建了一个进程。
	panic("sys_exofork failed");
	return cenvid;
}
if(cenvid>0){//如果是 父亲进程
	for (pn=PGNUM(UTEXT); pn<PGNUM(USTACKTOP); pn++){ //复制UTEXT 到USTACKTOP的页
           if ((uvpd[pn >> 10] & PTE_P) && (uvpt[pn] & PTE_P))
               if ((r = duppage(cenvid, pn)) < 0)
                   return r;
	}
	if ((r = sys_page_alloc(cenvid, (void *)(UXSTACKTOP-PGSIZE), PTE_U | PTE_P | PTE_W)) < 0)  //分配一个新的页
           return r;
	extern void _pgfault_upcall(void); //缺页处理
	if ((r = sys_env_set_pgfault_upcall(cenvid, _pgfault_upcall)) < 0)
           return r; //为儿子设置一个缺页处理分支
	if ((r = sys_env_set_status(cenvid, ENV_RUNNABLE)) < 0)//设置成可运行
           return r;
       return cenvid;
}
else {
	thisenv = &envs[ENVX(sys_getenvid())];//如果是儿子就直接运行。
	return 0;
}
//panic("fork not implemented");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// lib/fork.c
static int
duppage(envid_t envid, unsigned pn)
{
int r;

// LAB 4: Your code here.
void* vaddr=(void*)(pn*PGSIZE);

if((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)){
	if ((r = sys_page_map(0, vaddr, envid, vaddr, PTE_P | PTE_U | PTE_COW)) < 0)
           return r;//映射当前页为写时符合
       if ((r = sys_page_map(0, vaddr, 0, vaddr, PTE_P | PTE_U | PTE_COW)) < 0)
           return r;//把自己当前页页标记成写时复制。
}
else if((r = sys_page_map(0, vaddr, envid, vaddr, PTE_P | PTE_U)) < 0) {
	return r;//如果当前页已经是写时复制  就不需要更改了
}
//panic("duppage not implemented");
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// lib/fork.c
static void
pgfault(struct UTrapframe *utf)
{
void *addr = (void *) utf->utf_fault_va;
uint32_t err = utf->utf_err;
int r;
// LAB 4: Your code here.
if (!(
       (err & FEC_WR) && (uvpd[PDX(addr)] & PTE_P) &&
       (uvpt[PGNUM(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_COW)
)) panic("Neither the fault is a write nor copy-on-write page.\n");//如果不是因为这个原因 就panic
// LAB 4: Your code here.
if((r = sys_page_alloc(0, PFTEMP, PTE_U | PTE_P | PTE_W)) < 0){
	 panic("sys_page_alloc: %e\n", r);//分配了一个页
}
addr = ROUNDDOWN(addr, PGSIZE);//页对齐
memcpy((void *)PFTEMP, addr, PGSIZE);//把这个写时复制的页内容复制一遍
if ((r = sys_page_map(0, (void *)PFTEMP, 0, addr, PTE_P | PTE_U | PTE_W)) < 0)
       panic("sys_page_map: %e\n", r);//把当前映射的 地址 指向PFTEMP 新分配的页
   if ((r = sys_page_unmap(0, (void *)PFTEMP)) < 0) //取消PFTEMP 的映射，这样就把虚拟地址指向了一个新的页。
       panic("sys_page_unmap: %e\n", r);
//panic("pgfault not implemented");
}

三、抢占式多任务和进程间通讯（IPC）

1. 时钟中断和抢占

目前程序一旦进入用户模式，除非发生中断，否则CPU永远不会再执行内核代码。我们需要开启时钟中断，强迫进入内核，然后内核就可以切换另一个进程执行。

Exercise 13
修改kern/trapentry.S和trap.c来实现这些外部中断，与之前内部中断类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// kern/trapentry.S
TRAPHANDLER_NOEC(IRQ0, IRQ_OFFSET)
TRAPHANDLER_NOEC(IRQ1, IRQ_OFFSET+1)
TRAPHANDLER_NOEC(IRQ2, IRQ_OFFSET+2)
TRAPHANDLER_NOEC(IRQ3, IRQ_OFFSET+3)
TRAPHANDLER_NOEC(IRQ4, IRQ_OFFSET+4)
TRAPHANDLER_NOEC(IRQ5, IRQ_OFFSET+5)
TRAPHANDLER_NOEC(IRQ6, IRQ_OFFSET+6)
TRAPHANDLER_NOEC(IRQ7, IRQ_OFFSET+7)
TRAPHANDLER_NOEC(IRQ8, IRQ_OFFSET+8)
TRAPHANDLER_NOEC(IRQ9, IRQ_OFFSET+9)
TRAPHANDLER_NOEC(IRQ10, IRQ_OFFSET+10)
TRAPHANDLER_NOEC(IRQ11, IRQ_OFFSET+11)
TRAPHANDLER_NOEC(IRQ12, IRQ_OFFSET+12)
TRAPHANDLER_NOEC(IRQ13, IRQ_OFFSET+13)
TRAPHANDLER_NOEC(IRQ14, IRQ_OFFSET+14)
TRAPHANDLER_NOEC(IRQ15, IRQ_OFFSET+15)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// kern/trap.c
void IRQ0();
void IRQ1();
void IRQ2();
void IRQ3();
void IRQ4();
void IRQ5();
void IRQ6();
void IRQ7();
void IRQ8();
void IRQ9();
void IRQ10();
void IRQ11();
void IRQ12();
void IRQ13();
void IRQ14();
void IRQ15();

SETGATE(idt[IRQ_OFFSET], 0, GD_KT, IRQ0, 0);
SETGATE(idt[IRQ_OFFSET+1], 0, GD_KT, IRQ1, 0);
SETGATE(idt[IRQ_OFFSET+2], 0, GD_KT, IRQ2, 0);
SETGATE(idt[IRQ_OFFSET+3], 0, GD_KT, IRQ3, 0);
SETGATE(idt[IRQ_OFFSET+4], 0, GD_KT, IRQ4, 0);
SETGATE(idt[IRQ_OFFSET+5], 0, GD_KT, IRQ5, 0);
SETGATE(idt[IRQ_OFFSET+6], 0, GD_KT, IRQ6, 0);
SETGATE(idt[IRQ_OFFSET+7], 0, GD_KT, IRQ7, 0);
SETGATE(idt[IRQ_OFFSET+8], 0, GD_KT, IRQ8, 0);
SETGATE(idt[IRQ_OFFSET+9], 0, GD_KT, IRQ9, 0);
SETGATE(idt[IRQ_OFFSET+10], 0, GD_KT, IRQ10, 0);
SETGATE(idt[IRQ_OFFSET+11], 0, GD_KT, IRQ11, 0);
SETGATE(idt[IRQ_OFFSET+12], 0, GD_KT, IRQ12, 0);
SETGATE(idt[IRQ_OFFSET+13], 0, GD_KT, IRQ13, 0);
SETGATE(idt[IRQ_OFFSET+14], 0, GD_KT, IRQ14, 0);
SETGATE(idt[IRQ_OFFSET+15], 0, GD_KT, IRQ15, 0);

此外，还要在env_alloc()中开启这些中断。

1
2
3
4
// trap/env.c
// Enable interrupts while in user mode.
// LAB 4: Your code here.
e->env_tf.tf_eflags |= FL_IF;

注意：不要忘记sched_halt()函数中要取消的注释。

1
2
3
4
5
6
7
8
9
10
11
12
// kern/sched
asm volatile (
	"movl $0, %%ebp\n"
	"movl %0, %%esp\n"
	"pushl $0\n"
	"pushl $0\n"
	// Uncomment the following line after completing exercise 13
	"sti\n"
	"1:\n"
	"hlt\n"
	"jmp 1b\n"
: : "a" (thiscpu->cpu_ts.ts_esp0));

Exercise 14
修改trap_dispatch()，使时钟中断发生时，切换到另一个进程执行。

1
2
3
4
5
6
7
8
// kern/trap.c
// LAB 4: Your code here.
// 时钟中断
if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
	lapic_eoi();
	sched_yield();
	return;
}

2. IPC通信

2.1 JOS中的IPC

我们将要实现sys_ipc_recv()和sys_ipc_try_send()这两个系统调用，来实现进程间通信。并且实现两个包装函数ipc_recv()和 ipc_send()。
JOS中进程间通信的“消息”包含两部分：一个32位的值；可选的页映射关系。

2.2 发送和接受消息

sys_ipc_recv()和sys_ipc_try_send()协作方式：

  1. 当某个进程调用sys_ipc_recv()后，该进程会阻塞（状态被置为ENV_NOT_RUNNABLE），直到另一个进程向它发送“消息”。当进程调用sys_ipc_recv()传入dstva参数时，表明当前进程准备接收页映射。
  2. 进程可以调用sys_ipc_try_send()向指定的进程发送“消息”，如果目标进程已经调用了sys_ipc_recv()，那么就发送数据，然后返回0，否则返回-E_IPC_NOT_RECV，表示目标进程不希望接受数据。当传入srcva参数时，表明发送进程希望和接收进程共享srcva对应的物理页。如果发送成功了发送进程的srcva和接收进程的dstva将指向相同的物理页。

Exercise 15
实现sys_ipc_recv()和sys_ipc_try_send()。包装函数ipc_recv()和 ipc_send()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// kern/syscall.c
static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
// LAB 4: Your code here.
// panic("sys_ipc_try_send not implemented");
struct Env* env;
if (envid2env(envid, &env, 0) < 0) return -E_BAD_ENV; // 错误ID
if (env->env_ipc_recving == 0) return -E_IPC_NOT_RECV; // 进程不接收消息
if ((uintptr_t) srcva < UTOP) { // 页地址小于UTOP
	pte_t *pte;
	struct PageInfo *pg = page_lookup(curenv->env_pgdir, srcva, &pte);

	//按照注释的顺序进行判定
	if (srcva != ROUNDDOWN(srcva, PGSIZE)) return -E_INVAL; //srcva没有页对齐
	if ((*pte & perm) != perm) return -E_INVAL; //perm应该是*pte的子集
	if (!pg) return -E_INVAL; //srcva还没有映射到物理页
	if ((perm & PTE_W) && !(*pte & PTE_W)) return -E_INVAL; //写权限
	
	if (env->env_ipc_dstva < (void*)UTOP) {
		int ret = page_insert(env->env_pgdir, pg, env->env_ipc_dstva, perm); //共享相同的映射关系
		if (ret) return ret;
		env->env_ipc_perm = perm;
	}
}
// 设置一些值
env->env_ipc_recving = false;
env->env_ipc_from = curenv->env_id;
env->env_ipc_value = value;
env->env_status = ENV_RUNNABLE;
env->env_tf.tf_regs.reg_eax = 0;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// kern/syscall.c
static int
sys_ipc_recv(void *dstva)
{
// LAB 4: Your code here.
// panic("sys_ipc_recv not implemented");
if ((dstva < (void*)UTOP) && PGOFF(dstva)) return -E_INVAL; // 报错
curenv->env_ipc_recving = true;
curenv->env_ipc_dstva = dstva;
curenv->env_status = ENV_NOT_RUNNABLE;
sys_yield();
return 0;
}

注：不要忘了修改sys call()

1
2
3
4
5
6
7
// kern/syscall.c
	case SYS_ipc_try_send:
		ret =  sys_ipc_try_send((envid_t)a1, (uint32_t)a2, (void *)a3, (unsigned)a4); 
		break;
	case SYS_ipc_recv:
		ret =  sys_ipc_recv((void *)a1);
		break;

此外，还要实现一些向用户提供的库，修改ipc_recv()和ipc_send()即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// lib/ipc.c
int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
// LAB 4: Your code here.
// panic("ipc_recv not implemented");
if (pg == NULL) pg = (void*)-1;
int r = sys_ipc_recv(pg);
if (r < 0) { // UTOP相当于没有地址返回0
	if (from_env_store != NULL) *from_env_store = 0;
	if (perm_store != NULL) *perm_store = 0;
	return r;
}
if (from_env_store != NULL) *from_env_store = thisenv->env_ipc_from;
if (perm_store != NULL) *perm_store = thisenv->env_ipc_perm;
return thisenv->env_ipc_value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// lib/ipc.c
void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
// LAB 4: Your code here.
// panic("ipc_send not implemented");
if (pg == NULL) pg = (void*)-1;
int r;
while(1) {
	r = sys_ipc_try_send(to_env, val, pg, perm);
	if (r == 0) { //发送成功
		break;
	} else if (r == -E_IPC_NOT_RECV) { //接收进程没有准备好
		sys_yield();
	} else { //其它错误
		panic("ipc_send():%e", r);
	}
}
}

总结

本lab还是围绕进程这个概念来展开的。主要介绍了四部分：

  1. 支持多处理器。现代处理器一般都是多核的，这样每个CPU能同时运行不同进程，实现并行。需要用锁解决多CPU的竞争。
  2. 实现进程调度算法。 一种是非抢占式式的，另一种是抢占式的，借助时钟中断实现，时钟中断到来时，内核调用sched_yield()选择另一个Env结构执行。
  3. 实现写时拷贝fork（进程创建）。fork()是库函数，会调用sys_exofork(void)这个系统调用，该系统调用在内核中为子进程创建一个新的Env结构，然将父进程的寄存器状态复制给该Env结构，复制页表，对于PTE_W为1的页目录，复制的同时，设置PTE_COW标志。为父进程和子进程设置缺页处理函数，处理逻辑：当缺页中断发生是因为写写时拷贝的地址，分配一个新的物理页，然后将该虚拟地址映射到新的物理页。
  4. 实现进程间通信。本质还是进入内核修改Env结构的的页映射关系。