MIT6.S081

很早就听说MIT6.S081的课程比较经典了，所以从上周末就开始学习MIT6.S081的lecture,目前刚学习完lecture 1，并且成功完成了lab1，不得不说lab太花费时间了，lab设置的非常好，难度适中，有挑战性与趣味性并存，非常感谢这么好与经典的课程，不过不得不说因为确实平时没有时间，又要照顾家庭，又要上班，只能利用周末和晚上的时间抓紧来学习和完成这些lab的代码了，每次都需要花时间调试代码调试很长时间，目测后面的挑战题目更难。MIT的课程难度一向很大，难怪能够培养出很多非常优秀和出色的工程师。

lab环境：
所有的lab都是基于qemu的模拟硬件环境的，它的所有的lab全部更新为基于risc-v的硬件环境，紧跟最新的潮流，不像国内一个8086都还在讲，恨不得一门组成原理用了不知道多少年，目前还在停留在单核的x86时代，目前几乎所有的通用cpu都是基于多核处理器，所有的体系结构都应该更新了。所有的lab都是基于xv6的操作系统，一个非常精简的微小的操作系统。按照lab的提示从网上下载qemu模拟器和risc-v的编译环境，国内尽量将apt-get的源改为阿里或者清华的，很快就能完成下载。
测试结果：

1. sleep

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命令，这个基本上就是热身，通过最简单的题目来快速上手，实现一个最简单的程序，没有多少难度。

代码

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

int
main(int argc, char *argv[])
{
  int wait = 0;
  if(argc <= 1){
    printf("sleep: need parameter error\n");
    exit(0);
  }
  
   wait = atoi(argv[1]);
   sleep(wait);
   exit(0);
}

2. pingpong

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 "<pid>: received ping", where <pid> 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 "<pid>: received pong", and exit. Your solution should be in the file user/pingpong.c.

利用管道实现子进程与父进程的通信，通过这个简单的程序熟悉pipe的使用，不过很坑爹的是这个操作系统的管道不支持双端通信，只支持一端是写，一端是读，这个bug调试了很长时间才发现是这个问题。具体实现方法为：开两个管道，父进程往管道1里写数据，从管道2中读数据，子进程从管道1读数据，从管道2写数据。

代码

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

int
main(int argc, char *argv[])
{
    int p1[2];
    int p2[2];
    
    
    if(argc > 1){
       fprintf(2,"Only 1 argument is needed!\n");
       exit(1);
    }

    // creat a pipe
    pipe(p1);
    pipe(p2);
    // child
    if(fork() == 0) {
        char buffer[32];
        //read from the parent
        close(p1[1]);
        close(p2[0]);
        read(p1[0],buffer,4);
        close(p1[0]);
        // write a byte to the parent
        printf("%d: received ping\n",getpid());
        write(p2[1],"pong", 4);
        close(p2[1]);
    } else { 
        char buffer[32];
        // send a byte
        close(p1[0]);
        close(p2[1]);
        write(p1[1],"ping",4);
        close(p1[1]);
        // receive from child
        read(p2[0],buffer,4);
        printf("%d: received pong\n",getpid());
        close(p2[0]);
    }
    exit(0);
}

3. primes

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

利用进程实现素数筛选，不知道为什么实现的很蛋疼。估计还是xv6的文件描述符资源有限不能很好支持多个管道同时读写，因为开的管道过多，资源就卡住了，各种问题不知道有没有人实现快速版本，及子进程同时接受数据也同时开始计算，并同时开始写数据。目前这个的实现很糙，将当前进程筛选的不能被第一个素数整数的数据全部写入管道中，交给子进程去处理，依次这样递归下去即可。这个做法就是跟素数的快速筛查的算法是处理的一模一样的,在$O(n)$的时间复杂度内筛选出所有小于$n$的素数。

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

需要特殊处理的是父进程需要等待子进程完成后，才能退出。

代码

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


int process(const int * p){
    int prime = 1;
    int cnt = 0;
    int num = 0;
    int pip[2];
    int status;

    /*close p1*/
    pipe(pip);
    while(read(p[0],&num,4)){
        if(num == 0) break;
        if(prime == 1){
            prime = num;
            printf("prime %d\n",prime);
        }else{
            if(num%prime == 0) continue;
            write(pip[1],&num,4);
            cnt++;
        }
    }
    close(p[0]);
    close(pip[1]);
    if(prime > 1){
        if(fork() == 0){
            process(pip);
            exit(1);
        }
    }
    wait(&status);
    close(pip[0]);
    return 0;
}

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

    pipe(p);
    for(int i = 2; i <= 35; ++i){
        write(p[1],&i,4);
    }
    close(p[1]);
    process(p);
    close(p[0]);
    exit(0);
}

4. find

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

实现一个简单的查找文件名为指定关键字的程序，典型的利用递归查找到子目录下，即可完成所有子目录的查找。这个就是常规的操作。各种处理文件时需要查找相应的库函数，需要小心处理。

代码

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

char* getname(char *path)
{
  char *p;
  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--){}
  // skip '/'
  p++;
  // Return blank-padded name.
  return p;
}

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

  // open the dir
  if((fd = open(path, 0)) < 0){
    fprintf(2, "ls: cannot open %s\n", path);
    return;
  }
  // open stat
  if(fstat(fd, &st) < 0){
    fprintf(2, "ls: cannot stat %s\n", path);
    close(fd);
    return;
  }
  // check the current the file is 
  if(st.type != T_DIR){
    fprintf(2, "the current the file is not dictionary\n", path);
    close(fd);
    return;
  }

  //read all the files under the dir
  strcpy(buf, path);
  p = buf + strlen(buf);
  *p++ = '/';
  while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
          continue;
      // skip "." and ".."
      if(strcmp(de.name,".") == 0) continue;
      if(strcmp(de.name,"..") == 0) continue;

      curr = p;
      memmove(curr, de.name, DIRSIZ);
      curr[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
          printf("ls: cannot stat %s\n", buf);
          continue;
      }
      // printf("current file name is：%s \n",buf);
      // record the current file
      switch(st.type){
        // we check the current file
        case T_FILE:
            fname = getname(buf);
            if(strcmp(fname,filename) == 0){
                printf("%s\n",buf);
            }
            break;
        // we check the current dir
        case T_DIR:
            if(strlen(path) + 1 + DIRSIZ + 1 > sizeof(buf)){
                printf("ls: path too long\n");
                break;
            }
            find(buf,filename);
            break;
      }
  }

  close(fd);
}

int
main(int argc, char *argv[])
{
  if(argc != 3){
     printf("we need 3 paramters!\n");
     exit(0);
  }
  find(argv[1],argv[2]);
  exit(0);
}

5. xargs

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

实现类似于unix下的xargs操作，这个因为要求的比较低，其实非常容易完成，我们只需要利用fork和exec函数即可完成。我们每次标准输入，在xv6操作系统中，标准输入及时fd 0读取即可，标准输出即为写入fd 1即可，本质来说非常简单。将参数从标准输入读入然后作为附加参数执行xargs后面的程序。简单就是将输入参数进行重写即可。具体可以参考代码实现。

代码

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

int main(int argc, char *argv[])
{
   char buf[512];
   char *args[MAXARG];
   char c;
   char *p;
   int n;
   int status;

   memset(buf,0,sizeof(buf));
   memset(args,0,sizeof(args));
   if(argc < 2){
       printf("need more parameter!\n");
       exit(0);
   }

   /*read from the file*/
   for(int i = 1; i < argc; ++i){
       args[i-1] = argv[i];
   }
   for(;;){
     p = buf;
     /*read each line from the stand input*/
     while((n = read(0,&c,1)) && c != '\n'){
        *p = c;
        p++;
     }
     *p = '\0';
     if(p != buf){
        args[argc-1] = buf;
        if(fork() == 0){
            exec(argv[1],args);
            exit(1);
        }
        wait(&status);
     }
     if(n == 0) break;
     if(n < 0){
        fprintf(2, "read error\n");
        exit(1);
     }
   }

   exit(0);
}

Optional challenge exercises

最后看了后面几个挑战题目也都是非常有意思，后面准备继续将三个挑战题目也完成，总的来说题目质量真心非常不错。

uptime:

Write an uptime program that prints the uptime in terms of ticks using the uptime system call. (easy)

regular

Support regular expressions in name matching for find. grep.c has some primitive support for regular expressions. (easy)

sh:

The xv6 shell (user/sh.c) is just another user program and you can improve it. It is a minimal shell and lacks many features found in real shell. For example, modify the shell to not print a $ when processing shell commands from a file (moderate), modify the shell to support wait (easy), modify the shell to support lists of commands, separated by ";" (moderate), modify the shell to support sub-shells by implementing "(" and ")" (moderate), modify the shell to support tab completion (easy), modify the shell to keep a history of passed shell commands (moderate), or anything else you would like your shell to do. (If you are very ambitious, you may have to modify the kernel to support the kernel features you need; xv6 doesn't support much.)

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 公开课学习

← 【MIT6.S081】 lab3 pagetable 【MIT6.824】lab 1 mapreduce →

扫描二维码，分享此文章

【MIT6.S081】lab1 utils