Class 24 — Tuesday, November 17
Quiz 9 first, on Brightspace: one attempt now. The second comes near the end of class, when it is announced. Then the Opening Journal: its prompt is in the announcements.
- The navigator (not typing) says what the next line has to do.
- The driver types it, and decides how it becomes C.
- If either of you is stuck, drop the roles for a minute and talk it over.
- Swap at every section.
Work in a new folder, class-24, with this Makefile, which builds with -pthread and without -O2, because the sum is all the work and -O2 would rewrite the loop into one multiplication.
Every program is built two ways, and the Makefile knows both.
- To check it:
make count, the default, with-fsanitize=thread. The sanitizer reports a data race, a lock destroyed while held, and two locks taken in two orders. A program without threads is checked with-fsanitize=addressinstead, the checker from before: memory read or written past its end, and memory never freed. - To measure it:
make -B count MEASURE=1, no sanitizer. A sanitizer checks every byte a program touches and would be part of every time you take.
A time from a checking build measures the sanitizer, and a race a measuring build happens to show is luck. -B rebuilds whether or not the file changed, which a change of flags needs.
1 One sum, twelve threads
The sum of the numbers below a hundred million is 4,999,999,950,000,000, or N * (N - 1) / 2. In Class 23, each thread counted into a variable of its own and main added the twelve after the joins. Here every thread adds its numbers straight into one sum, through the address in its struct.
1.1 count.c
Save count.c, build it to measure, make -B count MEASURE=1, and run it a few times.
#include <stdio.h>
#include <pthread.h>
#define N 100000000L
#define THREADS 12
// one thread's part of the count
struct share {
long start; // the first number it counts
long end; // one past its last
long * sum; // the sum every thread adds to
};
// adds every number from s->start up to s->end into *s->sum
void * count_share(void * arg) {
struct share * s = (struct share *) arg;
for (long i = s->start; i < s->end; i++) {
*s->sum += i;
}
return NULL;
}
int main() {
long sum = 0;
pthread_t threads[THREADS];
struct share shares[THREADS];
for (int t = 0; t < THREADS; t++) {
shares[t].start = t * N / THREADS;
shares[t].end = (t + 1) * N / THREADS;
shares[t].sum = ∑
pthread_create(&threads[t], NULL, count_share, &shares[t]);
}
for (int t = 0; t < THREADS; t++) {
pthread_join(threads[t], NULL);
}
printf("sum %ld, want %ld\n", sum, N * (N - 1) / 2);
}Done when three runs print three different sums, each far short of the one wanted, and you have time ./count.
1.2 The tool that names the line
gcc has a checker for exactly this, the thread sanitizer, and the checking build is the default. Build and run again:
Done when the report says data race and names the line of count.c that holds *s->sum += i, and you can say which two things on that line race.
2 Taking turns, with a lock
The reading, [DIS] 14.3.1 — Mutual Exclusion, has the tool: a mutex, pthread_mutex_t, which one thread at a time can hold. A thread that calls pthread_mutex_lock on a mutex another thread holds waits until it is unlocked. There is one lock for the one sum, so it is declared above the functions, where every thread sees it, as the reading does; main sets it up and takes it down:
pthread_mutex_t lock; // guards sum, the one thing the threads share
int main() {
pthread_mutex_init(&lock, NULL);
// ... create and join the threads ...
pthread_mutex_destroy(&lock);
}2.1 A lock around every addition
Around the one line that touches sum:
Build it to measure, make -B count MEASURE=1, and run it a few times. Time it.
Done when every run prints the sum wanted, and you have the time, which is not small: write it down next to section 1.1’s.
2.2 A lock once per thread
Sum into a local, long mine = 0;, as in Class 23, and lock once, after the loop, to add it: *s->sum += mine; between the lock and the unlock.
Build it to measure, run it, time it, then make -B count, the checking build, and run it once more.
Done when every run prints the sum wanted, the sanitizer reports nothing, and you have the third time beside the other two.
2.3 A lock around the whole loop
If you are done, keep going here; the next part starts when the room stops. The reading’s first attempt: pthread_mutex_lock before the for, pthread_mutex_unlock after it, and *s->sum += i inside, unguarded.
Done when it is right every run, and you can say from its time how many threads were ever adding at once.
3 Two locks, two orders
For pairs done with section 2. Save deadlock.c: two threads and two mutexes, a and b. One thread takes a then b; the other takes b then a.
3.1 Run it
make -B deadlock MEASURE=1, then ./deadlock, a few times. When it does not come back, Ctrl-C ends it.
Done when you have seen it hang, and can say what each thread holds and what each is waiting for at that moment.
3.2 gdb shows the threads
Run it under the debugger, and when it hangs, interrupt it and ask:
gdb ./deadlock
(gdb) run
^C
(gdb) info threads
(gdb) thread apply all bt
Done when info threads lists three threads, and the two backtraces of first and second each end in pthread_mutex_lock, on the line that asks for the lock the other thread holds. Then make -B deadlock, the checking build, and run it: it warns of a lock-order-inversion (potential deadlock) and names both lines, before the program can hang.
3.3 Take them in one order
Make second take a then b, like first.
Done when ./deadlock prints moved 0 every run, and the checking build reports nothing.
4 Keep going
For pairs who are done with section 3.
4.1 The reading’s countElems
A million random numbers from 0 to 9, rand() % 10 into a malloc’d array, and a count of how many of each, long counts[10], on twelve threads: each thread counts its share into a long local[10] of its own and then, holding the lock once, adds its ten into counts. main prints the ten counts and their sum.
Done when the sum is a million on every run, the ten counts are the same on 1 thread and on 12, and the sanitizer reports nothing.
5 Before you leave
- A10 is due Wednesday, November 18.
- The second attempt of Quiz 9, now that it is announced, and then the Closing Journal: its prompt is in the announcements.