Talk:Spinlock

errors

There are many errors in this page:

• The example code:
  • the global variable needs a "volatile"
  • there is no lock! This code demonstrates polling, not a spinlock.
  • The drawn conclusions are wrong.
  • The code does not work (or only by pure chance). You cannot do spinlocks in C (or any other higher language)! The update must be atomic, special assembler instructions must be used for this. (otherwise, you get a race condition)
  • If you are using pthreads anyway, use pthreads_spinlock, since they have the same effect but are implemented in a useful way (see below; no, they are not really spinlocks).
• Spinlocks are not useful in User-space.
• In Kernels, they do have an application for SMP-System (on single CPU systems they are never useful). However, the art of kernel design is to avoid spinlock as far as possible (by using per-cpu data, for example).
• the alternatives for spinlocks are.... strange. Yielding (instead of busy waiting) per cpu/thread data, more complex synchronization mechanisms are better examples.
• the problem of atomic updating of the lock is not touched at all.
• even though many synchronization libraries offer something called spin lock, this is implemented in a different way. One example is the pthread library.
• spinlock are only used if the updating of the data is a bit more complex. A simple increment, decrement, setting, etc. of a single word is done with atomic updates (if available on the particular architecture).
• the reason to wait for the release of a spinlock is not (or to be more realistic: should never) be to avoid rescheduling, since that would take a long time. Rather, only use spinlock if you are sure that other holders will hold it for a (short) maximum time (rather in terms of nanoseconds than in number of instructions) AND you cannot do rescheduling (in a "normal" way). You also better make sure, that the holder gets not preempted, etc.
• The dangers of spinlocks are not stated (and how to avoid it):
  • memory bus usage
  • cache trashing
  • pipeline bubbles

(plus some more...) Don't have time right now, will correct it soon, however... --Uvatter 14:02, 17 Dec 2004 (UTC)

Need for disambiguation

Should create a disambiguation page to a stub for nuclear magnetic resonance spinlock pulse sequence. —Preceding unsigned comment added by 140.254.233.9 (talk) 15:18, 29 April 2009 (UTC)

Busy waiting page redirects here.

A lot of people, textbooks, and several of the papers cited at the bottom of this article use spinlocks and busy waiting interchangeably. Somebody else set up a redirect for the Busy Waiting page to route here, so that might be where the confusion comes from.

However, it sounds like you're not down with that, and I hate arguing about semantics. I'll undo the redirect for the busy waiting page, and copy my code there. I suggest you use this page to talk about the particular OS kernel spinlocks you interested in. Does that work for you?

--Waxmop 22:29, 29 Dec 2004 (UTC)

Spinlocks are an application of busy waiting, but a very specific one. I've written up new details in line with some of the suggestions above, although I haven't gone into quite that much depth.

Can somebody check my example code? Not quite sure I've got that right. JulesH 23:44, 9 July 2005 (UTC)

--

Spinlocks apply to OPERATING SYSTEMS-- not software engineering!

Merge with busy waiting

I say no. While spin locks are a form of busy waiting, there are also lots of other ways you can busy wait and spin locks are an important enough concept on their own to merit their own page. --NJM 03:42, 8 November 2005 (UTC)

I agree (unsigned comment by 72.136.48.238, 17 December 2005 -- attribution corrected JulesH 17:31, 20 December 2005 (UTC))

Absolutely should not be merged. I came to look for an article on spinlocks, not busy waiting. The concepts are related, but they merit two separate articles.

This has been up here for months now, and nobody has come up with a reason to perform the merge. I suggest removing the template suggesting it. JulesH 14:42, 18 January 2006 (UTC)

I've gone ahead and removed it. JulesH 13:25, 12 February 2006 (UTC)

Should the "significant optimizations" section be here?

The example is here just to give an idea of what a spinlock does and happens to be in x86 asm because that's relatively common. However, the opimizations section goes into great detail with x86 minutiae that isn't really relevant to the article and probably just confuses the issue. I think it should be removed and replaced with a note that the example was written to be easy to understand and isn't the most optimal solution. --NJM 06:44, 28 May 2006 (UTC)

I'm not sure. While some of the details are probably irrelevant, some of them are useful to know about. It may not be an ideal situation, but most of the world's general-purpose computers are based on the x86 architecture, so optimising things for it is important. And the information about cache protocols preventing bus traffic is unexpected; I think most people would expect a spinlock to generate a lot of bus traffic and therefore be inefficient because of that, so this is quite important and not x86-specific. All the information presented may be useful to spinlock implementors, so it should perhaps stay. JulesH 07:57, 26 June 2006 (UTC)

"Memory ordering" vs "Memory operation ordering"

I've reverted a change from "memory ordering" to "memory operation ordering".

My reason for doing this is that while "memory operation ordering" is a clearer phrase that is likely to be more meaningful to someone not familiar with it, "memory ordering" is the phrase used by most people when discussing it (see, e.g., Intel's description of memory ordering on the Itanium [1]). JulesH 13:52, 17 July 2006 (UTC)

Dijkstra Spinlocks

Currently the article says

Generally this is only possible with special assembly language instructions, such as atomic test-and-set operations, and cannot be implemented from high level languages like C.

I'm not sure what the author means by "generally", since it's definitely possible using the spinlock mechanisms described by Dikstra and Peterson in the 1960s. The main reason their mechanism is not used is that it's O(n) in time and space on the number of threads. I've used Dijkstra spinlocks in real commercial projects (written in C) where the hardware didn't have "compare and exchange" or "test and set" instructions. In fact, see Peterson's algorithm. RPTB1 13:08, 4 October 2006 (UTC)

I'll admit, I've never heard this class of algorithm called by the name "spinlock", so never considered it necessary to mention them on this page, which is about an entirely different approach to mutual exclusion. Also, it isn't *generally* possible to use such an algorithm from C, as is noted in the article you linked to:

Implementation of Peterson's and related algorithms on an out-of-order processor generally require use of [memory barrier] operations to work correctly to keep sequential operations from happening in an incorrect order.

C does not provide any means of guaranteeing a memory barrier (although I'll grant that there are a variety of add-on libraries for it in most platforms that do, these are typically implemented in assembly language).

A few other high level languages do include explicit memory barrier support (Java springs to mind; there is a memory barrier on entry and exit from a synchronized() block, IIRC) but these tend to be combined with higher level synchronization measures that make this kind of approach pointless, except perhaps for educational purposes.

It is worth noting that this class of algorithm can be used on architectures that lack atomic operations, though. JulesH 13:28, 5 October 2006 (UTC)

Source required

I've added this sentence:

But note that such an implementation may require more memory than a spinlock, be slower to allow progress after unlocking, and may not be implementable in a high-level language if out-of-order execution is in use.

While I'm confident that it's true, I could do with a source that confirms it. My primary reference for such things describes the algorithm, but fails to mention its lack of efficiency or any possible out-of-order problems. The closest it comes is describing the use of an atomic operation as "simpler". Any suggestions? JulesH 13:45, 5 October 2006 (UTC)

New section needed on "the dangers of spinlocks" as Uvatter mentioned above

• Deadlock/Livelock. In a real-time OS that obeys thread priorities, spinlocks can lead to deadlocks if used by threads with different priorities. The workaround is to never access spin-locks from threads of different priorities. Example: low-prio thread locks spin lock. High prio thread then tries to lock the spin lock. Deadlock, because the high-prio thread is spinning on the lock, and never allows the low-prio thread to unlock.

• • I guess this is part of the motivation for so-called "hybrid" spinlocks as used by solaris: if you don't spin unless you know the process that owns the lock is scheduled to another processor, this situation can never arise. It's an interesting point, and I can certainly see it would be useful to discuss it. Do you know of any books and/or papers that discuss the issue, that we can use as a reference? JulesH 21:25, 12 June 2007 (UTC)

While that is one workaround, there are several other ways to avoid that kind of deadlock -- any of the solutions to priority inversion would also work. --DavidCary (talk) 17:46, 21 March 2022 (UTC)

Getting read of atomic operation in unlock is not necessarily a "significant optimization"

The article says

On later implementations of the x86 architecture, spin_unlock can safely use an unlocked MOV instead of the locked XCHG, which is much faster.

While it's much faster for the cpu that does the unlock, it can be actually slower overall, because the write to the spinlock to unlock it will tend to stay in the CPU's store buffer instead of going directly to memory/cache, meaning that other CPUs will see the update later, and will spin for a longer period of time.

For this reason, I don't think this qualifies as a "significant optimization". —The preceding unsigned comment was added by 67.188.127.3 (talk) 09:01, 22 December 2006 (UTC).

I believe MESI or other cache coherency systems would take care of this issue in most architectures. Unless somebody knows otherwise? JulesH 21:29, 12 June 2007 (UTC)

In fact, reading the description of MESI linked above, it definitely prevents the issue. When it modifies the item, it is stored into the CPU's cache and other processors' copies are invalidated. When they next read the item, they read it directly out of the modifying processor's cache, not out of main memory. JulesH 21:33, 12 June 2007 (UTC)

What about this code: db F0H ;LOCK prefix, used when you want to modify shared memory between processors mov [lock], 0 Uses only one instruction and should have the same effect —Preceding unsigned comment added by 190.19.6.198 (talk) 17:03, 10 February 2009 (UTC)

Sadly, "lock mov" is an illegal instruction. The lock prefix only applies to a dozen or so instructions: see the list. "lock sub [locked],1" would work, but would be less clear.Olawlor (talk) 05:04, 3 October 2012 (UTC)

adding PAUSE informations..

it could be good adding some informations about PAUSE instruction and its effects on p4 , xeon and other intel processors...or only a little notify that link on a PAUSE_(x86) like wiki page , with the complete description of this instruction. —Preceding unsigned comment added by 151.16.98.203 (talk) 19:29, 11 August 2009 (UTC)

logical error in first sentence

I read : "... a spinlock is a lock where the thread simply waits ... until the lock becomes available. " So, the first term lock must mean something different than the second one, if not it would mean A waits until A is true. If A waits, it will never change and thus never become true. From my bit of understanding, what is called lock in the second place might be a token, a semaphore or just a certain state, while in the first place it is the code or algorithm performing the active waiting. While many terms in IT are overloaden, we should pay some attention to point to their particular meaning, especially if used close by. Thus, IMHO it should read: "... a spinlock is an algorithm implemented in a single thread which simply waits ... until a certain lock becomes available. "

As the same wording is used in the lock article, same applies for that one.

--Ufalke (talk) 16:32, 5 October 2011 (UTC)

I think what the first sentence is trying to say is that the lock causes the thread to wait for the lock. So A (the thread) waits until B (the lock) is true. But I'll try make it more clear. Jfmantis (talk) 03:12, 14 December 2012 (UTC)

sleeplock vs raw lock

After a quick googling, it doesn't seem that "sleeplock" has much traction. So I remove it while introducing the notion of "raw lock". ale (talk) 11:09, 15 May 2013 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Spinlock. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20041211235628/http://www.codeproject.com/threads/spinlocks.asp to http://codeproject.com/threads/spinlocks.asp

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 12:35, 9 December 2017 (UTC)