[intro.progress]

# 6 Basics [[basic]](./#basic)

## 6.10 Program execution [[basic.exec]](basic.exec#intro.progress)

### 6.10.2 Multi-threaded executions and data races [[intro.multithread]](intro.multithread#intro.progress)

#### 6.10.2.3 Forward progress [intro.progress]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L6913)

The implementation may assume that any thread will eventually do one of the
following:

- [(1.1)](#1.1)

terminate,

- [(1.2)](#1.2)

invoke the function std​::​this_thread​::​yield ([[thread.thread.this]](thread.thread.this "32.4.5 Namespace this_­thread")),

- [(1.3)](#1.3)

make a call to a library I/O function,

- [(1.4)](#1.4)

perform an access through a volatile glvalue,

- [(1.5)](#1.5)

perform an atomic or synchronization operation
other than an atomic modify-write operation ([[atomics.order]](atomics.order "32.5.4 Order and consistency")), or

- [(1.6)](#1.6)

continue execution of a trivial infinite loop ([[stmt.iter.general]](stmt.iter.general "8.6.1 General"))[.](#1.sentence-1)

[*Note [1](#note-1)*:

This is intended to allow compiler transformations
such as removal, merging, and reordering of empty loops,
even when termination cannot be proven[.](#1.sentence-2)

An affordance is made for trivial infinite loops,
which cannot be removed nor reordered[.](#1.sentence-3)

â *end note*]

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L6933)

Executions of atomic functions
that are either defined to be lock-free ([[atomics.flag]](atomics.flag "32.5.10 Flag type and operations"))
or indicated as lock-free ([[atomics.lockfree]](atomics.lockfree "32.5.5 Lock-free property"))
are [*lock-free executions*](#def:lock-free_execution "6.10.2.3 Forward progress [intro.progress]")[.](#2.sentence-1)

- [(2.1)](#2.1)

  If there is only one thread that is not blocked ([[defns.block]](defns.block "3.6 block"))
 in a standard library function,
 a lock-free execution in that thread shall complete[.](#2.1.sentence-1)
  [*Note [2](#note-2)*:
  Concurrently executing threads
 might prevent progress of a lock-free execution[.](#2.1.sentence-2)
  For example,
 this situation can occur
 with load-locked store-conditional implementations[.](#2.1.sentence-3)
  This property is sometimes termed obstruction-free[.](#2.1.sentence-4)
 â *end note*]

- [(2.2)](#2.2)

  When one or more lock-free executions run concurrently,
 at least one should complete[.](#2.2.sentence-1)
  [*Note [3](#note-3)*:
  It is difficult for some implementations
 to provide absolute guarantees to this effect,
 since repeated and particularly inopportune interference
 from other threads
 could prevent forward progress,
 e.g.,
 by repeatedly stealing a cache line
 for unrelated purposes
 between load-locked and store-conditional instructions[.](#2.2.sentence-2)
  For implementations that follow this recommendation and
 ensure that such effects cannot indefinitely delay progress
 under expected operating conditions,
 such anomalies
 can therefore safely be ignored by programmers[.](#2.2.sentence-3)
  Outside this document,
 this property is sometimes termed lock-free[.](#2.2.sentence-4)
 â *end note*]

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L6974)

During the execution of a thread of execution, each of the following is termed
an [*execution step*](#def:execution_step "6.10.2.3 Forward progress [intro.progress]"):

- [(3.1)](#3.1)

termination of the thread of execution,

- [(3.2)](#3.2)

performing an access through a volatile glvalue,

- [(3.3)](#3.3)

completion of a call to a library I/O function, or

- [(3.4)](#3.4)

completion of an atomic or synchronization operation
other than an atomic modify-write operation ([[atomics.order]](atomics.order "32.5.4 Order and consistency"))[.](#3.sentence-1)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L6985)

An invocation of a standard library function that blocks ([[defns.block]](defns.block "3.6 block"))
is considered to continuously execute execution steps while waiting for the
condition that it blocks on to be satisfied[.](#4.sentence-1)

[*Example [1](#example-1)*:

A library I/O function that blocks until the I/O operation is complete can
be considered to continuously check whether the operation is complete[.](#4.sentence-2)

Each
such check consists of one or more execution steps, for example using
observable behavior of the abstract machine[.](#4.sentence-3)

â *end example*]

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L6996)

[*Note [4](#note-4)*:

Because of this and the preceding requirement regarding what threads of execution
have to perform eventually, it follows that no thread of execution can execute
forever without an execution step occurring[.](#5.sentence-1)

â *end note*]

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7003)

A thread of execution [*makes progress*](#def:make_progress,thread "6.10.2.3 Forward progress [intro.progress]") when an execution step occurs or a
lock-free execution does not complete because there are other concurrent threads
that are not blocked in a standard library function (see above)[.](#6.sentence-1)

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7009)

For a thread of execution providing [*concurrent forward progress guarantees*](#def:concurrent_forward_progress_guarantees "6.10.2.3 Forward progress [intro.progress]"),
the implementation ensures that the thread will eventually make progress for as
long as it has not terminated[.](#7.sentence-1)

[*Note [5](#note-5)*:

This applies regardless of whether or not other threads of execution (if any)
have been or are making progress[.](#7.sentence-2)

To eventually fulfill this requirement means that
this will happen in an unspecified but finite amount of time[.](#7.sentence-3)

â *end note*]

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7020)

It is implementation-defined whether the
implementation-created thread of execution that executesmain ([[basic.start.main]](basic.start.main "6.10.3.1 main function")) and the threads of execution created bystd​::​thread ([[thread.thread.class]](thread.thread.class "32.4.3 Class thread"))
or std​::​jthread ([[thread.jthread.class]](thread.jthread.class "32.4.4 Class jthread"))
provide concurrent forward progress guarantees[.](#8.sentence-1)

General-purpose implementations should provide these guarantees[.](#8.sentence-2)

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7030)

For a thread of execution providing [*parallel forward progress guarantees*](#def:parallel_forward_progress_guarantees "6.10.2.3 Forward progress [intro.progress]"),
the implementation is not required to ensure that the thread will eventually make
progress if it has not yet executed any execution step; once this thread has
executed a step, it provides concurrent forward progress guarantees[.](#9.sentence-1)

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7037)

[*Note [6](#note-6)*:

This does not specify a requirement for when to start this thread of execution,
which will typically be specified by the entity that creates this thread of
execution[.](#10.sentence-1)

For example, a thread of execution that provides concurrent forward
progress guarantees and executes tasks from a set of tasks in an arbitrary order,
one after the other, satisfies the requirements of parallel forward progress for
these tasks[.](#10.sentence-2)

â *end note*]

[11](#11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7047)

For a thread of execution providing [*weakly parallel forward progress
guarantees*](#def:weakly_parallel_forward_progress_guarantees "6.10.2.3 Forward progress [intro.progress]"), the implementation does not ensure that the thread will eventually
make progress[.](#11.sentence-1)

[12](#12)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7053)

[*Note [7](#note-7)*:

Threads of execution providing weakly parallel forward progress guarantees cannot
be expected to make progress regardless of whether other threads make progress or
not; however, blocking with forward progress guarantee delegation, as defined below,
can be used to ensure that such threads of execution make progress eventually[.](#12.sentence-1)

â *end note*]

[13](#13)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7061)

Concurrent forward progress guarantees are stronger than parallel forward progress
guarantees, which in turn are stronger than weakly parallel forward progress
guarantees[.](#13.sentence-1)

[*Note [8](#note-8)*:

For example, some kinds of synchronization between threads of execution might only
make progress if the respective threads of execution provide parallel forward progress
guarantees, but will fail to make progress under weakly parallel guarantees[.](#13.sentence-2)

â *end note*]

[14](#14)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7071)

When a thread of execution P is specified to[*block with forward progress guarantee delegation*](#def:block_(execution),with_forward_progress_guarantee_delegation "6.10.2.3 Forward progress [intro.progress]") on the completion of a set S of threads of execution,
then throughout the whole time of P being blocked on S,
the implementation shall ensure that the forward progress guarantees
provided by at least one thread of execution in S is at least as strong as P's forward progress guarantees[.](#14.sentence-1)

[*Note [9](#note-9)*:

It is unspecified which thread or threads of execution in S are chosen
and for which number of execution steps[.](#14.sentence-2)

The strengthening is not permanent and
not necessarily in place for the rest of the lifetime of the affected thread of
execution[.](#14.sentence-3)

As long as P is blocked, the implementation has to eventually
select and potentially strengthen a thread of execution in S[.](#14.sentence-4)

â *end note*]

Once a thread of execution in S terminates, it is removed from S[.](#14.sentence-5)

Once S is empty, P is unblocked[.](#14.sentence-6)

[15](#15)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7091)

[*Note [10](#note-10)*:

A thread of execution B thus can temporarily provide an effectively
stronger forward progress guarantee for a certain amount of time, due to a
second thread of execution A being blocked on it with forward
progress guarantee delegation[.](#15.sentence-1)

In turn, if B then blocks with
forward progress guarantee delegation on C, this can also temporarily
provide a stronger forward progress guarantee to C[.](#15.sentence-2)

â *end note*]

[16](#16)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7101)

[*Note [11](#note-11)*:

If all threads of execution in S finish executing (e.g., they terminate
and do not use blocking synchronization incorrectly), then P's execution
of the operation that blocks with forward progress guarantee delegation will not
result in P's progress guarantee being effectively weakened[.](#16.sentence-1)

â *end note*]

[17](#17)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7109)

[*Note [12](#note-12)*:

This does not remove any constraints regarding blocking synchronization for
threads of execution providing parallel or weakly parallel forward progress
guarantees because the implementation is not required to strengthen a particular
thread of execution whose too-weak progress guarantee is preventing overall progress[.](#17.sentence-1)

â *end note*]

[18](#18)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/basic.tex#L7117)

An implementation should ensure that the last value (in modification order)
assigned by an atomic or synchronization operation will become visible to all
other threads in a finite period of time[.](#18.sentence-1)
