Talk:Non-blocking algorithm

Untitled

Article merged: See old talk page for merged in article talk:Lock-free and wait-free algorithms

Merge request

It has been suggested by someone else that both "Non-blocking algorithm" and "Lock-free and wait-free algorithms" be merged into this document. That said, I agree that non-blocking algorithm could be merged in/redirected (as algorithms to implement non-blocking sychronization is what is discussed, albeit very briefly, by that article). Similarly, as "Lock-free and wait-free algorithms" are also examples of non-blocking synchronization algorithms they could also be incorporated - however since the lock-free and wait-free conditions are developed concepts of their own, they probably should only be linked/referenced by this page.—The preceding unsigned comment was added by 216.16.237.2 (talk • contribs) .

"Non-blocking synchronization" should mean only what it says: that a synchronization primitive does not block. There are many ways to achieve this that do not involve lock-free techniques (another is by using callbacks), and merging the articles would impede fixing the current overemphasis on lock-free techniques in the article. DavidHopwood 21:35, 17 June 2006 (UTC)

Could you give me a reference to such a use of the term associated with such a technique? I wasn't aware of the dual use, and would just like to see it confirmed. It would then seem appropriate to move the current page contents to Non-blocking algorithm and reclaim this page-name for the more general idea. Agreed? --Chris Purcell 23:23, 17 June 2006 (UTC)

Merge request reopened

Requesting a merge with non-blocking synchronization, due to the fact that:

• non-blocking sync is the more general topic
• obstruction-freedom is also a non-blocking property and isn't covered in this article
• wait-free and lock-free are two different concepts, but both are non-blocking, hence it would makes only sense to a) merge with non-blocking or b)generate two articles one on wait-free algos and one for lock-free (and of course one for obstruction-free algos)

Rattusdatorum 15:00, 16 January 2007 (UTC)

In support of the merge, I would add that the Lock-free_and_wait-free_algorithms page is currently a subset of the Non-blocking synchronization page (apart from the links sections, which can be merged). If "non-blocking synchronization" is not the agreed term, the page should be renamed to Non-blocking algorithm, or simply Non-blocking (progress guarantee), but the merge should still be performed. --Chris Purcell 16:29, 16 January 2007 (UTC)

Lock free inter-task communication

I disagree very strongly.

Lock free and wait free algorithms are totally asynchronous - there is no synchronisation at all - they are the very antithesis of any form of synchronisation, blocking or otherwise.

Lock free and wait free algorithms were very heavily used in Sinclair_QDOS (1983) (which I am told was the operating system the Linus Torvalds cut his teeth on - is this true?) and subsequent systems (SMS and variants, Stella). The complete lack of synchronisation mechanisms and their associated problems in QDOS gave rise to the operating system's original name: Domestos, the trade mark for a bleach / toilet cleaner that claimed to destroy 99.9% of all known bugs.

TonyTebby 08:43, 29 March 2007 (UTC)

So is what you're saying that this page should be rewritten completely, to actually discuss non-blocking synchronization? Because I'd approve of that. It could include a non-blocking algorithms section, linking to the full discussion on that page. --Chris Purcell 15:33, 29 March 2007 (UTC)

I can see that I am going to regret ever having stuck my oar in! But here goes. I got here from the "Lock-free and wait-free algorithms page" and not the non-blocking synchronisation page. The problem is that non-blocking synchonisation as defined in the first paragraph seems to indicate, I would think correctly, that non-blocking synchronisation is about ways of implementing semaphore like operations without indefinite waits. I.e. pre-1965 resource locking. While this may be wait-free in the sense that the thread is not blocked it is not wait-free in the sense described on the "Lock-free and wait-free algorithms" page ""Wait-free" refers to the fact that a thread can complete any operation in a finite number of steps, regardless of the actions of other threads". With non-blocking semaphores, although there is no wait, the operation may not be completed. Furthermore synchronisation of two threads implies that one or other the threads may have to be delayed to synchronise with the other. This means that synchronisation cannot be wait-free by definition.

The rest of the "Non-blocking synchronization" page does not, however, seem to have much to do with non-blocking semaphores or synchronisation at all. The problem is possibly just the title - if the title were changed to "Non-blocking resource sharing" would the problem go away? Merging the two pages would still be a heavy job! TonyTebby 16:31, 30 March 2007 (UTC)

This is where I get confused: "non-blocking synchronization" has, in my academic experience, always been a synonym for a non-blocking algorithm. This makes sense in a way: callbacks, for instance, are only non-blocking if implemented with a non-blocking queue or suchlike. If some research were cited using "non-blocking synchronization" in a more general sense, that would make it clearer to me this isn't people getting the wrong end of the misnamed stick. If not, the page should be removed in favour of the better-defined "non-blocking algorithms". --Chris Purcell 05:28, 5 April 2007 (UTC)

Bumping topic

this merge discussion has fallen of the radar without being resolved so i am replacing the date in

{{Mergefrom|Lock-free and wait-free algorithms|date=January 2007}}
{{Mergeto|Non-blocking_synchronization|date=January 2007}}

to May 2008

"No lock-free implementation"

Someone quoth: "Unfortunately, even with special atomic primitives, some common data structures -- such as doubly-linked lists -- have no known lock-free implementation."

Herb Sutter is phrasing things badly. All algorithms have a lock-free implementation, proven decades ago using universal constructions. More recently, software transactional memory has provided reasonably efficient implementations, too. What he must presumably mean is "no direct implementation exists". —Chris Purcell , 13:08, 21 December 2008 (UTC)

Obstruction freedom and occ

From the article: "Obstruction-freedom is also called optimistic concurrency control."

Is this correct, it seems those things are different from the rest of the text

Dekker's algorithm is lock free?

The article says that Dekker's algorithm is lock-free. I think this statement is very vague, and, depending on the meaning, incorrect. Dekker's algorithm is a method for implementing critical sections. A program that uses it is, by definition, not lock-free (the program uses critical sections => a thread that crashes in the critical section will bring the whole system to a halt). If you agree, I would remove the mention of Dekker's algorithm. --Gigiultraplus (talk) 21:58, 11 April 2010 (UTC)

I agree that Dekker's algorithm is not lock free, and it is not wait free. If one of the threads crashes while executing the critical section, all other threads will deadlock. There is also further inconsistencies between the Non-blocking synchronization page (It says that Dekker is lock free only) and the Dekker's algorithm page (it says it is lock and wait free). Dorozcog (talk) 21:04, 3 August 2010 (UTC)

I agree. I've removed the link. However, I can't see any errors on the algorithm page, which says deadlock-free and starvation-free (necessary but not sufficient for lock-free and wait-free respectively). --Chris Purcell (talk) 14:55, 4 August 2010 (UTC)

FastFlow

Is FastFlow a programming paradigm or an operation that can be implemented in lock-free fashion? —Preceding unsigned comment added by 75.85.180.100 (talk) 08:36, 1 August 2010 (UTC)

Requested move

The following is a closed discussion of the proposal. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the proposal was Move Parsecboy (talk) 14:45, 25 August 2010 (UTC)

Non-blocking synchronization → Non-blocking algorithm — As discussed above, this page appears to be incorrectly named: changing "synchronization" to "algorithm" would disambiguate, and allow the more general term to be reclaimed. --Chris Purcell (talk) 15:05, 4 August 2010 (UTC)

• Comment. Could you provide a discussion where there is clear consensus to the name change?. MikeLynch (talk) 14:03, 25 August 2010 (UTC)
  • Why does it matter since nobody's objected to the move proposal in the three weeks since it was posted? Propaniac (talk) 14:18, 25 August 2010 (UTC)

The above discussion is preserved as an archive of the proposal. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

Lock-free algorithms avoid priority inversion?

I don't see how the claim, "Lock-free algorithms...avoid priority inversion", is supported by citations. It's certainly not true in general, as the system-wide progress guarantee can still be satisfied if the only thread making progress is the lowest-priority one. Is there work showing all lock-free algorithms can be modified to be priority-aware and prevent priority inversion?

(I intend to, at some future point, remove all reference to priority inversion if nobody clarifies this, by the way.)

--Chris Purcell (talk) 16:06, 13 January 2012 (UTC)

I removed the text. --Chris Purcell (talk) 13:09, 18 April 2012 (UTC)

What does 'weak' mean here

What does 'weak' mean here" "some data structures are weak enough to be implemented". It's use needs to be defined for the non-expert. -- Dougher (talk) 01:05, 5 May 2012 (UTC)

external links

1) Article "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" by Maged M. Michael and Michael L. Scott

3) Survey "Some Notes on Lock-Free and Wait-Free Algorithms" by Ross Bencina

4) java.util.concurrent.atomic – supports lock-free and thread-safe programming on single variables

5) System.Threading.Interlocked - Provides atomic operations for variables that are shared by multiple threads (.NET Framework)

6) The Jail-Ust Container Library

7) Practical lock-free data structures

8) Thesis "Efficient and Practical Non-Blocking Data Structures" (1414 KB) by Per Håkan Sundell

9) WARPing - Wait-free techniques for Real-time Processing

10) Non-blocking Synchronization: Algorithms and Performance Evaluation. (1926 KB) by Yi Zhang

11) "Design and verification of lock-free parallel algorithms" by Hui Gao

12) "Asynchronous Data Sharing in Multiprocessor Real-Time Systems Using Process Consensus" by Jing Chen and Alan Burns

13) Atomic Ptr Plus Project - collection of various lock-free synchronization primitives

14) AppCore: A Portable High-Performance Thread Synchronization Library - An Effective Marriage between Lock-Free and Lock-Based Algorithms

15) WaitFreeSynchronization and LockFreeSynchronization at the Portland Pattern Repository

16) Multiplatform library with atomic operations

17) A simple C++ lock-free LIFO implementation

18) libcds - C++ library of lock-free containers and safe memory reclamation schema

19) Concurrency Kit - A C library for non-blocking system design and implementation

moved from the article page. it has been tagged as a link farm for over 6 months. per WP:EL each link needs to be individually justified as appropriate. (I have removed some that clearly fail WP:ELNO.)

Which of the above meet the external link criteria and should be returned, and why? -- TRPoD aka The Red Pen of Doom 20:21, 28 October 2012 (UTC)

I vote none of them. Also, many of the internal "See also" links appear extraneous to me. --Chris Purcell (talk) 10:30, 5 November 2012 (UTC)

Realy non-blocking?

"With few exceptions, non-blocking algorithms use atomic read-modify-write primitives that the hardware must provide"

How do atomic operations not block all other cores from the same resource?

Dear reader,

Non-blocking algorithms are "non-blocking" in the same way a normal "read" instruction is considered "non-blocking".

In a multiprocessor system, often two CPUs simultaneously try to read data from different locations in the same RAM chip.

Since a typical RAM chip only has one set of address pins, it can only retrieve data from one location at a time.

In order for the system to work as expected, a properly constructed memory arbiter must somehow choose one of the CPUs to drive the address pins of that RAM chip, and somehow delay the other CPU and keep its desired address disconnected from the address pins of the RAM until the next memory cycle.

The read instruction running on the delayed CPU always appears to the software to have completed successfully.

Atomic instructions work the same way, except that a properly designed arbiter sometimes needs to delay the other CPUs several memory cycles in order for multi-memory-cycle atomic instructions to complete and actually appear atomic to those other CPUs -- but those delayed CPUs will resume and finish whatever instruction they are working on within "several memory cycles".

(By "properly designed", I'm excluding bugs like the Cyrix coma bug).

In this context, delaying a CPU such that it takes a little longer to execute an instruction, but that instruction always completes successfully within "several memory cycles", is not considered a "block".

In this context, a "block" is when some other CPU does something that could keep this CPU from doing anything useful for an unlimited amount of time, perhaps more than a hundred memory cycles.

How can we clarify this article to make this easier to understand? Does it need a distinction between "short delay" and "indefinite block"? --DavidCary (talk) 18:42, 11 March 2014 (UTC)

opinions about non-blocking algorithms

Someone once wrote, in a magazine that appears to be a reliable source, several articles criticizing lock-free code for giving "a false sense of security".

My understanding of Wikipedia's WP:YESPOV policy is that each Wikipedia article should mention all of the significant views that have been published by reliable sources on a topic, even the ones I don't agree with.

In an attempt to follow policy, I added a single sentence with a very brief and watered-down mention of that criticism, using articles in that magazine as a reference. (I used WP:BUNDLING to cram several articles into a single reference -- not sure if that was appropriate or not).

When that sentence (and the reference) was deleted, I more-or-less reverted, and the sentence (and the reference) was deleted again.[1][2]

Rather than deleting statements about the topic that people sincerely believe but are non-neutral (or even wrong), I feel it improves a Wikipedia article on that topic to mention those statements, and then give reliable sources that show that those statements are not facts but merely opinions -- or perhaps even sources that show that experts now consider those statements to be wrong.

This is the "discussion" part of the WP:BRD process. --DavidCary (talk) 20:04, 11 March 2014 (UTC)