CSSE 132 Mini-reading · Friday, November 6

Mutual Exclusion: Sharing a Counter Safely

Understand race conditions, protect a critical section, and recognize a deadlock. Allow about 5–8 minutes.

Why This Matters

Worksheet 26: Race Conditions and Mutual Exclusion starts with two threads incrementing the same counter. Each thread does its work, yet the total can be wrong. We will trace why this happens, protect the update with a mutex, and see how an extra lock can stop a program completely.

Core Idea: Shared Data Needs a Shared Rule

A race condition occurs when a program’s behavior depends on the timing or order of operations performed by multiple threads. In our counter example, both threads access the same integer. Their operations can overlap, so one thread can overwrite another thread’s update.

A critical section is a part of a program that accesses shared data or resources and needs protection from simultaneous access by other threads. A mutex is a lock used to provide mutual exclusion: only one thread at a time can execute the section protected by that mutex.

The rule is simple: acquire the same shared mutex before accessing the protected data, then release it when finished. A thread that cannot acquire the mutex waits. A deadlock occurs when execution is stuck waiting for something that cannot happen. Our example will show a thread waiting for a lock it already holds.

Worked Examples

1. Two increments, only one change

Conceptually, counter = counter + 1 reads a value, adds one, and stores the result. Starting at 10, consider this interleaving:

A conceptual lost update, in time order
StepWorker AWorker BShared counter
1Read 1010
2Read 1010
3Calculate 11; store 1111
4Calculate 11; store 1111

Two intended increments should produce 12. Instead, B overwrites A’s update. This trace explains the problem; it is not a promise about actual output. In C, unsynchronized conflicting accesses to an ordinary integer, including a write, are a data race and cause undefined behavior. Even an apparently correct run does not establish correctness. Running the program several times may show different results, but testing alone cannot make the unprotected update safe.

2. Put the entire update inside one mutex

A pthread mutex supplies the lock operation for us. This complete example uses the same shared-counter idea with 1,000,000 increments per worker, matching the worksheet. For readability, assume all pthread calls succeed; production code must check their return values.

A complete protected counter
C codeWhat this does
#include <pthread.h>
#include <stdio.h>

int counter = 0;
pthread_mutex_t lock =
    PTHREAD_MUTEX_INITIALIZER;
Initialize one shared mutex before starting workers. Both workers must use this same object.

static void *count(void *arg) {
    (void)arg; // no input needed
    for (int i = 0; i < 1000000; ++i) {
        pthread_mutex_lock(&lock);
        counter = counter + 1;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}
Lock before reading the counter. Keep the read, addition, and write together. Unlock after the update so another worker can enter. The loop variable is private to each invocation.

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, count, NULL);
    pthread_create(&b, NULL, count, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("%d\n", counter);
    pthread_mutex_destroy(&lock);
    return 0;
}
Start both workers, then wait for both. Main reads the counter after their successful joins, so no worker is still changing it. The expected result is 2000000. Destroy the mutex after all workers finish.

Compile with gcc -Wall -Wextra -pthread counter.c -o counter. Protecting only the final assignment is too late: both threads could already have read the same old value. Making a separate mutex for each worker also fails because neither worker excludes the other.

In pthread_mutex_lock(&lock), & passes the address of the mutex. The function needs a pointer so it can operate on the actual shared lock object. Both workers use that same address; two separate locks would not protect them from each other.

The critical section here is the counter update between lock and unlock. Keep the entire operation together: reading the old counter value outside the lock would still let two workers start from the same old value. Join waits for workers to finish; the mutex protects their updates while they run.

3. Deadlock: Trying to acquire the same lock again

Now consider the lecture demo below. There is only one thread, but it can still get stuck. Trace the messages in order and notice that no unlock occurs between the two lock calls.

Lecture deadlock demo: trace each lock call
C codeWhat this does
#include <stdio.h>
#include <pthread.h>

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

int main(void) {
    printf("Step 1: Trying to acquire lock...\n");
    fflush(stdout);
Set up one shared mutex. Print Step 1 and flush stdout so the message appears even when output is redirected.
    pthread_mutex_lock(&lock);
    printf("Step 2: Lock acquired!\n");
    fflush(stdout);

    printf("Step 3: Trying to acquire lock AGAIN...\n");
    fflush(stdout);
The first lock succeeds. Steps 2 and 3 print. The thread still holds the lock because it has not unlocked it.
    pthread_mutex_lock(&lock);  // DEADLOCK!

    printf("Step 4: This message will not print.\n");

    pthread_mutex_unlock(&lock);
    pthread_mutex_unlock(&lock);

    return 0;
}
The second lock is the problem. On our Linux VM’s usual default mutex, the thread waits for a lock it already holds. It never reaches Step 4 or either unlock.

The thread cannot continue until the mutex is released, but the only thread that could release it is stuck inside the second lock call. That is the deadlock. Adding unlock calls later does not help: execution cannot reach them.

Fix this example by removing the second lock and one of the unlock calls, leaving one successful lock paired with one unlock. If you need two separate protected sections, unlock after the first section before locking again for the second.

Compile the demo with gcc -O0 -pthread deadlock.c -o deadlock. On the course Linux VM, expect Steps 1, 2, and 3, then a hang. Press Ctrl+C to stop it. This explanation assumes the usual default mutex used in class; other mutex types can behave differently.

Common Mistakes

  • Protecting only the write: the shared read and update must stay together inside the critical section.
  • Expecting join to fix the counter: waiting for completion does not prevent overlapping updates.
  • Forgetting the address: pass &lock to the mutex functions so they use the same mutex object.
  • Locking twice before unlocking: the second call can wait forever for a release that cannot be reached.

Quick Reference

Term or operationRemember
Race conditionTiming or order affects behavior; counter updates can be lost.
Critical sectionShared-data code that needs protection from simultaneous access.
Mutual exclusionOnly one thread at a time in sections protected by the same mutex.
Mutex syntaxpthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock);
/* protected operation */
pthread_mutex_unlock(&lock);
DeadlockExecution cannot proceed because a required event cannot occur.

Check Yourself

Try these before opening the answers.

  1. Two workers each increment a protected counter 300 times, starting at 5. What should main read after both joins?
  2. Starting at 10, how can two unprotected increments both store 11?
  3. A worker reads counter into a temporary before locking, then stores temporary + 1 while holding the lock. Why is the critical section incomplete?
  4. Why do both workers pass &lock rather than each creating a separate mutex?
  5. In the deadlock demo, which call blocks on our Linux VM? Why do the later unlock calls fail to rescue it?

Answers

Show answers and reasoning
  1. 605: the initial 5 plus 600 protected increments, assuming pthread calls succeed.
  2. Both read 10 before either writes. Each calculates and stores 11, so the second store overwrites the first update. This conceptual trace illustrates a lost update; the actual unprotected C program has undefined behavior.
  3. The shared read also needs protection. Both workers can read the same old value before either acquires the lock. Move that read into the protected section.
  4. The address identifies the same shared mutex object. Separate mutexes let both workers enter at once and do not protect the shared counter.
  5. The second pthread_mutex_lock(&lock) waits for the mutex already held by this thread. The thread cannot reach the unlock calls while blocked, so Step 4 does not print.

Next Step

Return to Worksheet 26. Identify each shared value, mark the complete critical section, and trace every lock and unlock in execution order.