Talk:Non-blocking synchronization

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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)

[edit] 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)