mit6.828笔记 – lab4 Part C:抢占式多任务和进程间通信（IPC）

摘要

lab4到目前为止，我们能够启动多个CPU，让多个CPU同时处理多个进程。实现了中断处理，并且实现了用户级页面故障机制以及写时复制fork。
但是，我们的进程调度不是抢占式的，现在每个进程只有在发生中断的时候，才会被调度（调用shed_yeild），这样就有可能会有进程一直占用CPU不放。我们希望能够让各个进程平分CPU，在各个时间片上处理自己的任务。
于是实验室 4 的最后一部分，我们的任务就是修改内核，实现抢占式多进程调度，并实现进程间通信机制（IPC）。

Part C：抢占式多任务和进程间通信（IPC

lab4到目前为止，我们能够启动多个CPU，让多个CPU同时处理多个进程。实现了中断处理，并且实现了用户级页面故障机制以及写时复制fork。
但是，我们的进程调度不是抢占式的，现在每个进程只有在发生中断的时候，才会被调度（调用shed_yeild），这样就有可能会有进程一直占用CPU不放。我们希望能够让各个进程平分CPU，在各个时间片上处理自己的任务。
于是实验室 4 的最后一部分，我们的任务就是修改内核，实现抢占式多进程调度，并实现进程间通信机制（IPC）。

1. 时钟中断和抢占

我们为什么需要抢占式的进程调度？如果有进程一直占用CPU会是什么情况，user/spin.c就是个例子。看看 user/spin.c

尝试在命令行跑 make run-spin 会发现，父进程fork之后再也无法执行了。这是因为我们的内核目前还没有从未完成的进程中抢回控制的能力。

那时钟中断去哪了呢？

手册：
与 xv6 Unix 相比，我们在 JOS 中做了一个关键的简化。在内核中，外部设备中断始终处于禁用状态（与 xv6 一样，在用户空间中处于启用状态）。外部中断由 %eflags 寄存器（参见 inc/mmu.h）的 FL_IF 标志位控制。该位被设置时，外部中断被启用。 虽然可以通过多种方式修改该位，但为了简化操作，我们将仅通过在进入和离开用户模式时保存和恢复 %eflags 寄存器的过程来处理它。

您必须确保在用户环境中运行时设置 FL_IF 标志，以便在中断发生时将其传递给处理器，并由您的中断代码进行处理。 否则，中断将被屏蔽或忽略，直到中断被重新启用。我们在启动加载程序的第一条指令中就屏蔽了中断，到目前为止，我们还从未重新启用过中断。

我们在启动加载程序的第一条指令中就屏蔽了中断，到目前为止，我们还从未重新启用过中断。
接下来的任务，我们要完善外部中断的管理，

---

1.1 中断管理

外部中断（即设备中断）称为 IRQ。有 16 个可能的 IRQ，编号从 0 到 15。从 IRQ 编号到 IDT 条目之间的映射关系并不固定。picirq.c 中的 pic_init 将 IRQ 0-15 映射到 IDT 条目 IRQ_OFFSET 至 IRQ_OFFSET+15。

在 inc/trap.h 中，IRQ_OFFSET 被定义为十进制 32。因此，IDT 项 32-47 对应 IRQ 0-15。例如，时钟中断是 IRQ 0，因此 IDT[IRQ_OFFSET+0]（即 IDT[32]）包含内核中时钟中断处理程序例程的地址。选择这个 IRQ_OFFSET，是为了避免设备中断与处理器异常重叠，以免造成混淆。(事实上，在早期运行 MS-DOS 的 PC 中，IRQ_OFFSET 实际上为 0，这确实造成了处理硬件中断和处理处理器异常之间的大量混淆！）。

与 xv6 Unix 相比，我们在 JOS 中做了一个关键的简化。在内核中，外部设备中断始终处于禁用状态（与 xv6 一样，在用户空间中处于启用状态）。外部中断由 %eflags 寄存器（参见 inc/mmu.h）的 FL_IF 标志位控制。该位被设置时，外部中断被启用。 虽然可以通过多种方式修改该位，但为了简化操作，我们将仅通过在进入和离开用户模式时保存和恢复 %eflags 寄存器的过程来处理它。

您必须确保在用户环境中运行时设置 FL_IF 标志，以便在中断发生时将其传递给处理器，并由您的中断代码进行处理。 否则，中断将被屏蔽或忽略，直到中断被重新启用。我们在启动加载程序的第一条指令中就屏蔽了中断，到目前为止，我们还从未重新启用过中断。

Exercise 13

练习 13. 修改 kern/trapentry.S 和 kern/trap.c，初始化 IDT 中的相应条目，并为 IRQ 0 至 15 提供处理程序。然后修改 kern/env.c 中 env_alloc() 的代码，以确保用户环境始终在启用中断的情况下运行。  同时取消对 sched_halt() 中 sti 指令的注释，以便空闲的 CPU 能解除中断屏蔽。  在调用硬件中断处理程序时，处理器绝不会推送错误代码。此时，您可能需要重新阅读《80386 参考手册》第 9.2 节或《IA-32 英特尔体系结构软件开发人员手册》第 3 卷第 5.8 节。  完成此练习后，如果使用任何运行时间较长（如自旋）的测试程序运行内核，就会看到内核打印硬件中断的陷阱帧。虽然中断已在处理器中启用，但 JOS 还没有处理它们，所以你会看到它将每个中断错误地归属于当前运行的用户环境，并将其销毁。最终，它应该会用完要销毁的环境，并将其放入监视器中。 

在 trapentry.S 设置外部中断处理函数的入口点：

# 外部中断的入口点 	TRAPHANDLER_NOEC(irq_error_handler, IRQ_OFFSET+IRQ_ERROR) 	TRAPHANDLER_NOEC(irq_ide_handler, IRQ_OFFSET+IRQ_IDE) 	TRAPHANDLER_NOEC(irq_kbd_handler, IRQ_OFFSET+IRQ_KBD) 	TRAPHANDLER_NOEC(irq_serial_handler, IRQ_OFFSET+IRQ_SERIAL) 	TRAPHANDLER_NOEC(irq_spurious_handler, IRQ_OFFSET+IRQ_SPURIOUS) 	TRAPHANDLER_NOEC(irq_timer_handler, IRQ_OFFSET+IRQ_TIMER) 

在 trap.c:trap_init() 中定义外部设备中断的handler

	//初始化外部中断的中断向量 	void irq_error_handler(); 	void irq_kbd_handler(); 	void irq_ide_handler(); 	void irq_timer_handler(); 	void irq_spurious_handler(); 	void irq_serial_handler();  	SETGATE(idt[IRQ_OFFSET + IRQ_ERROR], 0, GD_KT, irq_error_handler, 3); 	SETGATE(idt[IRQ_OFFSET + IRQ_IDE], 0, GD_KT, irq_ide_handler, 3); 	SETGATE(idt[IRQ_OFFSET + IRQ_KBD], 0, GD_KT, irq_kbd_handler, 3); 	SETGATE(idt[IRQ_OFFSET + IRQ_SERIAL], 0, GD_KT, irq_serial_handler, 3); 	SETGATE(idt[IRQ_OFFSET + IRQ_SPURIOUS], 0, GD_KT, irq_spurious_handler, 3); 	SETGATE(idt[IRQ_OFFSET + IRQ_TIMER], 0, GD_KT, irq_timer_handler, 3); 

修改 env.c:env_alloc，在用户环境运行前开启外部设备中断，在注释提示处添加语句：

// Enable interrupts while in user mode. 	// LAB 4: Your code here. 	// 开启用户环境的外部设备中断 	e->env_tf.tf_eflags |= FL_IF; 

修改 kern/sched.c:sched_halt，将提示处的sti语句注释取消掉，sti 指令是开中断，如手册中所述，我们在 bootloader 中第一条指令 cli 就屏蔽了外部中断，到目前为止还没有重新开启外部中断。
sched_halt 这个让CPU陷入自旋，等待被timer打断。不开外部中断是不可能做到被抢断的。

完成了这些我们再次尝试 make run-spin

---

1.2 处理时钟中断

在 user/spin 程序中，子环境首次运行后，只是在循环中 spin，内核再也无法控制。
我们需要对硬件进行编程，使其周期性地产生时钟中断，从而迫使控制权回到内核，在内核中我们可以将控制权切换到不同的用户环境。

lapic_init 和 pic_init中设置了时钟和中断控制器以产生中断。现在我们需要编写代码来处理这些中断。

Exercise 14

练习 14. 修改内核的 `trap_dispatch()` 函数，使其在发生时钟中断时调用 `sched_yield()`，查找并运行不同的环境。  现在您应该可以让用户/自旋测试正常工作了：父环境应该分叉子环境，向其执行几次 `sys_yield()`，但每次都会在一个时间片后重新获得 CPU 的控制权，最后杀死子环境并优雅地终止。 

目前我们已经在中断向量表中添加了接受timer信号的中断描述符，timer中断发生后，控制流会来到trap，然后发往 trap_dispatch，但是 trap_dispatch 中还没有对应的hander接应，所以现在要在 trap_dispatch 中处理timer的中断信号。

	// Handle clock interrupts. Don't forget to acknowledge the 	// interrupt using lapic_eoi() before calling the scheduler! 	// LAB 4: Your code here. 	if(tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) 	{ 		cprintf("Timer interrupt on irq 0n"); 		lapic_eoi(); 		sched_yield(); 	}  

lapic_eoi() 函数的作用是开启IF标志位，接收外部中断，具体原理：

在接收到中断请求并处理完成后，向本地高级可编程中断控制器（Local Advanced Programmable Interrupt Controller, LAPIC）发送一个 EOI 命令，通知 LAPIC 中断处理已完成。这是为了释放中断控制器的资源，以便处理下一个中断。

但是好奇怪，进入trapentry.S 时候，从来没见过我们主动清零IF啊，为什么CPU自动关闭接收外部中断了呢？
翻了一下386手册，其中提到

中断门和陷阱门的区别在于对 IF（中断启用标志）的影响。矢量通过中断门的中断会重置 IF，从而防止其他中断干扰当前中断处理程序。随后的 IRET 指令将 IF 恢复为堆栈上 EFLAGS 映像中的值。通过陷阱门的中断不会改变 IF。

功能上的区别是这样，那格式上呢？

我们在trap_init 设置的全是中断门

这个时候我们再次尝试 make run-spin ，会发现程序可以正常执行了：

---

2. 进程间通信（IPC）

我们一直在关注操作系统的隔离功能，即它能让人产生一种错觉，以为每个程序都拥有一台独享的机器。操作系统的另一项重要功能是允许程序在需要时相互通信。让程序与其他程序进行交互是一项非常强大的功能。Unix 管道模型就是一个典型的例子。

进程间通信有许多模型。时至今日，人们仍在争论哪种模式最好。我们不讨论这个问题。相反，我们将实现一个简单的 IPC 机制，然后进行尝试。

2.1 JOS 的进程间通信

JOS已经实现了几个额外的JOS内核系统调用，它们共同提供了一个简单的进程间通信机制。
用户需要实现两个系统调用， sys_ipc_recv 和 sys_ipc_try_send 。

然后我们将实现两个库包装器 ipc_recv 和 ipc_send 。（话说，我们已经见识过了这种包装器，比如 set_pgfault_handler 是 sys_env_set_pgfault_upcall 的包装器，在其包装下，为我们简化了用户异常栈的清理和 trap-time 状态的恢复工作）

用户环境可以使用JOS的IPC机制相互发送的“消息”由两个部分组成:单个32位值和可选的单个页映射。允许进程以消息的形式传递页映射，这提供了一种高效的方式来传输比单个32位整数所能容纳的更多的数据，还允许进程轻松地建立共享内存。

2.2 发送和接收消息

为接收消息，进程调用 sys_ipc_recv 。该系统调用会挂起当前进程，直到收到消息后才再次运行。
当一个进程等待接收消息时，任何其他进程都可以向它发送消息——不仅仅是特定的进程，也不仅仅是与接收进程有父/子关系的进程。
换句话说，我们在 Part A 实现的权限检查不适用于IPC，因为IPC系统调用经过了精心设计，是“安全的”:一个进程不会仅仅通过向它发送消息就导致另一个进程故障(除非目标进程也有bug)。

要尝试发送一个值，进程会调用 sys_ipc_try_send，指定接受者的进程ID和要发送的值。
如果目标进程上正在接收（它调用了 sys_ipc_recv，但还没有得到值），那么调用者这边的 send 就会发送信息，并返回 0。否则，send 返回 -E_IPC_NOT_RECV 表示目标进程当前不希望收到值。

用户空间中的库函数 ipc_recv 负责调用 sys_ipc_recv，然后在当前环境的 struct Env 中查找接收到的值的信息。

类似地，库函数 ipc_send 将负责重复调用 sys_ipc_try_send ，直到发送成功。

2.3 发送内存页

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

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

如果发送方或接收方都没有表示应该传输页面，那么就不会传输页面。在任何 IPC 之后，内核都会将接收方 Env 结构中的新字段 env_ipc_perm 设置为所接收页面的权限，如果没有接收页面，则设置为 0。

Exercise 15 实现IPC

练习 15. 执行 `kern/syscall.c` 中的 `sys_ipc_recv` 和 `sys_ipc_try_send`。 在执行之前，请阅读有关这两个例程的注释，因为它们必须协同工作。 在这些例程中调用 `envid2env` 时，应将 `checkperm` 标志设置为 0，这意味着任何环境都可以向任何其他环境发送 IPC 消息，内核除了验证目标 `envid` 是否有效外，不会进行任何特殊的权限检查。  然后在 `lib/ipc.c` 中实现 `ipc_recv` 和 `ipc_send` 函数。  使用 `user/pingpong` 和 `user/primes` 函数测试你的 IPC 机制。`user/primes` 会为每个质数生成一个新环境，直到 JOS 用完环境为止。阅读 user/primes.c，了解所有分叉和 IPC 的幕后工作，你可能会觉得很有趣。 

在 kern/syscall.c 中实现 sys_ipc_try_send 。
按照注释进行一系列检查后将 srcva 所在的 pg ，映射到 dstva 所在的地址。

// 尝试将 “value ”发送到目标环境 “envid”。 // 如果 srcva < UTOP，则同时发送当前映射到 “srcva ”的页面，以便接收者获得同一页面的重复映射。 // 如果目标没有被阻塞，正在等待 IPC，则发送失败，返回值为 -E_IPC_NOT_RECV。 // 发送失败的原因还包括下面列出的其他原因。 // 否则，发送成功，目标的 ipc 字段更新如下： // env_ipc_recving 设置为 0 以阻止今后的发送； // env_ipc_from 设置为发送的 envid； // env_ipc_value 设置为参数 “value”； // 如果传输了页面，env_ipc_perm 设置为 “perm”，否则为 0。 // 目标环境再次被标记为可运行，返回 0。 // 从暂停的 sys_ipc_recv 系统调用中返回 0。 (提示：如果 // sys_ipc_recv 函数真的会返回吗？） // // 如果发送方想发送页面，但接收方没有要求发送，则不会传输页面映射，但也不会发生错误。 // 只有在没有错误发生时，ipc 才会发生。 // // 成功时返回 0，错误时返回 <0。 // 错误是 // -E_BAD_ENV 如果环境 envid 当前不存在。 // （无需检查权限。） // -E_IPC_NOT_RECV 如果 envid 当前未在 sys_IPC_recv 中阻塞、 // 或其他环境先发送。 // -E_INVAL 如果 srcva < UTOP 但 srcva 不是页面对齐的。 // -E_INVAL 如果 srcva < UTOP 并且 perm 不合适 // （参见 sys_page_alloc）。 // -E_INVAL 如果 srcva < UTOP 但 srcva 没有映射到调用者的 // 地址空间。 // 地址空间。 // -E_INVAL 如果（perm & PTE_W），但 srcva 在 // 当前环境的地址空间中是只读的。 // 当前环境的地址空间中是只读的。 // -E_NO_MEM 如果没有足够的内存将 srcva 映射到 envid 的 // 地址空间。 // 地址空间。 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"); 	int r; 	struct Env * env; 	if((r = envid2env(envid, &env, 0))< 0){ 		return -E_BAD_ENV; 	}  	if(env->env_ipc_recving == 0){ 		return -E_IPC_NOT_RECV; 	}  	if (srcva < (void*)UTOP) { 		// 获取物理页 		pte_t *pte; 		struct PageInfo *pg = page_lookup(curenv->env_pgdir, srcva, &pte);  		// 检查 srcva 是否 page-aligned. 		if(srcva != ROUNDDOWN(srcva, PGSIZE)){ 			return -E_INVAL; 		} 		// 检查 perm 是否合规 		if((*pte & perm & PTE_SYSCALL)!= (perm & PTE_SYSCALL)){ 			return -E_INVAL; 		} 	  		// 如果来源环境没有映射pg页 		if(!pg){ 			return -E_INVAL; 		} 		// 如果perm要求写权限，但是srcva没有写权限 		if ((perm & PTE_W) && !(*pte & PTE_W)){ 			return -E_INVAL; 		} 		// 如果目标环境以有效dstva参数调用 sys_ipc_recv，说明目标环境愿意接受页面映射 		if (env->env_ipc_dstva < (void*)UTOP) { 			// 将当前环境的 pg 页 映射到目标环境的dstva上 			r = page_insert(env->env_pgdir, pg, env->env_ipc_dstva, perm); 			if(r<0){ 				return -E_NO_MEM; 			} 			env->env_ipc_perm = perm; 		} 	} 	// 标记目标环境为 未准备接收 	env->env_ipc_recving = 0; 	// 将目标环境的 IPC发送方 设置为当前环境 	env->env_ipc_from = curenv->env_id; 	// 发送 message 的 value 	env->env_ipc_value = value;  	// 设置目标环境为可运行 	env->env_status = ENV_RUNNABLE; 	// 设置目标环境的eax 	env->env_tf.tf_regs.reg_eax = 0; 	return 0; } 

sys_ipc_recv 则是设置env的与IPC相关的成员，关键是env_ipc_recving=1，标记为准备接受数据。
然后调用 sched_yield 交出cpu，等待sender发送数据

// 阻塞，直到值准备就绪。  // 使用 struct Env 的 env_ipc_recving 和 env_ipc_dstva 字段记录要接收的信息， // 标记自己不可运行，然后放弃 CPU。 // // 如果'dstva'<UTOP，则表示愿意接收一页数据。 // 'dstva'是虚拟地址，发送的页面应映射到该地址。 // // 该函数仅在出错时返回，但系统调用最终会在成功时返回 0。 // 出错时返回 <0。 错误包括 // -E_INVAL 如果 dstva < UTOP 但 dstva 不是页面对齐的。 static int sys_ipc_recv(void *dstva) { 	// LAB 4: Your code here. 	// panic("sys_ipc_recv not implemented"); 	if ((uintptr_t)dstva < UTOP && PGOFF(dstva) != 0){ 		return -E_INVAL; 	} 	// 标识正在等待接收消息 	curenv->env_ipc_recving = 1; 	// 记录想要映射页的虚拟地址 	curenv->env_ipc_dstva = dstva; 	// 清空记录的发送者信息 	curenv->env_ipc_value = 0; 	curenv->env_ipc_from = 0; 	curenv->env_ipc_perm = 0;  	// 设置 Env 状态，在env_ipc_recving被改变之前，不再被唤醒 	curenv->env_status = ENV_NOT_RUNNABLE;  	// 交出控制权，等待数据输入 	sched_yield(); 	 	return 0; } 

然后不要忘了在 syscall 的 switch 中加上相关调用的分支：

		case SYS_ipc_try_send: 			ret = sys_ipc_try_send((envid_t) a1, (uint32_t) a2, (void *) a3, (unsigned int) a4); 			return ret; 		case SYS_ipc_recv: 			ret = sys_ipc_recv((void*)(a1)); 			return ret; 

接着去用户的lib/ipc.c 中实现相应库函数。

 // 通过 IPC 接收并返回值。 // 如果 “pg ”为非空，则发送方发送的任何页面都将映射到该地址。 // 如果 “from_env_store ”为非空，则将 IPC 发送方的 envid 保存在 *from_env_store 中。 // 如果 “perm_store ”为非空，则在 *perm_store 中存储 IPC 发送方的页面权限（如果页面已成功传输到 “pg”，则该值为非零）。 // 如果系统调用失败，则在 *fromenv 和 *perm（如果它们非空）中存储 0，并返回错误信息。 // 否则，返回发送者发送的值 // // 提示 // 使用 “thisenv ”发现值和发送者。 // 如果'pg'为空，则向 sys_ipc_recv 传递一个它可以理解为 “无页面 ”的值。 // 表示 “无页面”。 (零不是正确的值，因为这是 // 一个完全有效的页面映射位置）。 int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store) { 	// LAB 4: Your code here. 	// panic("ipc_recv not implemented"); 	// 检查pg是否为空 	if(pg == NULL) 	{ 		pg=(void *) -1; 	} 	//接收 message 	int r = sys_ipc_recv(pg); 	if(r<0) 	{ 		if(from_env_store) *from_env_store = 0; 		if(perm_store) *perm_store = 0; 		return r; 	} 	// 保存发送者的envid 	if(from_env_store) *from_env_store = thisenv->env_ipc_from; 	// 保存发送来的页面的权限 	if(perm_store) *perm_store = thisenv->env_ipc_perm; 	// 返回message的value 	return thisenv->env_ipc_value; }  // 将'val'（如果'pg'非空，则将'pg'与'perm'一起）发送到'toenv'。 // 该函数会不断尝试，直到成功为止。 // 如果出现除 -E_IPC_NOT_RECV 以外的任何错误，它都会 panic()。 // // 提示 // 使用 sys_yield()对 CPU 更友好。 // 如果 “pg ”为空，则向 sys_ipc_try_send 传递一个它能理解为 “无页面 ”的值。 // 表示 “无页面”。 (零值并不合适）。 void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm) { 	// LAB 4: Your code here. 	// panic("ipc_send not implemented"); 	// 如果pg为NULL， 要提供给sys_ipc_try_send一个能表达“no page”的值，0是有效的地址 	if(pg==NULL) 	{ 		pg = (void *)-1; 	} 	int r; 	//不停尝试发送消息直到成功 	while(1) 	{ 		r = sys_ipc_try_send(to_env, val, pg, perm); 		if (r == 0) {		//发送成功 			return; 		} else if (r == -E_IPC_NOT_RECV) {	//接收环境未准备接收 			sys_yield(); 		}else{ 			panic("ipc_send() fault:%en", r); 		} 	} } 

lab4 完成