LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   NON Blocking Algorithm in C/C++ (https://www.linuxquestions.org/questions/programming-9/non-blocking-algorithm-in-c-c-906052/)

nikunjbadjatya 10-02-2011 08:11 AM

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

Sergei Steshenko 10-02-2011 10:53 AM

Quote:

Originally Posted by nikunjbadjatya (Post 4488023)
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

In what sense do you use the "blocking algorithm" term ? In the sense of concurrent processes/threads ?

nikunjbadjatya 10-02-2011 10:57 PM

Yes.

Sergei Steshenko 10-03-2011 04:38 AM

Quote:

Originally Posted by nikunjbadjatya (Post 4488577)
Yes.

Then which part of traditional linked list "stuff" is blocking ?

johnsfine 10-03-2011 08:14 AM

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:

Originally Posted by nikunjbadjatya (Post 4488023)
I want to write a sample code with simplest of operations on linked list.

Please provide suitable guidance and references.

I don't have any good answer for that because of your phrase "I want to write". If you had said "I want to find or copy" then I could direct you to that Harris paper.

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:

Originally Posted by nikunjbadjatya (Post 4488023)
As a starting point, I gone through few research papers and wikipedia links about CAS, Non-Blocking Algorithm

Yesterday, I looked at the same wikipedia pages. As far as I recall I got a link to a pdf of the Harris paper (not the research.microsoft.com link I posted Today) directly from the Wikipedia page. So I was thinking of suggesting you should have taken a better look at the references you already found yourself. My browser history also says I looked at two wikipedia pages just before that pdf. But my browser history doesn't have the URL of the pdf and I couldn't find the link to it today that I followed yesterday. I googled a bunch of keywords from the paper plus the name Valois, because I couldn't recall the author's name but did recall he compared his work to an earlier version by Valois. I found the above URL, which I'm pretty sure is the same pdf but different URL than I read Yesterday. (Note to self, next time bookmark interesting links).

SigTerm 10-03-2011 11:36 AM

Quote:

Originally Posted by Sergei Steshenko (Post 4488691)
Then which part of traditional linked list "stuff" is blocking ?

list item insertion/deletion should be atomic (correct me if I'm wrong). Mutliple threads can scan single list, but if you want to insert/delete something, then I believe you'll have to use mutex/critical section, plus you'll need to notify threads that something has changed within list. It can quickly become complicated.

Anyway, OPs question is too vague. The answer to "I want to write" is "write it". I would prefer more specific question.

johnsfine 10-03-2011 12:11 PM

Quote:

Originally Posted by SigTerm (Post 4488915)
if you want to insert/delete something, then I believe you'll have to use mutex/critical section,

If you read the paper I linked, you will see that you don't need a mutex or critical section. I'm not convinced the alternative is better, but that paper clearly demonstrates an alternative.

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:

Anyway, OPs question is too vague. The answer to "I want to write" is "write it".
In this case, I agree. But in most areas of programming there are good answers to "I want to write this, please provide some guidance". Either the nature of this particular problem, or maybe my lack of knowledge about this topic, makes it seem like the only answers are "copy exactly what some expert already did" or "write it yourself with no guidance".

Quote:

Originally Posted by SigTerm (Post 4488915)
list item insertion/deletion should be atomic (correct me if I'm wrong).

One key step in insertion/deletion must be atomic. The trick is reducing that key step to a single CAS operation.

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.

SigTerm 10-03-2011 01:25 PM

Quote:

Originally Posted by johnsfine (Post 4488933)
One key step in insertion/deletion must be atomic. The trick is reducing that key step to a single CAS operation.

There are many other problems. Imagine that one thread traverses list items from first to last, and another thread changes item order (for example, swaps first and last halves (i.e. ABCD becomes CDAB)). In this case you may end up with infinite loop in traversing thread even if operations are atomic.

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.

a4z 10-03-2011 01:41 PM

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

johnsfine 10-03-2011 01:48 PM

Quote:

Originally Posted by SigTerm (Post 4488992)
There are many other problems.

True. A really big one is "when can you reuse the memory of deleted nodes".

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:

Imagine that one thread traverses list items from first to last, and another thread changes item order (for example, swaps first and last halves (i.e. ABCD becomes CDAB)). In this case you may end up with infinite loop in traversing thread even if operations are atomic.
Non blocking does not guarantee that every thread can make progress. Thread A might be making progress in a way that repeatedly causes thread B to restart a single operation. As long as thread A keeps doing that, thread B might spin in place consuming CPU time but making no progress. The overall algorithm is still "non blocking". If thread A could indefinitely delay thread B without thread A making real progress of its own, then the overall algorithm is unsound.

Quote:

Because of this, it is recommended to have a specification. I.e. what kind of operations are supposed to be performed on list
That should apply to the support for any data structure, regardless of whether there are special constraints such as "non blocking". "What operations are supported" is a basic question you must answer before detailed design.

Quote:

are all threads doing same thing or not, etc.
But you usually should be able to do the detailed design and coding without answering questions like that.

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:

Originally Posted by a4z (Post 4489010)
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

Standard stl containers don't support concurrent multi-threaded update. So in the context of this thread, they are neither "blocking" nor "non blocking".

If the client wraps access to an STL container inside some (correctly functioning) sync method, the result is "blocking".

nikunjbadjatya 10-04-2011 12:21 AM

Thank you all for your valuable inputs.

Quote:

Originally Posted by SigTerm (Post 4488992)
There are many other problems. Imagine that one thread traverses list items from first to last, and another thread changes item order (for example, swaps first and last halves (i.e. ABCD becomes CDAB)). In this case you may end up with infinite loop in traversing thread even if operations are atomic.

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.

Following function operations I want to implement. For both singly and doubly linked list. Function
* 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:

Anyway, OPs question is too vague...
* Not all people on earth has English as there first language. Not all people have decades of experience building software. My apologies if my question caused you much trouble. I hope you understand. !

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.