Memory model

define how threads interact with shared memory: when multiple threads may access same memory location and when writes become visible to other threads

Concepts

• A memory location is a scalar variable or a contiguous sequence of non-zero bitfield variables.
• Execution model is designed on the basis of evaluations
  • the evaluation of each expression includes 2 parts:
    • value computation
    • side-effect: read of volatile object, read/write a (volatile) object, IO calls, etc.
• Conflicting actions are 2 evaluations that access the same memory location and at least 1 of which is a write
• A data race is when 2 conflicting actions in different threads and they are not happen-before each other, not atomic, and not in the same signal handler
  • data race is undefined behavior
• Sequential consistency for data race-free program (SC-DRF):
  • Sequential consistency:
    • exists a sequence of operations that get the same result
    • the operations of each thread in the sequence align with the program order
  • if programmers makes sure there is no data race, the system guarantees sequentially consistent execution

Rules

• sequence-before: partial order, asymmetric, transitive
  • handwavingly: the top-to-bottom order when writing code
  • this is only applicable to the same thread…
  • if A is sequenced before B, then the evaluation A finished before the the evaluation starts (and vice versa)
  • if both A and B are not sequenced-before each other, then they can be evaluated in any order
    • e.g. argument expression in function calls: func(expr1, expr2) -> expr1 and expr2 can be evaluated in any order
    • evals can be overlap (called ”unsequenced”) (most cases are so, by default) or not (called “indeterminately sequenced”)
• synchronize-with:
  • if A synchronizes with B, then all writes before A in the thread of A becomes visible to the thread of B after B is evaluated
• happen-before:
  • if X sequence-before A, B sequence-before Y, A synchronize-with B, then X happen-before Y

Atomic ops

An atomic operation is an operation that is guaranteed to execute as a single transaction. Other threads see the state of the system either before or after the operation, but not any intermediate state.

At low level, atomic operations are special hardware instructions.

std::atomic

#include <atomic>

std::atomic<int> x(0);
++x; // now ++x is atomic

eligible types

• any trivially copyable type can be made atomic