[MIT 6.S081]Lab1 Xv6 and Unix utilities

1 通过gdb调试

参考链接

2 sleep（easy）

图2-1

结果如下：

图2-2

3 pingpong(easy)

图3-1

本题考查的是管道通信相关内容的理解。

If no data is available, a read on a pipe waits for either data to be written or for all file descriptors referring to the write end to be closed; in the latter case, read will return 1, just as if the end of a data file had been reached.

xv6书中指出，read会一直阻塞直到有数据被写入管道或者所有指向管道写端的文件描述符都被关闭。

一种简单的实现是创建两个管道，一个管道的流向为父进程到子进程，另外一个的流向为子进程到父进程。

另外一种实现只需要创建一个管道，但是由于父子进程读写的都是同一个管道，需要通过wait来同步父子进程读写的顺序，防止出现死锁的情况。代码如下，注意55行的 wait((int*)0)，父进程一定要等待子进程退出后，才可以从管道中读取数据，否则可能会出现父进程自写自读的情况，导致子进程阻塞在21行处。

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

int main(int argc, char *argv[])
{
    int p[2];
    pipe(p);

    int pid = fork();
    if (pid < 0)
    {
        // fork failed
        fprintf(2, "fork failure\n");
        exit(1);
    }

    char buf = '1';
    if (pid == 0) 
    {
        // child 
        pid = getpid(); // acquire the pid of the child process

        // read a byte from pipe
        if (read(p[0], &buf, sizeof(buf)) != 1)
        {
            fprintf(2, "child process read failed\n");
            close(p[0]);
            close(p[1]);
            exit(1);
        } 
        close(p[0]);
        printf("%d: received ping\n", pid); 
        // write a byte to pipe
        if (write(p[1], &buf, sizeof(buf)) != 1)
        {
            fprintf(2, "child process write failed\n");
            close(p[1]);
            exit(1);
        } 
        close(p[1]);
        exit(0);
    }
    else 
    {
        // father
        pid = getpid(); // acquire the pid of the parent process
        // write a byte to pipe
        if (write(p[1], &buf, sizeof(buf)) != 1) 
        {
            close(p[0]);
            close(p[1]);
            fprintf(2, "parent process write failed\n");
            wait((int*)0);
            exit(1);
        }
        close(p[1]);

        wait((int*)0);

        // read a byte from pipe
        if (read(p[0], &buf, sizeof(buf)) != 1) 
        {
            close(p[0]);
            fprintf(2, "father process read failed\n");
            exit(1);
        }
        close(p[0]);
        printf("%d:received pong\n", pid);
        exit(0);
    }
}

结果如下

图3-2

图3-3

4 primes (moderate)/(hard)

图4-1

这道题目考察的是利用 fork 进行多进程编程。

重点是理解下面的图和伪代码。本题用到了一种编程思想（Bell Labs and CSP Threads (swtch.com)），通过未缓冲的命名的通道来同时进行通信和同步。因为管道未缓冲，所以可以通过读写阻塞来进行同步。

图4-2

图4-3

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[])
{
    int left[2];
    int right[2];
    int start = 2;
    int end = 35;

    pipe(left);

    int pid = fork();

    if (pid < 0)
    {
        fprintf(2, "fork failed pid = <%d>\n", getpid());
        close(left[0]);
        close(left[1]);
        exit(1);
    }

    if (pid == 0)
    {
        // child
        close(left[1]); 
    }
    else
    {
        // parent
        close(left[0]);
        for (int num = start; num <= end; ++num)
        {
            if (write(left[1], &num, sizeof(int)) != sizeof(int))
            {
                fprintf(2, "write failed pid = <%d>\n", getpid());
                close(left[1]);
                wait((int*)0);
                exit(1);
            }
        }

        close(left[1]);
        wait((int*)0); // waits for its child to exit
        exit(0);
    }

    int num, prime, ret_r = 0, ret_w = sizeof(int);
    // if there is any number in the left pipe
    // the first number must be a prime
    while ((ret_r = read(left[0], &prime, sizeof(int))) == sizeof(int))
    {
        printf("primes %d\n", prime);
        // if there is still any number in the left pipe
        if ((ret_r = read(left[0], &num, sizeof(int))) == sizeof(int))
        {
            pipe(right);
            if ((pid = fork()) == 0)
            {
                // child
                // the parent's right is the child's left
                // note that the sequence of the next 4 lines cannot be changed 
                // first close the read end of the left pipe
                // cuz it is the parent's left pipe which the child doesn't need
                close(left[0]); 
                // then change the child's left to its right pipe
                // cuz the right pipe right now is the parent's right pipe 
                // which is also the child's left pipe
                left[0] = right[0];
                left[1] = right[1];
                // close the write end of the left pipe 
                close(left[1]);
                // continue the loop
                continue;   
            }
            else if (pid < 0)
            {
                fprintf(2, "fork failed pid = <%d>\n", getpid());
                close(right[0]);
                close(right[1]);
                close(left[0]);
                exit(1);
            }
            else
            {
                // parent
                close(right[0]);
                do {
                    if (num % prime == 0) continue;
                    else if ((ret_w = write(right[1], &num, sizeof(int))) == sizeof(int)) continue;
                    else 
                    {
                        fprintf(2, "write failed pid = <%d>\n", getpid());
                        break;
                    }
                } while((ret_r = read(left[0], &num, sizeof(int))) == sizeof(int));
                close(left[0]);
                close(right[1]);
                wait((int*)0);
                if (ret_r) fprintf(2, "read failed pid = <%d>\n", getpid());
                ret_r == 0 && ret_w == sizeof(int) ? exit(0) : exit(1);
            }
        }
        else break;
    }
    // only the last process in the pipeline will excute here
    close(left[0]);
    if (ret_r) fprintf(2, "read failed pid = <%d>\n", getpid());
    ret_r == 0 ? exit(0) : exit(1);
}

结果如下：

图4-4

图4-5

5 find (moderate)

图5-1

这道题目考察的是对xv6文件系统的理解，比较简单，参考 user/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
82
83
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"


void find(char *dir, char* file)
{   
    char buf[512], *p;

    if (strlen(dir) + 1 + DIRSIZ + 1 > sizeof buf)
    {
        fprintf(2, "find: path too long\n");
        return;
    }

    int fd;
    struct dirent de;
    struct stat st;

    if ((fd = open(dir, O_RDONLY)) < 0)
    {
        fprintf(2, "find: cannot open %s\n", dir);
        return;
    }

    if (fstat(fd, &st) < 0)
    {
        fprintf(2, "find: cannot stat %s\n", dir);
        close(fd);
        return;
    }

    if (st.type != T_DIR)
    {
        fprintf(2, "find: %s is not a directory\n", dir);
        fprintf(2, "Usage: find [directory] <filename>\n");
        close(fd);
        return;
    }

    
    strcpy(buf, dir);
    p = buf + strlen(dir);
    *p++ = '/';

    while (read(fd, &de, sizeof(de)) == sizeof(de))
    {
        // skip invalid dir entry
        if (de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0) continue;

        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;

        if (strcmp(de.name, file) == 0)
            printf("%s\n", buf);
        
        if (stat(buf, &st) < 0)
        {
            fprintf(2, "find: cannot stat %s\n", buf);
            continue;
        }

        if (st.type == T_DIR) find(buf, file);
    }
    close(fd);
    return;
}


int main(int argc, char *argv[])
{
    if (argc != 2 && argc != 3)
    {
        fprintf(2, "Usage: find [directory] <filename>\n");
        exit(1);
    }
    if (argc == 2) find(".", argv[1]);
    else find(argv[1], argv[2]);

    exit(0);
}

结果如下：

图5-2

图5-3

6 xargs (moderate)

图6-1

这道题目的难点主要在于对c语言数组的处理。

大致思路如下：

1.首先将xargs的参数拷贝到数组的前段。

2.然后从标准输入读取一行的内容作为额外参数拼接到数组后面，这里我们一行的内容只作为一个参数处理。

3.fork一个子进程出来调用exec执行命令

4.父进程调用wait等待子进程执行完毕，之后跳转到2继续执行。

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
82
83
84
85
#include "kernel/param.h"
#include "kernel/types.h"
#include "user/user.h"


int main(int argc, char *argv[])
{
    char buf[256];
    char *cmd[MAXARG + 5];
    int args_cnter = 1;
    if (argc == 1)
    {
        // 默认使用echo命令 
        cmd[1] = "echo";
        args_cnter = 2;
    }

    for (; args_cnter < argc; ++args_cnter) 
    {
        // 将参数拷贝到命令数组中
        // shallow copy
        cmd[args_cnter] = argv[args_cnter];
    }


    // b - 每次读取的起始位置 
    // e - 每次读取完成后的最后有效位的下一位 
    // r - 每次读取了多少字节 
    // s - 每行参数的起始 
    // 每次将数据读取到buf[b, e)中 buf[0, b)为上次未处理完的内容 
    int b = 0, e = 0, r = 0, s;
    while ((r = read(0, buf + b, 256 - b)) > 0)
    {
        e = b + r;
        s = 0;
        for (int i = 0; i < e; ++i)
        {
            // 如果遇到了换行符
            if (buf[i] == '\n')
            {
                // 将参数拷贝到数组中
                // deep copy
                buf[i] = 0;
                char *p = (char*) malloc(i - s + 1);

                if (!p)
                {
                    fprintf(2, "malloc failed\n");
                    exit(1);
                }

                memmove(p, buf + s, i - s + 1);
                cmd[args_cnter++] = p;
                // 更新s
                s = i + 1;
                if (fork() == 0)
                {
                    // child
                    cmd[args_cnter] = 0;
                    if (exec(cmd[1], cmd + 1) < 0) {
                        fprintf(2, "exec failed");
                        exit(1);
                    }
                }
                else    
                {
                    // parent
                    wait((int*)0);
                    free(cmd[--args_cnter]);
                }
            }
        }
        // 将未处理完的内容移动到数组首部
        memmove(buf, buf + s, e - s);
        b = e - s;
    }

    if (r < 0) 
    {
        fprintf(2, "read failed\n");
        exit(1);
    }

    exit(0);
}

结果如下：

图6-2

图6-3

7 测试结果

图7-1

8 uptime（easy）

图8-1

1
2
3
4
5
6
7
8
9
#include "kernel/types.h"
#include "user/user.h"


int main(int argc, char *argv[])
{
    printf("uptime<%d>\n", uptime());
    exit(0);
}

9 improve find（easy）

图9-1

这道题目直接参考grep.c，把其中正则表达式匹配的代码拿过来，修改find中判断匹配的条件即可。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"

int match(char*, char*);
void find(char *dir, char* pattern)
{   
    char buf[512], *p;

    if (strlen(dir) + 1 + DIRSIZ + 1 > sizeof buf)
    {
        fprintf(2, "find: path too long\n");
        return;
    }

    int fd;
    struct dirent de;
    struct stat st;

    if ((fd = open(dir, O_RDONLY)) < 0)
    {
        fprintf(2, "find: cannot open %s\n", dir);
        return;
    }

    if (fstat(fd, &st) < 0)
    {
        fprintf(2, "find: cannot stat %s\n", dir);
        close(fd);
        return;
    }

    if (st.type != T_DIR)
    {
        fprintf(2, "find: %s is not a directory\n", dir);
        fprintf(2, "Usage: find [directory] <pattern>\n");
        close(fd);
        return;
    }

    
    strcpy(buf, dir);
    p = buf + strlen(dir);
    *p++ = '/';

    while (read(fd, &de, sizeof(de)) == sizeof(de))
    {
        // skip invalid dir entry
        if (de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0) continue;

        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;

        // if (strcmp(de.name, file) == 0)
        //     printf("%s\n", buf);

        if (match(pattern, de.name)) 
            printf("%s\n", buf);

        if (stat(buf, &st) < 1)
        {
            fprintf(2, "find: cannot stat %s\n", buf);
            continue;
        }

        if (st.type == T_DIR) find(buf, pattern);
    }
    close(fd);
    return;
}


int main(int argc, char *argv[])
{
    if (argc != 2 && argc != 3)
    {
        fprintf(2, "Usage: find [directory] <pattern>\n");
        exit(1);
    }
    if (argc == 2) find(".", argv[1]);
    else find(argv[1], argv[2]);

    exit(0);
}


// Regexp matcher from Kernighan & Pike,
// The Practice of Programming, Chapter 9.

int matchhere(char*, char*);
int matchstar(int, char*, char*);

int
match(char *re, char *text)
{
  if(re[0] == '^')
    return matchhere(re+1, text);
  do{  // must look at empty string
    if(matchhere(re, text))
      return 1;
  }while(*text++ != '\0');
  return 0;
}

// matchhere: search for re at beginning of text
int matchhere(char *re, char *text)
{
  if(re[0] == '\0')
    return 1;
  if(re[1] == '*')
    return matchstar(re[0], re+2, text);
  if(re[0] == '$' && re[1] == '\0')
    return *text == '\0';
  if(*text!='\0' && (re[0]=='.' || re[0]==*text))
    return matchhere(re+1, text+1);
  return 0;
}

// matchstar: search for c*re at beginning of text
int matchstar(int c, char *re, char *text)
{
  do{  // a * matches zero or more instances
    if(matchhere(re, text))
      return 1;
  }while(*text!='\0' && (*text++==c || c=='.'));
  return 0;
}

10 improve shell（easy/moderate）

图10-1

操作系统
#MIT 6.1810
[MIT 6.S081]Lab1 Xv6 and Unix utilities
https://erlsrnby04.github.io/2024/09/21/MIT-6-S081-Lab1-Xv6-and-Unix-utilities/
作者
ErlsrnBy04
发布于
2024年9月21日
许可协议