I know the theoretical difference between lock-free and wait-free algorithms, but it's a little hard to me to figure out how do they differ in implementation (code). In particular, i would like to know how would the implementation (code) of a counter be. Thanks
3
-
$\begingroup$ This paper contains a wait-free algorithm for counters. $\endgroup$– hengxinCommented Apr 3, 2017 at 4:40
-
$\begingroup$ I think what you want is an example of a lock-free algorithm which isn't wait-free. $\endgroup$– Yuval FilmusCommented Apr 3, 2017 at 7:13
-
$\begingroup$ stackoverflow.com/q/4211180/21508463 $\endgroup$– user16034Commented Apr 29, 2023 at 10:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The lock free implementation will be Compare and Swap(CAS) on the counter, inside an indefinite while loop.Let's call it the increment method.The wait free version will have a help method and an announce method.The while loop will run for a fixed number of times, if the CAS does not succeed in these tries, the thread will "announce" for help by writing in it's id to a shared data structure.As soon as thread enters the increment(),it will first "help" all the operations that have been announced. PS:In my implementation,the counter is a structure consisting of integer value, thread id and other information.
