Scene One: User Space

Due by 11:59 PM on Sunday, Oct 25

Introduction

In this part of the project, you have to fix a multi threaded program that is troubled by race conditions. Specifically, we will give you an otherwise 100% correct, user space program that attempts to perform some computation across multiple threads. You are expected to fix the race conditions using synchronization mechanisms in the pthread library. You should begin by accepting the assignment on piazza. Then you can clone the repo from git@github.com:umbc-cmsc421-fa2020/project3-part1-yourGITusername.git. To do that you can:

1. cd ~/ This will get you to your home directory. If you want to clone the repository somewhere else you are free to do so.
2. git clone git@github.com:umbc-cmsc421-fa2020/project3-part1-yourGITusername.git project3-part1 You can make a copy of this directory if you want, same way you did for project0 and 2
3. cd project3-part1

Requirements

In order to complete this assignment you have to modify the source code you cloned from your project3-part1 repository. However you are not allowed to modify the utility or the functionality of the program in any way. That means you can add code relative to the locking mechanisms you decide to use. But you cannot for example change how the program checks if the final result is correct, or the way the INCREMENT macro works, or make it always return that the result was correct even though it wasn’t.

In addition to solving the race conditions, you must also produce a short report answering the following questions:

1. What was the reason for the race condition? (You should be able to identify at least one piece of memory)
2. Justify your selection of any critical sections. How did you identify them? Why is that the critical section (as opposed to more/fewer lines of code for instance)?
3. Describe the synchronization primitive you chose to use. Justify that choice.
4. Show us the results of your testing (there is more on testing in the following sections).
5. Anything else you would like to discuss. Instead of a README you got your report this time.

Any external sources you use, should be referenced in the report.

You are welcome to include images in the report as long as they are readable. The report MUST be in pdf format. No other format will be accepted. You can structure the report however you like, you can add introduction and conclusion sections. We do not however expect you to write a book. Be as to the point as you can be, while answering the above questions.

The program

The purpose of this program is to create a number of threads. Each thread on its own generates 500 random numbers between 0 and 50. For each number it generates it will increment a global sum variable by that number. It will also keep track of the sum of all the numbers it computed so far. As addition is commutative, we should expect that the sum of all the individual sums is equivalent to the global sum. If you run the program a couple of times, you will soon realize that that is not the case!

The program is not overly complicated and the code is fairly self explanatory as well as documented. However, since you have not necessarily seen pthreads in use during class we will go over a brief explanation here. If you open up the main.c file you will find code like this:

pthread_t thread_ids[NUMBER_THREADS];
int thread_args[NUMBER_THREADS];

// Create all the threads
for (size_t i = 0; i < NUMBER_THREADS; i++)
{
    thread_args[i] = i;
    // The thread starts working after this function call finishes
    pthread_create(&thread_ids[i], NULL, thread_function, &thread_args[i]);
}

By the time pthread_create finishes, the newly created thread has already begun execution. And the code it is executing is thread_function. The thread_ids and thread_args arrays are necessary so we can keep track for all our new threads.

The next piece of code will wait for each thread to finish, one at a time. Keep in mind that thread i might have finished before you even call pthread_join on it, or that thread i + 1 might finish before i. This is the nature of multithreaded programming. This function will eventually wait for all of them, no matter in what order they finish execution.

// We wait for each of the threads to finish here
for (size_t i = 0; i < NUMBER_THREADS; i++)
{
    pthread_join(thread_ids[i], NULL);
}

The rest of the code is pretty standard C code, so we will not go over it. It is very important to know that in order to increment a sum variable you must use the INCREMENT macro. You cannot remove that from the thread_function function.

Testing

After you compile the program with the provided make file you can run it and it will run through the scenario once (i.e 500 iterations per thread). If you want to, you can modify the NUM_THREADS macro in line 9 to change the amount of threads that are created. Feel free to experiment with that. However, even 500 iterations are nothing in the scope of a modern computer. Adding the complexity of multi-threading on top, and you can end up with bugs that only show up once in a blue moon. Literally.

For that reason, we have also given you a python script to help you run multiple tests faster, instead of running the threads executable each time. You can modify the iterations variable in order to run the threads executable more times. You are not allowed to modify anything else in that file. You can execute this script from the project3-part1 directory with the python3 ./tester.py command.

In your report there should be a section about testing. You can discuss the number of threads you used and the numbers of iterations you used in there. Feel free to include a couple of images with more than the default threads running and/or more than the default iterations running. You could also alter the number of cores you allocate to the vm (if it is possible on your machine) and see how that affects the behavior of the program.

Submission

For this part of the project you have to submit:

• Any modifications you made to main.c
• Your report

So just like your previous projects you can

• git status Will show you of all the changes git is aware of.
• git add FilesYouModifiedOrAdded This will tell git that you want to track the changes of that file
• git commit This will create a commit locally with all the new changes you have added so far.
• git push origin master