Intro to Shared State Concurrency
2026-10-29
This module: Concurrent programming with threads
Recommended: Rust Atomics and Locks, Ch 1-3
Shared memory programming is
There is a reason we repeat this stuff!
A quarter of the time in some code is spent on serial work, and the remainder can be parallelized on a \(p\)-core machine. Which of these is not true of the total runtime?
Respond at: https://PollEv.com/davidbindel252 or send davidbindel252 to 22333
Consider a language like C:
| Thread 1 | Thread 2 |
|---|---|
t1 = load(c) |
|
t2 = load(c) |
|
t1 += 1 |
|
t2 += 1 |
|
store t1 |
|
store t2 |
|
One update gets lost!
| Thread 1 | Thread 2 |
|---|---|
t1 = load(c) |
|
t1 += 1 |
|
store t1 |
|
t2 = load(c) cached |
|
t2 += 1 |
|
store t2 |
|
Might still lose update!
Synchronization is coordination needed to
Really about preserving understood invariants.
But synchronization has performance implications…
No logical sharing – but maybe shared cache line!
| Thread 1 | Thread 2 |
|---|---|
lock(x) |
|
lock(y) |
|
lock(y) |
|
lock(x) |
|
| Uh-oh | Uh-oh |
y while T2 waits for xlock and unlock operationsA common pattern:
Use condition variable to signal work ready
Bulk synchronous model: phases separated by barriers
Rc for shared ownership, RefCell for interior mutability
!Send: unprotected reference count/mutability flagsArc (atomic Rc) synchronizes ref count accessARefCell
panic! on concurrent writes is undesireable!Rust Mutex<T> type protects a data object of type T
RefCell)lock method returns LockResult<MutexGuard<'_, T>>MutexGuard implements Deref and DerefMutMutexGuard is droppedPoison<T>
Ex: From Comprehensive Rust
Common to use Arc<Mutex<T>> for shared data
Arc owns data, satisfies 'static (unlike raw ref)Similar to Rc<RefCell<T>> pattern in single-thread case
Mutex<T>: Only one thread can hold lockRwLock<T> replaces lock() with read()/write()RefCellMethods on a condition variable (Condvar):
wait(m): Unlock mutex m and go to sleep
wait_timeout(m,t): Wait with a timeout tnotify_one(): Unlock + wake one waiting threadnotify_all(): Unlock + wake all waiting threadsuse std::collections::VecDeque;
use std::sync::Condvar;
fn handle_queued_work(qmutex: &Mutex<VecDeque>, not_empty: &Condvar) {
loop {
{
let mut q = queue.lock().unwrap();
let item = loop {
if let Some(item) = q.pop_front() {
break item;
} else {
q = not_empty.wait(q).unwrap();
}
};
}
handle(item);
}
}fn main() {
let queue = Mutex::new(VecDeque::new());
let not_empty = Condvar::new();
thread::scope(|s| {
// Consuming thread
let t = s.spawn(|| handle_queued_work(&queue));
// Producing thread
for i in 0.. {
queue.lock().unwrap().push_back(i);
not_empty.notify_one();
thread::sleep(Duration::from_secs(1));
}
});
}Usually use Condvar, but can also call:
thread::park() - Put thread to sleepthread::park_timeout(t) - Park with timeout thandle.unpark() - Wake thread back upWhat was most confusing today?
Respond at: https://PollEv.com/davidbindel252 or send davidbindel252 to 22333
Shared memory requires synchronization!
Mutex<T> and Condvar in RustReminder for US folks