Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #1080
| Date | 2012-09-20 00:03 +0200 |
|---|---|
| From | Marcel Müller <news.5.maazl@spamgourmet.org> |
| Newsgroups | comp.programming.threads |
| Subject | Re: New solution for ABA in lock-free lists? |
| References | <991d0156-2748-4e1b-858d-702b4ca9e8e2@googlegroups.com> |
| Message-ID | <505a4124$0$6566$9b4e6d93@newsspool3.arcor-online.net> (permalink) |
| Organization | Arcor |
On 17.09.12 12.13, calum74@gmail.com wrote: > The basic idea is to introduce a new state to each pointer: NULL, node and BUSY. The BUSY state acts as a mutex, so if you are unlucky for two threads to access the same memory simultaneously, then the second thread must spin until the pointer becomes non-BUSY. A spin lock is nothing but a regular mutex. Your algorithm is no longer lock free, because it does not guarantee forward progress. Think if one thread is stopped by the scheduler while the lock bit is set, you might spin forever. Especially the priority inversion problem applies. One solution for the ABA problem is a strictly monotonic revision counter. Or, of course, more sophisticated atomic expression. CAS is not the answer to all questions (this is 42 ;-) ). E.g. optimistic memory locks do not share the ABA problem. Marcel
Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar
New solution for ABA in lock-free lists? calum74@gmail.com - 2012-09-17 03:13 -0700
Re: New solution for ABA in lock-free lists? Marcel Müller <news.5.maazl@spamgourmet.org> - 2012-09-20 00:03 +0200
Re: New solution for ABA in lock-free lists? calumg <spambox@calumgrant.net> - 2012-09-21 04:20 -0700
Re: New solution for ABA in lock-free lists? Marcel Müller <news.5.maazl@spamgourmet.com> - 2012-09-28 00:58 +0200
csiph-web