Content deleted Content added
→Obstruction-freedom: Optimistic concurrency control != obstruction freedom. |
m authorlink Faith Ellen |
||
Line 51:
It was shown in the 1980s<ref name=imp>{{cite book|last=Herlihy|first=Maurice P.|title=Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing : Toronto, Ontario, Canada|year=1988|publisher=Association for Computing Machinery|___location=New York, N.Y.|isbn=0-89791-277-2|pages=276–290|url=http://doi.acm.org/10.1145/62546.62593|chapter=Impossibility and universality results for wait-free synchronization|date=August 15–17}}</ref> that all algorithms can be implemented wait-free, and many transformations from serial code, called ''universal constructions'', have been demonstrated. However, the resulting performance does not in general match even naïve blocking designs. Several papers have since improved the performance of universal constructions, but still, their performance is far below blocking designs.
Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown<ref name=cond-sync>{{cite book|last=Fich|first=Faith|author1-link=Faith Ellen|last2=Hendler|first2=Danny|last3=Shavit|first3=Nir|title=Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, PODC 2004 : St. John's, Newfoundland, Canada|year=2004|publisher=ACM Press|___location=New York, NY|isbn=1-58113-802-4|pages=80–87|url=http://doi.acm.org/10.1145/1011767.1011780|chapter=On the inherent weakness of conditional synchronization primitives|date=July 25–28}}</ref> that the widely available atomic ''conditional'' primitives, [[Compare-and-swap|CAS]] and [[Load-link/store-conditional|LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.
But in practice these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2kb on ARM) of store per thread in the shared memory is not considered too costly for practical systems (typically the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed|date=June 2014}} is greater).
| |||