Computer Science 432/563
Operating Systems

Spring 2016, The College of Saint Rose

Home     Syllabus     Schedule

You may work alone in groups of size 2 or 3. Collaboration within a group is, of course, unrestricted. You may discuss the program with members of other groups, but what you turn in must be your own group's work. Groups must be formed no later than 4:00 PM, Friday, March 4, 2016, and be confirmed by all group members by electronic mail to terescoj AT strose.edu. All group members will be assigned the same grade for the lab. There are many subtasks that can be carved off and assigned to group members, so everyone is encouraged to join a group.

There are two parts for your work on this project. The basic functionality to run a single command is part 1, and is due at 11:59 PM, Tuesday, March 22, 2016. The remainder is due at 11:59 PM, Monday, April 4, 2016. Please refer to the grading guidelines at the end of this document for the specific functionality required for your part 1 submission.

Requirements

Like the Unix shells you use every day, knish should issue a prompt (below, it is "shell#"), at which it reads commands from the user and executes them.

Your shell should interpret the following commands and provide the following functionality:

• exit: exit from the shell
• help: display a message listing usage of all commands
• Execute a command (program on disk). As in the shells you use, the command should be located according to the PATH environment variable Appropriate choice of exec function will help here. The arguments following the command should be passed to the command.

  For example,

         shell# cat cat.c
  

  should execute cat with one argument, cat.c

  • Input and output redirection should be implemented.

    For example,

    	shell# cat < cat.c > myfile.c
    

    should cause the cat program to read from cat.c and write to the file myfile.c.

    	shell# ls -l >> dirlistings.txt
    

    should cause the output of ls -l to be appended to the end of the existing file dirlistings.txt.

    An individual command may only redirect input once and output once, but those redirections may be specified in any order.

            shell# > alines grep -i < Makefile a
    

    should be interpreted the same as the more usual

            shell# grep -i a < Makefile > alines
    

  • Pipes should be implemented.
    • For example,

             shell# cat cat.c | wc > count.txt
      

      should cause the output of cat cat.c to be the input of wc > count.txt.

    • You should allow a sequence of pipes to be specified:

             shell# ls -l *.c | grep "Oct 31" | wc -l
      

      The program should be able to handle a sequence of pipes of any length.

    • Only the first command in a pipeline may have input redirection. Only the last command in a pipeline may have output redirection. Redirection of other commands should be reported as an ambiguous command line.
  • Typing <ctrl-c> should abort a command being run, but not cause knish to terminate.
• A list of commands separated by semicolons should be executed in sequence.
• As with the familiar Unix shells, appending an & to the end of your command line will execute the command in the background.
  • An & may be anywhere in a command line, but it is treated like a ; in that anything on the command line following an & should be treated as a new command.

    For example,

           shell# sleep 5 & sleep 5
    

    should launch one instance of sleep 5 in the background, then a second in the foreground.

  • Typing <ctrl-c> should not kill the shell or any commands running in the background.
  • When any background command terminates, it should be reported.

     
           shell# sleep 55 &        ; invoke sleep in background
           shell# cat < hello.c     ; give other commands
           shell# ...               ; other commands
           shell# ...               ; other commands
           [2] "sleep" terminated   ; sleep command is done
    

  • All backgrounded processes should be maintained in a process table by knish, so that the program name is displayed when it terminates, and for use in the jobs and kill commands.
• jobs: Displays all the active background programs that have been started from this shell, along with their ids. (This id need not be that same as the actual process id. For example, it could be the index into your process table).

         shell# jobs
         PID     Name
         [0]    mycat < myfile.c > newfile.c
         [1]    sleep 20
         [4]    grep mysh < doc | wc
  

• kill: Without any arguments, prints a usage statement:

         shell# kill
         Usage: kill <pid> [<pid> ...]
  

  Otherwise it kills the processes with the specified ids and displays the processes killed.

         shell# kill 4
         [4] "grep" Killed
         shell# kill 3 7
         [3] "cat" Killed
         [7] "wc" Killed
  

• Implement a builtin cd command.
• Errors should be reported meaningfully.
• Additional functionality of your group's choosing should also be implemented (see also the Submission and Evaluation section below).

  Ideas for extra functionality include:

  • command history: history command, !command, !!, ^ modification of previous command
  • control structures in the shell (for, while, if)
  • aliases
  • user-specified prompts (as in bash, tcsh)
  • More advanced redirection and pipes: <<, >&, |&
  • <ctrl-z> trapping and corresponding job control (fg, bg commands)
  • Parenthesis-delimited subshells

  See builtin(1) for more ideas.

Notes

• The system(3) system call is not to be used.
• The system calls that you should use are fork(2), a variant of exec(3), signal(3), kill(2), open(2), dup2(2), close(2), pipe(2), and chdir(2).
• You may find the readline(3) and the strsep(3) functions to be useful. readline(3) is part of the GNU Readline Library and strsep(3) is in the Standard C Library. Note that this will require an extra link flag "-lreadline" and on mogul it also requires "-lncurses".
• You may assume the builtin commands (exit, help, jobs, kill) stand alone on a command line (no pipes, I/O redirection).
• Use knish scripts to test your shell.
• A shell may run for a long time. Be careful about memory management.
• gcc's -Wall flag will report additional compiler warnings. This can help you find some of the more subtle bugs that are so common in C code before they have a chance to cause their subtle problems. If you aren't absolutely certain that a given warning is harmless, fix it!
• A verbose/debugging mode is essential for, well, debugging.
• Keep your code under source code control. You may wish to use subversion to track your changes and to allow you to go back to previously working code. If you're working in a group, this is even more useful, allowing easier concurrent development. Group members should request a Unix group for safe sharing of files.
• The following might be a good order to tackle the required functionality.
  • exit and help commands
  • run a command (with no argument passing, no redirection, no pipes)
  • run a command with argument passing
  • run a command with input and output redirection
  • run a command in the background
  • jobs command
  • kill command
  • <ctrl-c> trapping
  • trapping termination of background processes
  • pipes
  • ;- or &-separated commands
  • cd command
  • extra functionality
• The shared areas on mogul and on ascg contain my version of knish under labs/shell/knish.

Submission and Evaluation

For each part, all necessary files should be submitted in a single tar file shell.tar. Include a Makefile to allow easy compilation of the Knight Shell program. Send this tar file as an attachment to terescoj AT strose.edu.

Your program will be graded based on a total of 50 points.

• 6 points for documentation. Your code should be commented appropriately throughout. Please also include a longer comment at the top of your program describing your implementation. This documentation should list your important design decisions, the assumptions that you made (if any), the additional functionality implemented, and any other relevant information.
• 1 point for a functional Makefile. (Part 1)
• 1 point for implementing the exit and help commands. (Part 1)
• 4 points for running a command with no arguments. (Part 1)
• 4 points for running a command with arguments. (Part 1)
• 1 point for a builtin cd command. (Part 1)
• 4 points for running a command with input/output redirection.
• 4 points for launching a command in the background.
• 4 points for launching a sequence of jobs separated by ;'s or &'s.
• 2 points for the jobs command.
• 2 points for the kill command.
• 2 points for correctly trapping the <ctrl-c> keystroke.
• 3 points for reporting termination of backgrounded jobs.
• 4 points for a pipeline of two processes.
• 3 points for an arbitrarily long pipeline of processes.
• Up to 5 points for extra functionality.
  • 1-point enhancements: aliases, more advanced redirection and pipes: <<, >&, |&, user-specified prompts.
  • 2-point enhancements: command history, control structures in the shell (for, while, if), modification of previous command with ^.
  • 3-point enhancements: <ctrl-z> trapping and corresponding job control (fg, bg commands).
  • Please ask about other possible enhancements. Point values will be based on level of difficulty.

Penalties may be applied for poor design choices, poor formatting of code, poor programming style, or if your program compiles with warnings (when using gcc -Wall).

Have fun and good luck!