CODEWITHSUNDEEP
c++coperating-systematomiccompare-and-swap
sidewala
sidewala

Reputation: 61

Writing a terminating atomic increment function

If I have the following increment function

void increment(atomic_int *v)
{
int temp;
do {
temp = *v;
}
while (temp != compare_and_swap(v, temp, temp+1));
}

How do I modify this to make it a terminating atomic increment function

Upvotes: 2

Views: 209

Answers (1)

Nate Eldredge
Nate Eldredge

Reputation: 58814

I don't think you can get a 100% guarantee of completion in bounded time, unless (in C++) you block all other threads temporarily.

The best you can do is use:

  • in C, any of atomic_fetch_add(v, 1), (*v)++, ++*v, *v += 1;

  • in C++, assuming v is std::atomic<int> *, any of v->fetch_add(1), ++*v, (*v)++, *v += 1.

If the hardware provides a method for an atomic increment with bounded completion, the above functions are likely to use it.

However, some machines do not provide such a feature; on an LL/SC architecture, every atomic read-modify-write may be internally compiled into a loop similar to your compare-exchange. In this case, if other threads are continuously writing to the object, there may not be any guarantee of eventual completion. (The hardware will probably have some sort of "fairness" feature that makes infinite starvation unlikely, but this may not be guaranteed.)

The only "forward progress" promise made by the C++20 standard is in [intro.progress], where it says that

If there is only one thread that is not blocked (3.6) in a standard library function, a lock-free execution in that thread shall complete. [Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes termed obstruction-free. — end note]

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

C currently doesn't have any such guarantees at all, as far as I can tell.

Upvotes: 1

Related Questions