Lab1

启动xv6(难度：Easy)

https://lmx.gitbook.io/mit-6.s081/

sleep(难度：Easy)

YOUR JOB

实现xv6的UNIX程序sleep：您的sleep应该暂停到用户指定的计时数。一个滴答(tick)是由xv6内核定义的时间概念，即来自定时器芯片的两个中断之间的时间。您的解决方案应该在文件*user/sleep.c*中

// user/ulib.c
int
atoi(const char *s)
{
  int n;

  n = 0;
  while('0' <= *s && *s <= '9')
    n = n*10 + *s++ - '0';
  return n;
}

// kernel/sysproc.c
uint64
sys_sleep(void)
{
  int n;
  uint ticks0;

  if(argint(0, &n) < 0)
    return -1;
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(myproc()->killed){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  return 0;
}
// kernel/sysproc.h
#define SYS_sleep  13

// user/user.h提供了sleep的声明以便其他程序调用,用汇编程序编写的user/usys.S可以帮助sleep从用户区跳转到内核区。

实现代码：

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

int 
main(int args,char *argv[]) 
{
    if (args < 2) {
        fprintf(2,"Usage: sleep time\n");
        exit(1);
    }

    int t;
    t = atoi(argv[1]);
    sleep(t);

    exit(0);
}

测试：

./grade-lab-util sleep

# output:
== Test sleep, no arguments == sleep, no arguments: OK (3.4s) 
== Test sleep, returns == sleep, returns: OK (1.0s) 
== Test sleep, makes syscall == sleep, makes syscall: OK (1.1s) 

pingpong（难度：Easy）

YOUR JOB

编写一个使用UNIX系统调用的程序来在两个进程之间“ping-pong”一个字节，请使用两个管道，每个方向一个。父进程应该向子进程发送一个字节;子进程应该打印“<pid>: received ping”，其中<pid>是进程ID，并在管道中写入字节发送给父进程，然后退出;父级应该从读取从子进程而来的字节，打印“<pid>: received pong”，然后退出。您的解决方案应该在文件*user/pingpong.c*中。

请使用两个管道

不用两个管道会报莫名其妙的错误(我还是看不透pipe)

p[0] 是管道的读端，p[1]是管道的写端

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

char buf[1024];
int
main(int argc, char const *argv[])
{
    if (argc > 1) {
        fprintf(2,"Usage: pingpong\n");
        exit(1);
    }
    // cp child pipe，pp parent pipe
    int cp[2],pp[2];
    // cbuf：child buf
    char cbuf[10],pbuf[10];
    
    // Initialize the read(p[0]) and write(p[1]) side of the pipeline
    pipe(cp);
    pipe(pp);

    int rc = fork();
    // fork 会让父子复制文件描述符，管道fork之后可以看成连接父子，四个端口，所以你会看到下面重复close
    if (rc==0) {
        //entry child
        // close the write side when reading
        close(cp[1]);
        // receive parent ping
        int r = read(cp[0],cbuf,1);
        if (r > 0) {
            printf("%d: received ping\n",getpid());
        }
        close(cp[0]);
        // send pong
        // Close the read side of parent when writing
        close(pp[0]);
        write(pp[1],"c",1);
        close(pp[1]);
        exit(0);
    } else if (rc > 0) {
        // entry parent
        // Close the read side of child pipe when writing
        close(cp[0]);
        write(cp[1],"p",1);
        // close the write side after writing
        close(cp[1]);
        // receive pong
        wait(0);
        // close the write side when reading
        close(pp[1]);
        int r = read(pp[0],pbuf,1);
        if (r > 0) {
            printf("%d: received pong\n",getpid());
        }
        // close the read side after reading
        close(pp[0]);
    } else {
        fprintf(2,"fork error\n");
        exit(1);
    }

    exit(0);
}

测试：

root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util pingpong

make: 'kernel/kernel' is up to date.
== Test pingpong == pingpong: OK (0.9s) 

Primes(素数，难度：Moderate/Hard)

tasks:

YOUR JOB

使用管道编写prime sieve(筛选素数)的并发版本。这个想法是由Unix管道的发明者Doug McIlroy提出的。请查看这个网站，该网页中间的图片和周围的文字解释了如何做到这一点。您的解决方案应该在*user/primes.c*文件中。

感觉上面那题会了的话，这题比上一题简单

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

int 
main(int argc, char const *argv[])
{
    int p[2],nums[36];
    int index = 0;
    for (int i=2;i<36;i++) {
        nums[index++] = i;
    }

    while (index > 0)
    {
        // p[0] read , p[1] write
        pipe(p);
        int rc = fork();
        if (rc > 0) {
            // entry parent
            close(p[0]);
            for(int i=0;i<index;i++) {
                write(p[1],&nums[i],sizeof(int));
            }
            close(p[1]);
            // 主进程一直在这里等着子进程完成，子进程一完成就会进入
            wait(0);
            // 如果这里不exit的话，当打完所有的素数后就会陷入死循环
            exit(0);
        } else if (rc == 0) {
            close(p[1]);
            index = -1;
            int val,prime;
            prime = -1;
            while (read(p[0],&val,sizeof(int)) > 0)
            {
                if (index < 0) {
                    prime = val;
                    index++;
                }else if (val%prime!=0) {
                    nums[index++] = val;
                }
            }
            close(p[0]);
            printf("prime %d\n",prime);
        }
    }
    
    exit(0);
}

测试：

root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util primes
make: 'kernel/kernel' is up to date.
== Test primes == primes: OK (1.5s) 

关于上面的主线程为什么要exit，有一个比较坑的地方：

看下面程序:

#include<stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char const *argv[])
{
    int index = 0;
    while (index <= 3)
    {
        printf("entry while\n");
        int rc = fork();
        if (rc == 0) {
            printf("child pid:%d\n",getpid());
            index++;
            printf("%d \n",index);
            sleep(1);
        }else {
            printf("parent pid:%d\n",getpid());
            wait(0);
            exit(0);
        }
    }
    printf("break while\n");
    exit(0);
}
// 它会进入死循环，然后一直 输出
/*
entry while
parent pid:24154
child pid:24167
3 
*/

• 首先fork出来的是进程，父和子的index是不相通的

• 当子进程的index超过3，子进程就会结束

• 这里意思就是在3之前主进程都在wait(),3的时候子进程会exit，这时候index为2的是它的父进程，而这个2的进程同时也是1的子进程，所以那个最初的进程一直都不会退出，然后一直卡在index为2的那个线程那里，一直fork。

• 当到子进程的index为2时，他成为父进程，fork一个子进程，子进程复制变量，index=2，index++ 变成3，然后该子进程退出。但是此时父进程的index是2，它还会继续进入循环，又fork一个子进程，子进程再复制变量，然后自增，周而复始...这样就一直卡在3这里了

• 所以必须有个 exit(0),在他完成所有的子任务第一遍时，也就是打印第一遍3的时候就退出程序，这样就完成了任务了

• 再看上面的通关代码，也是如此，如果没有exit(0),就会一直卡在输出31的地方，因为它也会在那时候一直fork一个子进程，然后退出然后再fork再退出再fork。

• 反正就是要记得，fork会复制变量，但是父子的变量是不同的，子进程的这个变量改变不会影响父进程的值。也就是fork是变量复制但不共享

find（难度：Moderate）

YOUR JOB

写一个简化版本的UNIX的find程序：查找目录树中具有特定名称的所有文件，你的解决方案应该放在*user/find.c*

刚开始不知道他要实现啥，写完只通过了第一个test，但是输出显示第二个test我失败是miss了一些输出，那我按它的输入去debug，发现我没有递归进子目录....蠢得可以，又改了一下才ok，所以还是要好好思考...

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
void find(char* path) {
    // 这里得代码主要是参照 ls.c 的，lab里面提示的，应该不算作弊(bushi
    int fd;
    char buf[512];
    char *p;
    struct dirent de;
    struct stat st;

    if ((fd=open(path,0))<0)
    {
        fprintf(2, "find: %s: No such file or directory\n", path);
        return;
    }
    if(fstat(fd, &st) < 0){
        fprintf(2, "find: %s:cannot stat\n", path);
        close(fd);
        return;
    }

    switch (st.type)
    {
    case T_FILE:
        // 如果是文件直接输出就可了
        printf("%s\n",path);
        break;
    case T_DIR:
        // 如果是dir处理起来麻烦点，但是不难，就是要记得如果子目录也是dir的话也要进行递归
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: path too long\n");
            return;
        }
        strcpy(buf, path);
        p = buf+strlen(buf);
        *p++ = '/';
        while (read(fd, &de, sizeof(de)) == sizeof(de))
        {
            if(de.inum == 0) {
                continue;
            }
            // 因为de.name的定义是 char name[DIRSIZ]; 
            // 这里会直接把p的值设为de.name
            // 但是前面已经*p++='/'了，所以de.name会添加在buf的'/'后面
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if(stat(buf, &st) < 0){
                printf("find: cannot stat %s\n", buf);
                continue;
            }
            if(st.type==T_FILE){
                printf("%s\n",buf);
            }else if (st.type==T_DIR&&strcmp(de.name,".")!=0&&strcmp(de.name,"..")!=0){
                printf("%s\n",buf);
                find(buf);
            }else {
                printf("%s\n",buf);
            }
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[])
{
    // the solution of find
    if(argc == 1) {
        find(".");
        exit(0);
    }
    
    // 有几个要查找得参数就查几次
    for(int i = 1;i < argc;i++) {
        find(argv[i]);
    }
    exit(0);
}

test:

./grade-lab-util find 

make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (2.1s) 
== Test find, recursive == find, recursive: OK (1.8s) 

不知道有没有更快得实现，期待一手

xargs (难度： Moderate)

前面的find实现有坑，我的find理解和出题人的find理解不同

在ubuntu下的 find . b 不是先 find . 再 find b吗，我试了一下就是这样啊，但是这道题目要求find . b 是在 . 路径下寻找 b 的目录，这让我不得不回去改了一下find的代码，先贴上改完的find，被迫无奈：

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

char* filename;

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

    if ((fd=open(path,0))<0)
    {
        fprintf(2, "find: %s: No such file or directory\n", path);
        return;
    }
    if(fstat(fd, &st) < 0){
        fprintf(2, "find: %s:cannot stat\n", path);
        close(fd);
        return;
    }

    switch (st.type)
    {
    case T_FILE:
        if(bool == 0) {
            printf("%s\n",buf);
        }else if (bool == 1 && strcmp(filename,de.name)==0){
            printf("%s\n",buf);
        }
        break;
    case T_DIR:
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: path too long\n");
            return;
        }
        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;
            if(stat(buf, &st) < 0){
                printf("find: cannot stat %s\n", buf);
                continue;
            }
            if(st.type==T_FILE){
                if(bool == 0) {
                    printf("%s\n",buf);
                }else if (bool == 1 && strcmp(filename,de.name)==0){
                    printf("%s\n",buf);
                }
            }else if (st.type==T_DIR&&strcmp(de.name,".")!=0&&strcmp(de.name,"..")!=0){
                if (bool == 0) {
                    printf("%s\n",buf);
                    find(buf,0);
                }else if(bool == 1) {
                    if (strcmp(filename,de.name)==0) {
                        printf("%s\n",buf);
                    }
                    find(buf,1);
                }
            }
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[])
{
    // the solution of find
    if(argc == 1) {
        find(".",0);
        exit(0);
    }

    if(argc == 3 && strcmp(argv[1],".")==0) {
        filename = (char *)malloc(sizeof(argv[2]));
        filename = argv[2];
        find(".",1);
        exit(0);
    }
    
    for(int i = 1;i < argc;i++) {
        find(argv[i],0);
    }
    exit(0);
}

通过实现：

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

const int MAXREAD = 1024;

int main(int argc, char *argv[])
{
    // stdout 0
    char* params[MAXARG];
    int index = 0;
    for(int i=1;i<argc;i++){
        params[index++] = argv[i];
    }

    char buf[MAXREAD];
    int bytes = 0;
    while ((bytes=read(0,&buf,MAXREAD))>0)
    {
        char *arg = (char *)malloc(sizeof(buf));
        int argi = 0;
        // 因为下面要执行 exec，所以需要fork
        int rc = fork();
        if(rc==0) {
            for(int i=0;i<bytes;i++) {
                // 如果碰到 \n or space 说明一个单词结束了，这时候添加进params然后重置初始化工作
                if(buf[i]=='\n'||buf[i]==' ') {
                    // 结束标志,不加也行
                    arg[argi] = '\0;
                    argi = 0;
                    params[index++] = arg;
                    arg = (char *)malloc(sizeof(arg));
                }else {
                    arg[argi++]=buf[i];
                }
            }
            exec(argv[1],params);
        }else {
            wait(0);
        }
    }
    
    exit(0);
}

test:

root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util xargs
make: 'kernel/kernel' is up to date.
== Test xargs == xargs: OK (2.0s) 
    (Old xv6.out.xargs failure log removed)

root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util find
make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (1.2s) 
== Test find, recursive == find, recursive: OK (1.1s)