XV6实验(1) Lab util

1. Sleep（easy）:Implement the UNIX programsleepfor xv6; yoursleepshould 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 int

hang_AI427

7255人浏览 · 2021-05-23 19:10:45

hang_AI427 · 2021-05-23 19:10:45 发布

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

在xv6中实现UNIXsleep程序，你的sleep程序应该可以暂停用户指定的刻度数。这个刻度数是xv6系统定义的时间概念，即定时器芯片两次中断之间的时间。你的解决方案应该在user/sleep.c.文件中。

一些提示：

在你开始编码之前，请阅读xv6手册的第1章。
查看user/中的一些其他程序（例如，user/echo.c、user/grep.c和user/rm.c），了解如何将获得的命令行参数传递给程序。
如果用户忘记传递参数，sleep应该打印一条错误消息。
命令行参数作为字符串传递，您应该使用atoi将其转换为整数（具体看user/ulib.c中的atoi函数）
请参阅实现睡眠系统调用的xv6内核代码kernel/sysproc.c（查找sys_sleep函数），user/user.h以获取可从用户程序调用的睡眠的c定义<意思就是我们需要配调用这个里面定义的函数>，user/usys.S以获取从用户代码跳转到内核以进行睡眠的汇编程序代码。
确保main调用exit（）以退出程序。
在Makefile中添加sleep程序；一旦您完成了，make qemu将编译您的程序，并且您将能够从xv6shell运行它。
查看Kernighan和Ritchie的书C编程语言（第二版）（K&R）来了解C语言。

相关内容：相信绝大多数程序员人生中的第一个程序都是“Hello，world”，而在 Linux Shell 中，这个程序是由 echo 命令来完成的。

[roc@roclinux ~]$ echo 'Hello World'
Hello World

echo.c

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

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

  for(i = 1; i < argc; i++){
    write(1, argv[i], strlen(argv[i]));
    if(i + 1 < argc){
      write(1, " ", 1);
    } else {
      write(1, "\n", 1);
    }
  }
  exit(0);
}

C语言中 int main(int argc,char *argv[])的两个参数详解

argc是命令行总的参数个数；

argv[]是argc个参数，其中第0个参数是程序的全名，以后的参数就是命令行后面跟的用户输入的参数。所以是for(i = 1; i < argc; i++)，

在Unix系统里面，默认情况下0代表stdin，1代表stdout，2代表stderr。所以write(文件标识符<输出到控制台>，argv[i]（输出的字符)，输出的字符长度）

通过上述代码，可以了解如何将命令行参数传递给程序。所以命令行参数传递给程序使用 main(int argc, char *argv[])，如果用户忘记传递参数，即表明argc<2，只有argv[0],argc==1。

同时需要了解两个函数：int fscanf ( FILE *fp, char * format, ... ); int fprintf ( FILE *fp, char * format, ... );

fp 为文件指针，format 为格式控制字符串，… 表示参数列表。与 scanf() 和 printf() 相比，它们仅仅多了一个 fp 参数。

可以用fprintf(2, "Usage:time outs\n"); 这里的2 为stderr，用此来打印一条错误信息。

然后再看atoi函数，可以直接将字符串转为整数。因此输入的字符串可以使用argv[1]表示，因为我们只输入一个字符串。

---->atoi(argv[1]) 输入的sleep时间

int
atoi(const char *s)
{
  int n;

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

然后查看系统中如何调用sleep。user.h中是存在sleep定义的函数。所以我们直接调用sleep(atoi(argv[1]))

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;
}

综上，完整代码如下：

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

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

  int time = atoi(argv[1]);
  sleep(time);
  exit(0);
}

2. 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 "<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.

编写一个程序，它通过一对管道在UNIX系统调用在两个进程之间“ping-pong”一个字节，每个方向一个。父进程通过向父进程parent_fd[1]写入一个字节来发送，子进程通过从父进程parent_fd[0]读取来接收。在从父进程接收到一个字节后，子进程用自己的字节响应，向child_fd[1]写入数据，然后由父进程读取。解决方案放在user/pingpong.c文件中。

一些提示：

使用pipe创建管道。
使用fork创建一个孩子。
使用read读取pipe，并使用write写入pipe。
使用getpid查找调用进程的进程ID。
将程序添加到Makefile中的UPROGS。
xv6上的用户程序可使用的库函数集有限。您可以在user / user.h中看到该列表；源（系统调用除外）位于user / ulib.c，user / printf.c和user / umalloc.c中《这里指的可能是除了系统调用的一些函数》。

首先需要了解进程间的通信机制：管道

不同进程间的通信本质：进程之间可以看到一份公共资源；而提供这份资源的形式或者提供者不同，造成了通信方式不同，而 pipe就是提供这份公共资源的形式的一种。

每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。

那么管道如何实现进程间的通信？

（1）父进程创建管道，得到两个⽂件描述符指向管道的两端

（2）父进程fork出子进程，⼦进程也有两个⽂件描述符指向同⼀管道。

（3）《0-读，1-写》父进程关闭fd[0],子进程关闭fd[1]，即⽗进程关闭管道读端,⼦进程关闭管道写端（因为管道只支持单向通信）。⽗进程可以往管道⾥写,⼦进程可以从管道⾥读,管道是⽤环形队列实现的,数据从写端流⼊从读端流出,这样就实现了进程间通信。

首先是我们之前学的fork的代码。

#include "kernel/types.h"
#include "user/user.h"
int main()
{
    int pid;
    pid = fork();
    printf("fork() return %d\n", pid);
    if(pid == 0){
        printf("child\n");
    }else{
        printf("parent\n");
    }
    exit(0);
}

我们可以使用pid = fork(); 创建子进程。if pid == 0，则为子进程。

我们发现了pipe函数，父进程和子进程都需要一个管道。那么如何描述管道？

可以用整数数据-> 创建管道：例如int pip_fd[2]; 其中pipe_fd[0]是接收管道描述，pipe_fd[1]是写管道描述

那么 ret = pipe(pip_fd) 就表示创建了 ret管道。那么写的时候就可以把write函数的文件标识符的位置写成创建的管道名称。

综上：完成代码如下：

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

int main(int argc, char *argv[]){
    int parent_fd[2];
    int child_fd[2];
    parent_fd= pipe(parent_fd[2]);
    child_fd= pipe(child_fd[2]);
    if(parent_fd== -1){
        printf("pipe1 error");
    }
    if(child_fd== -1){
        printf("pipe2 error");
    }
    int pid = fork();
    char buf[64];
    if(pid == 0){ //child 
        read(parent_fd[0], buf, 4);
        printf("%d: received %s\n", getpid(), buf);
        write(child_fd[1], "ping", strlen('ping'));
    }else{
        // parent
        write(parent_fd[1], "pang", strlen("pang"));
        read(child_fd[0], buf, 4);
        printf("%d: received %s\n", getpid(), buf);
    }
    close(parent_fd[0]);
    close(parent_fd[1]);
    close(child_fd[0]);
    close(child_fd[1]);
    exit(0);
}

3.primes (moderate)/(hard)

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.

写一个使用管道的的素数筛选的并发版本，。。。

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

你的目标是使用pipe和fork来建立管道。第一个进程将数字2-35传入管道。对于每个素数，您将安排一个进程，该进程通过管道从其左邻居读取，并在另一管道上向其右邻居写入。在35停止。

一些提示：

请小心关闭进程不需要的文件描述符，因为否则，您的程序将在第一个进程达到35之前在资源中运行xv6。
一旦第一个进程达到35，它应该等待直到整个管道终止，包括所有子代，孙代和＆c为止。因此，仅在打印完所有输出之后以及在所有其他准备工作都退出之后，才应退出主要准备工作。
提示：当管道的写侧关闭时，read返回零。
将32位（4字节）int直接写入管道是最简单的，而不是使用格式化的ASCII I / O。
您仅应在需要时才在管道中创建进程。
将程序添加到Makefile中的UPROGS。

首先应该思考如何进行并发的素数筛选：如下图所示，我们的第一个进程将2-35传入管道，读出2为素数，第二个进程筛选读取第一个管道中去掉2的倍数(不包括2)的内容（3，5，7.。。），读出3为素数，。。。。以此类推

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

int mian(int argc, char *argv){ //先创建一个父进程/管道
    //通过父进程传入1-35
    int p[2];
    int n;
    p_fd = pipe(p);
    if (p_fd == -1){
        fprint("pip error");
    }
    int pid = fork();
    if(pid==0){ //子进程需要套用一个循环
      read(p[0], &n, 4); //读取n=2(可以放到后面prime函数中)
    }else{
       for(int i=2; i<=35; i++){
         write(p[1], &i, 4); // 注意，这里用&i   
         }  
    }
}

下面能读取2，那么怎么可以去掉2的倍数，继续使用子进程读取呢？

首先我读出来4个字节，并赋值给了n，然后再依次迭代读出所有的字节：只要不读出来为空，那么我就可以读完（循环条件），因此可以用一个while

int num;
int p[2];
pipe[p];
while(read(p[0], &num, 4)){
   if(num%n !=0){
     //如果除不尽，那么我就可以用第二个管道写进去。
      write(p[1], &num, 4);
   }
}

怎么循环第三个管道呢？这里就可以使用自定义的函数了，（这里我的管道循环条件，在于里面的数字必须大于2个）（循环条件）<下面还未完成，存在错误>

void prime(rd){
  read(rd, &n, 4);
  fprint("prime %d\n", n);
  int num;
  int p[2];
  pipe[p];
  int cpip=1; //设置标志位，增加管道.每次prime都会增加一个管道
  while(read(p[0], &num, 4)){
    if(cpip==1){ //
    //每次增加一个子进程
      int pid = fork();
      cpip=0; 
      if (pid == 0){ //如果是子进程，则循环prime
         prime(p[0]);
        }
    if(num%n !=0){
      //如果除不尽，那么我就可以用第二个管道写进去。
       write(p[1], &num, 4);
     }
  }
}

综上：代码为：<未经调试>

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


void prime(rd){
  read(rd, &n, 4);
  fprint("prime %d\n", n);
  int num;
  int p[2];
  pipe[p];
  int cpip=1; //设置标志位，增加管道.每次prime都会增加一个管道
  while(read(p[0], &num, 4)){
    if(cpip==1){ //
    //每次增加一个子进程
      int pid = fork();
      cpip=0; 
      if (pid == 0){ //如果是子进程，则循环prime
         prime(p[0]);
        }
    if(num%n !=0){
      //如果除不尽，那么我就可以用第二个管道写进去。
       write(p[1], &num, 4);
     }
  }
}

int mian(int argc, char *argv){ //先创建一个父进程/管道
    //通过父进程传入1-35
    int p[2];
    int n;
    p_fd = pipe(p);
    if (p_fd == -1){
        fprint("pip error");
    }
    int pid = fork();
    if(pid==0){ //子进程需要套用一个循环
    //  read(p[0], &n, 4); 读取n=2(可以放到后面prime函数中)
       prime(p[0]);
    }else{
       for(int i=2; i<=35; i++){
         write(p[1], &i, 4); // 注意，这里用&i   
         }  
    }
    exit(0);
}

4.find (moderate)

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.

编写UNIX查找程序的简单版本：查找具有特定名称的目录树中的所有文件。您的解决方案应该在文件user / find.c中。

一些提示：

查看user / ls.c以了解如何读取目录。
使用递归允许find下降到子目录中。
不要递归到“。” 和 ”..”。
对文件系统的更改在qemu的运行过程中一直存在；运行干净的文件系统make clean，然后make qemu。
您将需要使用C字符串。看一下K＆R（C书），例如5.5节。
请注意，==不会像Python中那样比较字符串。请改用strcmp（）。
将程序添加到Makefile中的UPROGS。

我们需要首先查看user/ls.c中目录。下面进行注释分析。。

代码内涉及到结构体：

/kernel/stat.h 这里stat定义文件本身的信息。

#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device

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
};

kerel/fs.h 这里dirent定义文件名和文件名长。DIRSIZ 表示最大的文件名长度



// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

fstat函数：提示：本函数与 stat() 函数相似，不同的是，它是作用于已打开的文件指针而不是文件名。

了解以下open函数，open函数是我们开发中经常会遇到的，这个函数是对文件设备的打开操作，这个函数会返回一个句柄fd，我们通过这个句柄fd对设备文件读写操作.

调用成功时返回一个文件描述符fd。调用失败时返回-1，并修改errno

int open(constchar*pathname,intflags); pathname表示路径地址，flags：用来控制打开文件的模式，具有以下模式:

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

char*
fmtname(char *path)
{
  static char buf[DIRSIZ+1];
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;

  // Return blank-padded name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));
  return buf;
}

// 如何读取目录/文件信息
void
ls(char *path)
{
  char buf[512], *p; //定义buf, p指针
  int fd; //定义文件描述符<open路径后打开的>
  struct dirent de; //描述文件名称，名称大小
  struct stat st; //描述文件信息

  if((fd = open(path, 0)) < 0){ // 打开路径表示<0，路径不对，打不开。
    fprintf(2, "ls: cannot open %s\n", path);
    return;
  }

  if(fstat(fd, &st) < 0){ //该函数返回的数组具有该文件的统计信息，如果<0，没有文件的具体信
//----------st->st.type
//再返回路径
    fprintf(2, "ls: cannot stat %s\n", path);
    close(fd);
    return;
  }

//判断不同的文件类型。
  switch(st.type){ //st.type文件类型
  case T_FILE: //如果他是文件，则说明文件的类型，路径，信息，大小等。
    printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size);
    break;

  case T_DIR:  //文件名长度+路径长度  >  buf长度，则报错
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){ // 路径太长 报错
      printf("ls: path too long\n");
      break;
    }

// 下面是真正读取目录下文件信息
    strcpy(buf, path); //首先path先读到buf中，例如buf = './home/hang'
    p = buf+strlen(buf); // 应该是再往后取strlen长度个地址。保证长度足够
    *p++ = '/'; //'./home/hang/'   
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      memmove(p, de.name, DIRSIZ);  //p = './home/hang/hang.txt'
      p[DIRSIZ] = 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, st.size);
    }
    break;
  }
  close(fd);
}

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

  if(argc < 2){
    ls(".");
    exit(0);
  }
  for(i=1; i<argc; i++)
    ls(argv[i]);
  exit(0);
}

参考别人的做法，对当前目录排除掉.和..后进行递归遍历，同时对路径名进行匹配，匹配到了就输出。

排除.和..的代码。de.name

 if(de.name[0] == '.' && de.name[1] == 0) continue;
                if(de.name[0] == '.' && de.name[1] == '.' && de.name[2] == 0) continue;

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

char*
fmtname(char *path)
{
  static char buf[DIRSIZ+1];
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;

  // Return blank-padded name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));
  return buf;
}

//直接复制的
void match(const char* path, const char* name){
    //printf("%s %s", path, name);
    int pp = 0;
    int pa = 0;
    while(path[pp] != 0){
        pa = 0;
        int np = pp;
        while(name[pa] != 0){
            if (name[pa] == path[np]){
                pa++;
                np++;
            }
            else
                break;
        }
        if(name[pa] == 0){
            printf("%s\n", path);
            return;
        }
        pp++;
    }
}


void ls(char *path, char *name)
{
  char buf[512], *p; //定义buf, p指针
  int fd; //定义文件描述符<open路径后打开的>
  struct dirent de; //描述文件名称，名称大小
  struct stat st; //描述文件信息

  if((fd = open(path, 0)) < 0){ // 打开路径表示<0，路径不对，打不开。
    fprintf(2, "ls: cannot open %s\n", path);
    return;
  }

  if(fstat(fd, &st) < 0){ //该函数返回的数组具有该文件的统计信息，如果<0，没有文件的具体信
//----------st->st.type
//再返回路径
    fprintf(2, "ls: cannot stat %s\n", path);
    close(fd);
    return;
  }

//判断不同的文件类型。
  switch(st.type){ //st.type文件类型
  case T_FILE: //如果它是当前目录下的文件，可以直接输出，当前path中所有文件信息。
   # printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size);
    match(match(path, name)); 因为没有这个匹配的函数，所以需要自己写
    break;
  
  如果其他路径下的文件
  case T_DIR:  //文件名长度+路径长度  >  buf长度，则报错
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){ // 路径太长 报错
      printf("ls: path too long\n");
      break;
    }

// 读取其他目录下文件信息
    strcpy(buf, path); //首先path先读到buf中，例如buf = './home/hang'
    p = buf+strlen(buf); // 应该是再往后取strlen长度个地址。保证长度足够
    *p++ = '/'; //'./home/hang/'   
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      if(de.name[0] == '.' && de.name[1] == 0) continue;
      if(de.name[0] == '.' && de.name[1] == '.' && de.name[2] == 0) continue;
      memmove(p, de.name, DIRSIZ);  //p = './home/hang/hang.txt'
      p[DIRSIZ] = 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, st.size);
    }
    break;
  }
  close(fd);
}

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

  if(argc < 2){
    ls(".");
    exit(0);
  }
  for(i=1; i<argc; i++)
    ls(argv[i]);
  exit(0);
}

5.xargs (moderate)

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程序：从标准输入中读取行，并为每行运行一个命令，将行作为参数提供给命令。你的解决方案应该在文件里用户/xargs.c。

一些提示：