CSapp-Shell Lab

Shell Lab

本实验的目的是让学生更加熟悉过程控制和信号的概念，您可以通过编写一个简单的Unix shell程序来实现这一点，该程序支持作业控制

实验文件

• tsh.c：实验主体文件，代码写在这里
• tshref.out：包含参考shell程序的所有测试数据的输出结果
• tshref：示例程序

开始实验前需要补充一些知识（可以一边看函数，一边学习这些知识）

进程 & 线程 & 任务

进程

进程是指一个具有 独立功能 的程序在 某个数据集合上 的一次动态执行过程，它是操作系统进行资源分配和调度的基本单元

一次任务的运行可以发多个进程，这些进程相互合作来完成该任务的一个最终目标

每个进程都拥有自己的数据段，代码段和堆栈段，这就造成了进程在进行切换时操作系统的开销比较大，为了提高效率，操作系统又引入了另一个概念——线程

线程

线程是进程上下文中执行的代码序列，又称为轻量级的进程，它是操作系统能够调度的最小单元

线程可以对进程的内存空间和资源进行访问，并与同一进程中的其他线程共享，因此，线程的上下文切换的开销比进程小得多

一个进程可以拥有多个线程，其中每个线程共享该进程所拥有的资源，要注意的是，由于线程共享了进程的资源和地址空间，因此，任何线程对系统资源的操作都会给其他线程带来影响，由此可知，多线程中的同步是非常重要的问题

任务

任务是一个逻辑概念，指由一个软件完成的活动，或者是为实现某个目的的一系列操作

通常一个任务是一个程序的一次运行，一个任务包含一个或多个完成独立功能的子任务，这个独立的子任务是进程或者是线程

参考：操作系统中任务、进程和线程总结

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能

在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位

在三态模型中，进程状态分为三个基本状态，即运行态，就绪态，阻塞态

在五态模型中，进程分为新建态，终止态，运行态，就绪态，阻塞态

下面是实现进程控制的部分函数：

pid_t getpid(void);
pid_t getppid(void);

getpid 函数返回调用进程的 PID

getppid 函数返回它的父进程的 PID

void exit(int status);

exit 函数以 status 退出状态来终止进程

pid_t fork(void);

父进程通过调用 fork 函数创建一个新的运行的子进程

​ // 新创建的子进程几乎但不完全与父进程相同

fork 函数是有趣的（也常常令人迷惑），因为它只被调用一次，却会返回两次：一次是在调用进程（父进程）中，一次是在新创建的子进程中，在父进程中，fork 返回子进程的 PID，在子进程中，fork 返回 0，因为子进程的 PID 总是为非零，返回值就提供一个明确的方法来分辨程序是在父进程还是在子进程中执行

pid_t waitpid(pid_t pid, int *statusp, int options);

一个进程可以通过调用 waitpid 函数来等待它的子进程终止或者停止

• 默认情况下（当 options=0 时），waitpid 挂起调用进程的执行，直到它的 等待集合（wait set）中的一个子进程终止。
• 如果等待集合中的一个进程在刚调用的时刻就已经终止了，那么 waitpid 就立即返回

在这两种情况中，waitpid 返回导致 waitpid 返回的已终止子进程的 PID，此时，已终止的子进程已经被回收，内核会从系统中删除掉它的所有痕迹

unsigned int sleep(unsigned int secs);

sleep 函数将一个进程挂起一段指定的时间

int pause(void);

pause 函数让调用函数休眠，直到该进程收到一个信号

int execve(const char *filename, const char *argv[],
           const char *envp[]);

execve 函数在当前进程的上下文中加载并运行一个新程序

char *getenv(const char *name);
int setenv(const char *name, const char *newvalue, int overwrite);
void unsetenv(const char *name);

getenv 函数在环境数组中搜索字符串 “name=value”，如果找到了，它就返回一个指向 value 的指针，否则它就返回 NULL

如果环境数组包含一个形如 “name=oldva1ue” 的字符串，那么 unsetenv 会删除它，而 setenv 会用 newvalue 代替 oldvalue，但是只有在 overwirte 非零时才会这样，如果 name 不存在，那么 setenv 就把 “name=newvalue” 添加到数组中

int setpgid(pid_t pid, pid_t pgid);

将参数 pid 指定进程所属的组识别码设为参数 pgid 指定的组识别码

• 如果参数pid 为 0，则会用来设置目前进程的组识别码
• 如果参数pgid 为 0，则会以目前进程的进程识别码来取代

信号集函数

我们已经知道，我们可以通过信号来终止进程，也可以通过信号来在进程间进行通信，程序也可以通过指定信号的关联处理函数来改变信号的默认处理方式，也可以屏蔽某些信号，使其不能传递给进程

• SIGINT：程序终止(interrupt)信号，在用户键入INTR字符(通常是Ctrl-C)时发出，用于通知前台进程组终止进程
• SIGQUIT：和SIGINT类似，但由QUIT字符(通常是Ctrl-)来控制，进程在因收到SIGQUIT退出时会产生core文件, 在这个意义上类似于一个程序错误信号
• SIGTERM：程序结束(terminate)信号，与SIGKILL不同的是该信号可以被阻塞和处理，通常用来要求程序自己正常退出，shell命令kill缺省产生这个信号（如果进程终止不了，我们才会尝试SIGKILL）
• SIGSTOP：停止(stopped)进程的执行，注意它和terminate以及interrupt的区别，该进程还未结束，只是暂停执行，本信号不能被阻塞，处理或忽略
• SIGCHLD：告知父进程回收自己，但该信号的默认处理动作为忽略，因此父进程仍然不会去回收子进程，需要捕捉处理实现子进程的回收
• SIGTSTP：停止进程的运行，但该信号可以被处理和忽略，用户键入SUSP字符时(通常是Ctrl-Z)发出这个信号

那么我们应该如何设定我们需要处理的信号，我们不需要处理哪些信号等问题呢？信号集函数就是帮助我们解决这些问题的，下面是信号函数集：

int sigfillset(sigset_t * set); /* 填充 */ 

sigfillset 用来将参数 set 信号集初始化，然后把所有的信号加入到此信号集里

int sigemptyset(sigset_t *set); /* 清空 */

该函数的作用是将信号集初始化为空

int sigaddset(sigset_t *set, int signo); /* 添加 */

该函数的作用是把信号 signo 添加到信号集 set 中，成功时返回 0，失败时返回 -1

int sigdelset(sigset_t *set, int signo); /* 删除 */

该函数的作用是把信号 signo 从信号集 set 中删除，成功时返回 0，失败时返回 -1

int sigismember(sigset_t *set, int signo); /* 是否是成员 */

判断给定的信号 signo 是否是信号集中的一个成员，如果是返回 1，如果不是，返回 0，如果给定的信号无效，返回 -1

int sigprocmask( int how, const sigset_t *restrict set, sigset_t *restrict oset );

检测或更改其信号屏蔽字

• SIG_BLOCK 在本进程的阻塞列表中，添加 set 指向的阻塞列表
• SIG_UNBLOCK 在本进程的阻塞列表中，删除 set 指向的阻塞列表
• SIG_SETMASK 将目前的阻塞列表设成参数 set 指定的阻塞列表，如果参数 oset 不是 NULL ，那么目前的阻塞列表会由此指针返回（存储在 oset 中）

int sigpending(sigset_t *set); /* 代办(发出但没有没处理) */ 

将被阻塞的信号中 “停留在待处理状态” 的一组信号，写到参数 set 指向的信号集中，成功调用返回 0，否则返回 -1，并设置 errno 表明错误原因（获取被设置为SIG_BLOCK的信号集）

int sigsuspend(const sigset_t *sigmask); /* 挂起 */

通过将进程的屏蔽字替换为由参数 sigmask 给出的信号集，然后挂起进程的执行（在一个原子操作中先恢复信号屏蔽字，然后使进程休眠），如果接收到信号终止了程序，sigsuspend 就不会返回，如果接收到的信号没有终止程序，sigsuspend 就返回 -1，并将 errno 设置为 EINTR

​ // 注意操作的先后顺序，是先替换再挂起程序的执行

另外还有一个关键的结构体，以及其同名函数：

#include <signal.h>

struct sigaction
{
    void (*sa_handler) (int); // 函数指针(hook)
    sigset_t sa_mask; // 指定在信号处理函数执行期间需要被屏蔽的信号
    int sa_flags;
    void (*sa_restorer) (void);
}

int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact)

• sa_handler ：代表新的信号处理函数
• sa_mask ：用来设置在处理该信号时暂时将 sa_mask 指定的信号搁置
• sa_flags ：用来设置信号处理的其他相关操作
• sa_restorer ：此参数没有使用

函数 sigaction 会依参数 signum 指定的信号编号来设置该信号的处理函数，参数 signum 可以指定 SIGKILL 和 SIGSTOP 以外的所有信号

例子：

#include <stdio.h>
#include <signal.h>
#include <unistd.h>
 
void handler(int sig)
{
    printf("Handle the signal %d\n", sig);
}
 
int main(int argc, char **argv)
{	/* sigset_t类型专门用于定义信号集 */
    sigset_t sigset;    // 用于记录屏蔽字
    sigset_t ign;       // 用于记录被阻塞(屏蔽)的信号集
    struct sigaction act; 
 
    // 清空信号集
    sigemptyset(&sigset);
    sigemptyset(&ign);
 
    // 向信号集中添加 SIGINT
    sigaddset(&sigset, SIGINT);
 
    // 设置处理函数 和 信号集
    act.sa_handler = handler;
    sigemptyset(&act.sa_mask);
    act.sa_flags = 0;
    sigaction(SIGINT, &act, 0); /* 关联信号的处理函数 */
 
    printf("Wait the signal SIGNAL...\n");
    pause();
 
    // 设置进程屏蔽字, 在本例中为屏蔽 SIGINT
    sigprocmask(SIG_SETMASK, &sigset, 0);
    /* SIG_SETMASK:用sigset中的屏蔽字来替代该进程的信号屏蔽字 */
    printf("Please press Ctrl + C in 10 seconds...\n"); /* SIGINT已经被屏蔽 */
    sleep(10);
 
    // 测试 SIGINT 是否被屏蔽
    sigpending(&ign); /* 获取被阻塞的信号集(相当于执行:ign=sigset) */
    if (sigismember(&ign, SIGINT)) /* 检查屏蔽 */
    {
        printf("The SIGINT signal has ignored\n");
    }
 
    // 从信号集中删除信号 SIGINT
    sigdelset(&sigset, SIGINT);
    printf("Wait the signal SIGINT...\n");
 
    // 将进程的屏蔽字重新设置, 即取消对 SIGINT 的屏蔽
    // 并挂起进程
    sigsuspend(&sigset); /* 和sigprocmask(SIG_SETMASK, &sigset, 0)效果类似 */
 
    printf("The app will exit in 5 secondes!\n");
    sleep(5);
 
 	/* 由于先前的SIGINT信号停留在待处理状态，而现在进程已经不再阻塞该信号 */
 	/* 所以进程马上对该信号进行处理，从而在最后 */
 	/* 你不用输入 Ctrl+C 也会出现后面的处理语句 */
    return 0;
}

➜  [/home/ywhkkx/桌面] ./test
Wait the signal SIGNAL...
^CHandle the signal 2
Please press Ctrl + C in 10 seconds... # SIGINT 被终止了10秒
^C
^C
^C
^C
The SIGINT signal has ignored
Wait the signal SIGINT...
Handle the signal 2 # 设置的处理程序生效
The app will exit in 5 secondes!

实验要求

• tsh 的提示符为tsh>
• 用户的输入分为第一个的name和后面的参数，之间以一个或多个空格隔开，如果name是一个tsh 内置的命令，那么 tsh 应该马上处理这个命令然后等待下一个输入，否则，tsh 应该假设name是一个路径上的可执行文件，并在一个子进程中运行这个文件（这也称为一个工作、job）
• tsh 不需要支持管道和重定向
• 如果用户输入ctrl-c (ctrl-z)，那么SIGINT (SIGTSTP) 信号应该被送给每一个在前台进程组中的进程，如果没有进程，那么这两个信号应该不起作用
• 如果一个命令以“&”结尾，那么tsh应该将它们放在后台运行，否则就放在前台运行（并等待它的结束）
• 每一个工作（job）都有一个正整数PID或者job ID（JID）JID通过”%”前缀标识符表示，例如，“%5”表示JID为5的工作，而“5”代笔PID为5的进程
• tsh 应该有如下内置命令：
  • quit: 退出当前shell
  • jobs: 列出所有后台运行的工作
  • bg : 这个命令将会向代表的工作发送SIGCONT信号并放在后台运行，可以是一个PID也可以是一个JID
  • fg : 这个命令会向代表的工作发送SIGCONT信号并放在前台运行，可以是一个PID也可以是一个JID
• tsh 应该回收（reap）所有僵尸子进程，如果一个工作是因为收到了一个它没有捕获的（没有按照信号处理函数）而终止的，那么tsh应该输出这个工作的PID和这个信号的相关描述

解析已有代码

下面是实验已经给出的代码：

/*
 * tsh - A tiny shell program with job control
 *
 * <Put your name and login ID here>
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <errno.h>

 /* Misc manifest constants */
#define MAXLINE    1024   /* max line size */
#define MAXARGS     128   /* max args on a command line */
#define MAXJOBS      16   /* max jobs at any point in time */
#define MAXJID    1<<16   /* max job ID */

/* Job states */
#define UNDEF 0 /* undefined */
#define FG 1    /* running in foreground */
#define BG 2    /* running in background */
#define ST 3    /* stopped */

/*
 * Jobs states: FG (foreground), BG (background), ST (stopped)
 * Job state transitions and enabling actions:
 *     FG -> ST  : ctrl-z
 *     ST -> FG  : fg command
 *     ST -> BG  : bg command
 *     BG -> FG  : fg command
 * At most 1 job can be in the FG state.
 */

 /* Global variables */
extern char** environ;      /* defined in libc */
char prompt[] = "tsh> ";    /* command line prompt (DO NOT CHANGE) */
int verbose = 0;            /* if true, print additional output */
int nextjid = 1;            /* next job ID to allocate */
char sbuf[MAXLINE];         /* for composing sprintf messages */

struct job_t {              /* The job struct */
    pid_t pid;              /* job PID */
    int jid;                /* job ID [1, 2, ...] */
    int state;              /* UNDEF, BG, FG, or ST */
    char cmdline[MAXLINE];  /* command line */
};
struct job_t jobs[MAXJOBS]; /* The job list */
/* End global variables */


/* Function prototypes */

/* Here are the functions that you will implement */
void eval(char* cmdline);
int builtin_cmd(char** argv);
void do_bgfg(char** argv);
void waitfg(pid_t pid);

void sigchld_handler(int sig);
void sigtstp_handler(int sig);
void sigint_handler(int sig);

/* Here are helper routines that we've provided for you */
int parseline(const char* cmdline, char** argv);
void sigquit_handler(int sig);

void clearjob(struct job_t* job);
void initjobs(struct job_t* jobs);
int maxjid(struct job_t* jobs);
int addjob(struct job_t* jobs, pid_t pid, int state, char* cmdline);
int deletejob(struct job_t* jobs, pid_t pid);
pid_t fgpid(struct job_t* jobs);
struct job_t* getjobpid(struct job_t* jobs, pid_t pid);
struct job_t* getjobjid(struct job_t* jobs, int jid);
int pid2jid(pid_t pid);
void listjobs(struct job_t* jobs);

void usage(void);
void unix_error(char* msg);
void app_error(char* msg);
typedef void handler_t(int);
handler_t* Signal(int signum, handler_t* handler);

/*
 * main - The shell's main routine
 */
int main(int argc, char** argv)
{
    char c;
    char cmdline[MAXLINE];
    int emit_prompt = 1; /* emit prompt (default) */

    /* Redirect stderr to stdout (so that driver will get all output
     * on the pipe connected to stdout) */
    dup2(1, 2);

    /* Parse the command line */
    while ((c = getopt(argc, argv, "hvp")) != EOF) {
        switch (c) {
        case 'h':             /* print help message */
            usage();
            break;
        case 'v':             /* emit additional diagnostic info */
            verbose = 1;
            break;
        case 'p':             /* don't print a prompt */
            emit_prompt = 0;  /* handy for automatic testing */
            break;
        default:
            usage();
        }
    }

    /* Install the signal handlers */

    /* These are the ones you will need to implement */
    Signal(SIGINT, sigint_handler);   /* ctrl-c */
    Signal(SIGTSTP, sigtstp_handler);  /* ctrl-z */
    Signal(SIGCHLD, sigchld_handler);  /* Terminated or stopped child */

    /* This one provides a clean way to kill the shell */
    Signal(SIGQUIT, sigquit_handler);

    /* Initialize the job list */
    initjobs(jobs);

    /* Execute the shell's read/eval loop */
    while (1) {

        /* Read command line */
        if (emit_prompt) {
            printf("%s", prompt);
            fflush(stdout);
        }
        if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin))
            app_error("fgets error");
        if (feof(stdin)) { /* End of file (ctrl-d) */
            fflush(stdout);
            exit(0);
        }

        /* Evaluate the command line */
        eval(cmdline);
        fflush(stdout);
        fflush(stdout);
    }

    exit(0); /* control never reaches here */
}

/*
 * eval - Evaluate the command line that the user has just typed in
 *
 * If the user has requested a built-in command (quit, jobs, bg or fg)
 * then execute it immediately. Otherwise, fork a child process and
 * run the job in the context of the child. If the job is running in
 * the foreground, wait for it to terminate and then return.  Note:
 * each child process must have a unique process group ID so that our
 * background children don't receive SIGINT (SIGTSTP) from the kernel
 * when we type ctrl-c (ctrl-z) at the keyboard.
*/
void eval(char* cmdline)
{
    return;
}

/*
 * parseline - Parse the command line and build the argv array.
 *
 * Characters enclosed in single quotes are treated as a single
 * argument.  Return true if the user has requested a BG job, false if
 * the user has requested a FG job.
 */
int parseline(const char* cmdline, char** argv)
{
    static char array[MAXLINE]; /* holds local copy of command line */
    char* buf = array;          /* ptr that traverses command line */
    char* delim;                /* points to first space delimiter */
    int argc;                   /* number of args */
    int bg;                     /* background job? */

    strcpy(buf, cmdline);
    buf[strlen(buf) - 1] = ' ';  /* replace trailing '\n' with space */
    while (*buf && (*buf == ' ')) /* ignore leading spaces */
        buf++;

    /* Build the argv list */
    argc = 0;
    if (*buf == '\'') {
        buf++;
        delim = strchr(buf, '\'');
    }
    else {
        delim = strchr(buf, ' ');
    }

    while (delim) {
        argv[argc++] = buf;
        *delim = '\0';
        buf = delim + 1;
        while (*buf && (*buf == ' ')) /* ignore spaces */
            buf++;

        if (*buf == '\'') {
            buf++;
            delim = strchr(buf, '\'');
        }
        else {
            delim = strchr(buf, ' ');
        }
    }
    argv[argc] = NULL;

    if (argc == 0)  /* ignore blank line */
        return 1;

    /* should the job run in the background? */
    if ((bg = (*argv[argc - 1] == '&')) != 0) {
        argv[--argc] = NULL;
    }
    return bg;
}

/*
 * builtin_cmd - If the user has typed a built-in command then execute
 *    it immediately.
 */
int builtin_cmd(char** argv)
{
    return 0;     /* not a builtin command */
}

/*
 * do_bgfg - Execute the builtin bg and fg commands
 */
void do_bgfg(char** argv)
{
    return;
}

/*
 * waitfg - Block until process pid is no longer the foreground process
 */
void waitfg(pid_t pid)
{
    return;
}

/*****************
 * Signal handlers
 *****************/

 /*
  * sigchld_handler - The kernel sends a SIGCHLD to the shell whenever
  *     a child job terminates (becomes a zombie), or stops because it
  *     received a SIGSTOP or SIGTSTP signal. The handler reaps all
  *     available zombie children, but doesn't wait for any other
  *     currently running children to terminate.
  */
void sigchld_handler(int sig)
{
    return;
}

/*
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.
 */
void sigint_handler(int sig)
{
    return;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.
 */
void sigtstp_handler(int sig)
{
    return;
}

/*********************
 * End signal handlers
 *********************/

 /***********************************************
  * Helper routines that manipulate the job list
  **********************************************/

  /* clearjob - Clear the entries in a job struct */
void clearjob(struct job_t* job) {
    job->pid = 0;
    job->jid = 0;
    job->state = UNDEF;
    job->cmdline[0] = '\0';
}

/* initjobs - Initialize the job list */
void initjobs(struct job_t* jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
        clearjob(&jobs[i]);
}

/* maxjid - Returns largest allocated job ID */
int maxjid(struct job_t* jobs)
{
    int i, max = 0;

    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].jid > max)
            max = jobs[i].jid;
    return max;
}

/* addjob - Add a job to the job list */
int addjob(struct job_t* jobs, pid_t pid, int state, char* cmdline)
{
    int i;

    if (pid < 1)
        return 0;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid == 0) {
            jobs[i].pid = pid;
            jobs[i].state = state;
            jobs[i].jid = nextjid++;
            if (nextjid > MAXJOBS)
                nextjid = 1;
            strcpy(jobs[i].cmdline, cmdline);
            if (verbose) {
                printf("Added job [%d] %d %s\n", jobs[i].jid, jobs[i].pid, jobs[i].cmdline);
            }
            return 1;
        }
    }
    printf("Tried to create too many jobs\n");
    return 0;
}

/* deletejob - Delete a job whose PID=pid from the job list */
int deletejob(struct job_t* jobs, pid_t pid)
{
    int i;

    if (pid < 1)
        return 0;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid == pid) {
            clearjob(&jobs[i]);
            nextjid = maxjid(jobs) + 1;
            return 1;
        }
    }
    return 0;
}

/* fgpid - Return PID of current foreground job, 0 if no such job */
pid_t fgpid(struct job_t* jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].state == FG)
            return jobs[i].pid;
    return 0;
}

/* getjobpid  - Find a job (by PID) on the job list */
struct job_t* getjobpid(struct job_t* jobs, pid_t pid) {
    int i;

    if (pid < 1)
        return NULL;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].pid == pid)
            return &jobs[i];
    return NULL;
}

/* getjobjid  - Find a job (by JID) on the job list */
struct job_t* getjobjid(struct job_t* jobs, int jid)
{
    int i;

    if (jid < 1)
        return NULL;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].jid == jid)
            return &jobs[i];
    return NULL;
}

/* pid2jid - Map process ID to job ID */
int pid2jid(pid_t pid)
{
    int i;

    if (pid < 1)
        return 0;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].pid == pid) {
            return jobs[i].jid;
        }
    return 0;
}

/* listjobs - Print the job list */
void listjobs(struct job_t* jobs)
{
    int i;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid != 0) {
            printf("[%d] (%d) ", jobs[i].jid, jobs[i].pid);
            switch (jobs[i].state) {
            case BG:
                printf("Running ");
                break;
            case FG:
                printf("Foreground ");
                break;
            case ST:
                printf("Stopped ");
                break;
            default:
                printf("listjobs: Internal error: job[%d].state=%d ",
                    i, jobs[i].state);
            }
            printf("%s", jobs[i].cmdline);
        }
    }
}
/******************************
 * end job list helper routines
 ******************************/


 /***********************
  * Other helper routines
  ***********************/

  /*
   * usage - print a help message
   */
void usage(void)
{
    printf("Usage: shell [-hvp]\n");
    printf("   -h   print this message\n");
    printf("   -v   print additional diagnostic information\n");
    printf("   -p   do not emit a command prompt\n");
    exit(1);
}

/*
 * unix_error - unix-style error routine
 */
void unix_error(char* msg)
{
    fprintf(stdout, "%s: %s\n", msg, strerror(errno));
    exit(1);
}

/*
 * app_error - application-style error routine
 */
void app_error(char* msg)
{
    fprintf(stdout, "%s\n", msg);
    exit(1);
}

/*
 * Signal - wrapper for the sigaction function
 */
handler_t* Signal(int signum, handler_t* handler)
{
    struct sigaction action, old_action;

    action.sa_handler = handler;
    sigemptyset(&action.sa_mask); /* block sigs of type being handled */
    action.sa_flags = SA_RESTART; /* restart syscalls if possible */

    if (sigaction(signum, &action, &old_action) < 0)
        unix_error("Signal error");
    return (old_action.sa_handler);
}

/*
 * sigquit_handler - The driver program can gracefully terminate the
 *    child shell by sending it a SIGQUIT signal.
 */
void sigquit_handler(int sig)
{
    printf("Terminating after receipt of SIGQUIT signal\n");
    exit(1);
}

接下来就一个一个分析已有的函数（不包括 main）

Parseline

int main(int argc, char** argv)

argv[]：表示的是一个指针数组，一共有 argc 个元素，其中存放的是指向每一个参数的指针

argc：参数个数

int parseline(const char* cmdline, char** argv)
{ 
    static char array[MAXLINE]; /* holds local copy of command line */
    char* buf = array;          /* ptr that traverses command line */
    char* delim;                /* points to first space delimiter */
    int argc;                   /* number of args */
    int bg;                     /* background job? */

    strcpy(buf, cmdline);
    buf[strlen(buf) - 1] = ' ';  /* replace trailing '\n' with space */
    while (*buf && (*buf == ' ')) /* ignore leading spaces */
        buf++;

    /* Build the argv list */
    argc = 0;
    if (*buf == '\'') { // 转移符号,用于获取" ' "
        buf++;
        delim = strchr(buf, '\'');
    }
    else {
        delim = strchr(buf, ' ');
    }

    while (delim) {
        argv[argc++] = buf;
        *delim = '\0';
        buf = delim + 1;
        while (*buf && (*buf == ' ')) /* ignore spaces */
            buf++;

        if (*buf == '\'') {
            buf++;
            delim = strchr(buf, '\'');
        }
        else {
            delim = strchr(buf, ' ');
        }
    }
    argv[argc] = NULL;

    if (argc == 0)  /* ignore blank line */
        return 1;

    /* should the job run in the background? */
    if ((bg = (*argv[argc - 1] == '&')) != 0) {
        argv[--argc] = NULL;
    }
    return bg;
}

parseline 函数解析了以空格分隔的命令行参数（跳过所有空格和单引号，获取其中的有效指令），并构造最终会传递给 execve 的 argv 向量

​ // ‘&’ 表示后台运行，parseline 函数把是否在后台运行的信息存储在bg中，并返回

Struct job_t

struct job_t {              /* The job struct */
    pid_t pid;              /* job PID (进程ID) */
    int jid;                /* job ID [1, 2, ...] (任务ID) */
    int state;              /* UNDEF, BG, FG, or ST (任务状态) */
    char cmdline[MAXLINE];  /* command line (指令行) */
};
struct job_t jobs[MAXJOBS]; /* The job list */

全局结构体 job_t 是与“任务”有关的结构体

基于它，出现了以下的函数：

/* clearjob - Clear the entries in a job struct */
void clearjob(struct job_t* job) {
    job->pid = 0;
    job->jid = 0;
    job->state = UNDEF;
    job->cmdline[0] = '\0';
}

清空一个任务

/* initjobs - Initialize the job list */
void initjobs(struct job_t* jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
        clearjob(&jobs[i]);
}

任务初始化

/* maxjid - Returns largest allocated job ID */
int maxjid(struct job_t* jobs)
{
    int i, max = 0;

    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].jid > max)
            max = jobs[i].jid;
    return max;
}

获取最大的任务ID

/* addjob - Add a job to the job list */
int addjob(struct job_t* jobs, pid_t pid, int state, char* cmdline)
{
    int i;

    if (pid < 1)
        return 0;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid == 0) {
            jobs[i].pid = pid;
            jobs[i].state = state;
            jobs[i].jid = nextjid++;
            if (nextjid > MAXJOBS)
                nextjid = 1;
            strcpy(jobs[i].cmdline, cmdline);
            if (verbose) {
                printf("Added job [%d] %d %s\n", jobs[i].jid, jobs[i].pid, jobs[i].cmdline);
            }
            return 1;
        }
    }
    printf("Tried to create too many jobs\n");
    return 0;
}

添加一个新任务

/* deletejob - Delete a job whose PID=pid from the job list */
int deletejob(struct job_t* jobs, pid_t pid)
{
    int i;

    if (pid < 1)
        return 0;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid == pid) {
            clearjob(&jobs[i]);
            nextjid = maxjid(jobs) + 1;
            return 1;
        }
    }
    return 0;
}

删除一个任务

/* fgpid - Return PID of current foreground job, 0 if no such job */
pid_t fgpid(struct job_t* jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].state == FG)
            return jobs[i].pid;
    return 0;
}

返回某个任务的 进程ID

/* getjobpid  - Find a job (by PID) on the job list */
struct job_t* getjobpid(struct job_t* jobs, pid_t pid) {
    int i;

    if (pid < 1)
        return NULL;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].pid == pid)
            return &jobs[i];
    return NULL;
}

根据 进程ID 获取 任务地址

/* getjobjid  - Find a job (by JID) on the job list */
struct job_t* getjobjid(struct job_t* jobs, int jid)
{
    int i;

    if (jid < 1)
        return NULL;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].jid == jid)
            return &jobs[i];
    return NULL;
}

根据 任务ID 获取 任务地址

/* pid2jid - Map process ID to job ID */
int pid2jid(pid_t pid)
{
    int i;

    if (pid < 1)
        return 0;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].pid == pid) {
            return jobs[i].jid;
        }
    return 0;
}

根据 进程ID 获取 任务ID

/* listjobs - Print the job list */
void listjobs(struct job_t* jobs)
{
    int i;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid != 0) {
            printf("[%d] (%d) ", jobs[i].jid, jobs[i].pid);
            switch (jobs[i].state) {
            case BG:
                printf("Running ");
                break;
            case FG:
                printf("Foreground ");
                break;
            case ST:
                printf("Stopped ");
                break;
            default:
                printf("listjobs: Internal error: job[%d].state=%d ",
                    i, jobs[i].state);
            }
            printf("%s", jobs[i].cmdline);
        }
    }
}

打印任务的 “信息”，“状态” 和 “命令行”

Signal

对于程序的信号处理，先给出了 Signal：

/*
 * Signal - wrapper for the sigaction function
 */
handler_t* Signal(int signum, handler_t* handler)
{
    struct sigaction action, old_action;

    action.sa_handler = handler;
    sigemptyset(&action.sa_mask); /* block sigs of type being handled */
    action.sa_flags = SA_RESTART; /* restart syscalls if possible */

    if (sigaction(signum, &action, &old_action) < 0)
        unix_error("Signal error");
    return (old_action.sa_handler);
}

总而言之，Signal 用于初始化信号处理机制，通过调用 sigemptyset 来清空 sa_mask，通过调用 sigaction 把特定信号和特定处理程序绑定

最后给出了几个处理程序：

void unix_error(char* msg)
{
    fprintf(stdout, "%s: %s\n", msg, strerror(errno));
    exit(1);
}

void app_error(char* msg)
{
    fprintf(stdout, "%s\n", msg);
    exit(1);
}

void sigquit_handler(int sig)
{
    printf("Terminating after receipt of SIGQUIT signal\n");
    exit(1);
}

其他的处理程序就要自己完成了

编写目标代码

补全tsh.c中剩余的代码：

• void eval(char *cmdline)：解析并执行命令
• int builtin_cmd(char **argv)：检测命令是否为内置命令quit、fg、bg、jobs
• void do_bgfg(char **argv)：实现bg、fg命令
• void waitfg(pid_t pid)：等待前台命令执行完成
• void sigchld_handler(int sig)：处理SIGCHLD信号，即子进程停止或终止
• void sigint_handler(int sig)：处理SIGINT信号，即来自键盘的中断ctrl-c
• void sigtstp_handler(int sig)：处理SIGTSTP信号，即终端停止信号ctrl-z

Eval

void eval(char* cmdline)：解析并执行命令

void eval(char* cmdline)
{
    char* argv[MAXARGS] = { NULL };
    int FG_BG = parseline(cmdline, argv) + 1; // 获取命令存储到argv
    if (argv[0] == NULL)    return;

    if (!builtin_cmd(argv)) // 检查是否为内置命令
    {
        // 在函数内部加阻塞列表，不然之后可能会出现不痛不痒的bug
        sigset_t mask_all, mask_one, prev_one; // 定义信号集
        sigfillset(&mask_all); /* 添加所有信号到 mask_all */
        sigemptyset(&mask_one); /* 清空 mask_one */
        sigemptyset(&prev_one); /* 清空 prev_one */
        sigaddset(&mask_one, SIGCHLD); /* 添加 SIGCHLD 到 mask_one */

        pid_t fpid;
        sigprocmask(SIG_BLOCK, &mask_one, &prev_one); /* 防止子进程被调度 */
        fpid = fork(); /* 获取新进程 */
        if (!fpid)
        {
            // 子进程继承了父进程的阻塞表，也要解除阻塞(避免收不到它本身的子进程的信号)
            setpgid(0, 0); 
            sigprocmask(SIG_SETMASK, &prev_one, NULL);
            if (execve(argv[0], argv, environ) == -1) /* execve执行命令 */
            {
                printf("%s: Command not found\n", argv[0]);
                exit(0);
            }
        }
        else
        {
            // 依然是加塞，阻塞所有信号
            sigprocmask(SIG_BLOCK, &mask_all, NULL);
            addjob(jobs, fpid, FG_BG, cmdline);
            sigprocmask(SIG_SETMASK, &mask_one, NULL);

            // 后台则打印，前台则等待子进程结束
            if (FG_BG == FG)  waitfg(fpid);
            else
            {
                sigprocmask(SIG_SETMASK, &mask_all, NULL);
                int insert_jid = pid2jid(fpid);
                if (FG_BG == BG)	printf("[%d] (%d) %s", insert_jid, fpid, cmdline);
            }
        }
        sigprocmask(SIG_SETMASK, &prev_one, NULL);
    }
    return;
}

builtin_cmd

int builtin_cmd(char **argv)：检查 cmdline 是否为内置命令，并实现 jobs，quit

int builtin_cmd(char** argv)
{
    // 判断是不是内置函数，不是就返回，注意内置命令有要继续操作的一定
    // 要返回1，不是内置函数就是0

    if (!strcmp(argv[0], "quit"))
        exit(0);
    else if (!strcmp(argv[0], "jobs"))
    {
        listjobs(jobs); /* 打印jobs */
        return 1;
    }
    else if (!strcmp(argv[0], "bg") || !strcmp(argv[0], "fg"))
    {
        do_bgfg(argv); /* 执行bg,fg指令 */
        return 1;
    }
    // 对单独的&不处理
    else if (!strcmp(argv[0], "&"))
    {
        return 1;
    }
    return 0;     /* not a builtin command */
}

do_bgfg

实现 bg命令 (让后台工作继续在后台执行) 和 fg命令 (把后台命令恢复在前台执行)

void do_bgfg(char** argv)
{
    // 没有参数，其实应该也加上判断参数个数的语句才比较完整
    if (argv[1] == NULL)
    {
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return;
    }

    struct job_t* job;
    int id;

    // bg %5 和 bg 5 不一样，一个是对一个任务操作，另一个是对进程操作
    // 而任务代表了一个进程组

    // 要根据tshref的样例输出看有多少种情况

    // 读到jid
    if (sscanf(argv[1], "%%%d", &id) > 0)
    {
        job = getjobjid(jobs, id); /* 对任务操作 */
        if (job == NULL)
        {
            printf("%%%d: No such job\n", id);
            return;
        }
    }
    // 读到pid
    else if (sscanf(argv[1], "%d", &id) > 0)
    {
        job = getjobpid(jobs, id); /* 对进程操作 */ 
        if (job == NULL)
        {
            printf("(%d): No such process\n", id);
            return;
        }
    }
    // 格式错误
    else
    {
        printf("%s: argument must be a PID or %%jobid\n", argv[0]);
        return;
    }
    // 因为子进程单独成组，所以kill很方便
    if (!strcmp(argv[0], "bg"))
    {
        // 进程组是负数pid，发送信号并更改状态
        kill(-(job->pid), SIGCONT);
        job->state = BG;
        printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
    }
    else
    {
        // 如果fg后台进程，那么将它的状态转为前台进程，然后等待它终止
        kill(-(job->pid), SIGCONT);
        job->state = FG;
        waitfg(job->pid);
    }

    return;
}

waitfg

等待前台命令执行完成

void waitfg(pid_t pid)
{
    // 进程回收不需要做，只要等待前台进程就行
    sigset_t mask_temp;
    sigemptyset(&mask_temp);
    // 设定不阻塞任何信号
    // 其实可以直接sleep显式等待信号
    while (fgpid(jobs) > 0)
    	sigsuspend(&mask_temp);
    return;
}

sigchld_handler

• SIGCHLD：告知父进程回收自己，但该信号的默认处理动作为忽略，因此父进程仍然不会去回收子进程，需要捕捉处理实现子进程的回收

void sigchld_handler(int sig) 
{
    int olderrno = errno; /* 保存旧errno */
    pid_t pid;
    int status;
    sigset_t mask_all, prev; 
    
    sigfillset(&mask_all); /* 把所有信号放入mask_all */
    while((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0)
    {
        // WNOHANG | WUNTRACED 是立即返回
        // 用WIFEXITED(status)，WIFSIGNALED(status)，WIFSTOPPED(status)等来补获终止或者被停止的子进程的退出状态
    	if (WIFEXITED(status))  // 正常退出 delete
    	{
    		sigprocmask(SIG_BLOCK, &mask_all, &prev); /* 设置全阻塞 */
    		deletejob(jobs, pid); /* 删除任务 */
    		sigprocmask(SIG_SETMASK, &prev, NULL); /* 恢复信号集 */
    	}
    	else if (WIFSIGNALED(status))  // 信号退出 delete
    	{
    	    struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, &prev); /* 设置全阻塞 */
            printf("Job [%d] (%d) terminated by signal %d\n", job->jid, job->pid, WTERMSIG(status));
            deletejob(jobs, pid); /* 删除任务 */
            sigprocmask(SIG_SETMASK, &prev, NULL); /* 恢复信号集 */
    	}
    	else  // 停止 只修改状态就行
    	{
            struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, &prev); /* 设置全阻塞 */
            printf("Job [%d] (%d) stopped by signal %d\n", job->jid, job->pid, WSTOPSIG(status));
            job->state= ST; /* 设置任务状态为ST */
            sigprocmask(SIG_SETMASK, &prev, NULL); /* 恢复信号集 */
        }
    }
    errno = olderrno;  // 恢复
    return;
}

sigint_handler

• SIGINT：程序终止(interrupt)信号，在用户键入INTR字符(通常是Ctrl-C)时发出，用于通知前台进程组终止进程

void sigint_handler(int sig) 
{
        // 向子进程发送信号即可
   	int olderrno = errno;
   	pid_t pid = fgpid(jobs);
   	if (pid != 0)
            kill(-pid, sig);
   	errno = olderrno;
   	
   	return;
}

sigtstp_handler

• SIGTSTP：停止进程的运行，但该信号可以被处理和忽略，用户键入SUSP字符时(通常是Ctrl-Z)发出这个信号

void sigtstp_handler(int sig) 
{
    // 向子进程发送信号即可
    int olderrno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0)
    	kill(-pid, sig);
    errno = olderrno;
    return;
}

完整实验代码

/*
 * tsh - A tiny shell program with job control
 *
 * <Put your name and login ID here>
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <errno.h>

 /* Misc manifest constants */
#define MAXLINE    1024   /* max line size */
#define MAXARGS     128   /* max args on a command line */
#define MAXJOBS      16   /* max jobs at any point in time */
#define MAXJID    1<<16   /* max job ID */

/* Job states */
#define UNDEF 0 /* undefined */
#define FG 1    /* running in foreground */
#define BG 2    /* running in background */
#define ST 3    /* stopped */

/*
 * Jobs states: FG (foreground), BG (background), ST (stopped)
 * Job state transitions and enabling actions:
 *     FG -> ST  : ctrl-z
 *     ST -> FG  : fg command
 *     ST -> BG  : bg command
 *     BG -> FG  : fg command
 * At most 1 job can be in the FG state.
 */

 /* Global variables */
extern char** environ;      /* defined in libc */
char prompt[] = "tsh> ";    /* command line prompt (DO NOT CHANGE) */
int verbose = 0;            /* if true, print additional output */
int nextjid = 1;            /* next job ID to allocate */
char sbuf[MAXLINE];         /* for composing sprintf messages */

struct job_t {              /* The job struct */
    pid_t pid;              /* job PID */
    int jid;                /* job ID [1, 2, ...] */
    int state;              /* UNDEF, BG, FG, or ST */
    char cmdline[MAXLINE];  /* command line */
};
struct job_t jobs[MAXJOBS]; /* The job list */
/* End global variables */


/* Function prototypes */

/* Here are the functions that you will implement */
void eval(char* cmdline);
int builtin_cmd(char** argv);
void do_bgfg(char** argv);
void waitfg(pid_t pid);

void sigchld_handler(int sig);
void sigtstp_handler(int sig);
void sigint_handler(int sig);

/* Here are helper routines that we've provided for you */
int parseline(const char* cmdline, char** argv);
void sigquit_handler(int sig);

void clearjob(struct job_t* job);
void initjobs(struct job_t* jobs);
int maxjid(struct job_t* jobs);
int addjob(struct job_t* jobs, pid_t pid, int state, char* cmdline);
int deletejob(struct job_t* jobs, pid_t pid);
pid_t fgpid(struct job_t* jobs);
struct job_t* getjobpid(struct job_t* jobs, pid_t pid);
struct job_t* getjobjid(struct job_t* jobs, int jid);
int pid2jid(pid_t pid);
void listjobs(struct job_t* jobs);

void usage(void);
void unix_error(char* msg);
void app_error(char* msg);
typedef void handler_t(int);
handler_t* Signal(int signum, handler_t* handler);

/*
 * main - The shell's main routine
 */
int main(int argc, char** argv)
{
    char c;
    char cmdline[MAXLINE];
    int emit_prompt = 1; /* emit prompt (default) */

    /* Redirect stderr to stdout (so that driver will get all output
     * on the pipe connected to stdout) */
    dup2(1, 2);

    /* Parse the command line */
    while ((c = getopt(argc, argv, "hvp")) != EOF) {
        switch (c) {
        case 'h':             /* print help message */
            usage();
            break;
        case 'v':             /* emit additional diagnostic info */
            verbose = 1;
            break;
        case 'p':             /* don't print a prompt */
            emit_prompt = 0;  /* handy for automatic testing */
            break;
        default:
            usage();
        }
    }

    /* Install the signal handlers */

    /* These are the ones you will need to implement */
    Signal(SIGINT, sigint_handler);   /* ctrl-c */
    Signal(SIGTSTP, sigtstp_handler);  /* ctrl-z */
    Signal(SIGCHLD, sigchld_handler);  /* Terminated or stopped child */

    /* This one provides a clean way to kill the shell */
    Signal(SIGQUIT, sigquit_handler);

    /* Initialize the job list */
    initjobs(jobs);

    /* Execute the shell's read/eval loop */
    while (1) {

        /* Read command line */
        if (emit_prompt) {
            printf("%s", prompt);
            fflush(stdout);
        }
        if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin))
            app_error("fgets error");
        if (feof(stdin)) { /* End of file (ctrl-d) */
            fflush(stdout);
            exit(0);
        }

        /* Evaluate the command line */
        eval(cmdline);
        fflush(stdout);
        fflush(stdout);
    }

    exit(0); /* control never reaches here */
}

/*
 * eval - Evaluate the command line that the user has just typed in
 *
 * If the user has requested a built-in command (quit, jobs, bg or fg)
 * then execute it immediately. Otherwise, fork a child process and
 * run the job in the context of the child. If the job is running in
 * the foreground, wait for it to terminate and then return.  Note:
 * each child process must have a unique process group ID so that our
 * background children don't receive SIGINT (SIGTSTP) from the kernel
 * when we type ctrl-c (ctrl-z) at the keyboard.
*/
void eval(char* cmdline)
{
    char* argv[MAXARGS] = { NULL };
    int FG_BG = parseline(cmdline, argv) + 1;
    if (argv[0] == NULL)return;

    if (!builtin_cmd(argv))
    {
        sigset_t mask_all, mask_one, prev_one;
        sigfillset(&mask_all);
        sigemptyset(&mask_one);
        sigemptyset(&prev_one);
        sigaddset(&mask_one, SIGCHLD);

        pid_t fpid;
        sigprocmask(SIG_BLOCK, &mask_one, &prev_one);
        fpid = fork();
        if (!fpid)
        {
            setpgid(0, 0);
            sigprocmask(SIG_SETMASK, &prev_one, NULL);
            if (execve(argv[0], argv, environ) == -1)
            {
                printf("%s: Command not found\n", argv[0]);
                exit(0);
            }
        }
        else
        {
            sigprocmask(SIG_BLOCK, &mask_all, NULL);
            addjob(jobs, fpid, FG_BG, cmdline);
            sigprocmask(SIG_SETMASK, &mask_one, NULL);

            if (FG_BG == FG)waitfg(fpid);
            else
            {
                sigprocmask(SIG_BLOCK, &mask_all, NULL);
                int insert_jid = pid2jid(fpid);
                if (FG_BG == BG) printf("[%d] (%d) %s", insert_jid, fpid, cmdline);
            }
        }
        sigprocmask(SIG_SETMASK, &prev_one, NULL);
    }
    return;
}

/*
 * parseline - Parse the command line and build the argv array.
 *
 * Characters enclosed in single quotes are treated as a single
 * argument.  Return true if the user has requested a BG job, false if
 * the user has requested a FG job.
 */
int parseline(const char* cmdline, char** argv)
{
    static char array[MAXLINE]; /* holds local copy of command line */
    char* buf = array;          /* ptr that traverses command line */
    char* delim;                /* points to first space delimiter */
    int argc;                   /* number of args */
    int bg;                     /* background job? */

    strcpy(buf, cmdline);
    buf[strlen(buf) - 1] = ' ';  /* replace trailing '\n' with space */
    while (*buf && (*buf == ' ')) /* ignore leading spaces */
        buf++;

    /* Build the argv list */
    argc = 0;
    if (*buf == '\'') {
        buf++;
        delim = strchr(buf, '\'');
    }
    else {
        delim = strchr(buf, ' ');
    }

    while (delim) {
        argv[argc++] = buf;
        *delim = '\0';
        buf = delim + 1;
        while (*buf && (*buf == ' ')) /* ignore spaces */
            buf++;

        if (*buf == '\'') {
            buf++;
            delim = strchr(buf, '\'');
        }
        else {
            delim = strchr(buf, ' ');
        }
    }
    argv[argc] = NULL;

    if (argc == 0)  /* ignore blank line */
        return 1;

    /* should the job run in the background? */
    if ((bg = (*argv[argc - 1] == '&')) != 0) {
        argv[--argc] = NULL;
    }
    return bg;
}

/*
 * builtin_cmd - If the user has typed a built-in command then execute
 *    it immediately.
 */
int builtin_cmd(char** argv)
{
    if (!strcmp(argv[0], "quit"))
        exit(0);
    else if (!strcmp(argv[0], "jobs"))
    {
        listjobs(jobs);
        return 1;
    }
    else if (!strcmp(argv[0], "bg") || !strcmp(argv[0], "fg"))
    {
        do_bgfg(argv);
        return 1;
    }
    else if (!strcmp(argv[0], "&"))
    {
        return 1;
    }
    return 0;
}

/*
 * do_bgfg - Execute the builtin bg and fg commands
 */
void do_bgfg(char** argv)
{
    if (argv[1] == NULL)
    {
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return;
    }

    struct job_t* job;
    int id;

    if (sscanf(argv[1], "%%%d", &id) > 0)
    {
        job = getjobjid(jobs, id);
        if (job == NULL)
        {
            printf("%%%d: No such job\n", id);
            return;
        }
    }
    else if (sscanf(argv[1], "%d", &id) > 0)
    {
        job = getjobpid(jobs, id);
        if (job == NULL)
        {
            printf("(%d): No such process\n", id);
            return;
        }
    }
    else
    {
        printf("%s: argument must be a PID or %%jobid\n", argv[0]);
        return;
    }
    if (!strcmp(argv[0], "bg"))
    {
        kill(-(job->pid), SIGCONT);
        job->state = BG;
        printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
    }
    else
    {
        kill(-(job->pid), SIGCONT);
        job->state = FG;
        waitfg(job->pid);
    }
    return;
}

/*
 * waitfg - Block until process pid is no longer the foreground process
 */
void waitfg(pid_t pid)
{
    sigset_t mask_temp;
    sigemptyset(&mask_temp);
    while (fgpid(jobs) > 0)
        sigsuspend(&mask_temp);
    return;
}

/*****************
 * Signal handlers
 *****************/

 /*
  * sigchld_handler - The kernel sends a SIGCHLD to the shell whenever
  *     a child job terminates (becomes a zombie), or stops because it
  *     received a SIGSTOP or SIGTSTP signal. The handler reaps all
  *     available zombie children, but doesn't wait for any other
  *     currently running children to terminate.
  */
void sigchld_handler(int sig)
{
    int olderrno = errno;
    pid_t pid;
    int status;
    sigset_t mask_all, prev;

    sigfillset(&mask_all);
    while ((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0)
    {
        if (WIFEXITED(status))
        {
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            deletejob(jobs, pid);
            sigprocmask(SIG_SETMASK, &prev, NULL);
        }
        else if (WIFSIGNALED(status))
        {
            struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            printf("Job [%d] (%d) terminated by signal %d\n", job->jid, job->pid, WTERMSIG(status));
            deletejob(jobs, pid);
            sigprocmask(SIG_SETMASK, &prev, NULL);
        }
        else
        {
            struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, NULL);
            printf("Job [%d] (%d) stopped by signal %d\n", job->jid, job->pid, WSTOPSIG(status));
            job->state = ST;
            sigprocmask(SIG_SETMASK, &prev, NULL);
        }
    }
    errno = olderrno;
    return;
}

/*
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.
 */
void sigint_handler(int sig)
{
    int olderrno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0)
        kill(-pid, sig);
    errno = olderrno;
    return;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.
 */
void sigtstp_handler(int sig)
{
    int olderrno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0)
        kill(-pid, sig);
    errno = olderrno;
    return;
}

/*********************
 * End signal handlers
 *********************/

 /***********************************************
  * Helper routines that manipulate the job list
  **********************************************/

  /* clearjob - Clear the entries in a job struct */
void clearjob(struct job_t* job) {
    job->pid = 0;
    job->jid = 0;
    job->state = UNDEF;
    job->cmdline[0] = '\0';
}

/* initjobs - Initialize the job list */
void initjobs(struct job_t* jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
        clearjob(&jobs[i]);
}

/* maxjid - Returns largest allocated job ID */
int maxjid(struct job_t* jobs)
{
    int i, max = 0;

    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].jid > max)
            max = jobs[i].jid;
    return max;
}

/* addjob - Add a job to the job list */
int addjob(struct job_t* jobs, pid_t pid, int state, char* cmdline)
{
    int i;

    if (pid < 1)
        return 0;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid == 0) {
            jobs[i].pid = pid;
            jobs[i].state = state;
            jobs[i].jid = nextjid++;
            if (nextjid > MAXJOBS)
                nextjid = 1;
            strcpy(jobs[i].cmdline, cmdline);
            if (verbose) {
                printf("Added job [%d] %d %s\n", jobs[i].jid, jobs[i].pid, jobs[i].cmdline);
            }
            return 1;
        }
    }
    printf("Tried to create too many jobs\n");
    return 0;
}

/* deletejob - Delete a job whose PID=pid from the job list */
int deletejob(struct job_t* jobs, pid_t pid)
{
    int i;

    if (pid < 1)
        return 0;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid == pid) {
            clearjob(&jobs[i]);
            nextjid = maxjid(jobs) + 1;
            return 1;
        }
    }
    return 0;
}

/* fgpid - Return PID of current foreground job, 0 if no such job */
pid_t fgpid(struct job_t* jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].state == FG)
            return jobs[i].pid;
    return 0;
}

/* getjobpid  - Find a job (by PID) on the job list */
struct job_t* getjobpid(struct job_t* jobs, pid_t pid) {
    int i;

    if (pid < 1)
        return NULL;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].pid == pid)
            return &jobs[i];
    return NULL;
}

/* getjobjid  - Find a job (by JID) on the job list */
struct job_t* getjobjid(struct job_t* jobs, int jid)
{
    int i;

    if (jid < 1)
        return NULL;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].jid == jid)
            return &jobs[i];
    return NULL;
}

/* pid2jid - Map process ID to job ID */
int pid2jid(pid_t pid)
{
    int i;

    if (pid < 1)
        return 0;
    for (i = 0; i < MAXJOBS; i++)
        if (jobs[i].pid == pid) {
            return jobs[i].jid;
        }
    return 0;
}

/* listjobs - Print the job list */
void listjobs(struct job_t* jobs)
{
    int i;

    for (i = 0; i < MAXJOBS; i++) {
        if (jobs[i].pid != 0) {
            printf("[%d] (%d) ", jobs[i].jid, jobs[i].pid);
            switch (jobs[i].state) {
            case BG:
                printf("Running ");
                break;
            case FG:
                printf("Foreground ");
                break;
            case ST:
                printf("Stopped ");
                break;
            default:
                printf("listjobs: Internal error: job[%d].state=%d ",
                    i, jobs[i].state);
            }
            printf("%s", jobs[i].cmdline);
        }
    }
}
/******************************
 * end job list helper routines
 ******************************/


 /***********************
  * Other helper routines
  ***********************/

  /*
   * usage - print a help message
   */
void usage(void)
{
    printf("Usage: shell [-hvp]\n");
    printf("   -h   print this message\n");
    printf("   -v   print additional diagnostic information\n");
    printf("   -p   do not emit a command prompt\n");
    exit(1);
}

/*
 * unix_error - unix-style error routine
 */
void unix_error(char* msg)
{
    fprintf(stdout, "%s: %s\n", msg, strerror(errno));
    exit(1);
}

/*
 * app_error - application-style error routine
 */
void app_error(char* msg)
{
    fprintf(stdout, "%s\n", msg);
    exit(1);
}

/*
 * Signal - wrapper for the sigaction function
 */
handler_t* Signal(int signum, handler_t* handler)
{
    struct sigaction action, old_action;

    action.sa_handler = handler;
    sigemptyset(&action.sa_mask); /* block sigs of type being handled */
    action.sa_flags = SA_RESTART; /* restart syscalls if possible */

    if (sigaction(signum, &action, &old_action) < 0)
        unix_error("Signal error");
    return (old_action.sa_handler);
}

/*
 * sigquit_handler - The driver program can gracefully terminate the
 *    child shell by sending it a SIGQUIT signal.
 */
void sigquit_handler(int sig)
{
    printf("Terminating after receipt of SIGQUIT signal\n");
    exit(1);
}

实验验证

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace01.txt -s ./tsh -a "-p"
#
# trace01.txt - Properly terminate on EOF.
#

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace02.txt -s ./tsh -a "-p"
#
# trace02.txt - Process builtin quit command.
#

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace03.txt -s ./tsh -a "-p"
#
# trace03.txt - Run a foreground job.
#
tsh> quit

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace04.txt -s ./tsh -a "-p"
#
# trace04.txt - Run a background job.
#
tsh> ./myspin 1 &
[1] (8422) ./myspin 1 &

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace05.txt -s ./tsh -a "-p"
#
# trace05.txt - Process jobs builtin command.
#
tsh> ./myspin 2 &
[1] (8428) ./myspin 2 &
tsh> ./myspin 3 &
[2] (8430) ./myspin 3 &
tsh> jobs
[1] (8428) Running ./myspin 2 &
[2] (8430) Running ./myspin 3 &

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace06.txt -s ./tsh -a "-p"
#
# trace06.txt - Forward SIGINT to foreground job.
#
tsh> ./myspin 4
Job [1] (8441) terminated by signal 2

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace07.txt -s ./tsh -a "-p"
#
# trace07.txt - Forward SIGINT only to foreground job.
#
tsh> ./myspin 4 &
[1] (8447) ./myspin 4 &
tsh> ./myspin 5
Job [2] (8449) terminated by signal 2
tsh> jobs
[1] (8447) Running ./myspin 4 &

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace08.txt -s ./tsh -a "-p"
#
# trace08.txt - Forward SIGTSTP only to foreground job.
#
tsh> ./myspin 4 &
[1] (8458) ./myspin 4 &
tsh> ./myspin 5
Job [2] (8460) stopped by signal 20
tsh> jobs
[1] (8458) Running ./myspin 4 &
[2] (8460) Stopped ./myspin 5 

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace09.txt -s ./tsh -a "-p"
#
# trace09.txt - Process bg builtin command
#
tsh> ./myspin 4 &
[1] (8467) ./myspin 4 &
tsh> ./myspin 5
Job [2] (8469) stopped by signal 20
tsh> jobs
[1] (8467) Running ./myspin 4 &
[2] (8469) Stopped ./myspin 5 
tsh> bg %2
[2] (8469) ./myspin 5 
tsh> jobs
[1] (8467) Running ./myspin 4 &
[2] (8469) Running ./myspin 5 

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace10.txt -s ./tsh -a "-p"
#
# trace10.txt - Process fg builtin command. 
#
tsh> ./myspin 4 &
[1] (8478) ./myspin 4 &
tsh> fg %1
Job [1] (8478) stopped by signal 20
tsh> jobs
[1] (8478) Stopped ./myspin 4 &
tsh> fg %1
tsh> jobs

#
# trace11.txt - Forward SIGINT to every process in foreground process group
#
tsh> ./mysplit 4
Job [1] (8489) terminated by signal 2
tsh> /bin/ps a
    PID TTY      STAT   TIME COMMAND
   1050 tty2     Ssl+   0:00 /usr/lib/gdm3/gdm-x-session --run-script env GNOME_SHELL_SESSION_MODE=ubuntu /usr/bin/gnome-session --systemd --session=ubuntu
   1058 tty2     Sl+    0:10 /usr/lib/xorg/Xorg vt2 -displayfd 3 -auth /run/user/1000/gdm/Xauthority -background none -noreset -keeptty -verbose 3
   1385 tty2     Sl+    0:00 /usr/libexec/gnome-session-binary --systemd --systemd --session=ubuntu
   4288 pts/0    Ss     0:00 -/bin/zsh
   8486 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace11.txt -s ./tsh -a -p
   8487 pts/0    S+     0:00 ./tsh -p
   8492 pts/0    R      0:00 /bin/ps a

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace12.txt -s ./tsh -a "-p" 
#
# trace12.txt - Forward SIGTSTP to every process in foreground process group
#
tsh> ./mysplit 4
Job [1] (8507) stopped by signal 20
tsh> jobs
[1] (8507) Stopped ./mysplit 4 
tsh> /bin/ps a
    PID TTY      STAT   TIME COMMAND
   1050 tty2     Ssl+   0:00 /usr/lib/gdm3/gdm-x-session --run-script env GNOME_SHELL_SESSION_MODE=ubuntu /usr/bin/gnome-session --systemd --session=ubuntu
   1058 tty2     Sl+    0:11 /usr/lib/xorg/Xorg vt2 -displayfd 3 -auth /run/user/1000/gdm/Xauthority -background none -noreset -keeptty -verbose 3
   1385 tty2     Sl+    0:00 /usr/libexec/gnome-session-binary --systemd --systemd --session=ubuntu
   4288 pts/0    Ss     0:00 -/bin/zsh
   8504 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace12.txt -s ./tsh -a -p
   8505 pts/0    S+     0:00 ./tsh -p
   8507 pts/0    T      0:00 ./mysplit 4
   8508 pts/0    T      0:00 ./mysplit 4
   8511 pts/0    R      0:00 /bin/ps a

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace13.txt -s ./tsh -a "-p"
#
# trace13.txt - Restart every stopped process in process group
#
tsh> ./mysplit 4
Job [1] (8517) stopped by signal 20
tsh> jobs
[1] (8517) Stopped ./mysplit 4 
tsh> /bin/ps a
    PID TTY      STAT   TIME COMMAND
   1050 tty2     Ssl+   0:00 /usr/lib/gdm3/gdm-x-session --run-script env GNOME_SHELL_SESSION_MODE=ubuntu /usr/bin/gnome-session --systemd --session=ubuntu
   1058 tty2     Sl+    0:11 /usr/lib/xorg/Xorg vt2 -displayfd 3 -auth /run/user/1000/gdm/Xauthority -background none -noreset -keeptty -verbose 3
   1385 tty2     Sl+    0:00 /usr/libexec/gnome-session-binary --systemd --systemd --session=ubuntu
   4288 pts/0    Ss     0:00 -/bin/zsh
   8514 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace13.txt -s ./tsh -a -p
   8515 pts/0    S+     0:00 ./tsh -p
   8517 pts/0    T      0:00 ./mysplit 4
   8518 pts/0    T      0:00 ./mysplit 4
   8521 pts/0    R      0:00 /bin/ps a
tsh> fg %1
tsh> /bin/ps a
    PID TTY      STAT   TIME COMMAND
   1050 tty2     Ssl+   0:00 /usr/lib/gdm3/gdm-x-session --run-script env GNOME_SHELL_SESSION_MODE=ubuntu /usr/bin/gnome-session --systemd --session=ubuntu
   1058 tty2     Sl+    0:11 /usr/lib/xorg/Xorg vt2 -displayfd 3 -auth /run/user/1000/gdm/Xauthority -background none -noreset -keeptty -verbose 3
   1385 tty2     Sl+    0:00 /usr/libexec/gnome-session-binary --systemd --systemd --session=ubuntu
   4288 pts/0    Ss     0:00 -/bin/zsh
   8514 pts/0    S+     0:00 /usr/bin/perl ./sdriver.pl -t trace13.txt -s ./tsh -a -p
   8515 pts/0    S+     0:00 ./tsh -p
   8524 pts/0    R      0:00 /bin/ps a

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace14.txt -s ./tsh -a "-p"
#
# trace14.txt - Simple error handling
#
tsh> ./bogus
./bogus: Command not found
tsh> ./myspin 4 &
[1] (8667) ./myspin 4 &
tsh> fg
fg command requires PID or %jobid argument
tsh> bg
bg command requires PID or %jobid argument
tsh> fg a
fg: argument must be a PID or %jobid
tsh> bg a
bg: argument must be a PID or %jobid
tsh> fg 9999999
(9999999): No such process
tsh> bg 9999999
(9999999): No such process
tsh> fg %2
%2: No such job
tsh> fg %1
Job [1] (8667) stopped by signal 20
tsh> bg %2
%2: No such job
tsh> bg %1
[1] (8667) ./myspin 4 &
tsh> jobs
[1] (8667) Running ./myspin 4 &

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace15.txt -s ./tsh -a "-p"
#
# trace15.txt - Putting it all together
#
tsh> ./bogus
./bogus: Command not found
tsh> ./myspin 10
Job [1] (8686) terminated by signal 2
tsh> ./myspin 3 &
[1] (8688) ./myspin 3 &
tsh> ./myspin 4 &
[2] (8690) ./myspin 4 &
tsh> jobs
[1] (8688) Running ./myspin 3 &
[2] (8690) Running ./myspin 4 &
tsh> fg %1
Job [1] (8688) stopped by signal 20
tsh> jobs
[1] (8688) Stopped ./myspin 3 &
[2] (8690) Running ./myspin 4 &
tsh> bg %3
%3: No such job
tsh> bg %1
[1] (8688) ./myspin 3 &
tsh> jobs
[1] (8688) Running ./myspin 3 &
[2] (8690) Running ./myspin 4 &
tsh> fg %1
tsh> quit

➜  [/home/ywhkkx/shlab-handout] ./sdriver.pl -t trace16.txt -s ./tsh -a "-p"
#
# trace16.txt - Tests whether the shell can handle SIGTSTP and SIGINT
#     signals that come from other processes instead of the terminal.
#
tsh> ./mystop 2
Job [1] (8704) stopped by signal 20
tsh> jobs
[1] (8704) Stopped ./mystop 2
tsh> ./myint 2
Job [2] (8707) terminated by signal 2