LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 10-02-2011, 08:11 AM   #1
nikunjbadjatya
Member
 
Registered: Sep 2009
Location: Bangalore
Posts: 33

Rep: Reputation: 0
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
 
Old 10-02-2011, 10:53 AM   #2
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by nikunjbadjatya View Post
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 ?
 
Old 10-02-2011, 10:57 PM   #3
nikunjbadjatya
Member
 
Registered: Sep 2009
Location: Bangalore
Posts: 33

Original Poster
Rep: Reputation: 0
Yes.
 
Old 10-03-2011, 04:38 AM   #4
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by nikunjbadjatya View Post
Yes.
Then which part of traditional linked list "stuff" is blocking ?
 
Old 10-03-2011, 08:14 AM   #5
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197
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 View Post
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 View Post
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).

Last edited by johnsfine; 10-03-2011 at 08:36 AM.
 
Old 10-03-2011, 11:36 AM   #6
SigTerm
Member
 
Registered: Dec 2009
Distribution: Slackware 12.2
Posts: 379

Rep: Reputation: 234Reputation: 234Reputation: 234
Quote:
Originally Posted by Sergei Steshenko View Post
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.
 
1 members found this post helpful.
Old 10-03-2011, 12:11 PM   #7
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197
Quote:
Originally Posted by SigTerm View Post
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 View Post
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.

Last edited by johnsfine; 10-03-2011 at 12:33 PM.
 
Old 10-03-2011, 01:25 PM   #8
SigTerm
Member
 
Registered: Dec 2009
Distribution: Slackware 12.2
Posts: 379

Rep: Reputation: 234Reputation: 234Reputation: 234
Quote:
Originally Posted by johnsfine View Post
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.

Last edited by SigTerm; 10-03-2011 at 01:30 PM.
 
Old 10-03-2011, 01:41 PM   #9
a4z
Senior Member
 
Registered: Feb 2009
Posts: 1,727

Rep: Reputation: 742Reputation: 742Reputation: 742Reputation: 742Reputation: 742Reputation: 742Reputation: 742
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
 
Old 10-03-2011, 01:48 PM   #10
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197Reputation: 1197
Quote:
Originally Posted by SigTerm View Post
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 View Post
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".

Last edited by johnsfine; 10-03-2011 at 02:00 PM.
 
Old 10-04-2011, 12:21 AM   #11
nikunjbadjatya
Member
 
Registered: Sep 2009
Location: Bangalore
Posts: 33

Original Poster
Rep: Reputation: 0
Thank you all for your valuable inputs.

Quote:
Originally Posted by SigTerm View Post
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] blocking and non blocking TCP send/recv problem golden_boy615 Programming 5 12-27-2010 03:27 PM
[SOLVED] C - For system calls, is blocking or non-blocking default? golmschenk Programming 4 03-23-2010 10:29 PM
[SOLVED] C - What's the difference between a blocking and a non-blocking call? golmschenk Programming 5 03-06-2010 06:45 PM
token bucket algorithm vs Leaky bucket algorithm xeon123 Linux - Networking 2 03-26-2007 04:57 AM
hash algorithm scanner Programming 17 07-18-2006 08:08 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 04:10 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration