ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
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.
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 ?
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
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
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).
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.
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
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.
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.
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
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
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".
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.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.