Skip to content

CMSC 14300: Practice Set 7 - Threads, Race Conditions, and Mutexes

Practice for the material in Week 6: creating and joining threads from Lecture 11, and the race conditions and mutexes from Lecture 12. None of these repeats a lecture or homework exercise; together they drill the new moves - packaging thread arguments, splitting work across threads with no shared writes, recognizing a critical section, protecting it with a mutex, and locking more than one mutex without deadlocking. This is good preparation for later material that builds on concurrency.

Work in a fresh directory and compile everything with warnings on, linking the thread library:

mkdir -p ~/cmsc14300/pset07 && cd ~/cmsc14300/pset07
clang -Wall -Wextra -std=c17 -pthread problem1.c -o problem1

Keep this week's rules in view: a thread function is always void *fn(void *); create all threads, then join all threads; never hand a thread the address of a loop variable that keeps changing; and any memory more than one thread writes needs a mutex around every access to it, read or write.

#include <pthread.h>
pthread_t t;
pthread_create(&t, NULL, fn, arg);
pthread_join(t, NULL);

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock);
/* critical section */
pthread_mutex_unlock(&lock);

Problems 1 to 2 use thread creation and joining only, with no shared writes. Problems 3 to 5 add a mutex.

Problem 1 - Factorial, one thread per input

Write a thread function that computes n! for an n passed in and hands the result back through its return value. main reads several numbers, launches one thread per number, joins them all, and prints every result.

void *factorial(void *arg);   /* arg: int *n.  returns: malloc'd long * */

inputs: 5 7 10
5! = 120
7! = 5040
10! = 3628800
  • Cast arg back to int *, compute the product in a long, malloc a long for the result, store it, and return the pointer. The caller frees each result after printing it.
  • Give each thread its own int to read (an array of the inputs, one slot per thread) - never the address of a shared loop variable.
  • Check your understanding: why would returning the address of a local long computed inside factorial be unsafe, the same way it was unsafe to return the address of a local from an ordinary function?

Problem 2 - Warmest reading per sensor group (no locks needed)

You have readings from 40 temperature sensors, split into 4 groups of 10. Launch one thread per group to find that group's maximum reading; main joins all four and finds the overall maximum by comparing the four group maximums. No two threads should ever read or write the same memory.

typedef struct { int *readings; int start, end; int group_max; } group_t;
void *find_group_max(void *arg);

group 0 [0,10):  max = 91
group 1 [10,20): max = 88
group 2 [20,30): max = 97
group 3 [30,40): max = 85
overall max: 97
  • Each thread's group_t has its own readings pointer (into the shared array, but read-only), its own start/end slice, and its own group_max field that only that thread ever writes.
  • After joining all four, main scans the four group_max fields (a plain loop over 4 elements) for the overall maximum.
  • Check your understanding: this program touches a shared array (readings) from multiple threads with no mutex, and that is fine. What property of how the threads use readings makes that safe?

Problem 3 - A shared download counter (race, then fix)

Simulate 6 threads each "completing" 100,000 downloads by incrementing a shared long downloads_done. First write it with no protection and observe the count fall short of 600000 on some runs. Then add a mutex and confirm it is exact every time.

long downloads_done = 0;
void *download_worker(void *arg);

(no lock)   downloads_done = 583201    (varies by run, usually short)
(w/ lock)   downloads_done = 600000    (every run)
  • Unprotected version: downloads_done++; in the loop. Protected version: wrap just that line in pthread_mutex_lock/unlock.
  • Run the unprotected binary two or three times (rerunning the whole program) to see the final count actually change between runs.
  • Check your understanding: downloads_done++ compiles down to a load, an add, and a store. Describe, in your own words, an interleaving of two threads' loads and stores that loses one increment.

Problem 4 - Move books between two shared library counts

Two shared counters, main_branch and annex_branch, each start at 500 (books on the shelf at each location). Multiple threads call move_to_annex(int n) or move_to_main(int n) concurrently, each of which must lock both counters' mutexes before changing either count. Do this without deadlocking, no matter how many threads call each function at the same time.

int main_branch = 500, annex_branch = 500;
pthread_mutex_t lock_main  = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_annex = PTHREAD_MUTEX_INITIALIZER;
void move_to_annex(int n);   /* main_branch -= n; annex_branch += n; */
void move_to_main(int n);    /* annex_branch -= n; main_branch += n; */

8 threads, half moving each direction, 1000 moves of 1 book each
main_branch + annex_branch == 1000 at the end (every run, program terminates)
  • Both functions must lock the same mutex first, regardless of which direction books are moving - for example, always lock_main before lock_annex. Only the arithmetic differs between the two functions; the locking order does not.
  • Launch threads calling both functions concurrently and confirm the program finishes (does not hang) and the two counts always sum to 1000.
  • Check your understanding: if move_to_annex locked lock_main then lock_annex, but move_to_main locked lock_annex then lock_main, describe a specific pair of calls, running at the same time, that would deadlock.

Problem 5 - A shared "next free slot" counter

N worker threads each want to claim a unique slot index in a shared results array of size N, by reading and incrementing a shared int next_slot (starting at 0) and using the value they read as their own index - no two threads may ever claim the same slot, even though all N threads race to claim one at (nearly) the same time. Each thread then writes its thread number into results[slot].

int next_slot = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int results[N];
void *claim_slot(void *arg);   /* writes its own id into results[the slot it claimed] */

after all threads finish, results contains 0..N-1 in some order, each exactly once
  • The read of next_slot and the increment must happen together as one critical section: lock, read next_slot into a local my_slot, increment next_slot, unlock - then use my_slot (already a private local) to write results[my_slot] outside the lock.
  • Check your understanding: why is it not enough to just lock around next_slot++ alone if a thread also needs to know which value it claimed? What would go wrong if two threads each ran next_slot++ under the lock but then both used the shared next_slot (read again, unprotected) as "their" slot?

Self-check

You're ready for later material if you can, without looking it up:

  • Write the signature of a pthread thread function from memory, and say why it must be exactly that signature.
  • Explain why threads created in a loop must never be handed the address of the loop variable, and show the fix.
  • Say, in one sentence, what a race condition is and why x++ on shared x is not one atomic step.
  • Wrap a critical section in a mutex lock/unlock, and explain why the locked region should be as small as possible.
  • Explain what causes a deadlock between two mutexes and how a consistent lock order prevents it.