Synchro
A lesson on why shared-memory threads need explicit synchronization, how RISC-V fences establish ordering, and how to recognize and avoid data races.
Shared Memory, Timing, and Unreliable Fixes
Shared memory does not determine order
Threads can communicate through shared memory because they share a virtual memory address space: one thread can write a variable and another can read it. Each thread executes its own instructions sequentially, but that does not guarantee how instructions from different threads will be interleaved or when one thread will observe another’s memory update. This apparent simplicity can be misleading; threaded programs can be difficult to reason about.
Consider the source’s send/receive example. The send thread stores 3410 in a global variable named value; the receive thread reads and prints value. If receive runs before send stores, it may read the earlier value instead. Creating receive second does not ensure it runs second: the operating-system scheduler chooses when threads run. Even if both start near the same time on different CPU cores, a delay on the core running send can let receive reach its load first. Without a mechanism to order the store and load, the result is not reliable.
Why sleep is not
Adding sleep(1) at the beginning of receive might make it more likely that send has stored the value by the time receive reads it. But no fixed sleep duration guarantees that order. The threads may start at different times, and a sleep can last longer than requested. A timing-based workaround can therefore seem to work and still fail; correctness must not depend on time merely passing.
Such a failure is nondeterministic. Using the source’s probability notation, let its probability be : means the bug does not occur, describes a deterministic bug, and describes an intermittent bug. Some nondeterministic bugs are heisenbugs: they disappear when someone investigates them. That can make a timing-sensitive problem especially difficult to reproduce.
Fences and a Reliable Pair
Why ordinary loads and stores are not enough
A shared flag may look like a solution: the sender writes the data and then sets the flag, while the receiver waits for the flag before reading the data. But ordinary loads and stores alone do not reliably synchronize threads. A processor’s store buffer can delay when its stores become visible to other processors, which may observe updates after a delay and possibly in a different order. More generally, modern hardware uses memory consistency models that allow memory accesses to appear out of order to remote processors. The hardware details are outside the scope of this course.
Special instructions can force selected memory accesses into a sequentially consistent order, though this can cost performance. Correct must account for compiler behavior as well: a compiler may reorder or even eliminate memory accesses unless prevents inappropriate transformations.
A as an ordering barrier
A RISC-V prevents memory accesses from being reordered across it: loads and stores before the must finish before it runs, and accesses after it must occur afterward. A plain is described as the strongest form, with the most guarantees.
The source’s pair uses the in two different places. In sync_set, the comes before the flag is set. In sync_wait, the receiver first loops until the flag is nonzero, then executes a before proceeding to later accesses:
sync_set:
li t0, 1
fence
sw t0, 0(a0)
ret
sync_wait:
.loop:
lw t0, 0(a0)
beqz t0, .loop
fence
ret
The sender’s orders its earlier memory accesses before the store of 1 to the flag. The receiver’s ensures that its following memory accesses occur after it has observed the flag become nonzero. Thus, when the sender has stored the shared data before calling sync_set, and the receiver reads it after sync_wait, the pair orders those accesses across the threads. The flag begins at 0 in the example, and the sender changes it to 1.
The source presents this as a RISC-V assembly implementation. It also notes that recent C versions can express using special instructions through stdatomic, without hand-writing assembly.
Happens-Before and Recognizing Data Races
Think in terms of ordered events
A represents instructions or statements as events and their ordering as edges. Events within one thread are ordered by that thread’s execution. By default, there are no ordering edges between events in different threads. operations, such as the source’s sync_set and sync_wait, establish inter-thread ordering edges. This way of thinking separates what a thread does in sequence from what the program explicitly orders across threads.
Check the conditions for a
To identify a , check whether two accesses:
Occur in different threads.
Refer to the same memory location.
Conflict, meaning at least one is a store.
Have no operation establishing an order between them.
In the source’s original example, send stores 3410 to the global value, while receive loads value to print it. These accesses are in different threads, target the same location, and include a store. Because the original program has no that orders them, they form a . In the synchronized version, sync_set and sync_wait establish the needed order between the store and load.
The distinctions matter. Two accesses in the same thread are not a . Nor are accesses by different threads to different memory locations. Different threads can also read the same data without a ; the conflict arises when one thread writes and another reads, or when both write. In C and C++, the formal definition concerns conflicting non-atomic accesses. Concurrent accesses that are all atomic do not constitute a .
Why Data Races Are
A is more than a scheduling surprise
In C and C++, a is . It is therefore not merely a case where the operating system happened to schedule the threads in an inconvenient order. The compiler is allowed to assume that a program has no data races and to optimize on that basis. Consequently, a racy program’s behavior cannot be reliably reasoned about, even if a particular run seems to produce a plausible result.
To write working parallel software, prevent data races by using to order conflicting accesses, or otherwise ensure those accesses do not occur as unsynchronized conflicting non-atomic operations.
: A programming model in which multiple threads can read and write the same memory.
: A bug that occurs sometimes but not every time.
: A bug that disappears when investigated.