Lab 1

find 实现

这个小节的重点在于读懂 user/ls.c ，读懂之后，实现就很简单了。

ls 阅读

总共三部分

  • main
  • fmtname
  • ls

main 用来读取命令行输入以及做一些判断（这里我才发现原来 ls 可以带多个参数。。。）

fmtname 函数用于截取路径名中的最后一个 ‘/‘ 后的内容。

ls 则是逻辑核心，它涉及到两个结构体：

  • dirent

    • ```C
      #define DIRSIZ 14
      struct dirent {

      ushort inum; // inode num
char name[DIRSIZ]; // directory entry name

      }

      1
      2
      3
      4
      5
      6
      7

      文件夹是一种文件，它其实是 dirent 数组。而每一个 dirent 又代表一个文件或一个文件夹。可以从这一段代码中看出来：

      ```C
      while(read(fd, &de, sizeof(de)) == sizeof(de)) {
          ...
      }

      其中 fd 是指向文件夹的文件描述符，ls 代码中直接用读文件的方式，以 dirent 为单位，一个一个地读取，可见文件夹中的数据就是一个一个的 dirent 。结束的条件是，当读出的数据大小不等于 dirent 结构体大小。

    • 该结构体由 inode 节点号与文件夹条目名字构成。

  • stat

    • stat 就是文件状态结构体，里面存储了文件的一些基本信息。例如

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      struct stat {
                     dev_t     st_dev;         /* ID of device containing file */
                     ino_t     st_ino;         /* Inode number */
                     mode_t    st_mode;        /* File type and mode */
                     nlink_t   st_nlink;       /* Number of hard links */
                     uid_t     st_uid;         /* User ID of owner */
                     gid_t     st_gid;         /* Group ID of owner */
                     dev_t     st_rdev;        /* Device ID (if special file) */
                     off_t     st_size;        /* Total size, in bytes */
                     blksize_t st_blksize;     /* Block size for filesystem I/O */
                     blkcnt_t  st_blocks;      /* Number of 512B blocks allocated */
          			...
                 };

      可以用 c 库函数 fstat 来直接获取 stat 结构体信息。

      ls 用 stat 结构体和 fstat 函数来判断某个 fd 是对应文件还是文件夹一次做出不同的操作。

      实现 find 的过程中需要注意的地方

实现 find 的过程中需要注意的地方

  • 使用递归的方式去遍历所有的文件夹，出口条件就是 st.type == T_FILE

  • 因为一个文件夹下有 . 和 .. 文件，注意不能对这两个文件进行递归，不然就会一直递归下去直到文件描述符耗尽

  • 在出口返回的时候记得 close(fd) 来交还文件描述符资源。

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

 void find(const char *path, const char *filename) {
     char buf[512], *p;
     int fd;
     struct dirent de;
     struct stat st;

     if ((fd = open(path, 0)) < 0) {
         fprintf(2, "find, cannot open %s\n", path);
         return;
     }
     if (fstat(fd, &st) < 0) {
         fprintf(2, "find: cannot stat %s\n", path);
         close(fd);
         return;
     }
     if (st.type != T_DIR) {
         close(fd);
         return;
     }
     strcpy(buf, path);
     p = buf + strlen(buf);
     if (*(p-1) != '/')
         *p++ = '/';
     while(read(fd, &de, sizeof(de)) == sizeof(de)) {
         if (de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
             continue;
         if (strcmp(de.name, filename) != 0) {
             memmove(p, de.name, DIRSIZ);
             p[DIRSIZ] = 0;
             find(buf, filename);
         }
         else {
             memmove(p, de.name, DIRSIZ);
             printf("%s\n", buf);
         }

     }
     close(fd);
 }
 int main(int argc, char* argv[]) {
     if (argc != 3) {
         fprintf(2, "usage: %s path filename", argv[0]);
         exit(1);
     }
     find(argv[1], argv[2]);
     exit(0);
 }

primes

这道题目是想通过多进程的方式并发筛选质数。算法的思想可以看这个concurrent primes sieve。问题是如何去实现呢？

首先遇到的问题就是，如何创建一个子进程之后再让该子进程创建自己的子进程，不断递归下去。这个其实稍微思考下就能想到，可以用以下伪代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (;;) {
    if (0 == fork()) // a
    {
        // do something ...
    }
    else // b
    {
        // do something ...
        break;
    }
}
wait(0);
exit(0);

可以看到，子进程经过一次循环并执行 fork 后就变成父进程了，就好像有儿子之后就变成老子了。。。而作为父进程，完成了自己的使命（传宗接代）就 break 掉等待着退出。

仔细对照算法，发现只有第一个进程仅仅有父进程身份（看作类型1），最后一个进程仅仅有子进程身份（看作类型3），夹在中间的进程既是父进程又是子进程（看作类型2）。因此我们只需要把类型2的进程作为子进程时需要实现的逻辑替换 a 中的 do something，它作为父进程时需要实现的逻辑替 b 中的 do something。

然后就是加判定条件，当遇到类型1或类型3的进程时该做的逻辑放到对应的地方就可以了。

类型2 进程的逻辑

  • 作为父进程时

    此时该进程必定有自己子进程，并且已经有管道连接自己的子进程了。它需要读取它的父进程传给它的数据并做相应的处理后传给它的子进程。

  • 作为子进程时

    此时该进程还没有调用 fork。它从它的父进程读取第一个数据（即质数）并把它打印出来，如果读取失败表示父进程关闭了管道的写端，此时说明整个逻辑都已经结束了

对输入管道和输出管道定义如下：

对于一个进程来说，它读取数据对应的管道叫输入管道，它往外写数据对应的管道叫输出管道。

可以用以下伪代码表示上面的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int num;
int prime;
if (0 == fork()) // 子进程身份时
{
    if (0 == read(输入管道读端, &num, sizeof int)) {
        close(输入管道读端);
        exit(0);
    }
    prime = num;
    printf("prime %d\n", prime);
}
else // 父进程身份时
{
    while(0 != read(输入管道读端, &num, 1)) {
        if (num % prime != 0)	write(输出管道写端, &num, sizeof int);
    }
    close(输入管道读端);
    close(输出管道写端);
    break;
}

类型3 进程的逻辑

类型3 进程只有子进程身份，因此类型2 逻辑中的子进程身份时的代码也是符合的。

类型1 进程的逻辑

类型1 进程只有父进程身份，它无法从它的父进程中读取数据，因此要在上面代码的基础上加一些判断条件。第一个进程是吧 2~35 的数字传入子进程，因此便有以下伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
···
else // 父进程身份时
{
    if (!hasFather) // 如果该进程没有父进程,即类型1 进程
    {
        for (int i = 0;i < 34;++i)
        {
            num = i + 2;
            write(输出管道写端, &num, sizeof int);
        }
        close(输出管道写端);
    }
    else
    {
        while(0 != read(输入管道读端, &num, 1)) {
        	if (num % prime != 0)	write(输出管道写端, &num, sizeof int);
    	}
        close(输入管道读端);
    }
    close(输出管道写端);
    break;
}

用管道串起来

最后一步就是在上面的基础上，要用管道把所有进程串起来，样子就像数据结构里的链表一样。。。。每一个进程应该要记住两个管道，一个是输入管道，一个是输出管道。

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
int inpipefd[2]; // 输入管道
int outpipefd[2]; // 输出管道
inpipefd[0] = -1; // 用于区分类型1 进程

for (;;) {
    pipe(outpipefd); // 父进程创建输出管道
    if (0 == fork()) // fork 之后子进程要关闭 2 个没用的文件描述符，各自在 outpipefd[1] 和 inpipefd[0] 内
    {
        if (inpipefd[0] != 0) // 关闭父进程输入管道的读端（除类型1 进程外）
            close(inpipefd[0]);
        // 父进程的输出管道是子进程的输入管道
        inpipefd[0] = outpipefd[0];
        inpipefd[1] = outpipefd[1];
        close(inpipefd[1]); // 关闭输入管道的写端
        // do something ...
    }
    else // b
    {
        close(outpipefd[0]); // 关闭输出管道读端
        // do something ...
        break;
    }
}
wait(0);
exit(0);
最后代码如下：
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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main() {
    int hasFather = 0;
    int prime;
    int inpipefd[2];
    int outpipefd[2];
    inpipefd[0] = -1;
    for (;;) {
        int num;
        pipe(outpipefd);
        if (0 == fork()) {
            if (inpipefd[0] != -1)
                close(inpipefd[0]);
            inpipefd[0] = outpipefd[0];
            inpipefd[1] = outpipefd[1];
            close(inpipefd[1]);
            hasFather = 1;
            if (0 == read(inpipefd[0], &num, sizeof(int))) {
                close(inpipefd[0]);
                exit(0);
            }
            prime = num;
            printf("prime %d\n", prime);
        }
        else {
            close(outpipefd[0]);
            if (!hasFather) {
                for (int i = 0;i < 34;++i) {
                    num = i + 2;
                    write(outpipefd[1], &num, sizeof(int));
                }
            }
            else {
                while (0 != read(inpipefd[0], &num, sizeof(int))) {
                    if (num % prime != 0) write(outpipefd[1], &num, sizeof(int));
                }
                close(inpipefd[0]);
            }
            close(outpipefd[1]);
            break;
        }
    }
    wait(0);
    exit(0);
}

xargs 实现

lab 1 实现只要求我们实现一个简单版的 xargs，它包含基本功能和一个 [-n] 选项功能：

  • 基本功能：从标准输入读取数据，并以 ' ' 和 '\n' 为分隔符，得到参数元素列表，用伪代码表示就是：

    • 1
      2
      inputChar = read(stdin)
      argvs = inputChar.split([' ', '\n'])

    • 例如：

      1
      2
      3
      4
      5
      6
      $ cat test
      a b c
      d e f g
      $ cat test | xargs
      a b c d e f g
      $

  • [-n num] 选项功能就是在基本功能的基础上，xargs 限定每行 num 个元素：

    • 例如：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      $ cat test
      a b c
      d e f g
      $ cat test | xargs -n 1
      a
      b
      c
      d
      e
      f
      g
      $

xargs 处理逻辑

  1. 判断自身选项是否含有 [-n] 选项
  2. 获取要执行的 cmd 以及对应的 argv
  3. 获取从标准输入读取的参数 inargv
  4. 根据是否含有 [-n] 选项进行一次或多次调用 fork 与 exec
具体代码如下：
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
#include "kernel/types.h"
 #include "kernel/stat.h"
 #include "user/user.h"
 #include "kernel/fs.h"
 #include "kernel/param.h"
 char* ignoreSpaceAndNewline(char* p) {
     while(*p != 0 && (*p == ' ' || *p == '\n')) {++p;}
     return p;
 }
 char* findNextSpaceOrNewline(char* p) {
     while(*p != 0 && *p != ' ' && *p != '\n') {++p;}
     return p;
 }
 void doit(int argc, char* argv[]) {
     if (0 == fork())
         exec(argv[0], argv);
     else
         wait(0);
 }
 int getALine(char *buf) { // 以\n\0结尾
     char ch = 0;
     int i = 0;
     while(ch != '\n') {
         if (0 == read(0, &ch, 1))
             break;
         buf[i++] = ch;
     }
     buf[i] = 0;
     return i;
 }
 int getArgsFromStdin(char **argv) {
     int cnt = 0;
     int num;
     char buf[512];
     while(0 != (num = getALine(buf))) {
         buf[num - 1] = 0; // 用 0 把 \n 替换掉
         char* p;
         p = buf;
         while (*p) {
             p = ignoreSpaceAndNewline(p);
             if (*p == 0)    break;
             char *n = findNextSpaceOrNewline(p);
             *n = 0;
             char* tmp = (char*)malloc(strlen(p) + 1);
             argv[cnt++] = tmp;
             memcpy(tmp, p, strlen(p) + 1);
             p = n + 1;
         }
     }
     return cnt;
 }
 int main(int argc, char* argv[]) {
     int oneCol = 0;
     if (argc > 2 && strcmp(argv[1], "-n") == 0 && 0 == strcmp(argv[2], "1"))
         oneCol = 1;
     int i = (oneCol == 0 ? 1 : 3);
     char *cargv[MAXARG]; // cmd args
     memset(cargv, 0, MAXARG);
     int j = 0;
     for (;i < argc;++i)
         cargv[j++] = argv[i];

     char* inargv[MAXARG];// args from stdin
     memset(inargv, 0, MAXARG);
     int cnt = getArgsFromStdin(inargv);

     if (oneCol == 0) {
         for(int k = 0;k < cnt;++k)
             cargv[j++] = inargv[k];
         doit(j, cargv);
     }
     else {
         for (int k = 0;k < cnt;++k) {
             cargv[j] = inargv[k];
             doit(j + 1, cargv);
         }
     }
     for (int i = 0;i < cnt;++i)
         free(inargv[i]);
     exit(0);
 }