CSE550 Problem Set #1

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

Summary.

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:

• the main thread of your server is responsible for accepting incoming TCP network connections, reading the name of a file (absolute file paths) from a network connection, arranging to read the content of the file into memory, writing the file content over the network connection, then closing the network connection. This thread needs to be event-driven: it should use the poll() Linux system call to manage a set of file descriptors and receive event notifications associated with them.

• a threadpool implementation; this module should permit customers to dispatch a thread from the threadpool to a worker function. You should use the pthreads interface on Linux; you'll need to figure out how to create threads, locks, and condition variables, and you'll need to figure out how to use them to dispatch threads and put worker threads to sleep to wait for work.

• a worker function that receives the name of a file, reads the file content into memory, and arranges to return (a pointer to) the file content to whoever dispatched the thread to the worker function.

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:

• you'll need to use sigaction() to tell Linux not to send your process SIGPIPE signals whenever a client closes its end of a TCP connection.

• you'll need to use fcntl() twice to set a socket to non-blocking mode, so you can do asynchronous I/O. (The first call to get some flags; then you modify the flags, and call it again to set them in the OS.)

• you'll need to read up on how to set up a listening socket, accept an incoming connection, read/write over a socket, and close the connection. There are many, many web pages that describe how to do this in C, and you might be able to find some open source libraries that simplify this task. (You'll need to make sure they support non-blocking I/O, or you'll need to enhance them to use support it.)

• a worker thread will need to figure out how to notify the main event thread that it has finished reading a file. One way to solve this is with a self-pipe.

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 "gribble", I would run the command:

   tar -cvzf problemset1_submission_gribble.tar.gz problemset1

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

Grading

We will be basing your grade on several elements:

• Whether your code works! It should be correct, compile without warnings, and not leak memory, processes, descriptors, etc.

• How well structured your code is: you should have clean module interfaces, a nice decomposition, good comments, and so on.