1. Due Date

Complete lab (Parts 1 and 2): Due by 11:59 pm, Monday, April 26, 2021

  • NOTE: each part of this lab has a separate git repo. You need to push your solution to each parts to their corresponding repos before the due date. Here is a link to the Lab 6 Part 2 assignment.

Checkpoint: Monday, April 19 push to git repo before 11:59pm.

  • By the checkpoint, you should have completed Part1, the shell program. We encourage you to get started on Lab 6 Part 2 before the weekly lab 11 meeting next week.

This lab should be done with your Lab 6 partner, listed here: Lab 6 partners. Please review our guidelines for working with partners, etiquette and expectations.

2. Lab Overview and Goals

You will implement a Unix shell program. A shell implements the command-line interface to Unix-like operating systems. bash is the name of the shell program that you interact with on our system.

In general, a shell program does the following:

  1. Prints a prompt and wait for the user to type in a command.

  2. Reads in the command string entered by the user.

  3. Parses the command line string into an argv list. We provide a library function parse_cmd that you can use for this part.

  4. If the command (first element in the parsed argv list) is a built-in shell command, the shell will handles performing this command on its own (without forking a child process).

  5. Otherwise, if it’s not a built-in command, it forks a child process to execute the command and waits for the child to exit (if the command is run in the foreground), or doesn’t wait for the child to exit (if the command is run in the background).

  6. Repeats until the user enters the built-in command exit to exit the shell program.

2.1. Lab Goals

  • Learn how a Unix shell program works by writing one, including the following features:

    1. Executing commands that run in the foreground and the background.

    2. Executing previous commands by interacting with the shell history (using the !num syntax.)

  • Learn how to create and reap processes with the fork, execvp, waitpid system calls.

  • Interact with signals and write signal handler code.

  • Gain more expertise with gdb and valgrind for debugging C programs.

3. Starting Point Code

3.1. Getting Your Lab Repo

Both you and your partner should clone your Lab 6 repo into your cs31/labs subdirectory:

  1. get your Lab 6 ssh-URL from the CS31 git org. The repository to clone is named Lab6-userID1-userID2 where the two user names match that of you and your Lab 6 lab partner.

  2. cd into your cs31/labs subdirectory:

    $ cd ~/cs31/labs
    $ pwd
  3. clone your repo

    git clone [the ssh url to your your repo]
    cd Lab6-userID1-userID2

There are more detailed instructions about getting your lab repo from the "Getting Lab Starting Point Code" section of the Using Git for CS31 Labs page.

As your start each lab assignment, it is good to first test that you and your partner have both successfully cloned your shared repo, and that you can share code by pushing a small change and by pulling a small change made by your partner. Follow the directions in the "Sharing Code with your Lab Partner" section of the Using Git for CS31 Labs page.

3.2. Starting Point files

$ ls
Makefile README.md cs31shell.c  parsecmd.h sleeper.c
  • Makefile: A Makefile simplifies the process of compiling your program. We’ll look at these in more detail later in the course. You’re welcome to look over this one, but you shouldn’t need to edit it for this lab. If you are interested, take a look at Section 10 for more information about make and makefiles. make builds the cs31shell program

  • README.md: some notes to you

  • cs31shell.c: the file in which to implement your shell program

  • parsecmd.h: the header file for the parsecmd library (open this in an editor to view the comments that contain lot of documentation about using this library).

  • sleeper.c: a program that sleeps for some time, useful for testing your shell’s support for running commands in the background.

4. Compiling and Running

You will implement your program in cs31shell.c.

Run make to compile the cs31shell program. Make compiles your solution in the cs31shell.c file, and also links in the class parsecmd.o library.

$ make

Run your shell program, it will enter its main loop and print out its shell prompt cs31shell>:

$ ./cs31shell
cs31shell>

5. Sample Output

Here is output from a run of my shell program: Sample Output

Note when my shell prompt is printed for jobs run in the background, and how the history command and the !num built-in command works.

6. Lab Details

For this lab, you will implement a shell program that:

  1. executes commands in the foreground (e.g., ls -l)

  2. executes commands in the background (e.g., ./sleeper &)

  3. implements the built-in command exit to terminate the shell process

  4. implements the built-in command history, which prints out the most recent command lines entered by the user (and each one’s command number in the history of commands).

  5. implements running commands using !num syntax, where num is a command from the history with a matching command number (e.g. !5 would re-execute command number 5 in the history of past commands.

With the starting point code is the parsecmd.h library header file. The parsecmd libary contains a function (parse_cmd) that you should use to parse a string containing the user’s input line to your shell into its argv list. Read the comments in parsecmd.h to see how to use this function.

There is also a program named sleeper that you can use to test your shell program (it is good for running in the background).

You will implement your shell in the cs31shell.c file.

See the Section 2 for a reminder of the main control flow of a shell program; your shell will implement this same control flow.

6.1. Using the parsecmd library

In parsecmd.h is the function prototype for the parse_cmd function that you can use to construct the argv array of strings from the command line string. The argv array is passed into execvp. The function comment describes how to call the function. There are also constant definitions that you can use in your shell (note: parsecmd.h is already #included at the top of cs31shell.c, so your code can use anything it defines).

The parse_cmd function is already implemented for you. It is compiled into a binary .o file that is linked into your cs31shell executable when you type make: you do not need to implement the parse_cmd function, but just call it in your code when you want to use it (much like you can call printf in your code without implementing the printf function).

6.2. Running commands in the foreground

When a command is run in the foreground, for example:

cs31shell> ./sleeper 2

Your shell program should fork() a child process to execute sleeper and then wait until the child process exits before proceeding. You can accomplish this by calling waitpid in the parent (your shell) by passing in the pid of the child process (the return value of fork()).

Your shell should detect blank line command input and not try to execute an "empty" command.

6.3. Running commands in the background

When a command is run in the background, for example:

cs31shell> ./sleeper 3 &

Your shell program should fork() a child process to execute sleeper, but it should NOT wait for the child to exit. Instead, after forking the child process, it should immediately return to execution step 1 of its main control flow (print out the prompt and read in the next command line). The child process will execute the command concurrently while the parent shell handles other command(s).

Your shell must still reap background child processes after they exit (reap its zombie children), so you can’t just forget about them! When a child that was run in the background exits, your shell program will receive a SIGCHLD signal. You should install a SIGCHLD handler that will call waitpid() to reap the exited child process(es).

Look at the lecture slides and at 9.4.1 Signals of the textbook for how to reap background processes by registering a signal handler on SIGCHLD. The signals example from Week 10 weekly lab may also be helpful.

Your shell should be able to run any number of processes in the background, so if you type in quick succession:

cs31shell> ./sleeper &
cs31shell> ./sleeper &
cs31shell> ./sleeper &
cs31shell> ps

The ps program output should list all three sleeper child processes.

6.4. Built-in commands

Your shell should respond to the following three built-in commands on its own. It should not fork off a child to handle these!

  1. exit: Terminate the shell program. You can print out a goodbye message, if you’d like.

  2. history: Print a list of the user’s MAXHIST most recently entered command lines. (Note: blank lines should not be added to the history, but all other command lines should).

  3. !num (where num is an actual number, e.g., !5): Re-execute a previous command from the history.

    • This previous command could be a run-in-the-foreground, run-in-the-background, or a built-in command that your shell should execute appropriately.

    • The command line retrieved from the history list should be added to the history list. That is, executing !5 should not put !5 in the history list; instead, a copy of the command line associated with command ID 5 from the history list should be added to the history list. See Section 5 for some exmaple output from my shell that includes examples of history and !num commands.

In all three cases, as long as the first argument matches the built-in command, you should run the built-in command. You do not need to check if there are extraneous arguments after the built-in command. For example, exit now will trigger the exit built-in command, and history -a will trigger the history built-in command.

6.5. Implementing History and !num

Your shell program should keep a list of the MAXHIST most recently entered command lines by the user. The starter code for cs31shell.c contains the line #define MAXHIST 10: use MAXHIST in your code, not 10, when referring to the size of the history.

The built-in history command should print out the history list in order from first (oldest) to last (most recently entered) command. For each element in the list, it should print the command ID and its corresponding command line string. The command ID is an ever-increasing number, and each command should increment the command ID by one. Use an unsigned int to store this value (don’t worry, about executing 4 billion commands in an attempt to overflow this value).

Your history list should be implemented as a circular queue of MAXHIST buckets where new commands are added to one end and old ones removed from the other end. Implement your circular queue as a circular queue of history_t structs. With the starting point code, history is declared as a statically allocated array of struct history_t structs:

struct history_t {
  char command[MAXLINE];  // the command line from a past command
  // TODO: you are welcome to add more fields to this struct type
};
// global variable used for history list
static struct history_t history[MAXHIST];

The struct history_t currently has a single field value defined that is a copy of the command string for the command entered. Feel free to change the struct history_t struct definition to include any additional fields you need. (NOTE: You cannot store the argv value of past commands in the history list, as there is only as single argv variable in the program. Instead, you need to reconstruct the argv list from the command line in the history list when a command is re-run from the history).

To access fields in an array of structs, use array indexing to access the bucket, then dot notation to access the field of the struct in that bucket Textbook Chapter 2.7.4 has more information about arrays of structs):

  // copy "hello there" to the command field of the struct in bucket i
  strcpy(history[i].command, "hello there");
  // set ch to the value of the 3rd char in the command string field
  // of the history_t struct in bucket 4 of the history list
  char ch = history[4].command[3];

Users can request the execution of a previous command, as stored in the history list, by executing the built-in !num, where "num" is a number corresponding to a history command ID. Upon receiving such a command:

  1. Search your history list for a command with a matching command ID. Remember that the command ID is not the position in the history list, it is the unique number of the command in your shell’s execution history (i.e. !5 is the 5th command run by your shell, !34 is the 34th command run by your shell).

  2. If a matching command ID is not found, print out an error message.

  3. Otherwise, use the command line from the matching history command ID, and re-execute it (this command now also becomes the most recent command to add to your history list).

If the command from the history list is not a built-in command, then your shell should run it just like it does any foreground or background program (parse its command line into argv list, fork-execvp and waitpid or not).

If the command from the history list is a built-in command (which could only be the history command), then it should execute it directly just like any built-in command.

See my sample output for examples of running all types of commands that your shell needs to support.

7. Lab Requirements

  • Your shell should support running programs in the foreground (e.g. ls -l)

  • Your shell should support running programs in the background (e.g. ./sleeper &)

  • Your shell should support the built-in command exit to terminate.

  • Your shell should support the built-in command history that keeps a list of the MAXHIST most recently entered command lines entered by the user. Use a constant definition for MAXHIST, and submit your solution with it set to 10, but try your shell out with other sizes too.

  • Your shell should support running commands from the history using !num syntax, where num is the command ID of a command from your command history (e.g. !33 should execute the command with command ID 33 from your history list). If a matching command num is not found the current history list, then your shell should print out and error message (command not found), otherwise the command line from the matching command on the history list should be executed (again).

  • Use the execvp version of exec for this assignment and waitpid instead of wait. See the "Tips" section below for examples.

  • You need to add a signal handler for SIGCHLD signals so that you can reap exited child processes that are run in the background. You should not leave any zombie children!

  • Whenever your code calls a library or system call function that returns a value, you should have code that checks the return value and handles error values.` You can call exit for unrecoverable errors, but print out an error message first (printf or perror for system call error return values).

  • The only global variables allowed are those associated with the history list and its state. All other program variables should be declared locally and passed to functions that use them.

  • For full credit, your shell should use good modular design, be well-commented and free of valgrind errors. The main function should probably not be much longer than that in the starting point code. Think about breaking your program’s functionality into distinct functions.

8. Tips and Hints

  • Implement and test incrementally (and run valgrind as you go). Here is one suggestion for an order to implement:

    1. Add a call to parse_cmd to parse the input line into argv strings.

    2. Add support for the built-in command exit.

    3. Add support for running commands in the foreground (the parent process, the shell, waits for the child pid that it forks off to exec the command).

    4. Add support for running commands in the background (the parent process, the shell, does NOT wait for the child pid that it forks off to run the command). After forking off a child to run the command, the shell program should go back to its main loop of printing out a prompt and waiting for the user to enter the next command.

      You will need to add a signal handler on SIGCHLD so that when the process that is running in the background terminates, the shell reaps it. Use waitpid to reap all child processes. Use the sleeper program to test:

        cs31shell> ./sleeper &
        cs31shell> ./sleeper 2 &
        cs31shell> ps w
    5. Add support for the history list (implemented as a circular queue). The operations on your circular queue are slightly different when the queue is not yet full from when it is full and you need to replace the oldest entry each time a new command is entered. Think about all state you will need to keep to keep track of the first element in the list (for printing out), the next insertion spot, and the end of the list.

    6. Add support for !num built-in command that will run command num from your history list. num is a command ID, which is increasing as your shell runs commands. It is NOT the bucket index into the history list.

  • Read the parsecmd.h file comments to see how to use the parse_cmd function. Use this function to create the argv array of strings from the command line string. This is the argv value passed to execvp.

  • The maximum length of a command line is defined in parsecmd.h. You can use the MAXLINE constant in your program.

  • Use the functions execvp(), waitpid(), and signal() for executing programs, waiting on children, and registering signal handlers. Note that the first argument to waitpid is the process id (PID) of the process you’d like to wait for, but if you pass in an argument of -1, it will wait for ANY reapable child process. This is useful inside your SIGCHLD handler, where you won’t know which child (or children) exited. You can pass it WNOHANG as the third parameter to prevent it from blocking when there are no children to reap.

    See the man pages for these functions for more information about them. Also look at the textbook and Weekly lab examples.

  • You can call fflush(stdout); after any calls to printf to ensure the printf output is written immediately to the terminal. Otherwise, the C standard I/O library might buffer it for a short while.

  • circular queue: I suggest first implementing the Wednesday lab circular queue of ints program, and then once you get that working implement your circular array of strings in your shell program. If you get stuck on the circular queue part, start with a simpler version, where the first history list element is always in bucket 0 and the last in bucket MAXHIST-1, and then shift values over as you add a new command to the last bucket each time. Then, come back to this later and try to turn this into it a circular queue (which, for large MAXHIST values, is much more efficient than having to shift values over to maintain the queue ordering).

  • built-in commands: your shell should read in and parse built-in commands just like regular commands. I recommend checking for a built-in command after calling parse_cmd, which strips off any leading or trailing white space characters. Remember you can use strncmp to compare two string values. Individual char values can be directly compared using relational operators (i.e. argv[0][i] is a char value you could directly compare to a character literal like x:

    if (argv[0][2] == 'x') { ...}
  • Remember that for any C string, a substring starting at bucket i in the string is also a C string. For example:

    str = "hello";
    printf("%s\n", str);      // prints the string hello
    printf("%s\n", &str[1]);  // prints the string ello
    printf("%s\n", &str[2]);  // prints the string llo
  • atoi can be used to convert a string to an int value (see last week’s lab examples).

  • For executing !num commands, you can use the parsecmd library to create the argv list from the command string in the history. If you have used good modular design so far, you should be able to just make calls to existing functions to execute the command.

  • Remember that you know how to define and use structs in C, and that you know how to use strings in C. See past weekly lab code, your lab solutions, and my C documentation.

    Remember that you can compare individual char values directly, but you need to use strcmp to compare two string values:

      char str[20];
      strcpy(str, "hello");
      if(str[2] == 'x') {
        printf("x in 2\n");
      }
      if(strcmp(str, "yo ho ho") == 0) {
        printf("str seems like a pirate\n");
      }

    Remember if you dynamically allocate space for a string (using malloc), you need to allocate a space at the end for the terminating null character ('\0'), and that you need to explicitly free the space when you are done using it (call free).

  • cleaning up zombie children. Your correct shell program should reap all exited children and not leave around zombie children after it exits. However, in its development stages, you may find that it creates zombie processes that it never reaps. You should check for, and kill, all zombies after running your shell program.

    To do this, after running your shell program, run ps in bash to see if you have left any un-reaped zombie children (or any extra instances of your shell program still running):

      ps
      233  pts/7   00:00:01  sleeper <zombie>

    If so, send it (them) a kill signal to die using either kill -9 or pkill -9:

      kill -9 233       # kills the process with pid 233
      pkill -9 sleeper  # kills all sleeper processes
  • When in doubt about what your shell should do, try running the command in the bash shell (a standard system terminal) and see what it does. For example, here is a way to see how bash executes the history built-in command: example of history and !num in bash.

9. Submitting your Lab

Please remove any debugging output prior to submitting.

To submit your code, commit your changes locally using git add and git commit. Then run git push while in your lab directory. Only one partner needs to run the final git push, but make sure both partners have pulled and merged each others changes.

Also, it is good practice to run make clean before doing a git add and commit: you do not want to add to the repo any files that are built by gcc (e.g. executable files). Included in your lab git repo is a .gitignore file telling git to ignore these files, so you likely won’t add these types of files by accident. However, if you have other gcc generated binaries in your repo, please be careful about this.

Here are the commands to submit your solution in the sorter.c file (from one of you or your partner’s ~/cs31/labs/Lab6-userID1-userID2 subdirectory):

$ make clean
$ git add cs31shell.c
$ git commit -m "correct and well commented Lab6 solution"
$ git push

Verify that the results appear (e.g., by viewing the the repository on CS31-S21). You will receive deductions for submitting code that does not run or repos with merge conflicts. Also note that the time stamp of your final submission is used to verify you submitted by the due date, or by the number of late days that you used on this lab, so please do not update your repo after you submit your final version for grading.

If you have difficulty pushing your changes, see the "Troubleshooting" section and "can’t push" sections at the end of the Using Git for CS31 Labs page. And for more information and help with using git, see the git help page.

At this point, you should submit the required [Lab 6 Questionnaire] (each lab partner must do this).

10. Handy References

General Lab Resources

C programming Resource

Specific to this assignment

General C resources