Lab 4: Preemptive Multitasking

Part A: Multiprocessor Support and Cooperative Multitasking

在这个部分，我们要扩展JOS使得其能够运行在多处理器系统上，同时增加新的系统调用使得用户进程能够创建新的用户进程为part copy-on-write fork()做准备。之后我们将实现一个最基本的调度算法: Round-Robin调度算法。

多处理器支持

我们将在JOS中实现SMP架构，在这个架构中，每个CPU核都对如内存和I/O总线等系统资源在访问上具有相同的优先级，即每个核的地位是等同的。然而，在启动过程中，他们被分为两类：

bootstrap processor (BSP): 负责系统的初始化并启动系统。
application processors (APs): 除BSP之外的CPU，被BSP唤醒。

在SMP架构中，每个CPU都有一个对应的local APIC (LAPIC) unit，它负责向CPU传递系统中断。处理器通过MMIO来访问它的LAPIC。在lapic_init()中通过mmio_map_region()在物理地址lapicaddr处创建了MMIO的虚拟内存映射。我们首先需要完成mmio_map_region()这个辅助函数。它使用boot_map_region()来完成相应的地址分配。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void * mmio_map_region(physaddr_t pa, size_t size)
{
	static uintptr_t base = MMIOBASE;

	size_t pa_lim = ROUNDUP(pa + size, PGSIZE);
	pa = ROUNDDOWN(pa, PGSIZE);
	size_t sz = pa_lim - pa;
	void * ret;

	if (base + sz >= MMIOLIM) {
		panic("mmio_map_region: overflow MMIOLIM!\n");
	}
	boot_map_region(kern_pgdir, base, sz, pa, PTE_PCD | PTE_PWT | PTE_W);
	ret = (void *)base;
	base += sz;
	return ret;
}

应用处理器的启动

在启动其他AP之前，BSP首先通过kern/mpconfig:mp_init()函数收集CPU总数，其他核的APIC ID，MMIO地址等信息。之后在kern/init.c:boot_aps()中，由于AP将在实模式下启动，BSP将其他AP的entry code (kern/mpentry.S)复制到一个实模式下可寻址的位置MPENTRY_PADDR=0x7000，然后通过向每个AP的LAPIC发送STARTUP IPIs来一次唤醒这些AP，同时向它们传递启动代码的位置。BSP通过等待CPU_STARTED信号来判断某个CPU是否已经启动成功，从而唤醒下一个CPU。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


static void boot_aps(void)
{
	extern unsigned char mpentry_start[], mpentry_end[];
	void *code;
	struct CpuInfo *c;

	// Write entry code to unused memory at MPENTRY_PADDR
	code = KADDR(MPENTRY_PADDR);
	memmove(code, mpentry_start, mpentry_end - mpentry_start);

	// Boot each AP one at a time
	for (c = cpus; c < cpus + ncpu; c++) {
		if (c == cpus + cpunum())  // We've started already.
			continue;
		// Tell mpentry.S what stack to use 
		mpentry_kstack = percpu_kstacks[c - cpus] + KSTKSIZE;
		// Start the CPU at mpentry_start
		lapic_startap(c->cpu_id, PADDR(code));
		// Wait for the CPU to finish some basic setup in mp_main()
		while(c->cpu_status != CPU_STARTED)
			;
	}
}

AP被唤醒后，将首先执行mpentry.S中的代码（注意每唤醒一个AP，系统就多一个执行流）。它所做的工作和BSP的初始化类似：建立临时段表，进入保护模式，打开分页功能，然后控制流转移到mp_main()。

这里我们需要修改pmap.c:page_init()使其将MPENTRY_PADDR处的物理页标记为不可用从而保证我们可以安全地将AP的启动代码复制到这个位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void page_init()
{
    // ...
	size_t mmio_page_num = MPENTRY_PADDR / PGSIZE;
	for (i = 1; i < npages_basemem; i++) {
		// mark the physical page at MPENTRY_PADDR as in use for booting up APs
		if (i == mmio_page_num) {
			pages[i].pp_ref = 1;
			continue;
		}
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
    // ...
}

Per-CPU State and Initialization

对于一个多处理器系统来说每个CPU有其私有状态，也有共享的全局状态。在本实验中，我们需要关注的CPU私有状态包括：

Per-CPU kernel stack
Per-CPU TSS and TSS descriptor
Per-CPU current environment pointer
Per-CPU system registers

JOS通过struct CpuInfo来保存这些变量

1
2
3
4
5
6
7


// Per-CPU state
struct CpuInfo {
	uint8_t cpu_id;                 // Local APIC ID; index into cpus[] below
	volatile unsigned cpu_status;   // The status of the CPU
	struct Env *cpu_env;            // The currently-running environment.
	struct Taskstate cpu_ts;        // Used by x86 to find stack for interrupt
};

我们需要修改mem_init_mp()是BSP在启动其他AP之前，为每个CPU分配栈空间。

1
2
3
4
5
6
7
8
9


static void mem_init_mp(void)
{
	size_t i = 0;
	uintptr_t stop;
	for (; i < NCPU; i++) {
		stop = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);
		boot_map_region(kern_pgdir, stop - KSTKSIZE, KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_P | PTE_W);
	}
}

同时还要修改kern/trap.c:trap_init_percpu()使得其能为每个CPU初始化自己的TSS和TSS descriptor。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


void trap_init_percpu(void)
{
	size_t id = thiscpu->cpu_id;
    
	// Setup a TSS so that we get the right stack
	// when we trap to the kernel.
	thiscpu->cpu_ts.ts_esp0 = (uint32_t)percpu_kstacks[id] + KSTKSIZE;
	thiscpu->cpu_ts.ts_ss0 = GD_KD;
	thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

	// Initialize the TSS slot of the gdt.
	gdt[(GD_TSS0 >> 3) + id] = SEG16(STS_T32A, (uint32_t) (&thiscpu->cpu_ts),
					sizeof(struct Taskstate) - 1, 0);
	gdt[(GD_TSS0 >> 3) + id].sd_s = 0;

	// Load the TSS selector (like other segment selectors, the
	// bottom three bits are special; we leave them 0)
	ltr(GD_TSS0 + (id << 3));

	// Load the IDT
	lidt(&idt_pd);
}

注意通过ltr保存TSS selector时低三位为0，第i个CPU的TSS selector索引为(GD_TSS0 >> 3) + id，故叮当加载的值为GD_TSS0 + (id << 3)。

创建进程的系统调用

接下来我们需要完成创建进程所需要的系统调用，这也是在用户进程完成copy-on-write fork()所需要的元操作。

kern/syscall.c:sys_exofork(): 分配一个新的struct env(PCB)，设置其状态为ENV_NOT_RUNNABLE，复制父进程的trap frame到新创建的子进程，同时将其trap frame中的%eax寄存器，即系统调用的返回值置为0，使得该创建出的子进程被唤醒后的返回值为0。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


static envid_t sys_exofork(void)
{
	struct Env *env;
	int ret = env_alloc(&env, curenv->env_id);
	if (ret < 0) {
		return (envid_t)ret;
	}
	env->env_status = ENV_NOT_RUNNABLE;
	// memcpy(&env->env_tf, &curenv->env_tf, sizeof(struct Trapframe));
	env->env_tf = curenv->env_tf;
	env->env_tf.tf_regs.reg_eax = 0;
	return env->env_id;
}

还要注意将系统调用sys_exofork()封装为供用户进程的库函数时必须inline为一条汇编指令，否则子进程无法正确返回。

inc/lib.h:sys_exofork():

1
2
3
4
5
6
7
8
9


static inline envid_t __attribute__((always_inline))
sys_exofork(void)
{
	envid_t ret;
	asm volatile("int %2"
		     : "=a" (ret)
		     : "a" (SYS_exofork), "i" (T_SYSCALL));
	return ret;
}

kern/syscall.c:sys_env_set_status: 用于改变进程状态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


static int sys_env_set_status(envid_t envid, int status)
{
	struct Env *env;
	if (status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) {
		return -E_BAD_ENV;
	}
	int ret = envid2env(envid, &env, 1);
	if (ret < 0) {
		return ret;
	}
	env->env_status = status;
	return 0;	
}

sys_page_alloc/sys_page_map/sys_page_unmap: 用于分配页，更改页映射关系。这里需要注意做相关的检查。

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


static int sys_page_alloc(envid_t envid, void *va, int perm)
{
	struct Env *env;
	struct PageInfo* pp;
	int ret = envid2env(envid, &env, 1);
	if (ret < 0) {
		return ret;
	}
	if ((uintptr_t)va >= UTOP || (uintptr_t)va % PGSIZE != 0) {
		return -E_INVAL;
	}
	if ((perm & (PTE_U | PTE_P)) != (PTE_U | PTE_P) || (perm & ~(PTE_SYSCALL)) != 0) {
		return -E_INVAL;
	}
	if (!(pp = page_alloc(0))) {
		return -E_NO_MEM;
	}
	if ((ret = page_insert(env->env_pgdir, pp, va, perm)) < 0) {
		return ret;
	}
	return 0;
}

static int sys_page_map(envid_t srcenvid, void *srcva,
	     envid_t dstenvid, void *dstva, int perm)
{
	struct Env *srcenv, *dstenv;
	struct PageInfo *pp;
	pte_t *pte;
	int ret;
	if ((ret = envid2env(srcenvid, &srcenv, 1)) < 0) {
		return ret;
	}
	if ((ret = envid2env(dstenvid, &dstenv, 1)) < 0) {
		return ret;
	}
	if ((uintptr_t)srcva >= UTOP || (uintptr_t)srcva % PGSIZE != 0 || (uintptr_t)dstva >= UTOP || (uintptr_t)dstva % PGSIZE != 0) {
		return -E_INVAL;
	}
	if ((perm & (PTE_U | PTE_P)) != (PTE_U | PTE_P) || (perm & ~(PTE_SYSCALL)) != 0) {
		return -E_INVAL;
	}
	if (!(pp = page_lookup(srcenv->env_pgdir, srcva, &pte))) {
		return -E_INVAL;
	}
	if ((perm & PTE_W) && !(*pte & PTE_W)) {
		return -E_INVAL;
	}
	if ((ret = page_insert(dstenv->env_pgdir, pp, dstva, perm)) < 0) {
		return ret;
	}
	return 0;
}

static int sys_page_unmap(envid_t envid, void *va)
{
	struct Env *env;
	struct PageInfo* pp;
	int ret;
	if ((ret = envid2env(envid, &env, 1)) < 0) {
		return ret;
	}
	if ((uintptr_t)va >= UTOP || (uintptr_t)va % PGSIZE != 0) {
		return -E_INVAL;
	}
	page_remove(env->env_pgdir, va);
	return 0;
}

Part B: Copy-on-Write Fork

part A中的dumpfork()给出了一个可能的fork()实现，然而它在创建子进程时就将父进程中的页面全部复制到子进程中分配的新页面中。在本节中我们要实现一个更高效的copy-on-writefork()，即在fork()调用时并不复制全部的页面数据到子进程中，而只是将页表项复制到子进程的页目录中。即父子进程将各自的虚拟页面映射到相同的物理页面上，只有当其中一方需要写某个页面时才真正为其分配新的物理页并复制数据。显然，我们需要在缺页中断函数中处理这部分逻辑。这也使得用户可以通过更改自己的缺页中断处理函数来定制相应的fork()逻辑。

用户态缺页中断处理函数的设置

我们首先增加一个设置用户态缺页异常处理函数的系统调用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


static int sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
	int ret;
	struct Env *env;
	if ((ret = envid2env(envid, &env, 1)) < 0) {
		return ret;
	}
	env->env_pgfault_upcall = func;
	return 0;
}

用户态的异常处理栈

通常，用户态所使用的栈是栈顶位于USTACKTOP的栈空间，我们称之为normal stack。在发生缺页异常时，内核会在切换到另一个栈空间上(需要用户进程通过系统调用分配)运行相应的缺页中断处理函数，这个栈空间被称为exception stack。JOS中用户态的异常处理栈的栈顶位于UXSTAKTOP，大小为一页。在完成缺页异常的处理后，将通过pfentry.S:_pgfault_upcall恢复到发生缺页中断前的状态。

当进程没有注册缺页处理函数时，内核将销毁该进程。否则，内核会在异常处理栈上建立起如下所示的栈帧并调用缺页异常处理函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


                    <-- 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

kern/trap.c: 这里我们通过将struct UTrapframe *utf的地址改为相应的地址然后直接进行赋值来得到所需的栈帧布局。需要注意的是，如果在执行page_fault_handler的过程中发生了缺页异常，我们需要首先保留一个4个字节的空白区域然后再将栈帧构造为如上布局（我们可以通过%esp相对UXSTACKTOP的位置来判断是否是在执行page_fault_handler的过程中发生了缺页异常）。这个留出的4字节位置的作用将在后一部分解释。

 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


void page_fault_handler(struct Trapframe *tf)
{
	uint32_t fault_va;
	fault_va = rcr2();
	if ((tf->tf_cs & 0x3) == 0) {
		panic("page_fault_handler: receive page fault in kernel mode!");
    }
	struct UTrapframe *utf;
	if (curenv->env_pgfault_upcall != NULL) {
		if (curenv->env_tf.tf_esp >= UXSTACKTOP - PGSIZE && curenv->env_tf.tf_esp < UXSTACKTOP) {
			utf = (struct UTrapframe *)((char *)curenv->env_tf.tf_esp - 32 - sizeof(struct UTrapframe));
		} else {
			utf = (struct UTrapframe *)((char *)UXSTACKTOP - sizeof(struct UTrapframe));
		}

		user_mem_assert(curenv, (void *)utf, sizeof(struct UTrapframe), PTE_U | PTE_W | PTE_P);
		
		utf->utf_fault_va = fault_va;
		utf->utf_err = tf->tf_err;
		utf->utf_regs = tf->tf_regs;
		utf->utf_eip = tf->tf_eip;
		utf->utf_eflags = tf->tf_eflags;
		utf->utf_esp = tf->tf_esp;

		tf->tf_esp = (uint32_t)utf;
		tf->tf_eip = (uint32_t)curenv->env_pgfault_upcall;

		env_run(curenv);
	}
	cprintf("[%08x] user fault va %08x ip %08x\n",
		curenv->env_id, fault_va, tf->tf_eip);
	print_trapframe(tf);
	env_destroy(curenv);
}

Trap-time状态的恢复

接下来我们要在pfentry.S:_pgfalut_up_call中实现paeg_handler()处理完之后恢复到发生缺页中断之前状态的逻辑。这里的难点在于我们需要让所有状态都恢复到发生缺页中断之前，使得缺页中断的过程仿佛没有发生一样。如果我们简单地直接使用jmp指令，这需要我们首先将返回地址复制到一个寄存器中，这显然会破坏保存的寄存器状态。如果我们直接使用call指令，那么%esp寄存器将依然指向异常处理栈的栈顶。还要注意的是，当我们恢复了保存的状态寄存器后，我们就不能进行任何运行。当恢复通用寄存器后，也无法再使用这些通用寄存器。

为了在这些约束条件下条件下实现要求，我们需要一些特殊的技巧，具体而言，我们将修改生缺页中断时的trap-time %eip复制到当前normal stack栈帧的底部(即trap-time %esp下方的4字节)，这也是为什么在第一次缺页中断后需要在构造新的异常处理栈帧之前留出4字节的空白，其作用是为了存放%eip从而能够正确返回到调用之前的状态。下面是具体过程分析。

_pgfault_handler返回后栈帧布局如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


============== Normal Stack ===================
(instruction that cause page falut)    <- trap-time %esp 
============ Current Exception Stack ============
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

我们首先修改栈帧上保存的trap-time %esp从而将normal stack的栈空间扩大了4个字节，然后将trap-time %eip放入复制到这四个字节中（相当与向normal stack中压入了trap-time %eip）。（sizeof(struct UTrapframe)==52B，%esp此时指向栈顶的fault_va，0x30(%esp)即为trap-time %esp的地址，0x28(%esp)即为trap-time %eip的地址）。

1
2
3
4
5


	movl 0x30(%esp), %eax
	subl $0x4, %eax       // extend the trap-time stack to store the trap-time's %eip
	movl %eax, 0x30(%esp) // update the trap-time's %esp
	movl 0x28(%esp), %ebx // load trap-time's eip
	movl %ebx, (%eax) 	  // save the trap-time's %eip to the 'extended' trap-time stack

此时栈帧布局如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


============== Normal Stack ===================
(instruction that cause page falut)    <- trap-time %esp 
trap-time %eip     <- (trap-time %esp) - 4
============ Current Exception Stack ============
(trap-time %esp) - 4  
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

之后跳过fault_va和错误码，然后恢复通用寄存器。

1
2
3
4


	// Restore the trap-time registers.  After you do this, you
	// can no longer modify any general-purpose registers.
	addl $8, %esp // skip fault_va and tf_err
	popal // restore the trap-time registers

此时栈帧布局如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


============== Normal Stack ===================
(instruction that cause page falut)   <- trap-time %esp 
trap-time %eip     <- (trap-time %esp) - 4
============ Current Exception Stack ============
(trap-time %esp) - 4  
trap-time eflags
trap-time eip		<-- %esp
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     

然后跳过trap-time %eip并恢复状态寄存器。

1
2
3
4
5


	// Restore eflags from the stack.  After you do this, you can
	// no longer use arithmetic operations or anything else that
	// modifies eflags.
	addl $4, %esp // skip the trap-time's %eip
	popfl // restore the trap-time eflags

此时栈帧布局如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


============== Normal Stack ===================
(instruction that cause page falut)    <- trap-time %esp 
trap-time %eip     <- (trap-time %esp) - 4
============ Current Exception Stack ============
(trap-time %esp) - 4   <-- %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            

切回缺页中断前的栈空间

1
2


	// Switch back to the adjusted trap-time stack.
	pop %esp

此时栈帧布局如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


============== Normal Stack ===================
(instruction that cause page falut)    <- trap-time %esp 
trap-time %eip     <- %esp
============ Current Exception Stack ============
(trap-time %esp) - 4
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            

最后用ret指令返回

1
2


	// Return to re-execute the instruction that faulted.
	ret 

此时栈帧布局如下：

1
2


============== "Caller" Stack ===================
(instruction that cause page falut)    <- trap-time %esp | current %esp

于是我们恢复了所以寄存器的值，成功还原到了发生缺页中断之前的状态。

之后，我们在lib/pg_fault.c:set_pgfault_handler()中注册缺页中断函数同时在第一次调用时分配异常栈空间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void set_pgfault_handler(void (*handler)(struct UTrapframe *utf))
{
	int r;
	envid_t envid = 0;
	if (_pgfault_handler == 0) {
		if ((r = sys_getenvid()) < 0) {
			panic("set_pgfault_handler: %e!\n", r);
		}	
		if ((r = sys_page_alloc(envid, (void *)(UXSTACKTOP - PGSIZE), PTE_U | PTE_P | PTE_W)) < 0) {
			panic("set_pgfault_handler: %e!\n", r);
		}
		sys_env_set_pgfault_upcall(envid, _pgfault_upcall);
	}
	_pgfault_handler = handler;
}

实现`copy-on-write fork()`

完成前述工作后，我们终于可以来实现一个copy-on-write fork()。在此之前，我们还需要知道如何在用户进程中访问页表。这里JOS使用了一个trick来实现这一点。

fork()的控制流如下：

首先，父进程通过set_pgfault_handler()函数为自己注册缺页中断处理函数pgfault()。

pgfault()：通过由处理器返回的err和页表项判断是否符合复制的条件（写操作引发的缺页中断，对应的页表项被标记为PTE_COW），对于符合条件的页对其进行复制。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


static void pgfault(struct UTrapframe *utf)
{
	void *addr = (void *) utf->utf_fault_va;
	uint32_t err = utf->utf_err;
	int r;
	if (!((err & FEC_WR) == FEC_WR) || !((uvpt[PGNUM(addr)] & PTE_COW) == PTE_COW)) {
		panic("pgfault: the faulting access was not a write or not to a COW page! err: %u, addr:%p", err, addr);
	}
	if ((r = sys_page_alloc(0, PFTEMP, PTE_P | PTE_U | PTE_W)) < 0) {
		panic("sys_page_alloc: %e", r);
	}
	memcpy(PFTEMP, ROUNDDOWN(addr, PGSIZE), PGSIZE);
	if ((r = sys_page_map(0, PFTEMP, 0, ROUNDDOWN(addr, PGSIZE), PTE_P | PTE_U | PTE_W)) < 0) {
		panic("sys_page_map: %e", r);
	}
	if ((r = sys_page_unmap(0, PFTEMP)) < 0) {
		panic("sys_page_unmap: %e", r);
	}
}

之后，通过系统调用sys_exofork()创建一个新进程，由于子进程的状态为ENV_RUNNBALE，故此时不会被CPU调度。父进程修改子进程的页表，将UTOP以下的所有可写和COW页面在子进程中标记为COW，然后将其在父进程中的页表项也改为COW。

1
2
3
4
5


	for (addr = 0; addr < USTACKTOP; addr += PGSIZE) {
		if ((uvpd[PDX(addr)] & PTE_P) == PTE_P && (uvpt[PGNUM(addr)] & PTE_P) == PTE_P) {
			duppage(envid, PGNUM(addr));	
		}
	}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


static int duppage(envid_t envid, unsigned pn)
{
	int r;
	void *addr = (void *)(pn * PGSIZE);
	if ((uvpt[pn] & PTE_W) == PTE_W || (uvpt[pn] & PTE_COW) == PTE_COW) {
		if ((r = sys_page_map(0, addr, envid, addr, PTE_COW | PTE_P | PTE_U)) < 0) {
			panic("duppage panic: sys_page_map: %e!\n", r);
		}
		if ((r = sys_page_map(0, addr, 0, addr, PTE_COW | PTE_P | PTE_U)) < 0) {
			panic("duppage panic: sys_page_map: %e!\n", r);
		}
	} else {
		if ((r = sys_page_map(0, addr, envid, addr, PTE_U | PTE_P)) < 0) {
			panic("duppage panic: sys_page_map: %e!\n", r);
		}
	}
	return 0;
}

之后父进程为子进程的异常栈分配空间，同时为子进程注册缺页异常处理函数pgfault()。最后修改子进程状态使其可以被调度。子进程恢复后将从fork()函数的返回处开始执行并得到返回值0，父进程得到子进程的envid作为fork()的返回值。

我们再来梳理一遍一次fork()调用的执行流程：

对于父进程而言：
- 注册缺页处理函数pgfault() 。
- “调用”sys_exofork()（已确保被内联为fork()中的一条汇编指令），在该系统调用中创建子进程，且将此时的strcut Trapframe复制给子进程(其中%eip指向sys_exofork()对应的那条汇编指令)，并修改该struct Trapframe中的%eax(系统调用的返回值寄存器)的值为0。
- 根据自己的页表项初始化子进程的页表项。
- 为子进程分配异常处理栈并注册缺页处理函数pgfault()。
- 修改子进程的状态为ENV_RUNNABLE。
- 返回子进程的envid。
对于子进程而言：
- 当其第一次被某个CPU调度时，env_run()函数首先安装切换到子进程的内存空间，然后通过env_pop_tf()根据其struct Trapframe初始化各个寄存器状态。此时%eip指向sys_exofork()对应的那条汇编指令，于是子进程发现自己在这个系统调用的返回处“醒来”。
- 由于父进程将其系统调用返回寄存器%eax置为0，故其得到sys_exofork()的返回值为0。
- 将thisenv设置为当前进程所对应的struct Env。

这里我们清楚地看到了用户进程的fork()如何实现“调用一次，返回两次”的效果。

Part C: Preemptive Multitasking and IPC

在这个部分我们将实现抢占式调度与进程间通信。

时钟中断

为了防止某个无限循环无限占用CPU资源，CPU需要能够相应外部的时钟中断，在运行超过一定时间收到时钟中断时主动调用sched_yield()从而让出CPU。和处理其他中断一样，我们首先需要在kern/trapentry.S和kern/trap.c中初始化相关信息。

1
2
3
4
5
6


TRAPHANDLER_NOEC(handler32, IRQ_OFFSET + IRQ_TIMER)
TRAPHANDLER_NOEC(handler33, IRQ_OFFSET + IRQ_KBD)
TRAPHANDLER_NOEC(handler36, IRQ_OFFSET + IRQ_SERIAL)
TRAPHANDLER_NOEC(handler39, IRQ_OFFSET + IRQ_SPURIOUS)
TRAPHANDLER_NOEC(handler46, IRQ_OFFSET + IRQ_IDE)
TRAPHANDLER_NOEC(handler51, IRQ_OFFSET + IRQ_ERROR)

1
2
3
4
5
6


	SETGATE(idt[32], 0, GD_KT, handler32, 0);
	SETGATE(idt[33], 0, GD_KT, handler33, 0);
	SETGATE(idt[36], 0, GD_KT, handler36, 0);
	SETGATE(idt[39], 0, GD_KT, handler39, 0);
	SETGATE(idt[46], 0, GD_KT, handler46, 0);
	SETGATE(idt[51], 0, GD_KT, handler51, 0);

之后在trap.c:trap_dispatch()中处理时钟中断

1
2
3
4
5


		case IRQ_OFFSET + IRQ_TIMER: {
			lapic_eoi();
			sched_yield();
			return ;
		}

IPC

JOS中用户进程可以通过IPC传递的信息包括一个32位的值和一个可选的页映射。用户进程通过ipc_send()发送数据，通过ipc_recv()接收数据。发送方可以向任意进程发送数据，发送数据时会阻塞直到接收方接收。接收数据时也将阻塞直到有其他进程发送数据。

首先实现内核中的函数

kern/syscall.c:sys_ipc_try_send(): 我们只需要简单地进行相关的检查，然后将数据传递到接收方的struct Env当中。

 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
37
38
39


static int sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
	struct Env *env;
	int r;
	pte_t *pte;
	struct PageInfo *pp;
	if ((r = envid2env(envid, &env, 0)) < 0) {
		cprintf("envid: %u\n", (uint32_t)envid);
		return -E_BAD_ENV;
	}
	if (!env->env_ipc_recving) {
		return -E_IPC_NOT_RECV;
	}
	if ((uintptr_t)srcva < UTOP) {
		if (PGOFF(srcva) != 0) {
			return -E_INVAL;
		}
		if ((perm & (PTE_U | PTE_P)) != (PTE_U | PTE_P) || (perm & ~(PTE_SYSCALL)) != 0) {
			return -E_INVAL;
		}
		if (!(pp = page_lookup(curenv->env_pgdir, srcva, &pte))) {
			return -E_INVAL;
		}
		if ((perm & PTE_W) == PTE_W && (*pte & PTE_W) == 0) {
			return -E_INVAL;
		}
		if ((r = page_insert(env->env_pgdir, pp, env->env_ipc_dstva, perm)) < 0) {
			return -E_NO_MEM;
		}
		env->env_ipc_perm = perm;
	} else {
		env->env_ipc_perm = 0;
	}
	env->env_ipc_recving = 0;
	env->env_ipc_from = curenv->env_id;
	env->env_ipc_value = value;
	env->env_status = ENV_RUNNABLE;
	return 0;
}

kern/syscall.c:sys_ipc_recv() : 接收方的操作同样很简单，只需要改变状态然后将自身挂起即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


static int sys_ipc_recv(void *dstva)
{
	if ((uint32_t)dstva < UTOP && PGOFF(dstva) != 0) {
        return -E_INVAL;
    }
    curenv->env_ipc_recving = 1;
    curenv->env_ipc_dstva = dstva;
    curenv->env_status = ENV_NOT_RUNNABLE;
	return 0;
}

然后是两他们包装为供用户进程调用的库函数。lib/ipc.c: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


int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
	int r;
	void *dstva = pg == NULL ? (void *)UTOP : pg;
	if((r = sys_ipc_recv(dstva)) < 0) {
		if (from_env_store) {
			*from_env_store = 0;
		}
		if (perm_store) {
			*perm_store = 0;
		}
		return r;
	}
	if (from_env_store) {
		*from_env_store = thisenv->env_ipc_from;
	}
	if (perm_store) {
		*perm_store = thisenv->env_ipc_perm;
	}
	return thisenv->env_ipc_value;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
	int r;
	void *srcva = pg == NULL ? (void *)UTOP : pg;
	while ((r = sys_ipc_try_send(to_env, val, srcva, perm)) < 0) {
		if (r != -E_IPC_NOT_RECV) {
			panic("ipc_send panic: %e!", r);
		}
		sys_yield();
	}
}

MIT6.828-2018 Lab 4 Preemptive Multitasking

文章目录

Lab 4: Preemptive Multitasking

Part A: Multiprocessor Support and Cooperative Multitasking

多处理器支持

应用处理器的启动

Per-CPU State and Initialization

创建进程的系统调用

Part B: Copy-on-Write Fork

用户态缺页中断处理函数的设置

用户态的异常处理栈

Trap-time状态的恢复

实现`copy-on-write fork()`

Part C: Preemptive Multitasking and IPC

时钟中断

IPC

文章目录

Lab 4: Preemptive Multitasking

Part A: Multiprocessor Support and Cooperative Multitasking

多处理器支持

应用处理器的启动

Per-CPU State and Initialization

创建进程的系统调用

Part B: Copy-on-Write Fork

用户态缺页中断处理函数的设置

用户态的异常处理栈

Trap-time状态的恢复

实现copy-on-write fork()

Part C: Preemptive Multitasking and IPC

时钟中断

IPC

实现`copy-on-write fork()`