File EventCount.h
↰ Parent directory (ADS/concurrent)
An event count, beyond the book: the way for a thread to sleep until a condition on a lock-free structure holds, instead of looking at it again and again or between sleeps of a fixed length, with no lock and nearly no cost for the threads that make the condition true while nobody waits.
Definition (ADS/concurrent/EventCount.h)
Detailed Description
It holds an epoch and the number of the waiters, the two halves of one word of 64 bits on a line of its own. A waiter announces itself (prepareWait(), which adds 1 to the waiters and reads the epoch e in the same read-modify-write), looks at the condition once more, and if it is still false sleeps until the epoch is no longer e (commitWait( e ), by std::atomic::wait); otherwise it withdraws (cancelWait( e )). A notifier makes the condition true, then notify() reads the word after a fence and, only if there are waiters, advances the epoch and sets the waiters to 0 in one compare-and-swap, and wakes them (std::atomic::notify_all): the notifications that follow, while the woken threads are still on their way, find nobody to wake and cost no system call. The fences are asymmetric where the system has them (membarrier(2) on Linux): the waiter, which is about to sleep anyway, runs the heavy one, a system call that makes every running thread of the process run a full barrier, and the notifier the light one, which only stops the compiler, so that when nobody waits a notification costs the read of a line that stays shared (a full fence would wait, at each item, for the stores of the item to reach the caches of the other threads); elsewhere both are full fences. No wake-up is lost: the fence of the notifier and the read-modify-write and fence of the waiter are in the single total order of the sequentially consistent operations (a pair of asymmetric fences orders as a pair of full ones); if the notifier reads 0 waiters, its fence comes before the announcement of the waiter, which then sees the condition made true when it looks again, and if it reads 1 or more it advances the epoch by a release on the same word, which the announcement either precedes (and the wait on e returns at once or is woken) or follows, reading the new epoch with an acquire and seeing the condition made true. A spurious wake-up only makes the waiter look again. await( p ) packs the loop: it returns when p() is true, and p is called by the waiting thread only, so that it may take an item; it first looks again and again for 20 us (a parameter), with a pause of the processor between the looks, since an item that comes within that time costs no sleep and no wake-up (each about the time of a system call and of a switch of threads), and a waiter that does not sleep costs its notifier only the fence. The contracts [see File Contract.h]: each prepareWait() is followed by one commitWait() or cancelWait() of the same thread, with the epoch it returned. D. P. Reed, R. K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM 22(2), 115-123, 1979, doi:10.1145/359060.359076 (the event count)
Williams, C++ Concurrency in Action, 2nd ed., Manning, 2019, chapter 5 (the total order of the sequentially consistent operations and the fences)
Boehm, S. V. Adve, Foundations of the C++ concurrency memory model, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 68-78, 2008, doi:10.1145/1375581.1375591
Ladan-Mozes, I.-T. A. Lee, D. Vyukov, Location-based memory fences, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 75-84, 2011, doi:10.1145/1989493.1989503 (the asymmetric fences)
- Donato Meoli
Dipartimento di Informatica Universita’ di Pisa
by Donato Meoli
Includes
atomicchronocstdint