Keywords：管道，shell

管道

共享内存和管道都是进程间通信（IPC）的方式。管道分为有名管道（可以在任意两个进程之间通信）和匿名管道（只能在具有公共祖先的进程之间使用，通常是在父子进程之间）。

MOS实验中仅要求实现匿名管道

Unix 中的匿名管道

#include <unistd.h>
int pipe(int fd[2]);

在 Unix 中，管道由 int pipe(int fd[2]) 函数创建，成功创建管道返回 0，参数中的 fd用来保存读写端的文件描述符，fd[0] 对应读端，fd[1] 对应写端。通常，调用 pipe 的进程接着调用 fork，这样就创建了从父进程到子进程（或反向）的IPC通道。

匿名管道特点：

  1. 数据单向流动，具有固定的读端和写端
  2. 只能用于具有公共祖先的进程之间通信，实现依赖于父子进程文件共享
  3. 是一种只存在于内存中的文件。父进程调用 pipe函数时，会打开两个新的文件描述符：一个表示只读端，另一个表示只写端，两个描述符都映射到了同一片内存区域。在 fork 的配合下，子进程复制父进程的两个文件描述符，从而在父子进程间形成了四个（父子各拥有一读一写）指向同一片内存区域的文件描述符，父子进程可根据需要关掉自己不用的一个，从而实现父子进程间的单向通信管道，这也是匿名管道只能用在具有亲缘关系的进程间通信的原因。

MOS 中 pipe 的实现

保证负责父子进程通过管道访问的内存相同：在 pipe 中，首先分配两个文件描述符 fd0 和 fd1 并为其分配空间，然后给 fd0 对应的虚拟地址分配一页物理内存，再将 fd1 对应的虚拟地址映射到这一页物理内存。

PTE_LIBRARY ：共享页面是具有权限位 PTE_LIBRARY 的页面，需要保持共享可写的状态，使得父子进程对其进行修改的结果相互可见。当父子进程试图写共享页面时，直接在该页面上进行写操作即可。

int pipe(int pfd[2]) {
	int r;
	void *va;
	struct Fd *fd0, *fd1;

	/* Step 1: Allocate the file descriptors. */
	/* 	注意 fd_alloc 函数仅找到一个未使用的文件描述符，并返回对应的虚拟地址，
		依赖于调用者在调用fd_alloc之后负责分配物理内存。
	*/
	if ((r = fd_alloc(&fd0)) < 0 || (r = syscall_mem_alloc(0, fd0, PTE_D | PTE_LIBRARY)) < 0) {
		goto err;
	}

	if ((r = fd_alloc(&fd1)) < 0 || (r = syscall_mem_alloc(0, fd1, PTE_D | PTE_LIBRARY)) < 0) {
		goto err1;
	}

	/* Step 2: Allocate and map the page for the 'Pipe' structure. */
	// 给 fd0 对应的虚拟地址分配一页物理内存
	va = fd2data(fd0);
	if ((r = syscall_mem_alloc(0, (void *)va, PTE_D | PTE_LIBRARY)) < 0) {
		goto err2;
	}
	// 将 fd1 对应的虚拟地址映射到这一页物理内存
	if ((r = syscall_mem_map(0, (void *)va, 0, (void *)fd2data(fd1), PTE_D | PTE_LIBRARY)) <
	    0) {
		goto err3;
	}
	...
}

管道的读写

struct Pipe {
	// 下一个将要从管道读的数据的位置（读者更新）
	u_int p_rpos;	       // read position
	// 下一个将要向管道写的数据的位置（写者更新）
	u_int p_wpos;	       // write position
	// 32B的缓冲区（环形缓冲区）
	u_char p_buf[BY2PIPE]; // data buffer
};

读者在从管道读取大小不超过 n 字节的数据时，拷贝 p_buf[p_rpos%BY2PIPE] 的数据，然后 p_rpos++。注意当缓冲区此时还未写入数据（即管道数据为空，即 p_rpos >= p_wpos）时，若写者进程结束则return，否则进程切换到写者运行。

写者在向管道写入数据时，将数据存入 p_buf[p_wpos%BY2PIPE] ，然后 p_wpos++。注意当缓冲区满溢（即 p_wpos - p_rpos >= BY2PIPE）时，若写者进程结束则return，否则进程切换到读者运行。

static int pipe_read(struct Fd *fd, void *vbuf, u_int n, u_int offset) {
	int i;
	struct Pipe *p;
	char *rbuf;

	p = (struct Pipe *)fd2data(fd);
	rbuf = (char *)vbuf;
	for (i = 0; i < n; i++) {
		while (p->p_rpos >= p->p_wpos) {
			if (i > 0 || _pipe_is_closed(fd, p)) {
				return i;
			}
			syscall_yield();
		}
		rbuf[i] = p->p_buf[p->p_rpos++ % BY2PIPE];
	}
	return i;

	user_panic("pipe_read not implemented");
}
static int pipe_write(struct Fd *fd, const void *vbuf, u_int n, u_int offset) {
	int i;
	struct Pipe *p;
	char *wbuf;

	p = (struct Pipe *)fd2data(fd);
	wbuf = (char *)vbuf;
	for (i = 0; i < n; i++) {
		while (p->p_wpos - p->p_rpos >= BY2PIPE) {
			if (_pipe_is_closed(fd, p)) {
				return i;
			}
			syscall_yield();
		}
		p->p_buf[p->p_wpos++ % BY2PIPE] = wbuf[i];
	}
	return i;

	user_panic("pipe_write not implemented");

	return n;
}
判断管道一端是否关闭

static int _pipe_is_closed(struct Fd *fd, struct Pipe *p) 判断管道的读者或写者是否已关闭。

原理见教程 P144。

static int _pipe_is_closed(struct Fd *fd, struct Pipe *p) {
	int fd_ref, pipe_ref, runs;
    
    // 同步读
	do {
		runs = env->env_runs;
		fd_ref = pageref(fd); // pageref 查询虚拟地址对应的实际物理页，返回其 pp_ref 变量的值
		pipe_ref = pageref(p);
	} while (runs != env->env_runs);

	return fd_ref == pipe_ref;
}

在我们的 MOS 操作系统中，只有 syscall_ 开头的系统调用函数是原子操作，其他所有包括 fork 这些函数在运行时都是可能会被随时打断

对共享变量进行读写需要保证操作原子性：

env_runs是一个表示环境运行次数的计数器，每当发生一次上下文切换时，它的值就会增加。因此，如果在读取引用计数之前和之后，env_runs的值没有发生变化，那么可以认为在这期间环境没有发生切换或其他并发操作。

通过比较env_runs的值，可以实现一种简单的并发控制机制。如果在读取引用计数之前和之后的env_runs值不同，说明期间发生了环境切换，可能有其他线程或进程同时进行了对管道的读写操作，因此需要重新读取引用计数。

这种简单的机制并不是绝对可靠的，因为在某些情况下，环境可能会发生多次切换，而这段代码只能检测到最后一次切换。但在大多数情况下，这种机制已经足够满足需求，并能减少竞态条件和数据不一致性的发生概率。如果需要更精确的并发控制，可能需要使用更复杂的同步机制，如互斥锁或原子操作。

shell

——实现命令行式 shell

  • 解析命令：分析命令的基本单元——特殊符号或单词，解析用户输入的命令
  • 执行命令：调用spawn产生子进程并装载命令对应的ELF文件，子进程执行命令，父进程等待子进程执行结束后，结束进程。

思考

1.

示例代码中，父进程操作管道的写端，子进程操作管道的读端。如果现在想让父进程作为“读者”，代码应当如何修改？

#include <stdlib.h>
#include <unistd.h>

int fildes[2];
char buf[100];
int status;

int main(){

	status = pipe(fildes);

	if (status == -1 ) {
		printf("error\n");
	}

	switch (fork()) {
		case -1:
			break;

		case 0: 
			close(fildes[0]); /* 关闭不用的读端 */
            write(fildes[1], "Hello world\n", 12);
			close(fildes[1]); /* 读取结束，关闭写端 */
			exit(EXIT_SUCCESS);
		
        default: 
            close(fildes[1]); /* 关闭不用的写端 */
            read(fildes[0], buf, 100); 
            printf("child-process read:%s",buf);
            close(fildes[1]); /* 读取结束，关闭读端 */
            exit(EXIT_SUCCESS);
    }
}

2.

上面这种不同步修改 pp_ref 而导致的进程竞争问题在 user/lib/fd.c 中的 dup 函数中也存在。请结合代码模仿上述情景，分析一下我们的 dup 函数中为什么会出现预想之外的情况？

dup 函数功能是将一个文件描述符的内容映射到另一个文件描述符中。当我们将一个管道的读/写端对应的文件描述符映射到另一个文件描述符时，映射前 pageref(fd0)=1,pageref(fd1)=1,pageref(pipe)=2pageref(fd0)=1,pageref(fd1)=1,pageref(pipe)=2 ，若首先 map fd0 ，则 pageref(fd0)=2pageref(fd0) = 2 ，则 pageref(fd0)==pageref(pipe)pageref(fd0) == pageref(pipe) ，错误判断了写端已经关闭。

3.

阅读上述材料并思考：为什么系统调用一定是原子操作呢？如果你觉得不是所有的系统调用都是原子操作，请给出反例。希望能结合相关代码进行分析说明。

非原子性操作是因为发生了进程切换。CPU通过定时器产生的时钟中断确定一个时间片结束，从而跳转到内核下的schedule函数判断是否需要切换进程。

阅读指导书P83对 SR 寄存器的描述，每当异常发生时，执行 syscall 指令，CPU 会把 KUc 和 IEc 的数值拷贝到 KUp 和 IEp。随后将 KUc 和 IEc 置为 0。KUc = 0 表示 CPU 当前运行在内核态下， IEc = 0 表示 CPU 当前关闭了中断，也就不会产生时钟中断，那么系统调用就都是原子操作的。

4.

仔细阅读上面这段话，并思考下列问题

  • 按照上述说法控制 pipe_close 中 fd 和 pipe unmap 的顺序，是否可以解决上述场景的进程竞争问题？给出你的分析过程。
  • 我们只分析了 close 时的情形，在 fd.c 中有一个 dup 函数，用于复制文件内容。试想，如果要复制的是一个管道，那么是否会出现与 close 类似的问题？请模仿上述材料写写你的理解。

问题1：可以解决，在任何时刻 pageref(fd)≤pageref(pipe)pageref(fd) \leq pageref(pipe) ，所以先 unmap fd 就不会错误判断两者相等。更具体的分析在指导书 P146。

问题2：会出现类似问题，当我们将一个管道的读/写端对应的文件描述符映射到另一个文件描述符时，映射前 pageref(fd0)=1,pageref(fd1)=1,pageref(pipe)=2pageref(fd0)=1,pageref(fd1)=1,pageref(pipe)=2 ，若首先 map fd0 ，则 pageref(fd0)=2pageref(fd0) = 2 ，则 pageref(fd0)==pageref(pipe)pageref(fd0) == pageref(pipe) ，错误判断了写端已经关闭。

5.

思考以下三个问题。

  • 认真回看 Lab5 文件系统相关代码，弄清打开文件的过程。
  • 回顾 Lab1 与 Lab3，思考如何读取并加载 ELF 文件。
  • 在 Lab1 中我们介绍了 data text bss 段及它们的含义，data 段存放初始化过的全局变量，bss 段存放未初始化的全局变量。关于 memsize 和 filesize ，我们在 Note1.3.4中也解释了它们的含义与特点。关于 Note 1.3.4，注意其中关于“bss 段并不在文件中占数据”表述的含义。回顾 Lab3 并思考：elf_load_seg() 和 load_icode_mapper()函数是如何确保加载 ELF 文件时，bss 段数据被正确加载进虚拟内存空间。bss 段在 ELF 中并不占空间，但 ELF 加载进内存后，bss 段的数据占据了空间，并且初始值都是 0。请回顾 elf_load_seg() 和 load_icode_mapper() 的实现，思考这一点是如何实现的？

下面给出一些对于上述问题的提示，以便大家更好地把握加载内核进程和加载用户进程的区别与联系，类比完成 spawn 函数。

关于第一个问题，在 Lab3 中我们创建进程，并且通过 ENV_CREATE(…) 在内核态加载了初始进程，而我们的 spawn 函数则是通过和文件系统交互，取得文件描述块，进而找到 ELF 在“硬盘”中的位置，进而读取。

关于第二个问题，各位已经在 Lab3 中填写了 load_icode 函数，实现了 ELF 可执行文件中读取数据并加载到内存空间，其中通过调用 elf_load_seg 函数来加载各个程序段。在 Lab3 中我们要填写 load_icode_mapper 回调函数，在内核态下加载 ELF 数据到内存空间；相应地，在 Lab6 中 spawn 函数也需要在用户态下使用系统调用为 ELF 数据分配空间。

  • 打开文件的过程：user/lib/file.c 下的 open 函数接受文件路径 path 和 模式 mode 作为输入参数，先调用 fd_alloc 申请文件描述符，再调用 fsipc_open 向文件系统服务进程发送打开文件的请求， fsipc 向文件系统服务进程发送 IPC 请求，并等待响应。 文件系统服务进程收到请求后调用 serve_open 处理请求，serve_open 调用 file_open 打开路径并寻找到文件描述符。
  • 读取并加载 ELF 文件：load_icode 函数负责加载可执行文件 binary 到进程 e 的内存中。每当 elf_load_seg 函数解析到一个需要加载到内存中的页面，会将有关的信息作为参数传递给回调函数，并由它完成单个页面的加载过程，而这里 load_icode_mapper 就是 map_page 的具体实现。
  • 在 elf_load_seg 函数处理中，当该段在文件中的大小达不到为填入这段内容新分配的页面大小（即 bin_size < sgsize）时，余下的部分用 0 来填充，即为 bss 段的数据赋了初值 0 。

6.

通过阅读代码空白段的注释我们知道，将文件复制给标准输入或输出，需要我们将其 dup 到 0 或 1 号文件描述符 (fd)。那么问题来了：在哪步，0 和 1 被“安排”为标准输入和标准输出？请分析代码执行流程，给出答案。

在 user/init.c 中如下，将0号文件描述符映射到1号，相当于把控制台的输入输出缓冲区当做管道。

if ((r = dup(0, 1)) < 0) {
	user_panic("dup: %d", r);
}

7.

在 shell 中执行的命令分为内置命令和外部命令。在执行内置命令时 shell 不需要 fork 一个子 shell，如 Linux 系统中的 cd 命令。在执行外部命令时 shell 需要 fork一个子 shell，然后子 shell 去执行这条命令。

据此判断，在 MOS 中我们用到的 shell 命令是内置命令还是外部命令？请思考为什么Linux 的 cd 命令是内部命令而不是外部命令？

MOS中外部命令。

确保 cd 切换目录仅在当前进程发生，且子进程无法直接修改父进程的环境变量。

8.

在你的 shell 中输入命令 ls.b | cat.b > motd。

  • 请问你可以在你的 shell 中观察到几次 spawn ？分别对应哪个进程？
  • 请问你可以在你的 shell 中观察到几次进程销毁？分别对应哪个进程？

观察到两次spawn。在 main 函数中，对于每次输入的命令，先 fork 出一个子进程处理命令，该子进程在运行runcmd时会调用一次 spawn；在执行管道时，fork出的子shell进程执行 “|” 后的命令时又进行了一次 spawn。==（notsure）==

观察到四次进程销毁，首先销毁处理管道时fork出的子shell进程在runcmd时的spawn产生的进程，其次销毁管道fork的子进程，然后销毁整条命令作为参数传入runcmd时spawn产生的进程，最后销毁在main函数进程fork出的子进程。

image-20230521205126729