IC221: Systems Programming (SP15)

Home Policy Calendar

Lab 07: Fork-Exec-Wait, Repeat!

Table of Contents

Preliminaries

In this lab you will complete a set of C programs that will expose you to termination status, fork-exec-wait loops, and tokenizing strings. There are 3 tasks, you will likely complete only task 1 in lab, and begin with task 2. You will need to finish the remaining taks outside of lab.

Lab Learning Goals

In this lab, you will learn the following topics and practice C programming skills.

  1. fork(), exec, wait()
  2. Timing execution
  3. String tokenization
  4. Constructing argv arrays

Lab Setup

Run the following command 

~aviv/bin/ic221-up

Change into the lab directory 

cd ~/ic221/labs/07

All the material you need to complete the lab can be found in the lab directory. All material you will submit, you should place within the lab directory. Throughout this lab, we refer to the lab directory, which you should interpret as the above path.

Submission Folder

For this lab, all ubmission should be placed in the following folder: 

~/ic221/labs/07

In the top level of the lab directory, you will find a README file. You must complete the README file, and include any additional details that might be needed to complete this lab.

Compiling your programs with clang and make

You are required to provide your own Makefiles for this lab. Each of the source folders, timer, mini-sh, and XXXX, must have a Makefile. We should be able to compile your programs by typing make in each source directory. The following executables should be generated:

  • timer : execute for timer directory
  • mini-sh : execute for mini-sh directory

When compiling mini-sh, you will need to link against the readline library. We have provided you an example of this compilation process for compiling token-sh

README

In the top level of the lab directory, you will find a README file. You must fill out the README file with your name and alpha. Please include a short summary of each of the tasks and any other information you want to provide to the instructor.

Test Script

You are provided a test script which prints pass/fail information for a set of tests for your programs. Note that passing all the tests does not mean you will receive a perfect score: other tests will be performed on your submission. To run the test script, execute test.sh from the lab directory. 

./test.sh

You can comment out individual tests while working on different parts of the lab. Open up the test script and place comments at the bottom where appropriate: 

#****************************
# Comment out tests you aren't working on
#***************************
test_timer
test_mini-sh
test_makefile

Part 1: Timing the Execution of a Process

Now that you have a basic sense of how to fork() and also wait() for a process to complete, let's connect the dots and actually have the child process do something interesting, like execute another program.

Task 1 timer

In this task, change into the timer directory from the lab directory. In there, you will find a source file timer.c, and your task is to complete the program. The timer program will take another program as command line arguments, it will then fork and execute that program, record the amount of time it takes to execute, and then print the result afterwards.

You should use the gettimeofday() system call to retrieve the current time since programs often execute at the milisecond level. To make the subtraction of struct timeval's more sensible, I have provide you with a function (from the gnu website) which, given two time val's, will take the difference and store the result in result. You should use the following print format to output the resulting timestamp: 

printf("Run Time: %ld.%04ld (s)\n", diff.tv_sec, diff.tv_usec/1000);

Here is a sample run of the timer program, and, of course, runtimes will vary based on your computer performance. Using sleep as a baseline is a good test. 

aviv@saddleback: timer $ ./timer
Run Time: 0.0084 (s)
aviv@saddleback: timer $ ./timer ls
Makefile  timer  timer.c
Run Time: 0.0002 (s)
aviv@saddleback: timer $ ./timer ls -l
total 20
-rw-r----- 1 aviv scs    89 Feb 17 11:04 Makefile
-rwxr-x--- 1 aviv scs 10898 Feb 24 17:08 timer
-rw-r----- 1 aviv scs  1595 Feb 24 17:08 timer.c
Run Time: 0.0003 (s)
aviv@saddleback: timer $ ./timer ls -l -a
total 28
drwxr-x--- 2 aviv scs  4096 Feb 24 17:08 .
drwxr-x--- 5 aviv scs  4096 Feb 24 17:03 ..
-rw-r----- 1 aviv scs    89 Feb 17 11:04 Makefile
-rwxr-x--- 1 aviv scs 10898 Feb 24 17:08 timer
-rw-r----- 1 aviv scs  1595 Feb 24 17:08 timer.c
Run Time: 0.0002 (s)
aviv@saddleback: timer $ ./timer sleep 
sleep: missing operand
Try 'sleep --help' for more information.
Run Time: 0.0001 (s)
aviv@saddleback: timer $ ./timer sleep 1
Run Time: 1.0000 (s)
aviv@saddleback: timer $ ./timer sleep 2
Run Time: 2.0000 (s)
aviv@saddleback: timer $ ./timer BAD COMMAND
BAD: No such file or directory
Run Time: 0.0000 (s)
aviv@saddleback: timer $ fg
emacs -nw timer.c
aviv@saddleback: timer $ make
clang -g -Wall    timer.c   -o timer
aviv@saddleback: timer $ ./timer BAD COMMAND
./timer: No such file or directory
Run Time: 0.0000 (s)
#> ./timer 
Run Time: 0.0086 (s)
#>

Hint: You will need to construct an argv array for exec using the command line arguments to timer program. While this might seem challenging at first, consider that the difference between the two argv's is just one index. For example, consider the argv for one of the runs the last run of timer above: 

         .-----.
argv ->  |  .--+--> "./timer"
         |-----|
         |  .--+--> "ls"
         |-----|
         |  .--+--> "-l"
         |-----|
         |  .--+--> NULL
         '-----'

Why not just set the argv to exec to start one index down using pointer arithmetic? Then you have exactly what you need. 

           .-----.
           |  .--+--> "./timer"
           |-----|
argv+1 ->  |  .--+--> "ls"
           |-----|
           |  .--+--> "-l"
           |-----|
           |  .--+--> NULL
           '-----'

Part 2: A mini-shell

Believe it or not, you now have all the pieces necessary to implement a very basic shell. Think about it: A shell is just a fork-exec-wait loop. It prompts the user for input, then forks, tries to execute the input as a command, and then waits for that command to finish. The challenging part is constructing the argv array needed for exec based on the input.

String Tokenizer and Constructing an argv[]

To construct an argv array from an arbitrary string, we need to first split the string up based on a separator, such as whitespace. In C, this process is called string tokenization. The string library has a function strtok() to perform the tokenization, but it can be a little cumbersome.

Here is some sample code to start with: 

//retrieve first token from line, seperated using " " 
   tok = strtok(line, " ");

   i = 0;
   printf("%d: %s\n", i, tok);

   //continue to retrieve tokens until NULL returned
   while( (tok = strtok(NULL, " ")) != NULL){
     i++;
     printf("%d: %s\n", i, tok);
   }

Upon the first call to strtok(), you provide the string to be tokenized and the separator. In this case, that's the variable line and the separator is " ". This will return the first token in line. To continue to tokenize the same line, subsequent calls to strtok() take NULL for the string but still take the separator as the argument. You can keep retrieving tokens in this way until no more are available, and then NULL is returned.

In the mini-sh directory, we've provided you with the token-sh program that can help guide you through tokenization. The challenge for you is to save each token in a argv array that you can use in exec.

token-sh

To help you in the parsing fo this part of the lab. We have provided a sample program called token-sh found in the examples directory. The only thing this shell does is parse command lines and print them out one by one: 

aviv@saddleback: examples $ ./token-sh 
token-sh > ls
0: ls
token-sh > ls a b c d
0: ls
1: a
2: b
3: c
4: d
token-sh > who am i
0: who
1: am
2: i
token-sh >

At the heart is the code from above. Use this as a starting point for the task described below.

Task 2 mini-sh

For this task, you will write a mini-shell, mini-sh, that will continually prompt the user for a command, execute that command, timing the length of execution, and including that length in the next prompt. It is very much timer program in a loop, but now you have to build an argv. Here is some sample execution: 

aviv@saddleback: mini-sh $ ./mini-sh 
mini-sh (0.0000) #> ls
Makefile  mini-sh  mini-sh.c
mini-sh (0.0001) #> ls -a -l
total 32
drwxr-x--- 2 aviv scs  4096 Feb 24 16:32 .
drwxr-x--- 5 aviv scs  4096 Feb 24 16:31 ..
-rw-r----- 1 aviv scs   111 Feb 24 16:32 Makefile
-rwxr-x--- 1 aviv scs 15539 Feb 24 16:32 mini-sh
-rw-r----- 1 aviv scs  2970 Feb 17 11:04 mini-sh.c
mini-sh (0.0004) #> head -c 10M /dev/zero
mini-sh (0.0807) #>  bad command
./mini-sh: No such file or directory
mini-sh (0.0000) #>

To get started, change into the mini-sh directory and open the mini-sh.c program. You'll find that the looping and prompting has been provided for you. Your task is to complete the following parts:

  1. Tokenize line to construct an argv, stored in cmd_argv. Note that cmd_argv is declared with 256 slots. So you can only support commands with at most 256 arguments.
  2. Fork-exec-wait result and record the time execution in diff. You should use execvp to execute in the child, and you should wait() in the parent before continuing the loop.

Be very careful to always call _exit() after an exec in the child. The exec may fail, for example, because the command doesn't exist. In thtose case, it's very important to for the child to exit immediately, otherwise, you will now have 2 shells, one for the parent and one for the child. Then the next time through the loop, you'll have 3 shells, and so on.

Additionally, look in the examples directory for the sample token-sh program that gives an example using strtok.

Finally, to help make your shell feel a bit more shell-like, we have included the readline library. To compile your program use this in your Makefile: 

clang -g -Wall -lreadline mini-sh.c -o mini-sh