Step 3 of 6
Mutexes and lock_guard
A mutex (mutual exclusion, std::mutex from <mutex>) is a lock that only one thread can hold at a time. A thread calls lock() before touching shared data and unlock() after. If another thread already holds the mutex, lock() waits until it's released. The code between lock and unlock is a critical section: at most one thread is ever inside it, so its steps can't interleave with another thread's.
You almost never call lock() and unlock() yourself. std::lock_guard locks in its constructor and unlocks in its destructor, so the mutex is released on every path out of the block, including early returns and exceptions. It's RAII applied to locks.
#include <iostream>
#include <mutex>
#include <thread>
int main() {
long long counter = 0;
std::mutex m;
auto work = [&] {
for (int i = 0; i < 1000000; i++) {
std::lock_guard<std::mutex> lock(m); // lock m...
counter++;
} // ...unlocked here, every pass
};
std::thread a(work), b(work);
a.join();
b.join();
std::cout << counter << "\n";
}
2000000
Now the load, add and store of each increment happen while holding m, so no other increment can sneak in between them. The answer is right on every run, at every optimization level, and ThreadSanitizer stays quiet.
A mutex belongs with its data
In real code the mutex lives next to the data it protects, both private, and every member function that touches the data takes the lock. Callers can't forget, because they never see the data directly:
class Inventory {
public:
void add(const std::string& item, int n) {
std::lock_guard<std::mutex> lock(m_);
items_[item] += n;
}
int count(const std::string& item) const {
std::lock_guard<std::mutex> lock(m_);
auto it = items_.find(item);
return it == items_.end() ? 0 : it->second;
}
private:
mutable std::mutex m_; // mutable: const functions must lock it too
std::map<std::string, int> items_;
};
Locks cost time: share less
Locking and unlocking a million times is slow, and while one thread holds the lock the other just waits. The fastest shared data is data that isn't shared. Give each thread its own result and combine the results once at the end, like the partial sums in step 1. std::async (from <future>) makes this pattern short: it runs a function on another thread and hands back a std::future, whose get() waits for the result.
#include <future>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using Counts = std::map<std::string, int>;
Counts count_words(const std::vector<std::string>& words, std::size_t lo, std::size_t hi) {
Counts c; // private to this call: no lock needed
for (std::size_t i = lo; i < hi; i++) c[words[i]]++;
return c;
}
int main() {
std::vector<std::string> words = {"gg", "wp", "gg", "ez", "gg", "wp", "ns", "gg"};
auto first = std::async(std::launch::async, count_words, std::cref(words), 0, 4);
auto second = std::async(std::launch::async, count_words, std::cref(words), 4, 8);
Counts total = first.get(); // get() waits for that thread
for (const auto& [w, n] : second.get()) total[w] += n;
for (const auto& [w, n] : total) std::cout << w << " " << n << "\n";
}
ez 1
gg 4
ns 1
wp 2
std::cref(words) passes the vector by reference; without it, std::async would copy it for each thread. std::launch::async asks for a real new thread.
Simulating a lock
Back to the simulation from the last step. With a lock, each increment becomes five steps: lock, load, add, store, unlock. A thread whose turn comes while the other thread holds the lock can't proceed: its lock step fails, and it tries again on its next turn. That's all it takes to make lost updates impossible.
Your turn: write simulate_locked(schedule). Threads 'A' and 'B' repeat lock, load, add, store, unlock. A lock step only succeeds (and moves the thread on to its load) when nobody holds the lock; otherwise the thread stays at its lock step. Return the final counter.