Mit 6.s081 operating system enginerring lab1 utilities

2022-06-20

MIT 6.S081 Operating System Enginerring Lab1 Utilities

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.

$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$

Note that make grade runs all tests, including the ones for the assignments below. If you want to run the grade tests for one assignment, type:

$ trace 2147483647 grep hello README

Solution

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

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

   int sleep_time = atoi(argv[1]);
   if(sleep_time == 0){
    fprintf(2,"Wrong parameter.\n");
    exit(1);
   }
   sleep(sleep_time);
   exit(0);
}

这题很简单没什么好讲的。

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

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

int main(int argc, char *argv[])
{
    char buf[2];
    int p1[2];
    pipe(p1);
    int p2[2];
    pipe(p2);
    char *cMsg = "c";
    char *pMsg = "p";

    if(fork() == 0){
        close(p1[1]);
        close(p2[0]);
        if(read(p1[0], buf, 1) != 1){
            fprintf(2,"Child fail to read from the pipe!\n");
            exit(1);
        }
        close(p1[0]);
        if(write(p2[1], cMsg, 1) != 1){
            fprintf(2,"Child fail to write to the pipe!\n");
            exit(1);
        }
        close(p2[1]);
        printf("%d: received ping\n",getpid());
        exit(0);
    }
    else{
        close(p1[0]);
        close(p2[1]);
        if(write(p1[1], pMsg, 1) != 1){
            fprintf(2,"Parent fail to write to the pipe!\n");
            exit(0);
        }
        close(p1[1]);
        wait((void *)0);
        if((read(p2[0], buf, 1)) != 1){
            fprintf(2,"Parent fail to read from the pipe!\n");
            exit(0);
        }
        close(p2[0]);
        printf("%d: received pong\n",getpid());
        exit(0);
    }
}

这题需要利用管道实现两个进程之间的通信，在实现的过程中需要注意管道端口的关闭，否则read函数就会一直在等待数据的输入。

primes(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.

此题需要仔细理解下面这张图：

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

void primes_help(int fd[]){
    close(fd[1]);
    int first_number;
    if(read(fd[0],&first_number,sizeof(int)) == 0){
        exit(0);
    }
    printf("prime %d\n",first_number);
    
    int read_number;
    int child_fd[2];
    pipe(child_fd);
    if(fork() == 0){
        primes_help(child_fd);
    }else{
        close(child_fd[0]);
        while(read(fd[0], &read_number,sizeof(int)) != 0){
            if(read_number % first_number != 0){
                if(write(child_fd[1],&read_number, sizeof(int)) != sizeof(int)){
                    fprintf(2,"Fail to write the left number in child function\n");
                    exit(1);
                }
            }
        }
        close(child_fd[1]);
        wait((void *)0);
        exit(0);
    }
}

int main(int argc, char *argv[])
{
    int p[2];
    pipe(p);
    int i;
    int first_number = 2;
    printf("prime %d\n",first_number);

    if(fork() == 0){
        primes_help(p);
    }else{
        close(p[0]);
        for(i = 3; i <= 35;i++){
            if(i % 2 != 0){
                if(write(p[1],&i,sizeof(int)) != sizeof(int)){
                    fprintf(2,"Fail to write the left numer in main function\n");
                    exit(1);
                } 
            }
        }
        close(p[1]);
        wait((void *)0);
        exit(0);
    }
    exit(0);
}

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.

#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), 0, DIRSIZ-strlen(p));
  return buf;
}

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

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

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

    switch(st.type){
    case T_FILE:
        if(strcmp(fmtname(path), name) == 0){
            printf("%s\n",path);
        }
        break;
    case T_DIR:
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: 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 || 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;
            }
            find(buf,name);
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[])
{
    if(argc != 3){
        fprintf(2,"Incorrect number of parameters\n");
        exit(1);
    }

    char *find_path = argv[1];
    char *file_name = argv[2];

    find(find_path, file_name);
    exit(0);
}

这题主要参考的ls.c中的代码，但要注意这里面有个小坑，需要将fmtname函数中的代码中的 memset(buf+strlen(p), " ", DIRSIZ-strlen(p));修改为 ` memset(buf+strlen(p), 0, DIRSIZ-strlen(p));否则后面 if(strcmp(fmtname(path), name) == 0)`这里会出现问题。

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.

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

void copy(char **dst, char *src)
{
    *dst = malloc(strlen(src) + 1);
    strcpy(*dst,src);
}

void read_input(char **params,int index)
{
    int i = index;
    char buf[512];
    int j = 0; 
    
    while(read(0,buf+j,1) > 0){
        if(buf[j] == '\n' || buf[j] == ' '){
            buf[j] = 0;
        }
        j++;
        if(j > 512){
            fprintf(2,"Too many parameters");
            exit(1);
        }
    }
        
    int len = j;
    j = 0;
    while(buf[j] == ' '){
        j++;
    }
    int p = j;
    int state = 0;
    for(;j <= len;j++){
        if(buf[j] == 0){
            if(state == 0){
                copy(params + i, buf + p);
                i++;
                state = 1;
            }
        }
        else{
            if(state == 1){
                p = j;
                state = 0;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    if(argc < 2){
        fprintf(2,"Too few parameters\n");
        exit(1);
    }

    char *params[MAXARG];

    int i;
    for(i = 1;i < argc;i++){
        copy(&params[i-1], argv[i]);
    }

    if(fork() == 0){
        read_input(params,i-1);
        exec(params[0],&params[0]);
        exit(0);
    }else{
        wait((void *)0);
        exit(0);
    }
    
    exit(0);
}

这题比较麻烦的主要是字符串的处理，我这里的处理方式是首先将所有的参数都读入到一个buf中，在读入的过程中如果遇到space或 \n ，就将它转换成0休止符，方便后续的处理。所有的字符都读取到buf中后，我利用了一个自动状态机的方法，将每个参数正确的读取到params参数数组中。

自动状态机如图：

原文这里引用的是本机 Typora 截图，图片文件没有随仓库保存。