Operating system interface

本节大概是在讲操作系统的接口，系统调用占了很大一部分。

系统调用 描述
int fork() 创建一个进程，返回子进程的PID
int exit(int status) 终止当前进程，并将状态报告给wait()函数。无返回
int wait(int *status) 等待一个子进程退出; 将退出状态存入*status; 返回子进程PID。
int kill(int pid) 终止对应PID的进程，返回0，或返回-1表示错误
int getpid() 返回当前进程的PID
int sleep(int n) 暂停n个时钟节拍
int exec(char *file, char *argv[]) 加载一个文件并使用参数执行它; 只有在出错时才返回
char *sbrk(int n) 按n 字节增长进程的内存。返回新内存的开始
int open(char *file, int flags) 打开一个文件；flags表示read/write；返回一个fd（文件描述符）
int write(int fd, char *buf, int n) 从buf 写n 个字节到文件描述符fd; 返回n
int read(int fd, char *buf, int n) 将n 个字节读入buf；返回读取的字节数；如果文件结束，返回0
int close(int fd) 释放打开的文件fd
int dup(int fd) 返回一个新的文件描述符，指向与fd 相同的文件
int pipe(int p[]) 创建一个管道，把read/write文件描述符放在p[0]和p[1]中
int chdir(char *dir) 改变当前的工作目录
int mkdir(char *dir) 创建一个新目录
int mknod(char *file, int, int) 创建一个设备文件
int fstat(int fd, struct stat *st) 将打开文件fd的信息放入*st
int stat(char *file, struct stat *st) 将指定名称的文件信息放入*st
int link(char *file1, char *file2) 为文件file1创建另一个名称(file2)
int unlink(char *file) 删除一个文件

表1.2：xv6系统调用（除非另外声明，这些系统调用返回0表示无误，返回-1表示出错）

Process and memory

fork

1
2
3
4
5
6
7
8
9
10
int pid = fork();
if(pid > 0){
    printf("parent: child's pid = %d\n",pid);
    pid = wait(0);
    printf("child %d is done.\n",pid);
} else if(pid == 0){
    printf("child : exiting\n");
} else {
    printf("fork error\n");
}

这是一个利用fork的返回值对于父子进程来说不同这一特点进行编写的例程。其中比较不熟的还是wait(0)这一句的用法。这点具体可以看书中笔记和上面的系统调用表。

exec

exec是一个系统调用，它跟exe文件被执行的原理密切相关。当程序调用exec，就会跳转到exec参数文件去执行，原程序exec下面的指令都不再被执行，除非exec因错误而退出。

exec与fork

由shell的源码中main函数这一段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Read and run input commands.
while(getcmd(buf, sizeof(buf)) >= 0){
  if(buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' '){
    // Chdir must be called by the parent, not the child.
    buf[strlen(buf)-1] = 0;  // chop \n
    if(chdir(buf+3) < 0)
      fprintf(2, "cannot cd %s\n", buf+3);
    continue;
  }
  if(fork1() == 0)
    runcmd(parsecmd(buf));
  wait(0);
}
exit(0);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void runcmd(struct cmd *cmd)
{
  if(cmd == 0)
    exit(1);

  switch(cmd->type){
  ...
  case EXEC:
    ecmd = (struct execcmd*)cmd;
    exec(ecmd->argv[0], ecmd->argv);
    fprintf(2, "exec %s failed\n", ecmd->argv[0]);
    break;
    ...
        
  exit(0);
}

可以看到shell其实本质上就是这样的架构架构：

1
2
3
4
5
6
7
while(true){
	if(读到了command&&fork()==0){
        exec(command);
        printf("失败信息");
    }
    wait(0);
}

也即父进程创建出子进程来执行command，并且父进程等待子进程执行完再继续等待输入。

可以看到，fork和exec的使用是非常紧密的，联合使用也是非常顺理成章的。那么，如果干从fork的exec的对于内存管理的原理来讲，就会不免产生一点问题。

问题描述：

fork的内存原理，实质上是开辟一片新的与父进程等大的内存空间，然后把父进程的数据都copy一份进这个新内存空间。exec的原理是用一片可以容纳得下文件指令及其所需空间的内存空间去替代调用进程原有的那片内存空间。

可以看到，如果fork和exec接连使用，理论上其实是会产生一点浪费的，fork创建子进程复制完了一片内存空间，这片新复制的内存空间又马上被扔掉了，取而代之的用的是exec的内存空间。

为了解决这个问题，kernel使用了copy-on-write技术优化。

I/O and File descriptors

文件描述符

句柄就是一个int值，它代表了一个由内核管理的，可以被进程读写的对象.

A process may obtain a file descriptor by opening a file, directory, or device, or by creating a pipe, or by duplicating an existing descriptor.

每个进程的其三个句柄有默认值：

By convention, a process reads from file descriptor 0 (standard input), writes output to file descriptor 1 (standard output), and writes error messages to file descriptor 2 (standard error).

句柄0对应着standard input，1对应着standard output，2对应着standard error。

read、write

read和write的参数都是句柄，buf，读/写长度。都会导致文件指针的移动。使用如下例程【类似cat的原理】：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char buf[512];
int n;

for(;;){
    n = read(0);//从标准输入读
    if(n == 0){
        break;
    }
    if(n < 0){
        fprintf(2,"read error\n");
        exit(1);
    }
    if(write(1,buf,n) != n){//向标准输出写
        fprintf(2,"write error\n");
        exit(1);
    }
}

close

close函数释放了一个句柄，以后它释放掉的这个句柄就可以被用来表示别的文件了。

open

open函数会给参数的file分配一个句柄。这个句柄通常是目前空闲的句柄中值最小的那个。

重定向的实现

1
2
3
4
5
6
7
8
9
char *argv[2];

argv[0] = "cat";
argc[1] = 0;
if(fork() == 0){
    close(0);
    open("input.txt",O_RDONLY);
    exec("cat",argv);
}

xv6的重定向实现跟这个原理差不多：

1
2
3
4
5
6
7
8
9
case REDIR:
  rcmd = (struct redircmd*)cmd;
  close(rcmd->fd);
  if(open(rcmd->file, rcmd->mode) < 0){
    fprintf(2, "open %s failed\n", rcmd->file);
    exit(1);
  }
  runcmd(rcmd->cmd);
  break;

共享偏移量

fork出来的父子进程同一个句柄对同一个文件的偏移量是相同的，这个原理应该是因为，父子进程共享的是文件句柄这个结构体对象本身，也就是拷贝的时候是浅拷贝而不是深拷贝。

1
2
3
4
5
6
7
if(fork() == 0) {
	write(1, "hello ", 6);
	exit(0);
} else {
	wait(0);
	write(1, "world\n", 6);
}

dup

dup系统调用复制一个现有的文件描述符，返回一个引用自同一个底层I/O对象的新文件描述符。

dup和open一样，都是会占用一个新的句柄的，而且都是优先分配数值小的。比如说fd = dup(3)，得到fd=4，那么结果就是句柄3和句柄4指向同一个文件，并且偏移量一样。

dup可以让这样的指令变得可以实现：

1
ls existing-file non-existing-file > tmp1 2>&1

这个指令的意思是，先把stderr的结果重定向到stdout，再把stdout的结果重定向到tmp1中。

关于2>&1的解释，可以看这个 shell中的”2>&1”是什么意思？

这个的实现就要用到dup了。我们会fork一个子进程，在子进程里面close(2)，然后再dup(1)。这样一来，我们就成功实现了句柄1和2指向同一个文件

Pipe

使用

int pipe(int p[]) 创建一个管道，把read/write文件描述符放在p[0]和p[1]中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int p[2];
char* argv[2];

argv[0] = "wc";
argv[1] = 0;

pipe(p);
if(fork() == 0){
    close(0);
    dup(p[0]);
    close(p[0]);
    close(p[1]);
} else{
    close(p[0]);
    write(p[1],"hello world\n",12);
    close(p[1]);
}

完成了父进程-pipe-子进程的一个重定向。

pipe是阻塞的生产者消费者模式。对管道的read，在没有数据输入时会阻塞，直到读到数据，或者所有的write方向都被关闭。示例代码中，如果不使用pipe就需要显示close(p[0]) close(p[1])，正是为了防止没有数据输入时write方向不为0导致死锁的情况出现。

实现管道命令

管道命令的实现正是通过pipe。

执行原理就是，创建两个子进程分别执行左右两侧的句子，然后左侧子进程的out重定向到pip的write，右侧子进程的in重定向到pip的read。

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
 case PIPE:
   pcmd = (struct pipecmd*)cmd;
   if(pipe(p) < 0)
     panic("pipe");
//左
   if(fork1() == 0){
     close(1);
     dup(p[1]);
     close(p[0]);
     close(p[1]);
     runcmd(pcmd->left);
   }
//右
   if(fork1() == 0){
     close(0);
     dup(p[0]);
     close(p[0]);
     close(p[1]);
     runcmd(pcmd->right);
   }
   //中
close(p[0]);
   close(p[1]);
   //wait
wait(0);
   wait(0);
   break;

这实际上是二叉树的左右中递归过程。

附：对于管道命令的解读

1
cat a.txt | echo

我的本意是觉得，这意思就是把cat a.txt的输出连到echo的输入，这个命令结果跟cat a.txt是没什么差的。但具体执行出来发现最后的结果却是跟：

1
echo

这个指令的效果是一样的，也就是cat a.txt的output，即echo的input完全被丢弃了。

我想这是因为，echo这个命令的执行过程并没有用到stdin，仅仅用到了参数，也就是说管道read端的接入对它并没有什么影响。

这也是为啥

1
sleep 10 | echo hi

这个命令最后的结果是，秒速出hi，然后等待10s后结束，了。由于echo的输出与stdin没有关系，所以，echo不会阻塞读入stdin，等待管道关闭，而是会即刻输出hi。

管道实际上就相当于：

1
2
echo hello world | wc
echo hello world > /tmp/xyz; wc < /tmp/xyz

在这种情况下，管道相比临时文件至少有四个优势

  • 首先，不用删文件
  • 其次，管道可以任意传递长的数据流
  • 第三，管道允许一定程度上的并行
  • 第四，如果实现进程间通讯，管道的块读写比文件的非块语义更有效率。

File system

inode：代表文件本体，包括文件类型、文件长度、文件内容在磁盘位置、文件的链接数

link：指向文件的链接，一个文件可以有多个link，link内包含文件名和对inode的引用

当链接数=0，且句柄数=0，文件的磁盘空间和inode索引就会被释放

Lab Xv6 and Unix utilities

配置实验环境

参考文章：

xv6环境搭建

【MIT6.S081/6.828】手把手教你搭建开发环境

下载工具链

1
$ sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu

测试安装ok：

1
2
3
4
5
6
7
8
9
10
11
12
$ qemu-system-riscv64 --version
QEMU emulator version 5.1.0
//下面其中之一正常就行
$ riscv64-linux-gnu-gcc --version
riscv64-linux-gnu-gcc (Debian 10.3.0-8) 10.3.0
...
$ riscv64-unknown-elf-gcc --version
riscv64-unknown-elf-gcc (GCC) 10.1.0
...
$ riscv64-unknown-linux-gnu-gcc --version
riscv64-unknown-linux-gnu-gcc (GCC) 10.1.0
...

注，这里出现了一个问题，qemu-system-riscv64 --version打出来发现qemu-system-riscv64 command not found。似乎是我的ubuntu16.04版本太低了【悲】去看了下网上，可以按照这个来做：

rCore qemu risc-v 实验环境配置

下载编译xv6源码

随后，进入一个你喜欢的文件夹clone xv6的实验源码，输入

1
2
3
$ git clone git://g.csail.mit.edu/xv6-labs-2020
$ cd xv6-labs-2020
$ git checkout util

然后进行编译

1
2
$ make
$ make qemu

如果此处发生错误：unrecognized command line option -mno-relax，则按照此说法 xv6环境搭建更新gcc版本

1
2
$ sudo apt install gcc-8-riscv64-linux-gnu
$ sudo update-alternatives --install /usr/bin/riscv64-linux-gnu-gcc riscv64-linux-gnu-gcc /usr/bin/riscv64-linux-gnu-gcc-8 8

再执行一次

1
2
$ make
$ make qemu

就ok了。

关闭qemu

qemu退出操作

在这里记个强制方法：

1
ps -elf | grep qemu

image-20230105153458808

记住第二个的pid

然后

1
kill 3303

测试gdb是否ok

见该文章最后一部分

【MIT6.S081/6.828】手把手教你搭建开发环境

自测方法

1
make grade

或者如果只想测其中一个，可以：

1
./grade-lab-util sleep

make qemu后卡住

疑似qemu版本不对。解决方法

实验内容

编写sleep.c

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.

image-20230105164146100.png

体会
参数

注意，他要求我们实现的sleep的参数是ticks的数量，不是秒数。我花了半天找时钟周期大小这个参数在哪，找了许久没找到，估计是没考虑到这一点。

比如说，我翻了一下linux0.11的源码，在include/linux/time.h下有这句：

image-20230105162505574.png

说明了时钟频率大小。在xv6好像没有看到对这个的显式说明。

系统调用过程

感受了一下xv6的系统调用过程，跟linux0.11还是很相像的。

这个好像是lab2的内容，我暂且先在此放下我体会到的感受。

  1. xv6

    首先是从用户态到内核态的切换。

    在user/user.h中有各个系统调用外化的函数签名。在用户程序中调用里面的函数签名，就会执行【说实话，我没看懂为什么这里会知道要从user.h跳到usys.S中执行，也许是Makefile里有写？】user/usys.S中对应的汇编代码，比如说这种：

    image-20230105170701334

    然后这个SYS_close这种，其实是系统调用号宏，被定义在kernel/syscall.h中：

    image-20230105171327076.pn

    li a7,SYS_call就是把SYS_call的值放入a7寄存器，大概就是传参的意思。ecall是从用户态转到内核态的指令。这样一来，就完成了从用户态到内核态的切换。

    然后是在内核态的执行。

    切换到内核态之后的执行步骤跟linux0.11可以说是完全一样。

    首先应该是会去执行kernel/syscall.c中的syscall函数，具体应该是通过ecall引发0x80中断，然后查表得知这个syscall是中断处理函数

    image-20230105172110475.pn

    可以看到，syscall获取了a7里的参数，然后查了系统调用表

    image-20230105173019159

    然后去sysproc.c文件下执行相应的sys_xxx函数。这个函数指针用得真是牛逼。

    再然后，sys_xxx函数中会从栈中取出调用参数，再跳转到xxx(args)函数中去（这些xxx函数一般在kernel中以单独文件形式出现）。

    这样一来，就完成了一次系统调用。

  2. linux0.11

    首先是用户态到内核态的切换。

    在用户态中比方说调用system call close()，则会调用lib/close.c下的：

    image-20230105173820813

    展开这个宏之后，是这样的：

    image-20230105173845317

    具体意思就是把close的系统调用号存入参数寄存器，然后引发0x80中断，进入内核态。

    然后是在内核态的执行。

    查表会得知sys_call函数是0x80中断的中断处理函数，然后就会根据参数里的系统调用名字去找系统调用表执行

    image-20230105174832400

    这部分跟xv6差不多，不再赘述

可见，这两个系统在内核态的实现是差不多的，只是在用户态有点稍稍不一样。感觉linux0.11会更加精妙一些。

编写pingpong程序

Write a program that uses UNIX system calls to ‘’ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “: received ping”, where is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “: received pong”, and exit. Your solution should be in the file user/pingpong.c.

体会

思路很简单，我之所以写了那么久是因为走了好大的弯路……

题目要求输出格式为”: received ping”，我的思路固化为：先把pid化成数字，再用字符串拼接串成整个。为了实现我的思路，我就需要额外再写两个工具函数，一个是itoa，一个是strcat。而又由于malloc函数暂待实现，itoa和strcat的实现就仍然不够优雅。折腾了半天终于OK了，结果看到别人是怎么做到这个输出格式的呢？↓

1
fprintf(1,"%d: received ping\n",getpid());

这下是真的尴尬了23333

但总而言之，自己写了那俩不够优雅的函数还算是有点用【大概】。以下是我的代码

编写primes

参考：

MIT操作系统实验lab1（案例：primes（质数筛选）附代码、详解）

XV6实验-Lab0 Utilities

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

其实就是用生产者消费者模式来写素数计算的并发版本，这个我熟

……以上是第一印象。然后我看着超链接文章里的素数筛的图片，以及指导书给的提示：

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

  • Be careful to close file descriptors that a process doesn’t need, because otherwise your program will run xv6 out of resources before the first process reaches 35.

义无反顾地……使用了35个管道hhhhh

然后不知道为什么不行，也焦头烂额地感觉我思路太离谱了，去看了下发现大家都是只用一个管道……

我也搞了个单管道的出来，但是思路受第一篇的影响非常地串行，也即先筛完再创建子进程。看到

XV6实验-Lab0 Utilities

这篇文章，才发现还可以那样双管道并行……我虽然也考虑过双管道，但是觉得实现不了【因为我是用循环的思路，如果要双管道的话切换会很麻烦】就没写了，没想到还可以向他那样【他选择的是一个在外部定义的p，和一个作用域更小在每次循环内定义的p1，再加上递归传递参数这个技巧，就可以接连不断递归下去了】，深感佩服。写得是真好，可以去参考学习一下，我懒得改了（

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
#include"user/user.h"

int main(){
	int p[2];
	pipe(p);
    
	if(fork() == 0){
		while(1){
			char buf[3];
			//读入第一个数字 
			read(p[0],buf,3);
			int prime = atoi(buf);
			if(prime == 36){
				close(p[0]);
				close(p[1]);
				exit(0);
			}
			fprintf(1,"prime %d\n",prime);
			//读入其他数字 
			int tmp = atoi(buf);
			while(1){
				read(p[0],buf,3);
				tmp = atoi(buf);
                //输入结束
				if(tmp == 36){
					break;
				}
				if(tmp%prime!=0){
					write(p[1],buf,3);
				}
			}
            //作为标记，标志着输入序列结束
			itoa(36,buf);
			write(p[1],buf,3);
			if(fork()){
			}
			else{
				close(p[0]);
				close(p[1]);
				wait(0);
				exit(0);
			}
		}
	} else{
		close(p[0]);
		char buf[3];
		for(int i=2;i<=35;i++){
			itoa(i,buf);
			write(p[1],buf,3);
		}
        //作为标记，标志着输入序列结束
		itoa(36,buf);
		write(p[1],buf,3);
		close(p[1]);
		wait(0);
	}
	exit(0);
}

编写find

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

初始版

直接照着ls的模板改，改成递归就ok了。值得注意的是，目录也是一种文件，也可以通过read读取。目录文件的内容就是目录里的所有文件的名字。因而，我们在递归时可以忽略文件，只对目录处理，因为目录中就包含着所有文件名的信息。

附加题：支持正则表达式

把user/grep.c里面的匹配函数拿来就行。

编写xargs

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

体会

思路还是很直观的，就是从stdin一行一行读入数据，然后把这数据处理成参数，最后调用exec就行。就是中间有很多小细节值得注意。

有一点比较坑的是，main方法的那个argc的计算方法是这样的，不是直接用数组的长度：

1
for(argc = 0; argv[argc]; argc++)

可以看到，合格的argv的形式应该是：参1 参2 参3 “\0”，最后一个元素要以”\0”标志结束。

这个应该是编写者约定俗成的。在user/sh.c的parseexec，大概445行左右：

image-20230106172133338

shell处理命令时是会默认把最后一个清零的。

确实，后面在学内存的时候，用户空间的构成如图所示：

image-20230109234930690

可以看到栈那边，参数列完了之后是会有一个用以terminate的空指针的

附加题：改善shell

看起来又难又多所以我先摸了【润】等之后有时间再回来弄吧