Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #972
| Path | csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail |
|---|---|
| From | Vid <vidblr27@gmail.com> |
| Newsgroups | comp.programming.threads |
| Subject | Lock free linked lists with Harris's delete bit |
| Date | Mon, 23 Jul 2012 19:23:02 -0700 (PDT) |
| Organization | http://groups.google.com |
| Lines | 30 |
| Message-ID | <6751d074-07da-4f4e-9907-7b888e3c07e6@googlegroups.com> (permalink) |
| NNTP-Posting-Host | 144.49.131.1 |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=ISO-8859-1 |
| Content-Transfer-Encoding | quoted-printable |
| X-Trace | posting.google.com 1343096582 896 127.0.0.1 (24 Jul 2012 02:23:02 GMT) |
| X-Complaints-To | groups-abuse@google.com |
| NNTP-Posting-Date | Tue, 24 Jul 2012 02:23:02 +0000 (UTC) |
| Complaints-To | groups-abuse@google.com |
| Injection-Info | glegroupsg2000goo.googlegroups.com; posting-host=144.49.131.1; posting-account=WKV5aAkAAAAY_ASMEyhETZBCoj4ISLXs |
| User-Agent | G2/1.0 |
| X-Received-Bytes | 2412 |
| Xref | csiph.com comp.programming.threads:972 |
Show key headers only | View raw
Hi, I am fairly new to lock free programming and am attempting to implement (or reuse) a solution for lock free linked lists in C (logical delete only - multiple writers and multiple readers). I am aware of existing libraries that solve the problem (concurrency kit, liblfds) but am having trouble understanding the algorithm described in Harris's paper. The basic idea is to atomically mark a node X that is to be deleted and then delete the node, in order to ensure, X's right node is also not concurrently modified. This seems to solve concurrency issues that can arise in both of the below situations: 1. Inserting after node X, while concurrently deleting node X: As the next pointer on node X will be "marked" prior to a delete, either the node X will be successfully marked for delete or the new node will be successfully inserted after X, both cannot succeed due to the CAS operation involved in modifying X's next pointer 2. Deleting node X, while also deleting node Y = X->next: Similar to the above case, we can either succeed in marking node X for deletion, or changing X->next, to delete node Y, and not both due to the CAS operation on X's next pointer. Why do we then require the linked list to be sorted as is presented in algorithms that use Harris's delete bit? Am I missing any other concurrent operations that can cause a race condition? Thank you for your time. Vidya
Back to comp.programming.threads | Previous | Next — Next in thread | Find similar
Lock free linked lists with Harris's delete bit Vid <vidblr27@gmail.com> - 2012-07-23 19:23 -0700
Re: Lock free linked lists with Harris's delete bit Dmitriy Vyukov <dvyukov@gmail.com> - 2012-07-24 22:39 -0700
Re: Lock free linked lists with Harris's delete bit vidblr27@gmail.com - 2012-07-25 15:58 -0700
Re: Lock free linked lists with Harris's delete bit Toby Douglass <a@b.com> - 2012-09-10 09:48 +0200
csiph-web