BUAA-OS

「BUAA OS Lab4-1-Extra」IPC实现阻塞机制避免发送方轮询

Posted by saltyfishyjk on 2022-05-23
Words 1.6k and Reading Time 6 Minutes
Viewed Times

「BUAA OS Lab4-1-Extra」IPC实现阻塞机制避免发送方轮询

Part 0 前言

本篇博客记录Lab4-1-ExtraIPC实现阻塞机制避免发送方轮询的实现，Part 1为思路分析，Part 2为代码实现（经过重测已通过），Part 3 踩过的坑，读者可自取所需。

由于本次为线上上机，题目已经开源，不再在文中另附；如有需要者，可以联系yjk_official@foxmail.com获取。

Part 1 思路分析

本次题目加深了我对IPC和系统调用的理解，以下结合题目展开讲讲。

IPC与系统调用

首先需要明确，IPC是一种特殊的系统调用，遵循一般系统调用的规律。这里我们以writef为例重温系统调用的一般流程：

  1. 调用writef这一用户函数
  2. writef中调用了用户空间的syscall_*的用户空间函数（在user/lib.h中声明，在user/syscall_lib.c中实现）
  3. syscall_*函数调用了msyscall函数，进入内核态
  4. 内核态中将异常分发到handle_sys函数，将系统调用所需要的信息传递到内核
  5. 内核获取信息，执行对应的内核空间的系统调用函数sys_*
  6. 从系统调用函数返回，回到用户程序writef调用处

对照上述writef的执行流程，下面介绍IPC流程：

IPC的接收方流程可以概括如下：

  1. 调用user/ipc.c/ipc_recv这一用户函数
  2. ipc_send中调用了用户空间中的user/syscall_lib.c/syscall_ipc_recv
  3. syscall_ipc_can_send调用了user/syscall_wrap.S/msyscall函数，进入内核态
  4. 内核将异常进行分发到syscall.S/handle_sys函数（事实上，msyscall中调用了syscall，Lab3中介绍过，syscall会调用.text.exc_vec3代码段的代码进行异常分发，最终调用handle_sys函数）
  5. 内核获取信息，执行对应的内核空间的系统调用函数syscall_all.c/sys_ipc_recv
  6. 从系统调用函数返回

IPC的发送方流程可以概括如下：

  1. 调用user/ipc.c/ipc_send这一用户函数
  2. ipc_send中调用了用户空间中的user/syscall_lib.c/syscall_ipc_can_send
  3. syscall_ipc_can_send调用了user/syscall_wrap.S/msyscall函数，进入内核态
  4. 内核将异常进行分发到syscall.S/handle_sys函数
  5. 内核获取信息，执行对应的内核空间的系统调用函数syscall_all.c/sys_ipc_can_send
  6. 从系统调用函数返回

我们着重梳理了IPC过程，可以发现，我们的核心部分在于第五步，具体的系统调用实现函数sys_*，这也是这次Extra的重点。

多进程

首先需要重点再强调的是，我们实现的是多进程操作系统。

多进程在IPC问题中的表现为，我们不确定发送方和接收方调用sys_ipc_can_send和sys_ipc_recv的相对先后顺序。因此，我们在sys_*函数中，需要考虑调用本函数时可能存在的情况，以下具体分析。

接收进程

  • 发送进程已经准备好了，目前在接收进程的等待队列中
  • 接收进程的等待队列为空，说明发送进程还没有准备好（事实上，是发送进程还没运行到sys_ipc_can_send函数）

发送进程

  • 接收进程已经准备好了
  • 接收进程没有准备好，将这次发送的相关信息存到接收进程的等待队列

数据结构

上述分析中，当发送进程准备好而接收进程没有准备好的时候，我们将“相应信息”储存到接收进程对应的队列中。为了储存“相应信息”，我们构造如下数据结构：

1
2
3
4
5
6
7
struct wait2sendList {
	u_int from_env_id;
	u_int to_env_id;
	u_int value;
	u_int srcva;
	u_int perm;
};

这五项数据就已足够

Part 2 代码实现

sys_ipc_recv

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
void sys_ipc_recv(int sysno, u_int dstva)
{
	if (dstva > UTOP) {
		return ;
	}
    /* 如果已经有准备好的发送进程
     * 每次处理一个发送请求 
     */
	u_int envx = ENVX(curenv->env_id);
	if (ptLeft[envx] != ptRight[envx]) {
		struct Env *eFrom;
		int pt = ptLeft[envx];
		int r = envid2env(sendList[envx][pt].from_env_id, &eFrom, 0);
		if (r) return r;
		u_int value = sendList[envx][pt].value;
		u_int srcva = sendList[envx][pt].srcva;
		u_int perm = sendList[envx][pt].perm;
		curenv->env_ipc_dstva = dstva;
		send(curenv, eFrom, value, srcva, perm);
		//printf("RECV from %x to %x \n", eFrom->env_id, curenv->env_id);
		ptLeft[envx] += 1;
		eFrom->env_status = ENV_RUNNABLE;
		curenv->env_ipc_recving = 0;
		return;
	}
    /* 如果发送进程没有准备好 
     * 设置自己的状态
     * 以供届时发送进程查询自己状态
     * 使得届时发送进程可以直接发送消息 
     */
	curenv->env_ipc_recving = 1;
	curenv->env_ipc_dstva = dstva;
	curenv->env_status = ENV_NOT_RUNNABLE;
	sys_yield();
}

sys_ipc_can_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
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
int sys_ipc_can_send(int sysno, u_int envid, u_int value, u_int srcva,
					 u_int perm)
{

	int r;
	struct Env *e;
	struct Page *p;
	
	if (!(srcva < UTOP)) {
		return -E_INVAL;
	}
	r = envid2env(envid, &e, 0);
	if (r != 0) {
		return r;
	}
	/*if (e->env_ipc_recving != 1) {
		return -E_IPC_NOT_RECV;
	}*/
    /* 如果接收进程没有准备好
     * 将自己相应信息储存在数据结构中
     * 并将其储存在对应接收进程队列中
     */
	/* alter in lab4-1-Extra */
	if (e->env_ipc_recving != 1) {
		curenv->env_status = ENV_NOT_RUNNABLE;
		u_int envx = ENVX(e->env_id);
		//sendList[envx][ptRight[envx]] = {curenv->env_id. e->env_id, value, srcva, perm};
		int ct = ptRight[envx];
		sendList[envx][ct].from_env_id = curenv->env_id;
		sendList[envx][ct].to_env_id = e->env_id;
		sendList[envx][ct].value = value;
		sendList[envx][ct].srcva = srcva;
		sendList[envx][ct].perm = perm;
		ptRight[envx] += 1;
		//e->env_status = ENV_RUNNABLE;
		sys_yield();
		return 0;
	}
	/* alter in lab4-1-Extra finished */
	
	/* 如果接收进程已经准备就绪
     * 按照Lab4课下讲解直接发送即可
     */
	e->env_ipc_recving = 0;
	e->env_ipc_from = curenv->env_id; // TODO doubt : why not envid alone
	e->env_ipc_value = value;
	if (srcva != 0) {
		/* flags that need to pass a page */
		p = page_lookup(curenv->env_pgdir, srcva, NULL);
		if (p == NULL || 
				!(e->env_ipc_dstva < UTOP)) {
			return -1;
		}
		r = page_insert(e->env_pgdir, p, e->env_ipc_dstva, perm);
		if (r != 0) {
			return r;
		}
	}
	e->env_ipc_perm = perm;
	e->env_status = ENV_RUNNABLE;
	
	return 0;
}

Part 3 踩过的坑

课下bug

本次Extra在上机时间没有做出来，其中一个原因就是课下有bug：

page_look_up中pgdir参数

在syscall_all.c/sys_ipc_can_send中调用page_look_up和page_insert时，第一个参数本应为e->env_pgdir，课下误写为其他内容。

想深一点发现，其实是对Lab2中内存管理的知识掌握得还不到位，如果很明确查找页面需要一级页表基地址，那这个bug也应该很容易发现了。

load_icode_mapper中bzero

一方面，这个函数不需要调用bzero；另一方面，bzero函数的实现表明，其要求对齐，如果将没对齐的参数传入，可能会出现无输出等现象。

多进程认识不清

在课下写IPC部分代码时，没有过多考虑这是多进程问题，因此导致做题时没有清楚把握发送方和接收方都需要分类讨论这一点。

This is copyright.

FEATURED TAGS
BUAA-OS
FRIENDS