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:
| Step | Worker A | Worker B | Shared counter |
|---|---|---|---|
| 1 | Read 10 | 10 | |
| 2 | Read 10 | 10 | |
| 3 | Calculate 11; store 11 | 11 | |
| 4 | Calculate 11; store 11 | 11 |
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.
| C code | What this does |
|---|---|
| Initialize one shared mutex before starting workers. Both workers must use this same object. |
| 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. |
| 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.
| C code | What this does |
|---|---|
| Set up one shared mutex. Print Step 1 and flush stdout so the message appears even when output is redirected. |
| The first lock succeeds. Steps 2 and 3 print. The thread still holds the lock because it has not unlocked it. |
| 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
&lockto 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 operation | Remember |
|---|---|
| Race condition | Timing or order affects behavior; counter updates can be lost. |
| Critical section | Shared-data code that needs protection from simultaneous access. |
| Mutual exclusion | Only one thread at a time in sections protected by the same mutex. |
| Mutex syntax | pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; pthread_mutex_lock(&lock); /* protected operation */ pthread_mutex_unlock(&lock); |
| Deadlock | Execution cannot proceed because a required event cannot occur. |
Check Yourself
Try these before opening the answers.
- Two workers each increment a protected counter 300 times, starting at 5. What should main read after both joins?
- Starting at 10, how can two unprotected increments both store 11?
- A worker reads counter into a temporary before locking, then stores temporary + 1 while holding the lock. Why is the critical section incomplete?
- Why do both workers pass &lock rather than each creating a separate mutex?
- 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
- 605: the initial 5 plus 600 protected increments, assuming pthread calls succeed.
- 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.
- 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.
- The address identifies the same shared mutex object. Separate mutexes let both workers enter at once and do not protect the shared counter.
- 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.