tmp/tmpmto6w6ri/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,155 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
### Forward progress <a id="intro.progress">[[intro.progress]]</a>
|
| 2 |
+
|
| 3 |
+
The implementation may assume that any thread will eventually do one of
|
| 4 |
+
the following:
|
| 5 |
+
|
| 6 |
+
- terminate,
|
| 7 |
+
- make a call to a library I/O function,
|
| 8 |
+
- perform an access through a volatile glvalue, or
|
| 9 |
+
- perform a synchronization operation or an atomic operation.
|
| 10 |
+
|
| 11 |
+
[*Note 1*: This is intended to allow compiler transformations such as
|
| 12 |
+
removal of empty loops, even when termination cannot be
|
| 13 |
+
proven. — *end note*]
|
| 14 |
+
|
| 15 |
+
Executions of atomic functions that are either defined to be lock-free (
|
| 16 |
+
[[atomics.flag]]) or indicated as lock-free ([[atomics.lockfree]]) are
|
| 17 |
+
*lock-free executions*.
|
| 18 |
+
|
| 19 |
+
- If there is only one thread that is not blocked ([[defns.block]]) in
|
| 20 |
+
a standard library function, a lock-free execution in that thread
|
| 21 |
+
shall complete. \[*Note 2*: Concurrently executing threads may prevent
|
| 22 |
+
progress of a lock-free execution. For example, this situation can
|
| 23 |
+
occur with load-locked store-conditional implementations. This
|
| 24 |
+
property is sometimes termed obstruction-free. — *end note*]
|
| 25 |
+
- When one or more lock-free executions run concurrently, at least one
|
| 26 |
+
should complete. \[*Note 3*: It is difficult for some implementations
|
| 27 |
+
to provide absolute guarantees to this effect, since repeated and
|
| 28 |
+
particularly inopportune interference from other threads may prevent
|
| 29 |
+
forward progress, e.g., by repeatedly stealing a cache line for
|
| 30 |
+
unrelated purposes between load-locked and store-conditional
|
| 31 |
+
instructions. Implementations should ensure that such effects cannot
|
| 32 |
+
indefinitely delay progress under expected operating conditions, and
|
| 33 |
+
that such anomalies can therefore safely be ignored by programmers.
|
| 34 |
+
Outside this document, this property is sometimes termed
|
| 35 |
+
lock-free. — *end note*]
|
| 36 |
+
|
| 37 |
+
During the execution of a thread of execution, each of the following is
|
| 38 |
+
termed an *execution step*:
|
| 39 |
+
|
| 40 |
+
- termination of the thread of execution,
|
| 41 |
+
- performing an access through a volatile glvalue, or
|
| 42 |
+
- completion of a call to a library I/O function, a synchronization
|
| 43 |
+
operation, or an atomic operation.
|
| 44 |
+
|
| 45 |
+
An invocation of a standard library function that blocks (
|
| 46 |
+
[[defns.block]]) is considered to continuously execute execution steps
|
| 47 |
+
while waiting for the condition that it blocks on to be satisfied.
|
| 48 |
+
|
| 49 |
+
[*Example 1*: A library I/O function that blocks until the I/O
|
| 50 |
+
operation is complete can be considered to continuously check whether
|
| 51 |
+
the operation is complete. Each such check might consist of one or more
|
| 52 |
+
execution steps, for example using observable behavior of the abstract
|
| 53 |
+
machine. — *end example*]
|
| 54 |
+
|
| 55 |
+
[*Note 4*: Because of this and the preceding requirement regarding what
|
| 56 |
+
threads of execution have to perform eventually, it follows that no
|
| 57 |
+
thread of execution can execute forever without an execution step
|
| 58 |
+
occurring. — *end note*]
|
| 59 |
+
|
| 60 |
+
A thread of execution *makes progress* when an execution step occurs or
|
| 61 |
+
a lock-free execution does not complete because there are other
|
| 62 |
+
concurrent threads that are not blocked in a standard library function
|
| 63 |
+
(see above).
|
| 64 |
+
|
| 65 |
+
For a thread of execution providing *concurrent forward progress
|
| 66 |
+
guarantees*, the implementation ensures that the thread will eventually
|
| 67 |
+
make progress for as long as it has not terminated.
|
| 68 |
+
|
| 69 |
+
[*Note 5*: This is required regardless of whether or not other threads
|
| 70 |
+
of executions (if any) have been or are making progress. To eventually
|
| 71 |
+
fulfill this requirement means that this will happen in an unspecified
|
| 72 |
+
but finite amount of time. — *end note*]
|
| 73 |
+
|
| 74 |
+
It is *implementation-defined* whether the implementation-created thread
|
| 75 |
+
of execution that executes `main` ([[basic.start.main]]) and the
|
| 76 |
+
threads of execution created by `std::thread` ([[thread.thread.class]])
|
| 77 |
+
provide concurrent forward progress guarantees.
|
| 78 |
+
|
| 79 |
+
[*Note 6*: General-purpose implementations are encouraged to provide
|
| 80 |
+
these guarantees. — *end note*]
|
| 81 |
+
|
| 82 |
+
For a thread of execution providing *parallel forward progress
|
| 83 |
+
guarantees*, the implementation is not required to ensure that the
|
| 84 |
+
thread will eventually make progress if it has not yet executed any
|
| 85 |
+
execution step; once this thread has executed a step, it provides
|
| 86 |
+
concurrent forward progress guarantees.
|
| 87 |
+
|
| 88 |
+
[*Note 7*: This does not specify a requirement for when to start this
|
| 89 |
+
thread of execution, which will typically be specified by the entity
|
| 90 |
+
that creates this thread of execution. For example, a thread of
|
| 91 |
+
execution that provides concurrent forward progress guarantees and
|
| 92 |
+
executes tasks from a set of tasks in an arbitrary order, one after the
|
| 93 |
+
other, satisfies the requirements of parallel forward progress for these
|
| 94 |
+
tasks. — *end note*]
|
| 95 |
+
|
| 96 |
+
For a thread of execution providing *weakly parallel forward progress
|
| 97 |
+
guarantees*, the implementation does not ensure that the thread will
|
| 98 |
+
eventually make progress.
|
| 99 |
+
|
| 100 |
+
[*Note 8*: Threads of execution providing weakly parallel forward
|
| 101 |
+
progress guarantees cannot be expected to make progress regardless of
|
| 102 |
+
whether other threads make progress or not; however, blocking with
|
| 103 |
+
forward progress guarantee delegation, as defined below, can be used to
|
| 104 |
+
ensure that such threads of execution make progress
|
| 105 |
+
eventually. — *end note*]
|
| 106 |
+
|
| 107 |
+
Concurrent forward progress guarantees are stronger than parallel
|
| 108 |
+
forward progress guarantees, which in turn are stronger than weakly
|
| 109 |
+
parallel forward progress guarantees.
|
| 110 |
+
|
| 111 |
+
[*Note 9*: For example, some kinds of synchronization between threads
|
| 112 |
+
of execution may only make progress if the respective threads of
|
| 113 |
+
execution provide parallel forward progress guarantees, but will fail to
|
| 114 |
+
make progress under weakly parallel guarantees. — *end note*]
|
| 115 |
+
|
| 116 |
+
When a thread of execution *P* is specified to *block with forward
|
| 117 |
+
progress guarantee delegation* on the completion of a set *S* of threads
|
| 118 |
+
of execution, then throughout the whole time of *P* being blocked on
|
| 119 |
+
*S*, the implementation shall ensure that the forward progress
|
| 120 |
+
guarantees provided by at least one thread of execution in *S* is at
|
| 121 |
+
least as strong as *P*’s forward progress guarantees.
|
| 122 |
+
|
| 123 |
+
[*Note 10*: It is unspecified which thread or threads of execution in
|
| 124 |
+
*S* are chosen and for which number of execution steps. The
|
| 125 |
+
strengthening is not permanent and not necessarily in place for the rest
|
| 126 |
+
of the lifetime of the affected thread of execution. As long as *P* is
|
| 127 |
+
blocked, the implementation has to eventually select and potentially
|
| 128 |
+
strengthen a thread of execution in *S*. — *end note*]
|
| 129 |
+
|
| 130 |
+
Once a thread of execution in *S* terminates, it is removed from *S*.
|
| 131 |
+
Once *S* is empty, *P* is unblocked.
|
| 132 |
+
|
| 133 |
+
[*Note 11*: A thread of execution *B* thus can temporarily provide an
|
| 134 |
+
effectively stronger forward progress guarantee for a certain amount of
|
| 135 |
+
time, due to a second thread of execution *A* being blocked on it with
|
| 136 |
+
forward progress guarantee delegation. In turn, if *B* then blocks with
|
| 137 |
+
forward progress guarantee delegation on *C*, this may also temporarily
|
| 138 |
+
provide a stronger forward progress guarantee to *C*. — *end note*]
|
| 139 |
+
|
| 140 |
+
[*Note 12*: If all threads of execution in *S* finish executing (e.g.,
|
| 141 |
+
they terminate and do not use blocking synchronization incorrectly),
|
| 142 |
+
then *P*’s execution of the operation that blocks with forward progress
|
| 143 |
+
guarantee delegation will not result in *P*’s progress guarantee being
|
| 144 |
+
effectively weakened. — *end note*]
|
| 145 |
+
|
| 146 |
+
[*Note 13*: This does not remove any constraints regarding blocking
|
| 147 |
+
synchronization for threads of execution providing parallel or weakly
|
| 148 |
+
parallel forward progress guarantees because the implementation is not
|
| 149 |
+
required to strengthen a particular thread of execution whose too-weak
|
| 150 |
+
progress guarantee is preventing overall progress. — *end note*]
|
| 151 |
+
|
| 152 |
+
An implementation should ensure that the last value (in modification
|
| 153 |
+
order) assigned by an atomic or synchronization operation will become
|
| 154 |
+
visible to all other threads in a finite period of time.
|
| 155 |
+
|