Lab 3

POSIX Pthreads

Goals

Practice working with multi-threaded C programs. This lab will give you a good introduction on how to work with the Pthread library. You will be focusing on applying some of the most important concepts discussed in lecture. (Later labs will delve deeper into the topic.)
Practice working with C function pointers. The C language has a very interesting feature that allows programs to use functions as parameters to other functions. The concept and the syntax for function pointers can be a little intimidating, but this is something you will have to master in order to use Pthreads.

Credits

The material developed for this lab was developed by Prof. L. Felipe Perrone. Permission to reuse this material in parts or in its entirety is granted provided that this “credits” note is not removed. Additional students files associated with this lab, as well as any existing solutions can be provided upon request by e- mail to: perrone[at]bucknell[dot]edu

Set Up

Copy the following C source code to your local working directory for this lab:

~cs315/Labs/Lab3/summation.c

This program requires two command line arguments to execute:

numthreads – an integer value that specifies how many threads will be created, and
increment – the number of integer values that each thread will work with.

The task performed by this code is simple: It creates the specified number of threads and assigns to each one of them an interval of integer numbers, say [a,b). Each thread computes a value s, which is the summation of the squares of the integers in its interval, that is:

a^2 + (a+1)^2 + (a+2)^2 + … + (b-2)^2 + (b-1)^2

Essentially, this program “parallelizes” the computation of the summation of the squares of integers in the interval [0, numthreads*increment) balancing the load equally among the number of threads specified. We say “parallelizes” in quotes because in a single-core machine, the threads would execute not in parallel, but rather concurrently: splitting the time of one single CPU. If this code runs on a multi-core machine the threads may really run in parallel (this depends on the set up of the library and the OS).

IMPORTANT: The code given to you in the file summation.c is likely to compile with warnings. It is your task to ensure to you eliminate these warnings in the files you will generate using this code as starting point!

Problem 1 [15 points]

In order to compile and link this program, you cannot simply do

$ gcc -std=gnu99 -Wall summation.c -o summation

Try to compile with the command above to see what happens. Report the undefined symbols that the list of undefined references you see in a file called answers.txt.

It turns out that this program uses functions that are defined in libraries that are not being linked with your code by default. The two libraries in question, for this program, are the math library (which, among many other functions, defines pow(3)) and the pthread library (which defines all the data types and functions for POSIX threads).

Read the manual page of pow(3) and find any text that says “link with…” Pass the flag you find to gcc, when compiling the code. (By the way, this is a linker flag!) This links the math library with your program.

In answers.txt, write the linker flag that you discovered you need to use.

In order to put this flag to use, you should simply append that little bit of text to the invocation of gcc above.

Try it out and see what you get. If you see any undefined references, list them in answers.txt.

Now, append to the last invocation of gcc you used the flag -lpthread – the -l is telling gcc this is a linker flag, the pthread names the library to link. If all went as expected, you should now have an executable to run.

Create a rule in your Makefile to compile summation.c into an executable. This rule should be activated when one calls make without any command line arguments.

When you are done with this, you need to:

cd ~/csci315/Labs/Lab3
git add [all relevant files needed]
git commit -m “Lab 3.1 completed”
git push

Problem 2 [20 points]

Run your summation executable few times, passing different values of number of threads and increment. Start with two threads and a somewhat large increment. Then keeping the increment value fixed, increase the number of threads to see how things might change.

Read the source summation.c carefully and do your best to understand how it works. Now, respond to the questions below in your answers.txt file, writing as concisely and clearly as possible.

Explain the mechanism by which the main thread passes arguments to the other threads it creates.
Lines 89, 90, and 91 make calls to function calloc(3). Explain what this function does and why it is preferable to malloc(3) in this type of circumstance. (Hint: Consider the data type that is being dynamically allocated.)
Explain what is means for a thread to be in detached state (line 97 in source code). Discuss whether or not this program should create detached threads.
Explain the mechanisms by which the main thread receives the results from each computation thread and by which it synchronizes with them.
What would happen to the execution of the program if one of the child threads should decide to call exit(3) halfway through its computation? (Modify your source code to include this change and experiment with it. When you are done, leave this line commented out.)
What would happen if one of the child threads should decide to call execl(3) to run “/bin/ls” in the executable’s current working directory? (Again, modify your source code to include this change and experiment with it. When you are done, leave this line commented out.)

When you are done with this, you need to:

cd ~/csci315/Labs/Lab3
git add [all relevant files]
git commit -m “Lab 3.2 completed”
git push

Problem 3 [15 points]

Copy your summation.c to a new file summation3.c, which will compute the time it takes to execute to completion. To accomplish this, you should instrument the program to call gettimeofday(2) right when starts and then again when it ends.

With a little bit of arithmetic, using the two struct timeval values returned, you can compute the time it took the program to run. Be careful to do the right arithmetic when you subtract two time values. Have this time printed to the standard output exactly before the program terminates.

Update your Makefile so it will compile summation3.c properly.

When you are done with this, you need to:

cd ~/csci315/Labs/Lab3
git add [all relevant files]
git commit -m “Lab 3.3 completed”
git push

Problem 4 [20 points]

Copy your summation3.c to a new file summation4.c. In this new version, each thread will compute the time that it takes to execute individually and print the result to the standard output. Furthermore, have each thread print to the standard output the current time before it returns to the main thread. Note that you will have to use a combination of gettimeofday(2) and ctime(3) to produce a human readable date.

Update your Makefile so it will compile summation4.c properly.

Additionally, write in answers.txt the responses to the following questions.

Can you guarantee that the date printed by each thread is always the termination time of that very thread?
If there is any problem, explain what causes it and how you can avoid it. Also, remember to modify your source code and submit a version that sure prints out the termination time for each thread.

When you are done with this, you need to:

cd ~/csci315/Labs/Lab3
git add [all relevant files]
git commit -m “Lab 3.4 completed”
git push

Hand In

Before turning in your work for grading, create a text file in your Lab 3 directory called submission.txt. In this file, provide a list to indicate to the grader, problem by problem, if you completed the problem and whether it works to specification. Wrap everything up by turning in this file:

git add ~/csci315/Labs/Lab3/submission.txt
git commit -m “Lab 3 completed”
git push

Grading Rubric

Problem 1 [15 points total]

[5 points] Problem 1.1 – In answers.txt: undefined symbols in summation.c
[5 points] Problem 1.2 – In answers.txt: linker flag to use the math library
[5 points] Problem 1.3 – In answers.txt: any remaining undefined symbols?

Problem 2 [20 points total]

[3 points] Problem 2.1 – In answers.txt: passing arguments to threads
[3 points] Problem 2.2 – In answers.txt: how calloc may be better than malloc
[3 points] Problem 2.3 – In answers.txt: thread detached state
[3 points] Problem 2.4 – In answers.txt: thread synchronization and returning results
[4 points] Problem 2.5 – In answers.txt: what happens when one thread calls exit
[4 points] Problem 2.6 – In answers.txt: what happens when one thread calls execl

Problem 3 [15 points total]

[10 points] Problem 3.1 – Returns time for execution of summation (gettimeofday)
[5 points] Problem 3.2 – Correct subtraction of time values

Problem 4 [20 points]

[10 points] Problem 4.1 – Each thread computes its run time and prints end time with ctime
[5 points] Problem 4.2 – In answers.txt: is the end time printed reliable?
[5 points] Problem 4.3 – In answers.txt: what causes problems with ctime and how to avoid it

Note: [up to -10 points] An incorrect or incomplete Makefile to build all programs in lab and pre-lab.