You are expected to understand this. CS 111 Operating Systems Principles, Spring 2007
You are here: CS111: [[2007spring:lab1b]]

Lab 1b: CS 111, Spring 07

Due Monday, April 23

Skeleton code available on SEASnet


In this second part of Lab 1 you will build upon your command line parser to make a complete shell which can actually execute the parsed commands. You'll implement support for all commands that can be parsed, which may use features such as I/O redirection, pipes, and conditional, sequential, and background execution. You'll also implement the two internal commands cd and exit, which change the working directory and exit the shell, respectively. (Puzzle: why do these two commands have to be built into the shell, when all other commands are executed by running the corresponding program?)

We've provided extensive skeleton code for these parts of the lab. But in addition, you must complete an open-ended problem for which we have not provided skeleton code, namely command substitution.

What is a shell?

A shell is a program whose main purpose is to run other programs. The shell parses commands into lists of arguments, then executes those commands using fork() and execvp(). Here's a simple shell command:

$ echo foo

(The initial $ is not part of the command. That is shorthand for the prompt that the shell prints before reading a command.) The shell parses this command into two arguments, echo and foo. The echo argument names the binary that should be executed. So the shell forks a child process to execute echo with those two arguments. The echo program has a very simple job: it just prints its arguments to the console. (echo foo will just print foo.) Meanwhile, the parent waits for the child to finish; when it does, the parent returns to read another command.

You may be interested in a reasonable tutorial for Unix shells. You can find others by searching for, e.g., ''shell tutorial'' on Google. Let us know if you find one you really like.

Each program has standard input, standard output, and standard error file descriptors, whose numbers are 0, 1, and 2, respectively. (You know them in C++ as cin, cout and cerr; in C the files are called stdin, stdout, and stderr.) The echo program writes its output to the standard output file descriptor. Normally this is the same as the shell's standard output, which is the terminal (your screen). But the shell lets you redirect these file descriptors to point instead to other files. For example:

$ echo foo > output.txt

This command doesn't print anything to the screen. But let's use the cat program, which reads a file and prints its contents to standard output, to see what's in output.txt:

$ cat output.txt

The > filename operator redirects standard output, < filename redirects standard input, and 2> filename redirects standard error. (The syntax varies from shell to shell; we generally follow the syntax of the Bourne shell or bash.)

Shells offer many ways to chain commands together. For example, the ; operator says "do one command, then do another". This shell command prints two lines:

$ echo foo ; echo bar

The && and || operators chain commands together based on their exit status. If a command accomplishes its function successfully, that command generally exits with status 0, by calling exit(0). (This is also what happens when the program runs off the end of its main function.) But if there's an error, most commands will exit with status 1. For example, the cat command will exit with status 0 if it reads its files successfully, and 1 otherwise:

$ cat output.txt
foo                                                 [[exit status 0]]
$ cat doesnotexist.txt
cat: doesnotexist.txt: No such file or directory    [[exit status 1]]

Now, && says "execute the command on the right only if the command on the left exited with status 0". And || says "execute the command on the right only if the command on the left exited with status NOT equal to 0". For example:

$ cat output.txt && echo "output.txt exists!"
Output.txt exists!
$ cat doesnotexist.txt && echo "doesnotexist.txt exists!"
cat: doesnotexist.txt: No such file or directory    [[Note: does not run echo!]]
$ cat output.txt || echo "output.txt does not exist."
$ cat doesnotexist.txt || echo "doesnotexist.txt does not exist."
cat: doesnotexist.txt: No such file or directory
doesnotexist.txt does not exist.

Parentheses ( ) allow you to run a set of commands in a subshell. This, in turn, lets you redirect the standard input, output, and error of a group of commands at once. For example:

$ ( echo foo ; echo bar ) > output.txt
$ cat output.txt

The exit status of a subshell is the same as the exit status of the last command executed.

Finally, you can also execute a command in the background with the & operator. Normally, the shell will not read a new command until the previous command has exited. But the & operator tells the shell not to wait for the command.

$ echo foo &
$ foo

(foo is printed on top of the next shell prompt.)

You may find the following commands particularly useful for testing your shell. Find out what they do by reading their manual pages. Be creative with how you combine these! (Also see the Lab 1B tester, below.)

  • cat (print one or more files to standard output)
  • echo (print arguments to standard output)
  • true (exit with status 0)
  • false (exit with status 1)
  • sleep (wait for N seconds then exit)
  • sort (sort lines)

In addition to running programs from the file system, shells have builtin commands that provide functionality that could not be obtained otherwise. Our shell will implement two such builtin commands, to change directories (cd) and to exit the shell (exit).

The cd command changes the shell's current directory, which is the default directory that the shell uses for files. So cd dir changes the current directory to dir. (You can think of the current directory as the directory that shows up by default when you use an "Open" or "Save" dialog in a GUI program.) Of course, files can also be manipulated using absolute pathnames, which do not depend on the current directory; /home/cs111/cmdline.c is an example.

There may also come a time when you would like to leave the wonderful world of your shell; the exit command instructs the shell to exit with a given status. (exit alone exits with status 0.)

(Why are cd and exit part of the shell instead of standalone programs?)

Lab materials

The skeleton code you will get for this second part of the lab consists of an updated Makefile and three additional files beyond what Lab 1A provided: ospsh.c, ospsh.h, and main-b.c. They are contained in the file lab1b.tar.gz which you can extract just like you did in Lab 1A. You will need to copy your version of cmdline.c from your lab1a directory (with the cp command). Most of the instructions for Lab 1B are included as comments in ospsh.c, but there is one exercise to complete in main-b.c. Additionally, you will need to add simple job control features, as described below.

You will likely find it helpful to learn more about the following functions (their manual pages are fairly descriptive): fork(), WEXITSTATUS(), execvp(), waitpid(), open(), close(), dup2(), pipe(), and chdir(). Remember that you can read manual pages by using the man program.

Our solution to the labeled lab exercises takes 109 lines of code above & beyond the lab handout (not counting cmdline.c and cmdline.h from Lab 1A).


The updated Makefile's default target is now the program ospsh, rather than cmdline. (You can still compile just the parsing parts of your program by running "make cmdline" to tell make to build that target.) To run your shell, you can type "./ospsh" at the command prompt. It will display its prompt, just like cmdline did. Now you can type commands to it, and after each command you type, it will display the parser output and then attempt to execute the command. Initially, it won't execute anything, but as you complete the lab, more and more kinds of commands will work. To quit your shell, you can press control-C to kill it, and after you implement the exit command, you will be able to type "exit" to terminate your shell.

Open-Ended Problem

Most of the exercises in the lab are specified in the source code as EXERCISE comments. However, there is one exercise which is left entirely to you: command substitution.

Command substitution constructs and runs a command using the output of another command. If a command contains some text between backticks, like this:

 echo `expr 2 + 3`

the shell runs the nested command specified between the backticks, reads its standard output, and passes the resulting string to the outer command. For example, since the expr 2 + 3 command prints 5 to standard output, the command above has the same effect as:

 echo 5

Here's another example. This command:

 file `which echo`

will report some properties about the echo program on your Unix system. The file program reports properties of a file. file echo would report properties of the echo file in your home directory, which isn't what you want; but which can tell you the specific file on disk that holds another program. This series of examples might help explain:

 $ file answers.txt 
 answers.txt: ASCII English text
 $ file echo
 echo: ERROR: cannot open `echo' (No such file or directory)
 $ file /bin/echo
 /bin/echo: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV) ...
 $ echo file /bin/echo
 file /bin/echo
 $ which echo
 $ file `which echo`
 /bin/echo: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV) ...
 $ echo file `which echo`
 file /bin/echo

The shell first expands the file `which echo` command to file /bin/echo, then runs that.

Command substitution is a particularly powerful shell feature: you can do cool things with it. But for the lab you will implement only a subset of the real shell's command substitution functionality.

Here's what you should do.

  • Command substitutions, such as ` abc d e f `, are parsed as single words. For example, the command file `which echo` should be parsed as two words, "file" and "`which echo`".
  • Before it runs a command, the shell expands any backtick expressions by running the command line inside the backticks, reading its standard output, and using the resulting string as the argument. If the very last character in the command's output is a newline '\n', the shell removes that character as a special case.

Here's how we'll limit our testing.

  • Your shell only needs to expand command substitutions that appear as separate command words. For example, echo `which echo` should work, but echo xxx`which echo` doesn't need to work.
  • Your shell doesn't need to split the output of a command substitution into tokens. (The real shell does.) Instead, treat the command substitution's output as a single token.
  • Your shell doesn't need to expand command substitutions inside double quotes. (The real shell does.)

Make sure you get the following things right.

  • A command substitution should run only if its command is going to run. For example, the command false && echo `foo` will not run either echo `foo` or foo.
  • A redirection file name might consist of a command substitution. This is legal: echo foo > `echo bar`, and it has the same effect as echo foo > bar.
  • A command substitution might be a full command line, possibly including redirections of its own. This is legal: echo `which echo | rev`. It will print ohce/nib/.

Your solution will probably use the read system call in addition to malloc, free, and several other functions you've written or used elsewhere in the lab.


We have provided a script that will help you to test your shell by giving it a set of sample inputs designed to test many of the features of your shell. However, does not test all of the behavior the lab requires. You should also design your own test cases to run either by hand or automatically. You may compare your shell's behavior to that of the shell bash, which might even be your default system shell. If you're not sure, you can always run it by typing bash at your prompt. All the syntax your shell is required to handle is also accepted by bash. (In a few isolated cases, such as > out with no command, your shell should produce an error on syntax that is OK for bash. The lab1a tester caught those cases.)

We will be using scripts very similar to the tester scripts included with Lab 1B to actually grade your labs. To run the Lab 1A tester, you may need to run "make cmdline" first in order to compile the Lab 1A portions of the lab separately. These tester scripts expect to be run on a Linux machine; although you can do Lab 1 on other Unix machines or even Windows with Cygwin installed, the tester scripts will incorrectly report errors for some test cases when they are run on platforms other than Linux. It is probably easiest to just use a Linux machine, since later labs will require it anyway.

The Lab 1B tester does not test command substitution at all. You should design your own tests for that functionality.

Design problem ideas

If you have been assigned a design problem for Lab 1, you may implement one of the following problems, or design your own, as long as it's similar in difficulty and the course staff approves. (If you want to design your own, do it early and get approval from us early.)

How to do design problems.

Control structures

Design and implement analogues of the if, for, and while control structures common to many programming languages. For example, your if structure should execute several commands in order, but only if some condition is true -- for example, only if a command exits with status 0. You may investigate current shells, such as bash, to see how they implement these structures, but your design must differ from bash/tcsh in at least one way. Point out that difference and describe why you think your version is better.

Shell functions

Design and implement a way for shell users to write their own "functions". Once a function f is defined, typing f at the command line will execute the function, rather than a binary program named f. For example, the user might write a function echo_twice that printed its arguments twice, by running the echo command twice. Discuss how other command line arguments will be passed to the shell function. As above, you may investigate current shells, such as bash, to see how they implement these structures, but your design must differ from bash/tcsh in at least one way. Point out that difference and describe why you think your version is better.

Complex redirections

Design and implement a new shell syntax that allows more complex forms of redirection. In particular, your syntax should support arbitrary redirection graphs, including:

  • Run five commands, a, b, c, d, and e, where:
    • a stdout ==> b stdin (this is a conventional pipe).
    • a stderr ==> c stdin.
    • b file descriptor 3 ==> d file descriptor 4.
    • d stdout ==> e stdin.
  • Run two commands, a and b, where:
    • a stdout ==> b stdin.
    • b stdout ==> a stdin. (This is a "bidirectional" pipe.)

You may investigate bash's implementation for some ideas (look for >&), but bash does not completely support this feature.

Tab completion

You may have noticed that in the default shell on the Linux machines in the lab, you can use the tab key to automatically complete partially typed commands, if the shell can figure out what you were trying to type (by searching for programs or files starting with what you have typed so far). Add support for this tab completion feature. Your tab completion should handle both program names in the default path (use the PATH environment variable) and special commands, such as cd and exit. You may want to investigate the GNU readline library, which can help.


When you are finished, edit the file named answers.txt and follow the instructions at the top of the file to fill in your name(s), student ID(s), email address(es), short descriptions of any extra credit or challenge problems you did, any known limitations of your code (including known bugs), and any other information you'd like us to have.

Then run "make tarball" which will generate a file lab1b-yourusername.tar.gz inside the lab1b directory. Upload this file to CourseWeb using a web browser to turn in the project. Remember to upload it only once if you are working in a team - the answers.txt file will allow us to give both team members credit.

Good luck!

2007spring/lab1b.txt · Last modified: 2007/09/28 00:27 (external edit)
Recent changes RSS feed Driven by DokuWiki