Namespaces
Variants
Views
Actions

Multi-threaded executions and data races (since C++11)

From cppreference.com
< cpp‎ | language
 
 
C++ language
General topics
Flow control
Conditional execution statements
if
Iteration statements (loops)
for
range-for (C++11)
Jump statements
Functions
Function declaration
Lambda function expression
inline specifier
Dynamic exception specifications (until C++17*)
noexcept specifier (C++11)
Exceptions
Namespaces
Types
Specifiers
decltype (C++11)
auto (C++11)
alignas (C++11)
Storage duration specifiers
Initialization
Expressions
Alternative representations
Literals
Boolean - Integer - Floating-point
Character - String - nullptr (C++11)
User-defined (C++11)
Utilities
Attributes (C++11)
Types
typedef declaration
Type alias declaration (C++11)
Casts
Implicit conversions - Explicit conversions
static_cast - dynamic_cast
const_cast - reinterpret_cast
Memory allocation
Classes
Class-specific function properties
explicit (C++11)
static
Special member functions
Templates
Miscellaneous
 
 

A thread of execution is a flow of control within a program that begins with the invocation of a specific top-level function (by std::thread::thread, std::async, or other means), and recursively including every function invocation subsequently executed by the thread.

  • When one thread creates another, the initial call to the top-level function of the new thread is executed by the new thread, not by the creating thread.

Any thread can potentially access any object and function in the program:

  • Objects with automatic and thread-local storage duration may still be accessed by another thread through a pointer or by reference.
  • Under a hosted implementation, a C++ program can have more than one thread running concurrently. The execution of each thread proceeds as defined by the rest of this page. The execution of the entire program consists of an execution of all of its threads.
  • Under a freestanding implementation, it is implementation-defined whether a program can have more than one thread of execution.

For a signal handler that is not executed as a result of a call to std::raise, it is unspecified which thread of execution contains the signal handler invocation.

Contents

[edit] Data races

Different threads of execution are always allowed to access (read and modify) different memory locations concurrently, with no interference and no synchronization requirements.

When an evaluation of an expression modifies a memory location and another evaluation reads or modifies the same memory location, the expressions are said to conflict. A program that has two conflicting evaluations has a data race unless

  • both evaluations execute on the same thread or in the same signal handler, or
  • both conflicting evaluations are atomic operations (see std::atomic), or
  • one of the conflicting evaluations happens-before another (see std::memory_order).

If a data race occurs, the behavior of the program is undefined.

(In particular, release of a std::mutex is synchronized-with, and therefore, happens-before acquisition of the same mutex by another thread, which makes it possible to use mutex locks to guard against data races.)

int cnt = 0;
auto f = [&] { cnt++; };
std::thread t1{f}, t2{f}, t3{f}; // undefined behavior
std::atomic<int> cnt{0};
auto f = [&] { cnt++; };
std::thread t1{f}, t2{f}, t3{f}; // OK

[edit] Memory order

When a thread reads a value from a memory location, it may see the initial value, the value written in the same thread, or the value written in another thread. See std::memory_order for details on the order in which writes made from threads become visible to other threads.

[edit] Forward progress

[edit] Obstruction freedom

When only one thread that is not blocked in a standard library function executes an atomic function that is lock-free, that execution is guaranteed to complete (all standard library lock-free operations are obstruction-free).

[edit] Lock freedom

When one or more lock-free atomic functions run concurrently, at least one of them is guaranteed to complete (all standard library lock-free operations are lock-free — it is the job of the implementation to ensure they cannot be live-locked indefinitely by other threads, such as by continuously stealing the cache line).

[edit] Progress guarantee

In a valid C++ program, every thread eventually does one of the following:

  • Terminates.
  • Invokes std::this_thread::yield.
  • Makes a call to an library I/O function.
  • Performs an access through a volatile glvalue.
  • Performs an atomic operation or a synchronization operation.
  • Continues execution of a trivial infinite loop (see below).

A thread is said to make progress if it performs one of the execution steps above, blocks in a standard library function, or calls an atomic lock-free function that does not complete because of a non-blocked concurrent thread.

This allows the compilers to remove, merge and reorder all loops that have no observable behavior, without having to prove that they would eventually terminate because it can assume that no thread of execution can execute forever without performing any of these observable behaviors. An affordance is made for trivial infinite loops, which cannot be removed nor reordered.

[edit] Trivial infinite loops

A trivially empty iteration statement is an iteration statement matching one of the following forms:

while ( condition ) ; (1)
while ( condition ) { } (2)
do ; while ( condition ) ; (3)
do { } while ( condition ) ; (4)
for ( init-statement condition (optional) ; ) ; (5)
for ( init-statement condition (optional) ; ) { } (6)
1) A while statement whose loop body is an empty simple statement.
2) A while statement whose loop body is an empty compound statement.
3) A do-while statement whose loop body is an empty simple statement.
4) A do-while statement whose loop body is an empty compound statement.
5) A for statement whose loop body is an empty simple statement, the for statement does not have an iteration-expression.
6) A for statement whose loop body is an empty compound statement, the for statement does not have an iteration-expression.

The controlling expression of a trivially empty iteration statement is:

1-4) condition.
5,6) condition if present, otherwise true.

A trivial infinite loop is a trivially empty iteration statement for which the converted controlling expression is a constant expression, when manifestly constant-evaluated, and evaluates to true.

The loop body of a trivial infinite loop is replaced with a call to the function std::this_thread::yield. It is implementation-defined whether this replacement occurs on freestanding implementations.

Concurrent forward progress

If a thread offers concurrent forward progress guarantee, it will make progress (as defined above) in finite amount of time, for as long as it has not terminated, regardless of whether other threads (if any) are making progress.

The standard encourages, but doesn't require that the main thread and the threads started by std::thread offer concurrent forward progress guarantee.

Parallel forward progress

If a thread offers parallel forward progress guarantee, the implementation is not required to ensure that the thread will eventually make progress if it has not yet executed any execution step (I/O, volatile, atomic, or synchronization), but once this thread has executed a step, it provides concurrent forward progress guarantees (this rule describes a thread in a thread pool that executes tasks in arbitrary order).

Weakly parallel forward progress

If a thread offers weakly parallel forward progress guarantee, it does not guarantee to eventually make progress, regardless of whether other threads make progress or not.

Such threads can still be guaranteed to make progress by blocking with forward progress guarantee delegation: if a thread P blocks in this manner on the completion of a set of threads S, then at least one thread in S will offer a forward progress guarantee that is same or stronger than P. Once that thread completes, another thread in S will be similarly strengthened. Once the set is empty, P will unblock.

The parallel algorithms from the C++ standard library block with forward progress delegation on the completion of an unspecified set of library-managed threads.

(since C++17)

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
P2809R3 C++11 the behavior of executing “trivial”[1]
infinite loops was undefined
properly defines “trivial infinite loops”
and made the behavior well-defined
  1. “Trivial” here means executing the infinite loop never makes any progress.