You are expected to understand this. CS 111 Operating Systems Principles, Fall 2006
You are here: CS111: [[2006fall:lab1b]]

Lab 1b: CS 111, Fall 06

Due Friday, October 20 at 12:00 noon
Assigned Friday, October 6

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 simple job control.

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: simple job control.

The background execution operator & ordinarily runs programs in parallel in the background. For instance, this foreground command:

wc -l /usr/share/dict/words

will count the number of lines in /usr/share/dict/words, print the result, and finally return to the shell prompt. But in this background command:

wc -l /usr/share/dict/words &

the wc process runs in the background. The shell prompt appears immediately, so you can type more commands as wc works. wc's result is printed when it is done.

Job control is a shell feature that lets the shell user move commands into and out of the background. For instance, the user can decide that a command is taking too long, and put that command into the background; or take a command that is in the background, and put it into the foreground. We don't want you to implement all of job control, though, which gets surprisingly difficult. Instead you are to implement one small piece: the ability to put a background job into the foreground.

Here's how bash does this. When you run a command in the background, bash prints a number in brackets. This is the background command's job number. (It also prints the process ID of the command.)

$ sleep 100 &
[1] 23861

You can then put a background process into the foreground by typing %[job number]. For instance:

$ %1
sleep 100
(... waits a long time ...)

"Putting a background process into the foreground" means that the shell will not print its prompt and accept a new command until the formerly-background process completes.

Your job control implementation should have the following properties.

  • Every top-level background command should print a job number. That job number cannot be in use by any existing background command (i.e., any background command that hasn't completed yet). The bash shell picks the lowest number >= 1 that's not in use at the moment but you can use any other strategy.
  • The command %[job number] should "put that job in the foreground". Unlike bash, you do not need to print out the identity of the job; just put it "in the foreground". But if that job number has already exited by that time, you should print an error message instead. Specifically, you should print fg: no such job to standard error. As a special case, if the job only recently finished -- i.e., while the user was typing the %[job number] command -- you may print fg: job has terminated.
  • Background commands inside parentheses should not be given job numbers, and it is an error when %[job number] occurs inside parentheses. Investigate bash's behavior when %[job number] occurs in parentheses to see what type of error to print.
  • The user might try to give a foreground command %[job number] redirections, such as "%1 > foo"; or put it in the background, such as "%1 &"; or use it in a pipeline, such as "%1 | cat". We do not specify how foreground commands should act in these cases. For instance, they could be errors, or they could ignore the redirections/pipeline and work normally. Choose how your code behaves in these cases and document that choice in answers.txt.
  • However, foreground commands and semicolons must work together, as in %1 ; echo foo. This means "put job 1 in the foreground and wait till it completes; then run echo foo."

Here's some examples of how your shell might behave.

ospsh_fall06$ sleep 100 &
ospsh_fall06$ %1
                                   ... at this point the shell waits a while ...

ospsh_fall06$ sleep 100 &
ospsh_fall06$ sleep 1 &
ospsh_fall06$ sleep 1 ; %2         by the time "%2" runs, the old "sleep 1" will have exited
fg: no such job                    "fg: job has terminated" is also acceptable
ospsh_fall06$ %1
                                   ... at this point the shell waits a while ....


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 job control 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!

2006fall/lab1b.txt · Last modified: 2007/10/03 10:10 by kohler
Recent changes RSS feed Driven by DokuWiki