CSAPP 2e Shell Lab 笔记 – cyp0633's blog

本文最后更新于 302 天前，其中的信息可能已经有所发展或是发生改变。

通过完成一个简单的Shell程序（称为tsh），来熟悉程序控制与信号的内容。

本笔记根据第二版材料写出，可能与第三版有一定差别。由于测试用例本身就是由浅入深的，所以本笔记也按照这个方式组织。

前置知识

建议提前阅读官方Writeup（在这里下载），并学习课本“异常控制流”部分。

Writeup的Hints部分包含了很多有用的提示，太多了就不一块翻译了。

在原作者所属的顶级大学CMU，这个实验是分配给两个人做7天的，可以作为参考，决定自己的工作量。

关于Shell

Shell是一个交互式命令行解释器，就是执行你命令的程序。如果已经用得比较熟了，就没必要看这个部分了。

命令是一串空格分隔的字符，第一个单词是程序名或内置命令名。如果是程序名，Shell会fork出一个进程执行它；如果是内置命令，就在当前进程中运行。

比如下面的命令：

gcc     a.c    -o       a     -O2
程序名 | 参数1 | 参数2 | 参数3 | 参数4

如果一个命令以&结尾，则任务应在后台运行。只有一个程序可以在前台运行，而后台程序的数量没有多少限制。

Unix Shell支持任务控制，即使用Ctrl+C可以发送SIGINT信号停止任务，使用Ctrl+Z可以发送SIGTSTP暂停进程（也可能有其他行为）。此外，还应该支持jobs显示任务列表、bg <job>让程序后台运行、fg <job>让程序前台运行，以及kill <job>来杀掉进程。

特别地，在本Lab中，需要做到的有以下几点：

命令行prompt以”tsh>”开头。
不需要支持IO重定向（<>）和管道（|），这点大家在Buffer Lab里应该很熟悉。
Ctrl+C和Ctrl+Z需要向前台程序和其后代进程对应的信号。
如果命令以&结尾，将其放到后台运行。
为每个进程或工作分配一个PID或JID，JID应以%开头。这一部分已被实现
实现quit、jobs、bg和fg内置命令。
实现终止所有后代僵尸进程。

关于测试

每进行一次修改，都要运行make命令以重新编译，然后运行./tsh来执行。

本实验提供一个参考程序tshref，做出来的tsh与其输出相同，便代表你是正确的。如果要测试正确性，可以在tsh和tshref中手动输入命令对比，使用sdriver.pl来自动判断，或者结合使用。目录中还有16个测试文件，可以使用如下的命令来对比测试。其中的-p参数表示不输出命令行tsh>开头。

unix> ./sdriver.pl -t trace01.txt -s ./tsh -a "-p"
unix> ./sdriver.pl -t trace01.txt -s ./tshref -a "-p"
# 上面两个与下面两个命令等效
unix> make test01
unix> make rtest01

但也不是所有情况都需要让两个输出相同。比如运行的PID很可能甚至一定不相同。另外，trace11-13的ps输出可能次次不同，但重点是使进程状态相同。

此外，lab文件还带有几个测试程序，用法和作用分别如下：

mystop <n> – 睡眠n秒，然后向自己发送SIGTSTP。
mysplit <n> – fork一个子进程，自旋n秒。
myspin <n> – 睡眠n秒。
myint <n> – 睡眠n秒，然后向自己发送SIGINT。

如果你想要一次对比所有测试的输出，可以使用以下的方法（参考资料4）：

在Shell Lab目录中放置这个文件和这个文件；
运行下面的命令：

./judge.sh > test.log
./rjudge.sh > rtest.log

将rtest.log中的tshref全部替换为tsh，使用你喜欢的编辑器（如vscode）的正则表达式替换，将两文件的\(\d*\)替换为10000；
使用你喜欢的对比工具（仍然可用vscode）对比test.log和rtest.log，不同应该只有ps命令输出的PID。

更多的用法请自行参见Writeup的Checking Your Work一节。

Tricks

个人建议使用Git进行版本控制，并进行相对密集的Commit，以分清各阶段所做的工作，并方便地回退代码。

如果你测试过程中发现无法退出tsh，可以打开另一个终端窗口，执行killall tsh。

错误处理也可以先不做，在trace14处对照填写。

trace01

trace01.txt – 在EOF处正确地停止。

eval函数是根据输入命令行进行对应操作的函数。在CSAPP 2e 8.4.6节（中文版P502/英文版P733），有eval函数的大致框架，先填上再说。语句作用我都填到注释里了：

void eval(char *cmdline)
{
    char *argv[MAXARGS];
    char buf[MAXLINE]; // command will be parsed and modified?
    int bg;            // whether it runs in background
    pid_t pid;
    // preprocess cmd line
    strcpy(buf, cmdline);
    bg = parseline(buf, argv); // convert the command into argv
    if (argv[0] == NULL)       // the line is empty, return
    {
        return;
    }
    // run external command
    if (!builtin_cmd(argv))
    {
        if ((pid = fork()) == 0) // this is child
        {
            if (execve(argv[0], argv, environ) < 0) // execute command failed
            {
                printf("%s: Command not found\n", argv[0]);
                exit(0); // here only child exited
            }
        }
        if (!bg) // run the process in foreground:
        // wait for foreground job to terminate
        {
            int status;
            if (waitpid(pid, &status, 0) < 0) // if return -1, then waiting failed
            {
                unix_error("waitfg: waitpid error");
            }
        }
        else
        {
            printf("%d %s", pid, cmdline);
        }
    }
    return;
}

这个框架做的事情如下：

使用parseline预处理命令行，将一整个字符串按空格分割为字符串数组；
使用builtin_command检测并处理内置命令，如果为内置命令，归builtin_command函数处理；
fork出一个新进程；
在新进程中，execve运行对应的程序，如果运行失败，提示错误信息，将子进程退出；
如果运行的程序是前台进程，那么就要等待前台进程结束，再继续运行shell；
否则，如果是后台进程，直接打印命令信息。

trace01只需要正确响应EOF就可以了。在课本的程序框架中，已经使用parseline函数将命令行解析为了参数，并判断了第一个参数是否为NULL。显然，第一个参数是NULL，后面当然更是NULL，意味着没有输入。也就是说，我们什么额外的工作都不用干……

详细的Git Commit更改见此处。通过如图：

trace02

trace02.txt – 处理内置的quit命令。

在tsh中，内置的命令实在builtin_cmd函数中处理的。只需要在其中判断一下第一个参数是否为quit，如果是的话退出即可。

在builtin_cmd中插入以下代码：

    if (strcmp(argv[0], "quit") == 0) // process quit command
    {
        exit(0);
    }

详细的Git Commit更改见此处。通过如图：

trace03/04

trace03.txt – 运行一个前台任务。
trace04.txt – 运行一个后台任务。

在课本的eval框架中，首先使用builtin_cmd判断并处理内置函数，然后根据bg值（由parseline得到）判断是否在后台运行。这其中会先fork出一个子进程，然后使用execve执行目标程序。请注意，只有子进程会在运行失败时exit。根据是否是前台任务，判断是直接打印执行详情还是等待前台进程结束。

    if (!builtin_cmd(argv)) // built-in command is done in `builtin_cmd`
    {
        if ((pid = fork()) == 0) // this is child
        {
            if (execve(argv[0], argv, environ) < 0) // execute command failed
            {
                printf("%s: Command not found\n", argv[0]);
                exit(0); // here only child exited
            }
        }
        if (!bg) // run the process in foreground:
        // wait for foreground job to terminate
        {
            int status;
            if (waitpid(pid, &status, 0) < 0) // if return -1, then waiting failed
            {
                unix_error("waitfg: waitpid error");
            }
        }
        else
        {
            printf("%d %s", pid, cmdline);
        }
    }

说了这么多又是什么意思？这道题又什么都不用做。

此题没有Commit，输出有一个格式问题，在trace05的commit内一起解决。通过如图。这里的job编号不同是正常现象，这个问题将在trace05中解决。

trace05

trace05.txt – 处理jobs内置命令。

先拿软柿子下手，将处理jobs命令的地方做好。tsh已经为我们实现了listjobs函数，可以直接放到builtin_cmd中。注意return 1用来告诉eval已经找到了一个内置命令，否则会提示“command not found”。

    if (strcmp(argv[0], "jobs") == 0) // t5: process jobs command
    {
        listjobs(jobs);
        return 1; // this IS a builtin command, return 1 to notify
    }

但是不管怎么样，运行jobs都不会输出任何东西。毕竟在我们已有的代码里，既没有在任务开始时将其添加到任务列表，也没有在结束时将它移出。要做到将任务添加到任务列表，需要在fork后调用addjob：

                printf("%s: Command not found\n", argv[0]);
                exit(0); // here only child exited
            }
        }
        addjob(jobs, pid, bg ? BG : FG, cmdline); // add the job to job list.
        // When bg=1, state=2; bg=0, state=1. this way it's just elegant
        if (!bg)                               // run the process in foreground:

上述代码的addjob中第三个参数state有三个取值，FG=1、BG=2、ST=3。虽然直接使用bg+1也是可行的方案，但这样使用三元运算符会更优雅更容易理解。

至于删除任务的工作，需要在sigchld_handler函数中处理。这涉及到对waitpid函数的更深入理解，在CSAPP 8.4.3节（中文版P496，英文版P724），提到了这样一段话，介绍了waitpid函数的默认行为，以及退出状态的检查方法（中翻太烂了，这是我自己翻的）：

（更改默认行为）WNOHANG|WUNTRACED：立即返回。如果等待集里面没有子进程已经终止，那么返回0；否则，返回其中一个已终止子进程的PID。
（检查回收子进程的返回状态）WIFEXITED(status)：如果子进程正常退出，即通过调用exit或者return，则返回真。

Writeup中也提到WNOHANG|WUNTRACED或许会有用。如果没有WNOHANG参数，shell会一直等待，直到有一个子进程退出。而如果没有WUNTRACED参数，那么程序无法捕捉到STOP的子进程情况，这样会卡在trace16。

上述的前一个更改默认行为的部分对应了waitpid的第三个参数，后一个函数检查用于确定是否有个子进程真的退出了（而非没有子进程终止，waitpid返回了0）。有了这些知识，可以得到实现如下，如此便可以将退出的进程从任务列表删除：

void sigchld_handler(int sig) 
{
    pid_t pid;
    int status;
    while((pid=waitpid(-1,&status,WNOHANG|WUNTRACED))>0) // check if a child has become zombie, without wait
    {
        if(WIFEXITED(status))
        {
            deletejob(jobs,pid); // remove pid from job list
        }
    }
    return;
}

这并没有结束，我们需要干其他的亿些工作。我们知道如果shell要继续运行，需要等待前台任务（如果有）结束，比如在前面的通过截图中，只有make test04结束后，shell才会再打印出“cyp0633@cyp0633-R7000-Linux > ~/桌面…”字样，在本实验中就是“tsh>”。但tsh有一个waitfg函数，看起来他们不想让我们把等待工作放到eval中。于是这一部分改成：

        if (!bg) // run the process in foreground:
        // wait for foreground job to terminate
        {
            waitfg(pid); // the waiting stuff should be done in `waitfg`
        }

至于waitpid函数的实现，Writeup中已经给了提示：

实验有一个棘手的部分，是决定 waitfg 和 sigchld 处理函数之间的工作分配。我们推荐以下方法：
– 在waitfg中，用一个死循环包裹sleep函数。
– 在sigchld_handler中，调用且仅调用一次waitpid。

所谓的工作分配，指的是waitfg和sigchld_handler都有等待进程结束的功能。waitfg的作用前面已经说明，而sigchld_handler负责接收任何子进程结束的信号，并将其回收，注意它是一个handler。waitfg的实现如下：

void waitfg(pid_t pid)
{
    while (pid == fgpid(jobs))
    {
        sleep(0);
    }
    return;
}

也可以在这里调用waitpid等待前台进程退出，但它可能会抢走sigchld_handler的信号，而不会执行deletejob。结果就是在trace05中会打印一堆tsh。那当然可以在这里也加一个deletejob，但Writeup中指出这种工作分配是不明确的。所以最好的办法就是在有前台进程的时候一直等待。

另外还要处理eval中的信号问题。Writeup中提到：

在eval中，父进程在fork子进程之前，必须使用sigprocmask函数来阻断SIGCHLD信号，然后在使用addjob将子进程加入任务列表之后，再调用sigprocmask恢复SIGCHLD信号。因为子进程继承了父进程的中断向量，所以子进程必须在它执行新程序之前将SIGCHILD恢复。
父进程这样将SIGCHLD信号阻断，是为了避免子进程被SIGCHLD处理程序回收（然后被从任务列表中移除），之后父进程调用addjob时的竞态条件。

于是，我们在eval函数最前面声明变量的区域加入几行：

    sigset_t mask;
    sigemptyset(&mask);

然后在判断不是内置命令之后，阻断SIGCHLD信号，修改如下：

    if (!builtin_cmd(argv)) // built-in command is done in `builtin_cmd`
    {
        sigaddset(&mask, SIGCHLD);
        sigprocmask(SIG_BLOCK, &mask, NULL); // 5. block SIGCHLD
        if ((pid = fork()) == 0)             // this is child

然后，在子进程execve之前，恢复信号，修改如下：

        if ((pid = fork()) == 0)             // this is child
        {
            sigprocmask(SIG_UNBLOCK, &mask, NULL);  // 5. unblock SIGCHLD
            if (execve(argv[0], argv, environ) < 0) // execute command failed

再然后，父进程addjob完毕后也要恢复：

        addjob(jobs, pid, bg ? BG : FG, cmdline); // add the job to job list.
        // When bg=1, state=2; bg=0, state=1. this way it's just elegant
        sigprocmask(SIG_UNBLOCK, &mask, NULL); // 5. unblock SIGCHLD
        if (!bg)                               // run the process in foreground:

这样就可以通过trace05的测试了，Git Commit见此处，通过截图如下。

trace06

trace06.txt – 将SIGINT信号发送到前台任务。

这个trace解决起来比较简单。最核心的，我们需要实现SIGINT信号的处理例程。这里使用-pid是为了将整个进程组的进程全部干掉。

void sigint_handler(int sig)
{
    pid_t pid = fgpid(jobs);    // get pid of foreground job
    if (kill(-pid, SIGINT) < 0) // try to send SIGINT
    {
        unix_error("sigint error"); // failed
    }
    return;
}

在tshref中，终止进程后还会输出一行提示信息，由于这也算是子进程结束了，这部分也是在sigchld_handler中处理的。将函数修改为如下的样子即可。

void sigchld_handler(int sig) 
{
    pid_t pid;
    int status;
    while((pid=waitpid(-1,&status,WNOHANG|WUNTRACED))>0) // check if a child has become zombie, without wait
    {
        if(WIFEXITED(status))
        {
            deletejob(jobs,pid); // remove pid from job list
        }
        if (WIFSIGNALED(status))
        {
            printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(status));
            deletejob(jobs, pid);
        }

    }
    if (pid < 0 && errno != ECHILD)
    {
        unix_error("waitpid error");
    }
    return;
}

还有一个坑，在Writeup中已经提到。

当你在标准Unix shell中运行你的shell时，你的shell处于前台进程组。如果你的shell创建一个子进程，那么它默认也会被加到前台进程组内。因为输入Ctrl+C会向前台进程组的所有进程发送SIGINT信号，所以你输入Ctrl+C也会向你的shell和你创建的子进程发送SIGINT，这显然不对。
这里有个解决办法：在fork之后，execve之前，子进程应该调用setpgid(0, 0)，来将子进程放置到一个新的进程组内，组ID与子进程PID相同。这确保了只会有一个进程——即你的shell——处于前台进程组内。当你按下Ctrl+C，shell应该捕获SIGINT信号，然后将其传递到正确的前台应用（或更准确地，包含前台进程的进程组）。

长话短说，就是使用Ctrl+C结束tsh中运行的前台进程，会把shell一起干掉。解决办法就是在execve之前设置进程组。两个0分别代表要加入的是当前进程，以及新建一个GID=PID的组。

            sigprocmask(SIG_UNBLOCK, &mask, NULL);  // 5. unblock SIGCHLD
            setpgid(0, 0);                          // put the child process (0=current) into a new process group (0=current)
            if (execve(argv[0], argv, environ) < 0) // execute command failed

Git Commit 见此处，通过截图见下。

trace07

trace07.txt – 将SIGINT信号只发送到前台任务。

其实单论测试的话，上个trace的程序现在也可以直接用，能过。但测试用例没有测试没有前台任务的情况，为了让程序更完善，还是要做一处修改。

在sigint_handler中。需要判断是否存在前台任务，如果没有，就不需要做任何事。这样，在什么都没运行的时候按下Ctrl+C，tsh就不会直接挂掉，什么都输不进去。在没有前台任务的情况下，fgpid会返回0，我们可以利用这个特性。

void sigint_handler(int sig)
{
    pid_t pid = fgpid(jobs);    // get pid of foreground job
    if (pid != 0) // if no foreground job (PID=0), do nothing (ONLY send to foreground)
    {
        if (kill(-pid, SIGINT) < 0) // try to send SIGINT
        {
            unix_error("sigint error"); // failed
        }
    }
    return;
}

Git Commit见此处，通过截图见下。

trace08

trace08.txt – 将SIGTSTP信号只发送给前台任务。

SIGTSTP对应的是Ctrl+Z。实现方法很像上两个trace的方法，只需改sigtstp_handler和sigchld_handler就行了。

首先是sigtstp_handler：

void sigtstp_handler(int sig) 
{
    pid_t pid = fgpid(jobs);
    if (pid != 0)
    {
        if (kill(-pid, SIGTSTP) < 0)
        {
            unix_error("sigtstp error");
        }
    }
    return;
}

然后是sigchld_handler。注意这里额外地要将工作的状态改为停止（对应上文addjob说明处的三种状态类型）：

        if (WIFSIGNALED(status)) // SIGINT, etc.
        {
            printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(status));
            deletejob(jobs, pid);
        }
// 插入下面的部分
        if (WIFSTOPPED(status)) // SIGTSTP, etc.
        {
            printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, WSTOPSIG(status));
            struct job_t *job = getjobpid(jobs, pid);
            job->state = ST;
        }

这样就通过了。Git Commit见此处，通过截图见下。

trace09/10

trace09.txt – 处理bg内置命令
trace10.txt – 处理fg内置命令

bg和fg命令是由do_bgfg函数处理的，我们需要在builtin_cmd里添加合适的调用。

    if (strcmp(argv[0], "bg") == 0 || strcmp(argv[0], "fg") == 0) // judge bg & fg
    {
        do_bgfg(argv);
        return 1;
    }

bg和fg命令的参数<job>可以是PID或者JID。在Writeup的Specification一节中，有这样一段话：

bg <job>命令通过发送SIGCONT指令给工作来使它重新开始，然后让它运行在后台。
fg <job>命令通过发送SIGCONT指令给工作来使它重新开始，然后让它运行在前台。

这么一来，用一个函数处理两个命令就显得很合理了。在do_bgfg函数中，要获取参数中的PID或者JID，解析为合适的任务类型指针，发送SIGCONT信号，然后根据前台和后台决定所要做的事情。

当然，首先不能忘了定义变量。end的作用将在后面说明。

    char *id = argv[1], *end; // JID or PID
    struct job_t *job;
    int numid;

然后检查参数是否存在。

    // extract job or process
    if (id == NULL) // not specified
    {
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return;
    }

对JID和PID的第一、二步处理是不尽相同的，斟酌再三还是分开处理为好。

首先是JID的情况。将id指针自增1，是为了让指针指向第一个数字，然后使用strtol功能将其从字符串转为数字。在转换的过程中，end会被设定为指向被转换的最后一个数字的下一个字符。正常情况下，JID/PID并不应该包含除开头%号外的字符，所以end指向的应该是表示字符串结尾的\0。具体可以参考这个链接，但他的判断条件只能保证不以字符开头，如果遇到类似于1a23的字符串，仍然不会提示异常，并返回1。虽然我这么做只是为了避免多遍历一遍字符串判断是否有其他字符，稍快一点，代码也优雅一点……

然后就是调用getjobjid得到job了，再加一个是否存在的判断。

    if (id[0] == '%') // this is a job
    {
        id++;                         // point to the number position
        numid = strtol(id, &end, 10); // convert id char[] to integer
        if (*end != '\0')             // contains non-digit characters
        {
            printf("%s: argument must be a PID or %%jobid\n", argv[0]);
            return;
        }
        job = getjobjid(jobs, numid); // try to get job
        if (job == NULL)
        {
            printf("%%%d: No such job\n", numid);
            return;
        }
    }

对于PID的情况，不同的地方只在于没有自增，换了适用于PID的函数，以及提示信息改变而已。

    else // this is a process
    {
        numid = strtol(id, &end, 10);
        if (*end != '\0')
        {
            printf("%s: argument must be a PID or %%jobid\n", argv[0]);
            return;
        }
        job = getjobpid(jobs, numid); // try to get proc
        if (job == NULL)
        {
            printf("(%d): No such process\n", atoi(id));
            return;
        }
    }

发送信号很简单，就一行。仍然是给全组发送。

    kill(-(job->pid), SIGCONT);

最后是根据前台或者后台的要求，做出相应的行为，这与eval最后的行为比较类似，将waitfg封装起来也是便于这里再利用。

    if (strcmp(argv[0], "fg") == 0) // foreground
    {
        job->state = FG;
        waitfg(job->pid);
    }
    else // background
    {
        job->state = BG;
        printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
    }

把这些都填上，就实现了bg和fg内置命令的处理。Git Commit见此处，通过图如下。

trace11-16

trace11.txt – 将SIGINT信号发送给前台进程集里的每个进程
trace12.txt – 将SIGTSTP信号发送给前台进程集里的每个进程
trace13.txt – 将进程集里的每个停止的进程重启
trace14.txt – 简单的错误处理
trace15.txt – 全都混到一起
trace16.txt – 测试shell是否能够处理来自其他进程（而不是终端）的SIGTSTP和SIGINT信号

到上一节，我们所写的Shell应该也能够完美处理这些测试用例，你什么都不用做，应该就能看到正确的输出。
在Trace 11-12中，要做到“发送给进程集中的每个进程”，重点在于kill(-pid, signal)中的负号。这表示对整个进程集发送。Trace 11中SIGINT把整个进程集干掉了，所以ps的输出应该没有任何一个mysplit；而Trace 12让整个进程集停止，所以在ps的输出中，你应该能看到两个停止状态的mysplit。关于ps的输出，可以参见这里。

在Trace 13中，mysplit先被停止，然后被转到前台运行，直到结束。所以可以观察到第一个ps的输出中有两个等几秒，然后第二个ps的输出没有mysplit。

如果说在前面不知道错误处理的文字怎么写，可以参考make rtest14的输出。

Trace 16的处理方法其实有点意思。在前面写的过程中，我们可以发现SIGINT和SIGTSTP的提示输出都放到了sigchld_handler中，而不是各自的handler函数中。因为如果放到各自的handler中，就不会在Trace 16的情况下被唤起（因为信号不是发给Shell的），而sigchld_handler却可以接收因任何原因造成的停止，恰巧可以使用WIFSIGNALED等函数判断停止原因，所以也能够实现分信号的处理。参考文献3的Step 6就是这方面的讲解，值得一看。

参考文献

https://zhuanlan.zhihu.com/p/89224358（只有代码，抄倒是可以抄）
https://hackmd.io/@KYWeng/SyK1Hk63S（讲得很详细，主要参考这篇；做到了高于实验标准）
https://www.jianshu.com/p/7f5e78e83a0e（分step的想法不错，而且Step 6讲得很好）
http://home.ustc.edu.cn/~liuly0322/blog/2022/03/19/csapp-shell/（结果测试方法值得学习，Trace 16讲得也明白）

参考文献可能有各自的许可证。

This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.