Lab 1 是让我们在 user 文件夹下编写五个用户程序

Sleep（easy）

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.
这里的目的即是停顿一段时间，时间即是 sleep 后的 ticks 参数
Run the program from the xv6 shell:

1
2
3
4
5
6
$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$

这里只需要使用 sleep 系统调用即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    if (argc != 2) { // 检查参数数量
        exit(1); 
    }
    int ticks = atoi(argv[1]); // 命令行中的数字是字符串，将其转化成int型
    if (ticks < 0) { // 判断时间参数
        exit(1);
    }
    sleep(ticks); // sleep系统调用
    exit(0);
}

在 makefile 中添加应用程序
$U/_sleep
对其进行单独测试

1
$ make GRADEFLAGS=sleep grade

pingpong（easy）

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.
即通过pipe管道实现父子进程的通信

这里需要用到几个系统调用,xv6-book第一章开头有提供系统调用的介绍

  • int pipe(int p[])
  • int write(int fd, char *buf, int n)
  • int read(int fd, char *buf, int n)
    系统调用 描述
    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) 删除一个文件

其中特别注意当使用两个管道进行父子进程通信时,如果管道的写端没有关闭,那么管道中数据为空时对管道的读取将会阻塞.因此,为了避免读端一直阻塞,需要尽快关闭不需要的管道描述符,特别是写端。这样可以让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
56
57
58
59
60
61
62
63
64
#include "kernel/types.h"
#include "user/user.h"

#define RE 0 // pipe read port
#define WR 1 // pipe write port

int main(int argc, char *argv[]) {
    char byte = 'A'; //the byte will be sent
    
    int p_fd[2];
    int c_fd[2];
    pipe(p_fd);
    pipe(c_fd);

    int pid = fork();
    int exit_status = 0;

    if (pid < 0) {
        fprintf(2, "fork() error!\n");
        close(c_fd[RE]);
        close(c_fd[WR]);
        close(p_fd[RE]);
        close(p_fd[WR]);       
        exit(1);
    } else if (pid == 0) { // child process
        close(c_fd[RE]);
        close(p_fd[WR]);

        if (read(p_fd[RE], &byte, sizeof(char)) != sizeof(char)) {
            fprintf(2, "child read() error!\n");
            exit_status = 1;
        } else {
            fprintf(1, "%d: received ping\n", getpid());
        }

        if (write(c_fd[WR], &byte, sizeof(char)) != sizeof(char)) {
            fprintf(2, "child write() error!\n");
            exit_status = 1;
        }

        close(c_fd[WR]);
        close(p_fd[RE]);
        exit(exit_status);
    } else { //parent process
        close(p_fd[RE]);
        close(c_fd[WR]);
        
        if (write(p_fd[WR], &byte, sizeof(char)) != sizeof(char)) {
            fprintf(2, "parent write() error!\n");
            exit_status = 1;
        }
        
        if (read(c_fd[RE], &byte, sizeof(char)) != sizeof(char)) {
            fprintf(2, "parent read() error!\n");
            exit_status = 1;
        } else {
            fprintf(1, "%d: received pong\n", getpid());
        }
        
        close(c_fd[RE]);
        close(p_fd[WR]);        
        exit(exit_status);
    }
}

在 makefile 中添加应用程序

1
$U/_pingpong\

对其进行单独测试

1
$ make GRADEFLAGS=pingpong grade

Primes（Moderate/Hard）

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes.Your solution should be in the file user/primes.c.
参考资料

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

#define RE 0 // pipe read port
#define WR 1 // pipe write port

int lpipe_fir(int lpipe[2], int *dst) { //接受左管道的第一个数字，如果没有返回-1
    if (read(lpipe[RE], dst, sizeof(int)) == sizeof(int)) {
        printf("prime %d\n", *dst);
        return 0;
    }
    return -1;
}

void trans(int lpipe[2], int rpipe[2], int first) { //传递给右管道
    int data;
    while (read(lpipe[RE], &data, sizeof(int)) == sizeof(int)) {
        if (data % first) {
            write(rpipe[WR], &data, sizeof(int));
        }
    }
    close(lpipe[RE]);
    close(rpipe[WR]);
}

void primes(int lpipe[2]) {
    close(lpipe[WR]);
    int first;
    if (lpipe_fir(lpipe, &first) == 0) {
        int fd[2];
        pipe(fd);
        trans(lpipe, fd, first);
        int pid = fork();
        
        if (pid == 0) {
            primes(fd); //递归
        } else {
            close(fd[RE]);
            wait(0);
        }
    }
    exit(0);
}

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

    for (int i = 2; i <= 35; i++) {
        write(init_fd[WR], &i, sizeof(int));
    }
    int pid = fork();

    if (pid == 0) {
        primes(init_fd);
    } else {
        close(init_fd[WR]);
        close(init_fd[RE]);
        wait(0);
    }
    exit(0);
}

在 makefile 中添加应用程序
$U/_primes
对其进行单独测试

1
$ make GRADEFLAGS=pingpong grade

find (Moderate)

基本就是copy 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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

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

    if ((fd = open(path, 0)) < 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;
    }

    if (st.type != T_DIR) {
        fprintf(2, "usage: find <DIRECTORY> <filename>\n");
        return;
    }

    if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
        fprintf(2, "find: path too long\n");
        return;
    }
    strcpy(buf, path);
    p = buf + strlen(buf);
    *p++ = '/'; //p指向最后一个'/'之后

    while (read(fd, &de, sizeof de) == sizeof de) {
        if (de.inum == 0) {
            continue;
        }
        memmove(p, de.name, DIRSIZ); //添加路径名称
        p[DIRSIZ] = 0;               //字符串结束标志
        if (stat(buf, &st) < 0) {
            fprintf(2, "find: cannot stat %s\n", buf);
            continue;
        }
        //不要在“.”和“..”目录中递归
        if (st.type == T_DIR && strcmp(p, ".") != 0 && strcmp(p, "..") != 0) {
            find(buf, target);
        } else if (strcmp(target, p) == 0) {
            printf("%s\n", buf);
        }
    }

    close(fd); 
}


int main(int argc, char *argv[]) {
    if (argc != 3) {
        exit(1);
    }
    find(argv[1], argv[2]);
    exit(0);
}