CSE550 Problem Set #1

out: Monday Jan 6th
due: Wednesday Jan 22nd by 5:00pm.

[ summary | part a | part b | how to submit | grading ]


For this problem set, you will be implementing two (hopefully simple!) pieces of systems software: a basic UNIX shell and a basic AMTED server. You must use C or C++ as your implementation language, and you should build your implementation on top of the CSE Linux distribution. If you like, you can use one of the UW CSE home VMs to develop on; note that VMware is free for UW students.

Part A -- implement a simple shell with pipe support

Your job is to implement, using C or C++ on Linux, a very simple UNIX shell capable of executing commands through a pipe. Our goal for this assignment is two-fold: to exercise your C/C++/Linux skills, and to get you to think about a clean design that handles the concurrency aspect of the shell. Because of this, you shouldn't worry about any of the more complex aspects of shells, like supporting command line arguments, environment variables, or other shell features. All you need to do is handle the execution of programs and being able to pipe stdout from one program to the stdin of another. More specifically, if the user types ls | wc, your shell program should fork off the two programs, which together calculate the number of files in the current directory. Similarly, if the user types ls | head | wc, you'll need to arrange to fork three processes.

To solve this programming exercise, you'll need to use some (but perhaps not all) of the following Linux system calls: fork, execve, open, close, pipe, dup2, and wait. The semantics of these system calls are very particular, and fork/wait have different semantics than in the Mesa paper, so read their man pages carefully. As a hint, you should use pipe to create a pipe, fork to execute the programs, and dup2 to replace stdin or stdout, and wait to wait for the processes to terminate, probably in that order.

You might also want to look at the readline() system call (man 3 readline) available on Linux, as well as strtok() in libC. Together, those calls will simplify the job of parsing user input in your shell.

Part B -- Implement a simple AMTED server

Your job is to implement in C/C++/Linux a simple asymmetric multi-threaded event driven server (AMTED), similar to the AMPED server architecture described in the Flash paper. In a nutshell, your implementation will need to have three pieces:

So, putting these three pieces together, when you launch your server, you should be able to use telnet to connect to your server, type in the pathname of a file, and then see the contents of the file. Better, you should be able to have multiple, simultaneous connections open into your server, and it should process them concurrently.

This assignment doesn't require a massive amount of code, but if you've never implemented an event-driven server before, it can be a little mind-bending. You need to use asynchronous I/O to handle all network interactions, and you'll need to keep some kind of finite state machine representation of each connection to know whether you are waiting for network input, waiting for file input from the thread pool, waiting to be able to write data back over the network, etc.

Use Google and stackoverflow.com to get hints on all the things you'll need to do. Some hints:

Finally, to support automated testing of your code, here is a more concrete specification:

What to turn in

When you're ready to turn in your assignment, do the following:

  1. Create a directory called "problemset1". In it, you should have three things: a subdirectory called "parta", a subdirectory called "partb", and a README.TXT file.

  2. The README.TXT file should contain your name, student number, and UW email address, as well as instructions on how to launch your server.

  3. "parta" should contain your part a code, as well as a Makefile for compiling it. Running "make" should produce an executable called "550shell". Your code should be clean, well commented, etc.

  4. "partb" should contain your part b code, as well as a Makefile for compiling it. Running "make" should produce an executable called "550server". Your code should be clean, well commented, etc.

  5. Create a submission tarball by running the following command, but replacing "UWEMAIL" with your email account name:
    tar -cvzf problemset1_submission_UWEMAIL.tar.gz problemset1
    For example, since my email account is "arvind", I would run the command:
    tar -cvzf problemset1_submission_arvind.tar.gz problemset1

  6. Use the course dropbox (there will be a link on the course homepage) to submit that tarball.


We will be basing your grade on several elements: