Out: Monday, October 6
Due: Monday, October 13
The project is due at the beginning of class on the indicated due date. You can work on the project on any platform that you want, but you must submit your work on the DEC Alpha instructional machines sanjuan or orcas using the turnin program (use man turnin for specific details). You should use C for all programming in this project.
The project is intended to accomplish a number of things:
For this assignment, we'd like you to work alone. You may certainly discuss the problems with other people in the class, but everyone must turn in their own solutions. As always, feel free to ask the TA any questions you wish, whether during office hours, during section, or over e-mail.
If you haven't done so already, please send mail to majordomo@cs with subscribe cse451 in the body of the message to subscribe to the course mailing list. You will also need to create a personal page on the course homepage where you will get project grades and feedback. This can be done by going to the course homepage and following the appropriate links and instructions.
We will want you to turn in all three parts to this assignment at the same time. Running cp -r /cse/courses/cse451/97au/projects/project1 ~ will make the appropriate directories and copy all the files you'll need into a subdirectory project1 under your home directory.
The queue is a fundamental data structure in operating systems. A queue is useful, for example, when several processes or threads need the same resource (say, the CPU). Typically the first process/thread will get the resource and the others are placed on a queue while they wait for the resource to become available.
Write a queuing package that manages the opaque queue data type defined in /cse/courses/cse451/97au/projects/project1/queue/queue.h. As specified in the header file, your queue management package will implement operations for:
The template makefile and the queue header file should already be in the ~/project1/queue/ subdirectory you copied earlier. Your job is to write the API (Application Programming Interface) routines that allow another application to use your queueing code with no knowledge of its underlying implementation. The function names and arguments that you need to implement for this assignment are already defined in queue.h. Note that the queue_t passed to the functions is not mutable (so you cannot change the value once created). Your program should include our queue.h header file using the #include C preprocessor directive. Do not change the function names or arguments. Do not modify queue.h. An operating system is its API; you can't change it if you're the user, and you can't (easily) change it if you're the implementor. Getting the API right the first time is therefore incredibly important. Getting it right means "usable, efficient, implementable, correct." Consider these criteria when you are implementing your queue package.
A client of your queue API package should only have to include queue.h and link your object file. Place the code implementing the functions in a file named "queue.c".
Like any component of a large software system, your code will need to be tested. You will need to create a main program that will give your queue API a good workout. Your main program should not be in queue.c; instead, place it in queuetest.c. Put some thought into how to best test the queue routines. Come up with tests that cover many scenarios. Careful testing is vital to quality code development. Keep in mind that your queue code may be tested by a similar automatic test program written by the TA, so it's in your interest to make your test program at least as thorough as you think the TA's will be! Your queue code should never incur a segmentation violation if passed valid parameters, and don't forget those "corner cases" (adding/deleting from an empty queue, iterating over an empty queue, etc.).
Use the Makefile provided as a template to construct a Makefile that will compile your queue package and test program. You should have a make target named queuetest such that, when make queuetest is invoked in the directory, your test program will compile into a program named queuetest.
You should demonstrate that your queue package functions correctly by printing the results of all of your tests of the queue operations. For example, you should demonstrate the iteration function by printing every element in a queue. Direct the output of your test program into a file named queue.out in the directory.
System calls take a long time, possibly much more so than regular procedure calls. Show that this is the case by timing how long system calls take to execute relative to simple procedure calls. You will probably want to use the standard Unix timing facility gettimeofday(). The Unix timer is quite coarse-grained relative to the time for a single system call, so you will need to execute each timed operation a large number of times in order to get accurate results. The system call getpid(), which was discussed in section, is extremely simple, and so is a good candidate for measurement. Remember to factor out any timing overhead that you may introduce and keep in mind the fact that you may be sharing the CPU(s) with other processes.
To see the cost of system calls relative to procedure calls, in addition to timing getpid() you should measure the time to call a regular user-level C function that simply returns the value of an integer global variable. This is essentially what getpid() does once it reaches the inside of the kernel. Thus the difference in time between your function call and the system call should give you a notion of the cost of making a system call.
Under your project1 directory, inside the timegetpid directory, create a file called timegetpid.c in which you will implement the code to time the system call and function call. Also create a Makefile that will build your program. You should be able to use the Makefile template again. The Makefile should have a target called timegetpid such that, when make timegetpid is invoked, your program will compile into an executable named timegetpid. Run your test program and place the two measurements it produces into a file called timegetpid.out. Please remember to include units with your measurements.
If you used a machine other than orcas or sanjuan for your measurements then in your timegetpid.out you should note which platform you used for your measurements (the name of the operating system and the type of machine used; try man uname). For fun, you may want to try running and compiling timegetpid on several different machines.
For the final part of the project you will be extending a simple UNIX shell program. A shell is the user-level program that allows the user to enter commands that execute and control programs. There are a zillion popular UNIX shell programs, including tcsh, csh, sh, ksh, bash, and zsh.
Under your project1/shell directory, make sure you have a copy of the very simple shell in /cse/courses/cse451/97au/projects/project1/shell/shell.c. Create a Makefile that will build this program. You should be able to use the Makefile template again. The Makefile should have a target called shell so that when make shell is invoked, the program will compile into an executable named shell.
Compile the program and then execute it by typing shell. From this shell's % prompt, try executing ls, ps, w, and finger to convince yourself that it is working. Note that it will not allow you to pass command-line arguments to programs (for example, you can type ls but not ls mydir). It will also not allow you to exit unless you press control-C, nor will it allow you to change directories. It is your job to fix those three deficiencies, producing a usable UNIX shell by modifying shell.c.
Look at the source code for the shell. It has a very simple structure, with a large outer loop. Inside this loop, it reads a line of text and then forks into two processes using the system call fork(). The child process then "becomes" the program that the user specified by using the system call execlp(). The parent process waits for the child process to complete by invoking the system call wait(). You will need to read the man pages for fork, execlp, and wait and sections 4.3.1, 19.3.2, and 19.4.1 to get a better idea of what exactly is going on.
To allow users to pass arguments to programs you will have to parse the input line into words separated by whitespace (spaces and'\t' tab characters) and place these words into an array of strings. You might try using strtok() for this (man strtok for a very good example of how to solve exactly this problem with strtok). Then you'll need to pass the name of the command as well as the entire list of tokenized strings to one of the other variants of exec, such as execvp(). These tokenized strings will then end up as the argv[] argument to the main() function of the new program executed by the child process.Try man execlp or man execvp for more details.
The second and third features, changing directories and exiting, are common shell commands that are of necessity commands internal to the shell. That is to say, forking a copy of the shell and then telling the child to execute a program that will change directories or exit would leave the parent shell process unaffected. To allow the user to execute internal commands, you'll need to check for these as special cases before forking and execing.
To allow the user to exit the shell, create a new internal command called exit that takes no parameters (i.e., usage = "exit"). When the user uses this command, the shell should exit.
To allow the user to change the current working directory, create a new internal command called cd that takes a single paramter: the directory to change to (i.e., usage = "cd <directory>"). The system call to change the current working directory is chdir().
Here is an example session with your finished shell :
% echo hello world
hello world
% pwd
~/project1/shell
% ls ..
queue timegetpid shell
% cd ..
% ls
queue timegetpid shell
% cd shell
% ls ..
queue timegetpid shell
% exit
NOTE: Please be very careful when working on this program that you do not alter the placement of the fork(), exec() and wait() calls, or the while() and if () statements guarding them. Many disasters can result when a program has a loop containing a fork() system call. Often if this happens a huge number of processes are created so that nobody else can use the machine. Some operating systems may even crash if this happens.
We would like you to turn in all three parts together. All three parts of the assignment should be under your project1 directory. Use the turnin program to turn in the directory:
If you are in section AA, use this turnin command: turnin -c cse451=AA -p project1 project1
If you are in section AB, use this turnin command: turnin -c cse451=AB -p project1 project1
Get to know the Unix man page facility. You will be using it often this quarter! In particular, check out make, gdb, turnin, gettimeofday, getpid, fork, wait, execl, execvp, strtok, and ps. If you don't know what command you're looking for, try apropos <guess>(try man apropos for help on apropos).
Have fun!