mit6.828笔记 - lab4 Part C:抢占式多任务和进程间通信(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_initpic_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 0\n");
		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_recvsys_ipc_try_send

然后我们将实现两个库包装器 ipc_recvipc_send 。(话说,我们已经见识过了这种包装器,比如 set_pgfault_handlersys_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:%e\n", r);
		}
	}
}

lab4 完成

热门相关:无敌剑神   无双剑尊   母亲的情人2   爱定了,皇妃娘娘也挡不住   路边摊