This is a very new CS 61C lab (only the second time ever)! Please be patient with any bumps in the road...
You will run this lab on the new instructional cluster, which consists of 26 compute nodes each with:
Sweet! Thanks, Google and Intel!
The purpose of this lab is to acquaint you with basic POSIX Thread (PThread) programming as well as to introduce some of the common design issues in multicore programming.
For an excellent PThread tutorial to supplement this lab, please refer to POSIX Thread Programming.
First, log into the icluster front-end node:
$ ssh -X icluster.eecs.berkeley.edu
Once logged into the icluster, create a subdirectory in your home folder called "lab14", and copy the lab files into the directory:
$ mkdir ~/lab14 $ cd ~/lab14 $ cp -R ~cs61c/labs/14/* .
When compiling any code with PThreads, be sure that you call gcc with the -lpthread switch:
$ gcc -o HelloWorld HelloWorld.c -lpthread
Several warnings will print when you compile. Don't worry about them.
In this exercise you will write a simple Hello World program in which multiple threads print messages.
Our emphasis in this lab will not be on writing code that runs faster on multicore. Instead, it will be on writing correctly synchronized code, which means code that will produce the correct result regardless of the order that threads are scheduled to run. This is valuable not only for writing programs on parallel processors, but also for writing threaded programs for single core processors. For this reason, you are not allowed to edit or delete any of the existing lines of code in the program. You many only add lines.
First, you will need to be able to create new threads, which you can do with the following PThread API routine:
int pthread_create(pthread_t *thread, pthread_attr_t attr, void* (*start_routine)(void*), void *arg)
The first argument, pthread_t *thread, allows the calling thread to keep a structure that contains data relevant to the thread it creates; you can think of it as keeping a reference. We will not use the pthread_attr_t attr argument. The start_routine argument is a function pointer to the function that the thread will start in. In C, you will always pass a function name for this argument. Finally, the arg argument is a value of ambiguous type (thus the void * typing) that will be passed to the start_routine that is called when the thread begins.
A typical call to create a thread looks like:
pthread_t the_other_thread; pthread_create(&the_other_thread, NULL, startingFunction, 1234);
The call above creates and runs a new independent thread of execution which passes the value 1234 as an argument to startingFunction and begins executing that function.
Note: The implementation of pthreads we are using seems to yield control of execution to the newly spawned thread right after creating it. This is only a quirk of our implementation and is not part of the pthread standard. Remember that properly synchronized programs should make no assumptions about how threads are scheduled, so do not rely on this quirk of the implementation in your program.
Read the file HelloWorld.c and add a call to pthread_create to create threads that call the sayHello function. You will need to compile your code with the -lpthread flag. Disregard any compiler warnings.
$ gcc -o HelloWorld HelloWorld.c -lpthread
You will notice that not all the threads were able to print their hello AND goodbye messages. When the original thread (the one that started with main) of a program exits, the entire process quits and thus all threads within that process are killed. In this case, the original thread creates child threads and relinquishes execution control to them because of the implementation quirk mentioned above. As soon as the original thread regains control, however, it immediately exits without waiting for any of its child threads to complete, thus killing all of them.
To make the original thread wait for its child threads to complete, we must add another loop to HelloWorld.c with a call to pthread_join, which has the following prototype:
int pthread_join(pthread_t thread, void **value_ptr);
When thread A joints thread B, thread A will not continue out of the call to pthread_join until thread B has completed and exited. The first argument is the pthread that the caller thread will join. We will not use the second argument.
Add a loop to HelloWorld.c so that the main thread joins each child thread before main finishes and returns. Your new program should allow all the child threads to print goodbye.
| Show your TA the output of your HelloWorld program. |
In this exercise, you will introduce some data that is shared between the threads. Namely, you will have each thread print a number that corresponds to the order in which they print.
When you ran your program from Exercise 1, you should have noticed that the threads attempt to count off while saying goodbye, but fail miserably. You will add code to correct this. Remember not to edit or delete existing lines of code (unless you added it in Exercise 1).
First, note the global integer variable global_counter at the beginning of the file. We want each thread to increment this counter when it prints. If you try running your program again, however, you should notice that the threads don't manage to increment it more than once or twice. This is because the counter variable is shared across multiple threads without any synchronization constructs to protect it. We will need to use the mutex counter_lock to ensure that multiple threads do not access the variable at the same time and introduce race conditions.
One can lock and unlock a mutex with the functions prototyped below:
int pthread_mutex_lock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex);
Some typical lock code would be:
// as a global variable pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER; // before a critical section corresponding to lock1 pthread_mutex_lock(&lock1); // critical section pthread_mutex_unlock(&lock1); // after critical section
The PTHREAD_MUTEX_INITIALIZER is a macro that initializes the mutex variable to contain the necessary lock information. Mutexes must be initialized before use.
Edit the sayHello function so that the threads which call it will first try to acquire the counter_lock before incrementing the global counter variable. After doing this, each thread should number itself properly while saying goodbye.
| Show your TA the output of your new HelloWorld program. |
Now we want to have our threads say goodbye in a specific order: we want those with an even id to print first, and those with an odd id to print after all the evens have printed. Since we are not guaranteed that the threads will start in any given order, we must have the odd threads wait until all the even threads have printed. (We won't care about the order they print hello).
Enter the dreaded condition variable (or CV for short)! A condition variable is a construct that allows threads to sleep until a certain condition is met, where the condition is determined by some shared information (such as a counter variable). CVs are always associated with locks because the shared information that they depend on must be synchronized across threads.
You can think of a CV as a "big pillow" in the sense that threads can fall asleep on a condition variable and be woken from that condition variable. One story to keep in your head is: Tommy the Thread wanted to access shared information. He acquired the appropriate lock but then was disappointed to see that the shared information wasn't ready yet. Without anything else to do, he decided to sleep (or wait) on a nearby condition variable until another thread updated the shared information and woke him up. Timmy the Thread finally came along and updated the shared information while Tommy was asleep on the nearby CV. Timmy noticed Tommy asleep, so Timmy signaled him to wake up off the condition variable. Timmy then went on his way and left Tommy to play with his new, excited shared information.
The above story sounds like a pretty useful thing for threads to be able to do, but there's one thing we glossed over: we know that to access the shared information a thread needs to hold the lock. Since Timmy needs to update the shared information while Tommy is asleep and waiting, we must have any thread that sleeps on a condition variable release the lock while it is asleep. But since Tommy had the lock when he fell asleep, he expects to still have the lock when he wakes up, and so the condition variable semantics guarantee that a thread sleeping on a condition variable will not fully wake up until (1) it receives a wake-up signal and (2) it can re-acquire the lock that it had when it fell asleep.
For more of a description (with no silly story), you can check out POSIX Thread Programming
To achieve the evens-print-first functionality, you will need to use the condition variable routines in the PThread library:
pthread_cond_wait(pthread_cond_t *condition, pthread_mutex_t *lock); pthread_cond_broadcast(pthread_cond_t *condition);
The pthread_cond_wait routine will put the caller thread to sleep on the condition variable condition and release the mutex lock, guaranteeing that when the subsequent line is executed after the caller has woken up, the caller will hold lock. The pthread_cond_broadcast routine wakes up all threads that are sleeping on condition variable condition.
IMPORTANT: To call any of the above routines, the caller must first hold the lock that is associated with that condition variable. Failure to do this can lead to several problems.
Check these global variables in your HelloWorld.c file:
pthread_mutex_t print_order_lock = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t evens_done_CV = PTHREAD_COND_INITIALIZER; int number_evens_finished = 0;
Add the logic necessary to have all the evens print before the odds. You will need to edit the sayHello function to contain calls to pthread_mutex_lock, pthread_mutex_unlock, pthread_cond_wait, and pthread_cond_broadcast. Do not use pthread_cond_signal.
| Show your TA the output of your new HelloWorld program in which the threads with even-numbered IDs print before any threads with odd-numbered IDs. |
Read about barriers on Wikipedia
Barriers are not standard in the PThread library (though some implementations contain them). Implement a my_barrier_t type and associated functions.
Lab edited for CS61C Summer 2008 by Albert Chae. Originally created for CS 61C in Spring 2008 by Matt Johnson and Ramesh Sridharan.