NON Blocking Algorithm in C/C++
Hi,
I want to implement 1) singly linked list using any non-blocking algo. 2) double linked list using any non-blocking algo. As a starting point, I gone through few research papers and wikipedia links about CAS, Non-Blocking Algorithm, etc. I want to write a sample code with simplest of operations on linked list. Please provide suitable guidance and references. Thanks Nikunj Bangalore-India |
Quote:
|
Yes.
|
Quote:
|
This thread seems to have pulled in only an expert who didn't even know the topic existed.
Before I read the question Yesterday, I didn't know the topic existed. So I didn't reply. I found this paper by Timothy Harris http://research.microsoft.com/en-us/.../2001-disc.pdf It details a specific algorithm for linked list very clearly. A quick skim of a few Wiki and other pages describing the concepts left me still feeling like I was missing the point. This one concrete example by Harris really helped in getting that point. So if any of the other experts are curious what the OP is asking about, I suggest reading that paper. Quote:
I can't think of any guidance one could give a non expert algorithm developer to help him be able to put together an algorithm like the one Harris described. To work, a design like this must be a single unified concept. Quote:
|
Quote:
Anyway, OPs question is too vague. The answer to "I want to write" is "write it". I would prefer more specific question. |
Quote:
Imagine you have many threads working on a task and you have an evil preemptive scheduler that will suspend a few of your threads for a very long time and will pick the threads and the moments per thread to do max harm. You need an algorithm that will make good progress despite that interference. Any lock allows the evil scheduler to suspend the thread holding the lock, thus stopping progress for all threads. A critical section that locks out the scheduler as well as other threads is impractical for other reasons. A critical section that doesn't lock out the scheduler is just a lock. The hypothesis of the evil preemptive scheduler seems to be an axiom within this topic. So you can't answer a question in this topic by noting how unlikely it is that a real scheduler would act that way. Within the topic you can only look at how the algorithm can reliably succeed despite that scheduler. Quote:
Quote:
One more clarification: At the lowest level of this design you must assume the CAS operation is atomic. The difference between this and a "blocking" design is that a "blocking" design uses a tiny hardware defined/enforced atomic combination of steps to guard a larger software defined atomic collection of steps. A non blocking design uses the hardware atomic combination of steps in some other way that does not involve making a larger combination of steps atomic. |
Quote:
Because of this, it is recommended to have a specification. I.e. what kind of operations are supposed to be performed on list, are all threads doing same thing or not, etc. |
please correct me if I am wrong, but the standard stl container are non blocking, or ?
ok, may depend on the implementation, but normally this should be left to the client/user to sync add delete sort operations |
Quote:
While ordinary progress seems to be possible in non blocking algorithms while some threads are stalled, reusing memory of deleted nodes may require that every other thread make progress. Quote:
Quote:
Quote:
You have defined a set of operations performable on a data structure. You have decided to support multiple threads sharing the data structure. The sequence and timing of the supported operations by the threads ought to be up to those threads. I really suggest you read that paper by Harris. It is neither long nor hard to understand. Quote:
If the client wraps access to an STL container inside some (correctly functioning) sync method, the result is "blocking". |
Thank you all for your valuable inputs.
Quote:
* To check list consistency between the back and forward operations. * To add an entry at the start of a linked list * To add an entry at the end of a linked list * To delete an entry from a linked list * To get the first entry in a linked list * Get the last entry of a linked list * A list Iterator Multiple threads will be sharing this data structure. Quote:
Thanks for sharing the paper by Harris. Sure I would read it once. If anyone has other advise about the things to be taken care of in this implementation, do let me know. |
All times are GMT -5. The time now is 11:51 PM. |