This page is from the Fall 2013 course.
It may be replaced with an updated version later this semester. [Permalink to this version]

Problem Set 2 - The Good Auld Shell

Due: 8:59pm on Monday, 30 September.

That good auld shell of Wah-who-wah,
We'll bash it o'er and o'er.

It touch es our head and greps our dirs To split them tee and tar.
test -d Virginia ; echo $?
where more is Bourne-Again
less su join xargs |& cron aspell
for ls -t | tail -1 > vi.
Wha-who-wha
!!

traceroute 128.143.22.36
id -p ray
!!
fsck; !mount -u VA!

Note the earlier deadline time to ensure you are well-rested for class the following morning. In addition to the on-line submission, you will schedule a time to do a demo with Dave, Purnam, or Weilin.

Submission Form
Scheduling Demos

Purpose

The goals of this assignment are to:

Learn about process abstractions provided by MULTICS and its successors, and how they are used in Linux and its derivatives.
Understand how to create and manage processes by implementing a simple shell.
Do our part to help reduce the chances that homophobic chants will occur at UVa football games (although it is not clear this assignment will improve the overall quality or tastefullness of such chants). (Note: if you can get the stadium to use this version of the lyrics on the Jumbotron, you don't have to take the midterm. Sorry, its harder to earn credit at UVa than at Caltech.)

Collaboration Policy. For this problem set, you are expected to work with one other student in the class. You may select your own partner (but will be required to work with someone else on the next assignment). If you don't already have a partner, use the Piazza forum.

You and your partner should work together in a way that is efficient and collaborative, and ensures that both of you understand everything in the code you submit. You could choose to use pair programing if you want, but it is also fine to discuss together a plan for the assignment, work independently on different parts of the project, then explain and do code reviews on each others work after.

As part of the grading for this assignment, you will be a short demo with one of the course staff, and both partners will be expected to be able to answer questions about how your code works.

Please note that only one of you need to create the private repository for this problem set, the other member should work in the same repository as a collaborator.

In addition to working directly with your partner, you should feel free to discuss the problems, provide coding help, and ask for help with any students in the class (or anyone else in the world, for that matter), so long as you don't to it in a way that is detrimental to your own or anyone else's learning. You can do this in person, using the Piazza forum, using the #cs4414 and #rust IRC channels, or any other communication medium you find most effective.

Getting Started

Before continuing with this assignment, you should find a teammate and one of you should:

Set up the private repository named 'cs4414-ps2'.
Add your teammate and 'cs4414uva' as the collaborators.
Clone the empty private repository to your working environment. Instead of mygithubname below, use your github username.

    git clone https://github.com/mygithubname/cs4414-ps2.git

Get the starting code for ps2.

    git remote add course https://github.com/cs4414/ps2.git
    git pull course master
    git push --tags origin master

After finishing these steps, everyone in the team should have access to your own cs4414-ps2 repository that contains starting code for ps2.

Background

A shell is a program that provides an interface for users of an operating system to access the services of a kernel and launch other programs.

In some documents, operating system shells may include both command-line shell (e.g., bash and what you will build for this assignment) and graphical shell (e.g. Windows Shell). However, you are just required to design and implement a simple interactive shell that provides a command-line interface (CLI) to the operating system.

A simple interactive shell can just accept commands in interactive mode. Batch mode is not required even though it has become a common feature of modern OS shells.

The most popular text-based shell today is Bourne-Again shell (bash), which can be found on most GNU/Linux and Mac OS X systems (this is the default shell that runs when you open a Terminal on a Mac).

Exploring Processes

For the short answer (prose) questions, you should create a file answers.md in your cs4414-ps2 repository. The first lines of your answers.md file should be:

Title: Problem Set 2 Answers
Authors: <your names>

Start a bash shell on your computer (if you are running Mac OS X or some other Unix variant natively, you should be able to do this directly; if you are using Windows, you may do this on Ubuntu inside VirtualBox, but the results will be less interesting).

Exercise 1. Run ps aux in the bash shell to see the processes that are running. Visit the Piazza forum and post something interesting you learn from this (that hasn't already been contributed by another student there) in the "Exercise 1: What you learned from ps aux" forum thread.

Exercise 2. Use top (like I demoed in class) to examine how the resources are being used on your computer. Try running some programs like a web browser, playing a video, and running a large system build (for example, you could get the latest version of the Rust sources from https://github.com/mozilla/rust.git) and use that instead of the Rust 0.7 version for this assignment). While you do, watch which processes are getting to run and which are sleeping.

Is your operating system doing a good job allocating resources? Describe something interesting you observed or learned by doing the "Exercise 2: What you learned from top" forum thread.

The Good Auld Shell

For this assignment, we have provided starting code for a simple interactive shell in gash.rs. It is enough to start processes running, but not much else. The only internal command is 'exit', and it can only run external programs in foreground mode. For this assignment, you will modify gash to include some common and useful shell features, similar to those provided by bash.

Compile and run the shell. You should see the gash prompt on your screen:
gash>
Now try launching some programs using gash. For example, try running uname -a to view your system information. You should see something like:

gash> uname -a
Linux xuweilin-530U3BI-530U4BI-530U4BH 3.2.0-52-generic #78-Ubuntu SMP Fri Jul 26 16:21:44 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux

Add internal commands

Before working on process management, warm up by adding some basic internal commands for gash. At this point, the only internal command of gash is exit, which is really not sufficient for an OS shell.

For the next problem, you are required to implement two internal commands on gash:

cd: change the working directory of gash
history: list the commands you typed on gash

If you are not familiar with these commands, try them in the bash shell to get a sense of what they do. (The bash versions of these commands can take options that allow them to do more complex things, but it is not expected for you to implement any of those options.)

Problem 1. (modify gash.rs)
Modify the gash code so it supports the internal cd and history commands.

Running programs in the background

For the next problem, your goal is to enable the program launched by gash to run in background mode. This feature is very necessary in a multi-programming operating system. For example, you can use gash to run a zhttpto server in the background, and continue to use the shell to run other programs. This is very cool! Without background processes, you could only have one program running at a time in a shell, and would need to run many shells to run many programs.

The syntax for running a program in the background is to add an ampersand (&) at the end of the command. For example,

gash> ./zhttpto &

starts a zhptto server running in the background. Note that you get the gash prompt back after this and can run another command, but the zhttpto server is still running. (Try this in the bash shell to see the desired behavior that you will implement in your shell.)

Problem 2. (modify gash.rs)
Modify the gash code so it supports running programs in the background.

Warning/hint: This is a tough problem and you should think carefully about how to do it before starting to write code. You may need to call glibc functions such as fork() and execv() in unsafe blocks in Rust (but its best if you can figure out a way to avoid this).

Challenging ("optional") question: Suppose you are running a zhttpto server on a machine that is open to the rest of the Internet. Is there anyway for someone with only an external connection to your host (that is, they can just send requests over the Internet to your zhttpto server) to determine if your server is running as a foreground or background process? (If you have ideas on this, post them in the "Discussion 1: External Detection" Piazza post.)

I/O Redirection and Pipes

One useful feature most shells provide is input/output (I/O) redirection which allows you to connect two programs (and iteratively, connect any number of programs). For example, if you ask someone to run your simple zhttpto as a service, she might use this command to save all of the output as a log file while running it in the background:

$ ./zhttpto > ./zhttpto.log 2>&1 &

The command redirects standard output (stdout) to ./zhttpto.log and redirects the standard error (stderr) stream to standard output. Thus, all of the output that you can see on the screen in foreground mode will be redirected to ./zhttpto.log.

You are not expected to spend much time on parsing arguments, so your gash does not have to handle complex arguments like 2>&1, but I/O redirection using the basic < and > operators should work.

Problem 3. Modify your gash code to support I/O redirection for the standard output and standard input streams using < and >.

A similar feature is a pipe, which, like the I/O redirects is useful for connecting multiple programs, allows us to do it without needing to go through files.

Unix is designed to allow users to perform many complex operations by combining lots of simple programs using pipes. For example, we used ps aux | wc -l to count the number of processes running. This connects the output produced by ps aux to the input to wc -l. You can use pipes to connect multiple programs. For example, ./zhttpto | grep User-Agent | uniq | wc -l should count the number of unique user agent strings seen by your server. (Aside: if you are wondering why you might care, see https://panopticlick.eff.org/ to get a sense of how many browsers share your User Agent string.)

Problem 4. Modify the gash code so it supports piping using `|`.

Exercise 3. Now that you have both pipes and redirects working, you should be able to make some creative shell commands. Come up with an interesting way to combine small programs to accomplish something useful or interesting, and post it in the Piazza forum for Exercise 3: Fun With Pipes and Redirects.

Signal Handling

At this point, gash can now run your zhttpto program well in either the foreground or background. However, when you try to close zhttpto by pressing Ctrl-C or Ctrl-Z, you will find that not only zhttpto exits as expected, gash also exits! In order to solve this problem, you need to add signal handling in gash code.

Figure out what happens (in the bash shell) when you press Ctrl-C and Ctrl-Z. What's the difference between these two signals? For all signals in Unix, which is the most powerful one to stop process? And how can you do that? (You don't need to write up answers to these, but should think about them and discuss them with your teammate. Feel free to also discuss in the forums.)

Problem 5. [Optional Challenge: we have not figured out a reasonable way to do this in Rust, so you should consider this problem an "optional challenge" problem. But, we hope some students will come up with good solutions to it.]

Modify the gash code to support signal handling for Ctrl-C to have the behavior that it kills the current process, but does not exit the gash shell. If this is done correctly, you should be able to start a zhttpto server in the background, then run a command like tail -f gash.rs (which never completes). When you use Ctrl-C to kill the tail process, the zhttpo server running in the background should continue running, and you should get a new gash prompt and be able to run more commands.

Extra Features

Problem 6. Popular shells like bash provide many other features (e.g., command completion, but not very well), but there are also many features I would like in a shell that bash doesn't provide. For this question, its up to you to decide what you would like to add to your shell and to add it. It could be something that other shells already provide, or something more creative and interesting. The most obvious thing would be to add support for Ctrl-Z behavior and other commands to make it useful, but I'm hoping most teams will come up with more interesting ideas than that!

Submission and Demos

Once you decide to submit your project for grading after commiting some code and documents, you should add a tag on your code repository with a version number, and submit your assignment by providing the corresponding URL using the form (not yet posted) for PS2.

In addition to submitting using the form, you will also schedule a demo at which you will present your (hopefully working!) gash shell to one of the course staff and answer questions about how you did it. Both team members are expected to be able to answer questions about how you implemented your shell at the demos.

Submission Form
Scheduling Demos

Teaser

We will use both web server and shell in Problem Set 3 to build the ztta server (which, among other things, will include functionality similar to Apache server-side-includes that can run shell commands).

This assignment was created by Weilin Xu, Purnam Jantrania, and David Evans for University of Virginia cs4414 Fall 2013.