Assignment: The Yash Shell

CS230/330 - Operating Systems (Winter 2002).

Due : Friday, January 11, 11:59 p.m.

Overview

In this assignment, you will implement a simple Unix command shell known as Yash (Yet Another Shell). Your shell will have to support I/O redirection, pipes, signals, and background processes. The primary goal of this assignment is to familiarize yourself with the basic functionality of the Unix operating system including processes, files, and interprocess communication. In addition, you will be learning how to use some of the development tools needed for the class project.

Get an account

Your first step is to get a CS account. Afterwards, stop by my office in Ryerson 257B to introduce yourself and to get an account on the class machines. All of your work in this class must take place on these machines as they have been configured for the OS project and provide some additional stability when compared to other machines in the department. Please note, the following machines are available:

stonecrusher.cs.uchicago.edu
sunspot.cs.uchicago.edu
sidewinder.cs.uchicago.edu
stimulation.cs.uchicago.edu

Description

The input to your shell is a sequence of commands, each provided on a separate line of input text typed interactively at the keyboard. The following commands must be supported:

progname [args]

Runs the program progname with the given, possibly optional, arguments. For example:
yash % ls
foo.c
bar.c
yash % cp foo.c foo1.c
yash % rm -f foo.c

exit

Forces the shell to exit.

I/O Redirection

In addition to the above commands, your shell must support I/O redirection. I/O redirection is specified using the < and > operators at the end of a command line. For example:

progname [args] >file.out

Directs the standard output of progname to the file file.out.

progname [args] <file.in

Uses the contents of the file file.in as the standard input to program progname.

Both input and output redirection may be specified for a single command so your shell will have to check for both.

Pipes

Your shell also needs to support pipes. A pipe is nothing more than a way of hooking up the standard output of one program to the standard input to another. A pipe is indicated using the | operator as follows:

progname1 [args] | progname2 [args]

Pipes the output of program progname1 to the input of program progname2. For example:
yash % ls -l | wc
       7      56     366
yash % foo <infile | bar >outfile

Your shell only needs to support a single pipe. You do NOT need to support commands with multiple pipes, such as

yash % foo | bar | spam

Background Jobs

When a program runs, it normally blocks you from performing any other operations until it has completed. However, you can put a program into the background using the & operator. For example:

progname [args] &

Detaches the program progname and runs it in the background. Control is immediately returned to the command shell where additional commands can be executed. Background jobs should continue to run even if you quit the shell before they have finished.

History Buffer

Your shell should maintain a buffer of the last ten commands executed. You should also provide support for the following shorthand for re-executing a command from the history buffer:

![pattern]

Executes the most recent command from the history buffer which starts with the given pattern. For example:
yash % ls -l | wc
       8      67     484
yash % rm foo
yash % !l
ls -l | wc
       7      58     424 

Note that [pattern] does not contain any spaces. This shorthand should work in conjunction with I/O redirection, pipes, and backgrounding:

yash % !l >test
ls -l |wc >test

Signals

Finally, your shell needs to ignore a single signal, SIGINT. This signal is generated when a user presses Control-C on the keyboard. When received, it should be passed to the currently running program, but it should not cause your shell to terminate. Control-C has no effect on background jobs.

Exit codes

When programs terminate, they return an integer exit code to your shell. If this code is non-zero, your shell should print the returned value. For example:

yash % cp foo bar
cp: cannot access foo
[ Program returned exit code 1 ]
yash %

How to get started

Make sure you understand the assignment before beginning any work. Now, consider the following steps as a rough guide.

Step 1 : Create a CVS project

All projects in this class must be submitted using CVS. You should create a CVS project for your shell project BEFORE WRITING ANY CODE!

To create a project, follow these steps:

Create a directory called yash. For example:
```
unix % mkdir yash
```
In this directory, create two files, Makefile and yash.c. Makefile should look like this:
```
# Makefile for yash project
all:
       gcc yash.c -o yash
```
Note: The indentation before the 'gcc' must be a tab character--not a bunch of spaces.
Your yash.c file should look like this:
```
/* yash.c */
/* Your Name, CS230, Winter 2001 */
```
Now, in the SAME directory as your Makefile and yash.c files, type the following to create your CVS project:
```
unix % cvs import -m "Yash shell" yash yash start
```
Leave the yash directory you created and remove it. For example:
```
unix % cd ..
unix % rm -rf yash
```
Check out your yash project from CVS as follows:
```
unix % cvs checkout yash
```
This will create a directory called 'yash' and it will include the two files you created earlier. Do all of your subsequent work on these files and in this directory.

Do not proceed to step 2 until you successfully create a CVS project for your shell. Contact the TAs if you are unable to create a project for some reason.

Step 2 : Command line parsing

Write a function that takes a line of input text and parses it into some sort command structure containing information about the program name, arguments, and options for I/O redirection, pipes, and background jobs. If it helps, the syntax for the the shell is roughly as follows (optional fields are in brackets) :

command    :   program
           |   program | program
           |   "exit"
           ;
            
program    :   identifier [ arglist ] [ <infile ] [ >outfile ] [ & ]

Tokens and arguments are separated by white space. To simplify parsing, Your shell does NOT need to support quoted strings such as the following:

yash % foobar "This is a quoted argument"

Furthermore, you can assume that no whitespace separates the < and > operators from the filename that follows.

After you've got your command line parser working, write an infinite loop that does nothing but print the shell prompt ("yash % "), read a line of input, and pass it to your command line parser. Check the data returned from the parsing function to make sure it looks reasonable.

Note: writing the command parser should be easy. Just use the strtok() function from the C library. There is no need to write a lex/yacc based parser or anything of comparable complexity (your parser should only be around 50 lines of code).

Commit your changes to CVS. For example:

unix % commit -m "parsing" yash.c

Step 3 : Make your shell run programs

Once you're satisfied with the parser, modify the command loop to execute programs. You will need to use the fork() and exec() system calls to do this. While running, the shell process should wait for the program to complete by calling wait(). The shell should also check the exit code returned by the program and print a message if it is nonzero. Note : the exit code is placed into the lower 8-bits of the status code set by wait(). Your code will look roughly like this:

while (1) {
    read a line of input
    cmd = parse command line
    pid = fork();
    if (pid == 0) {
        extract the program name from cmd
        ...
        exec( ... args ...);   /* Execute the command */
    } else {
        wait(&status);         /* Wait for command termination */
        check return code placed in status;
    }
}

At this point you should have a working shell. Try it out by running some of your favorite Unix commands such as "ls", "cp", "cat" and so forth. If it doesn't work, you have done something wrong.

Commit your changes to CVS.

Step 4 : Add I/O direction

To add I/O redirection, modify the child process created by fork() by adding some code to open the input and output files specified on the command line. This should be done using the open() system call. Next, use the dup2() system call to replace the standard input or standard output streams with the appropriate file that was just opened. Finally, call exec() to run the program.

Commit your changes to CVS.

Step 5 : Add Background Jobs

This is a little more tricky. When a job is put into the background, the shell just starts it and forgets about it (the shell should return to the command prompt and allow more commands to be typed). However, this presents two problems. First, the background job should keep running even if the shell terminates. Thus, this means that the background job can't be a child of the shell process. Second, when the background job finishes, it needs to have its exit code collected--otherwise it turns into a zombie.

Modify your shell to run background jobs in a way that solves both of these problems. Hint : the solution involves the fork() function.

Commit your changes to CVS.

Step 6 : Add pipes

To support a pipe, you need to execute two separate programs and play some funny games with I/O to make the output of one program go to the input of the other program. To do this, you'll need to use the pipe() and the dup2() system calls.

Commit your changes to CVS.

Step 7 : Implement the history buffer

You will need some sort of queue, to keep track of the last ten commands, and to update them each time a new command is run. Then to implement the shorthand, you simple walk through the queue starting at the most recent command, comparing the pattern until you find a command that matches. When a command is matched, it is placed on the tail of the queue (just like you had typed the command manually).

Commit your changes to CVS.

Step 8 : Make control-C work

Modify your shell so that the SIGINT signal causes the currently running program to terminate while the shell continues to run (i.e., your shell should ignore SIGINT).

Commit your changes to CVS.

Step 9: Create a README file

Within the 'yash' directory created in Step 4, create a README file that contains your name and any other pertinent information about your solution that we should know about.

Add the README file to the CVS project as follows:

% cvs add README
% cvs commit -m "" README

Step 10 : Sit back and relax.

By now, you should be ready for the kernel project. "Ha, bring it on!", you say.

Did you remember to commit your changes to CVS?

Other Odds and Ends

Header files

You will probably need to use the following header files in your solution.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <errno.h>

Error handling

This is not a compilers course so we are not going to test your shell against every possible bad command. Your shell should not crash, but it does not need to do anything other than print "Bad command" if the user supplies bad input.

Getting Help

Since this is an upper division/graduate computer science course, you are expected to do your own research regarding the usage of various system calls, header files, and libraries. Information is readily available in the man pages, Unix reference books, or on the web.

Otherwise, do not hesistate to ask a question if you are unclear about how some part of the assignment is supposed to work.

Handin Procedure

The shell project will be automatically collected from CVS at 11:59 p.m. on the due date. Your project must be checked into a CVS project named 'yash'. If you made it this far and skipped step 1, shame on you! Go back and read the instructions.

Your final solution to the shell project should be a directory of files that look like this:

yash/
     Makefile
     README
     yash.c

To grade your shell, we will perform the following steps:

unix % cvs checkout yash
unix % cd yash
unix % make
unix % yash

If your shell fails to check out of CVS, does not build using make, or fails to run, you will receive no credit!

Make sure you test your shell by typing the above commands in some kind of junk directory---do not assume that your shell will work until you have tested it yourself!

Grading

Your shell will primarily be graded for correctness. We will run your shell on a series of simple commands that exercise all of its features. Your solution should not deviate from the specifications described in this handout (i.e., don't change the name of the commands or the shell syntax).

Your grade will consist of the following:

Correctness. 80%
Programming style and efficiency. 20%.

No late handins are accepted!