Talk:Non-blocking algorithm

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

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)