mit6.1810 fall 2024 project1

引言

最近在学习mit的操作系统课程，本系列博客主要记录课程项目实现的过程及一些思考过程。对应课程网址如下6.1810 / Fall 2024

sleep(easy)

第一个任务实现用户下的sleep程序，只需调用sleep系统调用即可。sleep.c文件实现如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"


int main(int argc, char** argv) {
    if (argc != 2) {
        fprintf(2,"Usage: sleep time(s)...");
        exit(1);
    }

    int time = atoi(argv[1]);

    sleep(time);
    exit(0);
}

pingpong(easy)

前置知识

实验前准备：理解pipe的使用，会linux下pipe系统调用即可。

实现过程

本任务主要实现了一个父子进程通过管道来进行通信，pingpong.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


#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"


int main(int argc, char** argv) {
    int pipefd[2];      // 用于父进程向子进程发送一字节数据
    int pipefd2[2];     // 用户子进程对父进程的回复
    pipe(pipefd);
    pipe(pipefd2);

    if (0 != fork()) {
        close(pipefd[0]);
        close(pipefd2[1]);
        char buf = 'a';
        write(pipefd[1],&buf,1);
        read(pipefd2[0],&buf,1);
        printf("%d: received pong\n",getpid());
        close(pipefd[1]);
        close(pipefd2[0]);
        exit(0);
    } else {
        close(pipefd[1]);
        close(pipefd2[0]);
        char buf = 'a';
        read(pipefd[0],&buf,1);
        printf("%d: received ping\n",getpid());
        write(pipefd2[1],&buf,1);
        close(pipefd[0]);
        close(pipefd2[1]);
        exit(0);
    }
}

primes(moderate)/(hard)

前置知识

前置知识：理解fork系统调用的使用，会linux下fork系统调用即可。

实现过程

虽然本实验标注了hard，但是主要还是理清筛选素数的过程，理清了过程很快也就能写出来了。首先要理解埃氏筛的过程。埃氏筛是通过每次过滤已经确定的最后一个素数的所有倍数，来完成素数的筛选。

程序一开始的父进程只需要通过管道向子进程传递所有范围数字即可。
其他进程用于接受父进程的数据来进行过滤，并将过滤后的数据再传给子进程
- 子进程的过滤及传递过程都是通过primes函数实现，需要接受父进程创建的管道的读端fd作为参数，来接受父进程发送的数据。
- 同时需要再primes创建一个新的管道并进行fork系统调用，用于该进程过滤后将数据发送给创建的子进程。
下面的任务就是确定每一个进程需要过滤哪些数据
- 子进程首先会接受父进程发送的第一个数cur，这个第一个cur就是当前确认的素数，进行打印，然后根据这个数cur进行过滤，如果后面接受的父进程的数字不是这个cur的倍数，就可以发送给其子进程；是cur的倍数不发送，完成过滤。
- 到最后一定是某个子进程只接受了其父进程一个数cur,接受完第一个数后直接关闭文件描述符，其子进程调用read返回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
50
51
52
53
54
55


#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

void primes(int) __attribute__((noreturn));

void primes(int in_fd) {
    int pipefd[2];
    pipe(pipefd);
    int cur;
    int n = read(in_fd, &cur, sizeof(int));     // 先读确定本次输出
    if (0 == n) {                               // 如果父进程没有发送任何数据
        close(in_fd);
        close(pipefd[0]);
        close(pipefd[1]);
        exit(0);
    } 

    if (fork() != 0) {
        close(pipefd[0]);
        printf("prime %d\n",cur);
        int tmp;
        while(0 != read(in_fd, &tmp, sizeof(int))) {        // 循环获取父进程发送的数据
            if (tmp % cur != 0) {
                write(pipefd[1],&tmp, sizeof(int));
            }
        }
        close(pipefd[1]);
        close(in_fd);
        wait(0);
    } else {        // 子进程只需要保留接受读取父进程数据的fd即可
        close(pipefd[1]);
        close(in_fd);       
        primes(pipefd[0]);                      // 递归调用子进程
    }
    exit(0);
}

int main(int argc, char** argv) {
    int pipefd[2];
    pipe(pipefd);
    
    if (fork() != 0) {      // 主线程将2-280所有数据放入管道左端
        close(pipefd[0]);
        for (int i = 2; i <= 280; ++i) {
            int tmp = i;
            write(pipefd[1],&tmp,sizeof(int));
        }
        close(pipefd[1]);
        wait(0);
    } else {                
        close(pipefd[1]);
        primes(pipefd[0]);
    }
}

find(moderate)

本实验主要实现查找指定目录树中特定名称的所有文件

前置知识

前置知识，学习user/ls.c中目录读取的内容
fstate根据指定fd获取文件对应信息存放在struct stat数组中
while(read(fd,&de,sizeof(de))) // 循环读取文件夹中的每一项，放到de中，主要存储文件名

 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


// user/ls.c中关键步骤
void
ls(char *path)
{
  char buf[512], *p;
  int fd;
  struct dirent de;
  struct stat st;
    
   // struct dirent {
   //   ushort inum;
   //   char name[DIRSIZ];
   // };

   // struct stat {
   //   int dev;     // File system's disk device
   //   uint ino;    // Inode number
   //   short type;  // Type of file
   //   short nlink; // Number of links to file
   //   uint64 size; // Size of file in bytes
   // };


  if((fd = open(path, O_RDONLY)) < 0){	// 打开文件
    fprintf(2, "ls: cannot open %s\n", path);
    return;
  }

  if(fstat(fd, &st) < 0){		// 获取文件信息
    fprintf(2, "ls: cannot stat %s\n", path);
    close(fd);
    return;
  }

  switch(st.type){				// 判断文件类型，根据不同类型进行不同操作
  case T_DEVICE:
  case T_FILE:					// 设备文件或普通文件直接输出对应信息 ls 文件
    printf("%s %d %d %d\n", fmtname(path), st.type, st.ino, (int) st.size);
    break;

  case T_DIR:					// ls 目录
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("ls: path too long\n");
      break;
    }
    strcpy(buf, path);
    p = buf+strlen(buf);
    *p++ = '/';
    while(read(fd, &de, sizeof(de)) == sizeof(de)){	// 循环读取文件夹里的每一个文件
      if(de.inum == 0)
        continue;
      memmove(p, de.name, DIRSIZ);		// 拼接文件路径
      p[DIRSIZ] = 0;					// 字符串末尾'\0'
      if(stat(buf, &st) < 0){			// 获取文件信息
        printf("ls: cannot stat %s\n", buf);
        continue;
      }
      printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, (int) st.size);
    }
    break;
  }
  close(fd);
}

实现过程

学会了ls中的相关操作，就可以来完成find操作了
find操作主要是在文件树中进行一个深度优先遍历(dfs)来查找，找到对应文件信息符合要求就可以进行打印
- 前面模仿ls中的操作来打开对应的目录，注意find命令接受的第一个参数必须是文件夹路径
- while循环根据每一个子文件名(完整路径的文件名，需路径拼接)调用sate来获取文件信息，路径拼接和ls中一样
  - 注意判断子文件名(非完整路径，无需拼接)要排除".“和”.."
- 子文件还是目录，进行递归调用即可；是文件比较是否是要查找的，是就输出即可。

find.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


#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"

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

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

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

    if (T_DIR != st.type) {
        char err_msg[128] = "you must find in directory!";
        write(3, err_msg, strlen(err_msg) + 1);
    }


    if(strlen(dir_path) + 1 + DIRSIZ + 1 > sizeof(buf)) {
        printf("find: path too long\n");
        close(fd);
        exit(-1);
    }
	
    // 找dir_path中名字为file_name的文件
    strcpy(buf,dir_path);
    p = buf + strlen(buf);
    *p++ = '/';
    while(read(fd, &de, sizeof(de)) == sizeof(de)) {
        if (de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0) {
            continue;
        }
        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;
        
        if (stat(buf, &st) < 0) {
            printf("find: cannot stat %s\n",buf);
            continue;
        }

        if (T_DIR == st.type) {
            find(buf, file_name);
        } else {
            if (strcmp(de.name,file_name) == 0) {
                printf("%s\n",buf);
            }
        }
    }
}


int main(int argc, char** argv) {
    if (argc < 3) {
        char err_msg[32] = "argv error";
        write(3, err_msg, strlen(err_msg) + 1);
        exit(0);
    }

    find(argv[1], argv[2]);
}

xargs(moderate)

前置知识

理解文件重定向，以及fork 和 exec中间进行文件重定向的操作。这一块xv6 book中应该有很好的解释。
你需要实现xargs.c文件，因此你需要知道操作系统是如何调用你写的这个程序
理解匿名管道的调用过程，在echo hello too | xargs echo bye 中操作系统是如何执行xargs程序的

在user/sh.c中找到下面这些代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 一些数据结构
struct pipecmd {
  int type;
  struct cmd *left;
  struct cmd *right;
};

struct cmd {
  int type;
};

在这个实验里，我们只需要知道sh根据用户输入的命令，将命令解析为struct cmd结构体
- 当cmd是一个pipecmd的时候，里面有左右两个cmd分别代表了管道|左右两个命令
  - 如echo hello too | xargs echo bye 中， cmd->left 对应echo hello too解析出来的命名，cmd->right 对应 xargs echo bye 解析出来的命令。
- 随后会调用fork函数来进行重定向

 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


void runcmd(struct cmd *cmd) {
	switch(cmd->type){		
    ......
            
        case PIPE:
        pcmd = (struct pipecmd*)cmd;		// 恩哼？有点像多态
            								// sh.c中还有很多struct othername_cmd{}的结构体
            								// 只需要保证前四个字节都是用来标识type类型，我们就可以强制类型转换
            								// 将公共sturct cmd转换为你所需要的struct类型
        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(0);
        wait(0);
        break;  
            
    ......
    }
}

理解了过程，就可以知道xargs程序的执行会将左命令生成的标准输出追加到其指定要执行程序的参数后面

实现过程

1

find . b | xargs grep hello

以上面的命令为例，对于find . b 找到的每一个文件，都要指定一次 grep hello b，因此xargs是实现可以如下所示
首先循环标准输入，解析标准输入，当标准输入已经读完一行就可以开始执行grep命令了
- 调用fork创建子进程，子进程将获得的那一行标准输入添加到grep的参数后面，中调用exec系统调用执行grep命令
- 父进程用于恢复之前读取的buf缓存

xargs.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


#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"
#include "kernel/param.h"

int main(int argc, char** argv) {
    char buf[1024] = {0};
    int offset = 0;
    while(read(0,buf + offset,1)) {
        int is_end = 0;
        if (buf[offset] == '\n' || buf[offset] == '\0') {
            if (buf[offset] == '\0') {
                is_end = 1;
            }
            buf[offset] = '\0';
            // buf中已经读取了一行数据，子进程将buf追加到参数中去，执行exec
            if (0 != fork()) {
                wait((void*) 0);
                offset = 0;
                memset(buf,0,sizeof(buf));
                continue;
            } else {
                char* new_argv[MAXARG];
                int index = 0;
                new_argv[index++] = argv[1];
                for (int i = 2; i < argc; ++i) {
                    new_argv[index++] = argv[i];
                }
                new_argv[index++] = buf;
                new_argv[index] = (void*) 0;
                exec(argv[1], new_argv);
                exit(0);
            }
        } 
        if (is_end == 1) {
            break;
        }
        ++offset;
    }
}