Project 1: A Simple Shell

In this project you will implement a simple shell program that supports I/O redirection and pipelines. The goal of this project is for you to learn about the fork, execvp, and waitpid system calls, as well as I/O redirection.

Commands

Your shell will read commands from its standard input and execute them. Each command consists of one or more words separated by white space (spaces or tabs). The first word specifies a program to run. The shell invokes this program as a child process and all passes of the words (including the program name) to it as arguments. For example, consider this command:

find . -name shell.cc

It has four words: find, ., -name, and shell.c. The first word, find, is the name of the program to run.

I/O Redirection

Normally, the shell’s child processes use the same standard input and standard output files as the shell. However, the characters < and > can be used to change the standard input and/or output of a command. For example, the command

grep std::string shell.cc > lines

will write all of the lines of the file shell.cc that contain the string std::string to the file lines instead of the terminal, and the command

wc < shell.cc

will read shell.cc and output statistics such as the number of lines. The characters < and > can appear anywhere in a command; they terminate the current word, if any, and the next word is taken as the name of the file. The redirection information is not included in the arguments passed to the command. For example, consider the following command:

grep<shell.cc>match.txt -H

The grep command will receive two arguments, grep and -H; its standard input will come from the file shell.cc and its output will be written to the file match.txt.

Pipelines

If the character | appears in a command line, it ends one command and starts another; the standard output of the first command will be passed as input to the second command using a pipe. This is called a pipeline. For example,

grep std::string shell.cc | wc

will arrange for the lines of shell.cc containing the string std::string to be passed as standard input to wc, where they will be counted. It has the same effect as the following commands

grep std::string shell.cc > tmp
wc < tmp
rm tmp

If a pipeline also includes I/O redirection, < and > apply to their respective commands in the pipeline and redirections take priority over pipes (see Other Requirements for details).

Implementation

For this project you will need to use the following system calls:

You can learn more about these system calls with the man program. For example,

man execvp

will print information about the execvp system call.

Development and Testing

Do your work for this project on the Myth cluster. To get started, invoke the following command:

git clone https://web.stanford.edu/class/cs111/starters/shell.git cs111_p1

This will create a new directory cs111_p1. Do your work for the project in this directory. You can use Git to manage your revisions to the project.

The directory will contain a skeleton file sh111.cc in which we have provided code to parse command lines. The parser creates one cmd struct describing each suprocess that must be invoked; each cmd contains the words that must be passed to that command, plus zero or more redirect structs that describe I/O redirection for that command. See the code for detailed documentation of these structures. Once a command line has been parsed, the function run_pipeline will be invoked to create the child processes and wait for them to complete. You must implement the body of this function, creating children as described by the argument to run_pipeline. If more than one command is specified, you must create pipes between consecutive commands in the pipeline.

The directory will also contain a Makefile. If you type make, it will compile sh111.cc, creating an executable file sh111. You can run your shell by typing the following command:

./sh111

A prompt should appear and you should be able to invoke shell commands. Most simple shell commands should work just as well in sh111 as in your normal shell. However, a few commands, such as cd and exit, won’t work in sh111. These are built-in commands: normal shells such as bash execute them directly, without invoking a child process. Commands like cd need to be built-in because executing them in a child process won’t be useful. For example, if a child process changes its working directory, that won’t have any effect on the shell or on future commands it invokes, and if a child process exits, that won’t cause the parent shell to exit. sh111 doesn’t support built-in commands, so these commands won’t work.

You can run a series of basic tests on your shell by invoking the command ./run_tests. It will print error messages if tests fail; you should then be able to go back and run the failing tests manually (each is just a series of shell commands) to debug the problem. We do not guarantee that these tests are exhaustive, so passing all of the tests is not necessarily sufficient to ensure a perfect score (CAs may discover other problems in reading through your code).

Other Requirements

Submitting Your Work

To submit your solutions, cd to the directory containing your work, then invoke the command

./submit

If you discover problems or improvements after you have submitted, you may resubmit; only the latest submit will be graded.