摘要
本篇是 MIT6.S081 的实验课程的 lab1 实验报告。实验内容是在一个类 unix 操作系统 xv6 上实现各种功能。lab1 内容较为简单，主要是通过系统调用实现一些工具程序。
目录结构
可以看到源代码主要分为两个目录 user/, kernal/，分别对应用户程序和内核程序。在 user/user.h 中，声明了 xv6 支持的系统调用和一些工具函数，工具函数的实现在 user/ulib.c 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| struct stat;
struct rtcdate;
int fork(void);
int exit(int) __attribute__((noreturn));
int wait(int*);
int stat(const char*, struct stat*);
char* strcpy(char*, const char*);
void *memmove(void*, const void*, int);
|
此外，user/ 目录下也保存了用户态的应用程序，以 echo.c 为例，通过 main 完成命令行传参，使用 write 系统调用完成写入标准输出流，调用 exit 显式结束执行。程序需要加入 makefile 中的 UPROGS，才会被编译加载。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
int
main(int argc, char *argv[])
{
int i;
for(i = 1; i < argc; i++){
write(1, argv[i], strlen(argv[i]));
if(i + 1 < argc){
write(1, " ", 1);
} else {
write(1, "\n", 1);
}
}
exit(0);
}
|
kernel 目录下，syscall.h, syscall.c 声明了系统调用号及映射关系，系统调用的实现在 sysproc.c, sysfile.c 等文件中。在本次 lab 中只需要编写用户态程序。
Exercises
sleep
比较简单，调用 sleep 系统调用，实现用户程序，代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include "kernel/types.h"
#include "user/user.h"
int main(int argc, char *argv[])
{
int ticks;
if (argc <= 1)
{
fprintf(2, "usage: sleep n(ticks)");
exit(0);
}
ticks = atoi(argv[1]);
sleep(ticks);
exit(0);
}
|
pingpong
通过一对管道，实现父子进程的通信。
背景知识
在 linux 下，IO 资源均抽象为文件描述符（file description，fd），本质上就是一个整数，每个进程有一个独立的 fd 映射表，用于把 fd 映射为 IO 资源。标准输入 / 输出 / 异常分别映射到 0,1,2。在增加 IO 资源时，会分配最小可用的 fd。xv6 也使用了这种思想，因此可以通过关闭 fd，重新分配 fd 比较简单地实现 IO 重定向功能。参见实验指导书中的例子
xv6 中的 pipe 调用，用于初始化一对 fd 作为管道，分别用于读写。
解决方法
pipe 只能用于单向通信，为达到双向通信，需要创建一对 pipe，并关闭无用的写管道，避免 read 卡死。另外，为了避免交叉输出的混乱，建议在父进程中 wait 子进程结束再输出。
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
| #include "kernel/types.h"
#include "user/user.h"
int main(int argc, char *argv[])
{
int pid = fork();
int parent[2];
int child[2];
pipe(parent);
pipe(child);
if (pid == 0)
{
close(child[1]);
read(child[0], 0, 1);
fprintf(1, "%d: received ping\n", getpid());
write(parent[1], 0, 1);
}
else
{
close(parent[1]);
write(child[1], 0, 1);
read(parent[0], 0, 1);
wait(0);
fprintf(1, "%d: received pong\n", getpid());
}
exit(0);
}
|
primes
实现一个并行的素数筛。图示如下：
可以看到，其思想是一个流水线一样的操作。每个数从最左侧输入，在每个模块里，通过下面的伪代码，从左侧读入数，判断是否能被当前模块的素数整除，若不能再送到右边的模块。
1
2
3
4
5
6
| p = get a number from left neighbor
print p
loop:
n = get a number from left neighbor
if (p does not divide n)
send n to right neighbor
|
需要思考的一个点就是模块是什么时候创建的。实验要求我们只能在必要的时候创建模块。思考这个过程可以发现，如果一个数到达了流水线的边界还没有被筛掉，就意味着它是一个素数，就需要在流水线末尾创建一个模块用于筛去它的倍数。代码如下：
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
64
65
| #include "kernel/types.h"
#include "user/user.h"
int p[40][2];
void process(int idx, int prime)
{
fprintf(1, "prime %d\n", prime);
int num;
while (read(p[idx][0], &num, 4))
{
if (num % prime != 0)
{
if (p[idx + 1][0] == 0)
{
pipe(p[idx + 1]);
if (fork() == 0)
{
close(p[idx + 1][1]);
process(idx + 1, num);
}
else
{
close(p[idx + 1][0]);
}
}
else
{
write(p[idx + 1][1], &num, 4);
}
}
}
close(p[idx][0]);
if (p[idx + 1][1])
{
close(p[idx + 1][1]);
}
wait(0);
exit(0);
}
int main(int argc, char *argv[])
{
int nums[34];
for (int i = 0; i < 34; i++)
{
nums[i] = i + 2;
}
pipe(p[0]);
if (fork() == 0)
{
close(p[0][1]);
process(0, 2);
}
else
{
close(p[0][0]);
write(p[0][1], nums, sizeof(nums));
close(p[0][1]);
wait(0);
}
exit(0);
}
|
find
实现类似 linux find 的功能。也比较简单，需要注意的是当文件夹匹配查找名的时候，就不用递归向下了。从 ls.c 中可以借鉴读取文件类型和遍历文件夹的逻辑。代码如下：
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
char buf[1024];
int idx;
void find(char *path, char *filename)
{
if (strcmp(path, filename) == 0)
{
printf("%s%s\n", buf, path);
return;
}
int ori = idx;
int fd;
struct dirent de;
struct stat st;
char *p = buf + idx;
int len = strlen(path);
memcpy(p, path, len + 1);
idx += len;
if ((fd = open(buf, 0)) < 0)
{
fprintf(2, "find: cannot open %s\n", buf);
return;
}
if (fstat(fd, &st) < 0)
{
fprintf(2, "find: cannot stat %s\n", path);
close(fd);
return;
}
switch (st.type)
{
case T_FILE:
break;
case T_DIR:
if (idx + 1 + DIRSIZ + 1 > sizeof buf)
{
printf("find: path too long\n");
break;
}
buf[idx++] = '/';
buf[idx] = 0;
char name[15];
while (read(fd, &de, sizeof(de)) == sizeof(de))
{
if (de.inum == 0)
continue;
memcpy(name, de.name, DIRSIZ);
name[DIRSIZ] = 0;
if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0)
{
continue;
}
find(name, filename);
}
break;
}
close(fd);
idx = ori;
buf[idx] = 0;
}
int main(int argc, char *argv[])
{
if (argc < 3)
{
fprintf(2, "usage: find {path} {filename}");
exit(0);
}
find(argv[1], argv[2]);
exit(0);
}
|
xargs
实现类似 linux xargs 的功能。从标准输入读取每一行，作为参数加在命令的后面。最简单的做法就是按实验提示，每次读入一个字符，如果是换行就处理这一行，否则继续读。不过每次读一个字符会有很大的 IO 开销，实际应用中肯定是不能这么写的。
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
| #include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/param.h"
char buf[1024];
int main(int argc, char *argv[])
{
int idx = 0;
if (argc <= 1)
{
fprintf(2, "usage: xargs commands...");
exit(0);
}
char *params[MAXARG];
for (int i = 1; i < argc; i++)
{
params[i - 1] = argv[i];
}
params[argc] = 0;
while (read(0, buf + idx, 1))
{
if (buf[idx] != '\n')
{
idx++;
continue;
}
buf[idx] = 0;
if (fork() == 0)
{
params[argc - 1] = buf;
exec(params[0], params);
fprintf(2, "command failed:");
for (int i = 0; i < argc + 1; i++)
{
fprintf(2, "%s ", params[i]);
}
fprintf(2, "\n");
exit(1);
}
else
{
wait(0);
idx = 0;
}
}
exit(0);
}
|
参考
我个人使用的是 2021 年秋季版本。课程官网为 6.S081 / Fall 2021 (mit.edu)。