IC221: Systems Programming (SP18)


Home Policy Calendar Units Assignments Resources

Project 02: nvysh : The Navy Shell

Table of Contents

Project Preliminaries

Project Learning Goals

The goal of this project are:

  1. To write a pipeline shell with background/foreground control
  2. Parse pipelines with strtok()
  3. Manage process groups
  4. Manage terminal control
  5. waiting/killing processes within process groups
  6. Using sprintf()/readline() for prompting

Project Grading and Due Date

This project is graded out of 100 points and is due on Mon. 3 Apr at 2359. Late submissions will not be allowed.

We will apply the following grading rubric to this project

  • 70% Complete a nvysh such that it can parse and execute an arbitrary command without pipes but does not place the process in its own process group
  • 85% Complete a nvysh such that it can parse and execute arbitrary pipeline commands but does not place the process in its own process group.
  • 92% Complete a nvysh such that it can parse and execute arbitrary pipeline commands and places the pipeline in its own process group.
  • 100% Complete a nvysh such that it can parse and execute arbitrary pipeline commands and places the pipeline in its own process group with terminal management, allowing for just a single background process.

Additional Requirements:

  • You must provide a Makefile to compile your program
  • You must ensure that there are no memory leaks
  • You must provide a README file for your program describing tasks completed and processes used. This is also the place to provide additional details to your grader.

Project Setup:

  • Run the following command in your terminal
~aviv/bin/ic221-up
  • Then change into the following directory
cd ic221/proj/02
  • You will find all the material you need to complete this lab in that directory.
  • During the course of this lab, we will refer to the ic221/proj/02 as the project directory

Project Submission

To submit this lab you will place all relevant content into your lab directory:

ic221/proj/02

Then issue the submission script

~aviv/bin/ic221-submit

Select the option for proj/02, and confirm. If you see SUCCESS at the end. You may submit multiple times up until the submission deadline. Only your final submission will be considered for grading.


Project Description

In this project, you will implement a pipeline capable shell with minimal job control, the Navy Shell or nvysh. Your shell should be able to perform the following tasks:

  1. Parse a command line user input using string tokenizer and separate individual commands along a pipeline
  2. Unroll the pipeline using fork, pipe, and exec
  3. Establish each of the child process in a process group
  4. Wait on the process group to fully complete
  5. Allow for terminal signaling to the foreground process group
  6. Allow for one backgrounded/stopped command that can be moved to the foreground.

As there are many moving parts here, we strongly recommend you build simpler, smaller versions of the shell building up to a full complete model.

Here's some demo of a working version of the shell. In this example we can put together arbitrary pipelines.

aviv@saddleback: sol $ ./nvysh 
nvysh (-1) $ ls /
bin  boot  cdrom  courses  devetc  home  initrd.img  initrd.img.old  lib  lib64  lost+found  media  mnt  optproc  root  run  sbin  snap  srv  sys  tmp  usr  var  vmlinuz  vmlinuz.old  xtras
nvysh (-1) $ ls / | head -2 
bin
boot
nvysh (-1) $ ls / | head -2 | tail -1
boot
nvysh (-1) $ ls / | head -2 | tail -1 | cat | cat | cat | cat | cat 
boot
nvysh (-1) $ ^C
aviv@saddleback: sol $

Further, as you are required to wait until all processes in the group complete, the following command should run for 3 seconds:

nvysh (-1): sol $ sleep 1 | sleep 3 | sleep 1

There is some additional details below on how to do this with waitpid().

With job control, all process in the pipeline should be in the same process group, which you can see based on the ps output. When the user issues ^Z, all the processes in the foreground process group should stop and the process group leader's (or the pgid) should be printed in the parenthesis within the prompt, indicating there is a background process. If there is not a background process, then -1 is used in the prompt.

After a process group has been stopped, the shell should return and prompt the user for more input.

aviv@saddleback: sol $ ./nvysh 
nvysh (-1) $ cat | cat | head 
^Z
nvysh (10008) $ ps -o pid,pgid,cmd
  PID  PGID CMD
 1900  1900 -bash
 9978  9978 ./nvysh
10008 10008 cat
10009 10008 cat
10010 10008 head
10073 10073 ps -o pid,pgid,cmd
nvysh (10008) $

If the user issues a fg command and there is a background process group, the background process group is moved to the foreground via a kill() command by sending the SIGCONT signal. The shell then waits for that process group to finish before proceeding, just like it does with any normal command.

nvysh (10008): sol $ fg
hello
hello
world
world
^D
nvysh (-1) $ ps -o pid,pgid,cmd
  PID  PGID CMD
 1900  1900 -bash
 9978  9978 ./nvysh
10156 10156 ps -o pid,pgid,cmd

It's important that there cannot be more than one background process at a time. So, if a process stops while there is already a background process, the foreground process group should be continued with a kill() command and not allowed to be stopped. Meanwhile, the shell continues to wait for the foreground process group to finish, like normal.

nvysh (-1) $ cat
^Z
nvysh (10360): sol $ cat
^Z^Z^Z^Z^Z^Z^Z^Z^C
nvysh (10360): sol $ fg
^C
nvysh (-1) $

When there is no background process, as indicated with a -1 in the parenthesis, an error should be reported when the user issues a fg command.

nvysh (-1) $ fg
ERROR: no background process

Managing Terminal Signals

A big part of this project that differs from the labs is that you will need to manage terminal signals in addition to parsing and unrolling a pipeline. This requires specifying a process group as the foreground process group such that it can receive the terminal signals generated from Ctrl-C and Ctrl-Z.

There is a new system call that does that: tcsetpgrp(). The "tc" in tcsetpgrp() stands for "terminal control" and the system call takes two options: a file descriptor for the terminal tty, which is usually 0 for standard input, and a pgrp for the foreground process group identifier (a pid).

int tcsetpgrp(int fd, pid_t pgrp);

Transferring control the terminal should solely be the domain of your shell. The child should never call tcsetpgrp(). The shell will call tcsetpgrp() in the following situations

  • When control of terminal is going from the shell to the child process, i.e., the child is becoming the foreground process.
  • When control of the terminal is going from the child process to the shell, i.e., the shell is becoming the foreground process.

There is one more property of tcsetpgrp() that you must consider in regards to what happens when a background process tries to reclaim the foreground, as your shell will do when a child process group completes. Here's an excerpt from the man page:

If tcsetpgrp() is called by a member of a background process group in
its session, and the calling process is not blocking or ignoring
SIGTTOU, a SIGTTOU signal is sent to all members of this background
process group.

To prevent your shell from stopping, the default action of SIGTTOU signal, whenever it tries to reclaim the foreground, you will need to block/ignore SIGTTOU:

Waiting/Killing on all processes in a process group

Another important part of this project is the ability to write a wait routine to wait on all process in a process group. To do that, you will use the waitpid() system call, which is a slightly more powerful form of the wait() system call.

Using waitpid() if you were to negate a pid, as in, waitpid(-2020, &status) then you will wait on a status change from any process in the process group identified by -2020. Of course, you could also pass a variable as the pid value, and negate it in the same way, and you can also use the return value to check which child changed state.

//wait on all children in the process group pgid
//the return value is the pid of the child whose status changed
cpid = waitpid(-pgid,&status,NULL);

The final step is determining if any of the children in the process group are still running, or have they all been waited upon? That can be done easily by checking the return value of waitpid(), which, like wait(), returns a negative error value if their are no children to wait upon.

cpid = waitpdi(-pgid, &status,NULL);
if(cpid < 0)
  printf("All children in the process group have terminated\n");
else
  printf("Child %d in process group %d just changed state\n", cpid,pgid);

Similar to the waitpid() system call syntax for process groups, kill() also uses negative pid's to indicate that you wish to send a signal to all process in the process group.

//send SIGCONT to all processes in the process group pgid
kill(-pgid, SIGCONT);

Waiting on state changes other than termination

Normally, when we call wait() we only care about one state change of the child: did the child terminate yet? But this project is going to require you to also consider state changes from running to stopped, that is, when the user types ^Z to send SIGTSTP.

You can also wait on that event using waitpid() by adding WUNTRACED option. For example, if you were waiting on a state change from running to stopped of any process in a process group, you might end up with the following code:

cpid = waitpid(-pgid,&status, WUNTRACED);

where, like before, the return value is which process changed state to stopped. However, if it is the case that they were stopped via ^Z and you managed your terminal signaling properly, then all processes in the foreground process group should have received the SIGTSTP signal.

Prompting with readline library to make your terminal nicer

As with the mini-sh lab, you're more than welcome to use the readline library to make your shell more user friendly. This will allow you to use the arrow keys left and right to edit input as well as provide a command history by using arrow up and down.

To use readline, first include the appropriate headers:

#include <readline/readline.h>
#include <readline/history.h>

In your main function, you can prompt and get user input in one step:

char * input;
input = readline("Enter input> ");

//...

free(input);

Whatever is passed to the readline() function is prompted to the screen, and whatever the user entered, is returned as a char * which you can assign to a variable of your choosing.

Importantly, the string that is returned by readline() is created via a malloc(), so you'll need to free() it at some point to avoid a memory leak.

The last piece of the prompting is to include the background process group's pgid in the prompt. Normally, you'd do this by using a printf(), but the readline() command does not take a format, it takes a string. You'll need to do the formatting differently.

The right tool for this job is sprintf(), which like printf(), will format print a string, but instead of printing it to stdout will store the result in another string. For example, here's how I produced the prompt in the examples above:

 char prompt[64+PATH_MAX]; //PATH_MAX is a pre-defined length of the path
 char cwd[PATH_MAX];

 getcwd(cwd,path_max); //get the current working directory

 sprintf(prompt,              //store result of formating in string prompt
         "nvysh (%d): %s $ ", //the format string 
         bg_pgid,             //the process group id of the background process
         basename(cwd));      //the basename of the current working directory


input = readline(prompt); //prompt with the prompt

More Tips

  • Much of this project is figuring out how to interact between the previous labs. Take a close look at the key parts of those labs before proceeding.
  • You may find it useful to use a linked list for your parsing. This way you can parse all the commands and then perform the pipeline unrolling. But you could also use the the parsing methods from the lab.
  • You can assume that all command lines have no more than 1024 arguments. This will make setting up the argv array more straightforward.
  • You may want look into strtok_r(), which allows you to tokenize the same string multiple times, but there are other ways to do your parsing.
  • Use valgrind to find memory errors and violations as these may cause strange errors down the road.
  • The man pages are your best friend. Read them carefully, and scroll all the way down. There may be some sample code in there.