What is a spinlock in Linux?

Question

I would like to know about Linux spinlocks in detail; could someone explain them to me?

Solution 1

A spin lock is a way to protect a shared resource from being modified by two or more processes simultaneously. The first process that tries to modify the resource "acquires" the lock and continues on its way, doing what it needed to with the resource. Any other processes that subsequently try to acquire the lock get stopped; they are said to "spin in place" waiting on the lock to be released by the first process, thus the name spin lock.

The Linux kernel uses spin locks for many things, such as when sending data to a particular peripheral. Most hardware peripherals aren't designed to handle multiple simultaneous state updates. If two different modifications have to happen, one has to strictly follow the other, they can't overlap. A spin lock provides the necessary protection, ensuring that the modifications happen one at a time.

Spin locks are a problem because spinning blocks that thread's CPU core from doing any other work. While the Linux kernel does provide multitasking services to user space programs running under it, that general-purpose multitasking facility doesn't extend to kernel code.

This situation is changing, and has been for most of Linux's existence. Up through Linux 2.0, the kernel was almost purely a single-tasking program: whenever the CPU was running kernel code, only one CPU core was used, because there was a single spin lock protecting all shared resources, called the Big Kernel Lock (BKL). Beginning with Linux 2.2, the BKL is slowly being broken up into many independent locks that each protect a more focused class of resource. Today, with kernel 2.6, the BKL still exists, but it's only used by really old code that can't be readily moved to some more granular lock. It is now quite possible for a multicore box to have every CPU running useful kernel code.

There's a limit to the utility of breaking up the BKL because the Linux kernel lacks general multitasking. If a CPU core gets blocked spinning on a kernel spin lock, it can't be retasked, to go do something else until the lock is released. It just sits and spins until the lock is released.

Spin locks can effectively turn a monster 16-core box into a single-core box, if the workload is such that every core is always waiting for a single spin lock. This is the main limit to the scalability of the Linux kernel: doubling CPU cores from 2 to 4 probably will nearly double the speed of a Linux box, but doubling it from 16 to 32 probably won't, with most workloads.

Solution 2

A spin lock is when a process continually polls for a lock to be removed. It is considered bad because the process is consuming cycles (usually) needlessly. It is not Linux-specific, but a general programming pattern. And while it is generally considered a bad practice, it is, in fact, the correct solution; there are cases where the cost of using the scheduler is higher (in terms of CPU cycles) than the cost of the few cycles that the spinlock is expected to last.

Example of a spinlock:

#!/bin/sh
#wait for some program to clear a lock before doing stuff
while [ -f /var/run/example.lock ]; do
  sleep 1
done
#do stuff

There is frequently a way to avoid a spin lock. For this particular example, there is a Linux tool called inotifywait (it's not usually installed by default). If it was written in C, you would simply use the inotify API that Linux provides.

The same example, using inotifywait shows how to accomplish the same thing without a spin lock:

#/bin/sh
inotifywait -e delete_self /var/run/example.lock
#do stuff

Solution 3

When a thread tries to acquire a lock, three things can happen if it fails - it can try and block, it can try and continue, it can try then go to sleep telling the OS to wake it up when some event happens.

Now a try and continue uses a lot less time than a try and block. Let's say for the moment that a "try and continue" will take a unit of time and a "try and block" will take a hundred.

Now let us for the moment assume that on average a thread will take 4 units of time holding the lock. It's wasteful to wait 100 units. So instead, you write a loop of "try and continues". On the fourth attempt, you will usually acquire the lock. This is a spin lock. It's called that because the thread keeps spinning in place till it gets the lock.

An added safety measure is to limit the number of times the loop runs. So for example, you make a for-loop run, say, six times, if it fails then you "try and block".

If you know that a thread will always hold the lock for, say, 200 units, then you are wasting the computer time for each try and continue.

So in the end, a spin lock can be very efficient or wasteful. It is wasteful when the "typical" time to hold a lock is higher than the time it takes to "try and block". It is efficient when the typical time to hold a lock is much lower than the time to 'try and block".

Ps: The book to read on threads is "A Thread Primer", if you can still find it.

Solution 4

A lock is a way for two or more tasks (processes, threads) to synchronize. Specifically, when both tasks need intermittent access to a resource that can only be used by one task at a time, it's a way for the tasks to arrange not to be using the resource at the same time. In order to access the resource, a task must perform the following steps:

take the lock
use the resource
release the lock

Taking a lock is not possible if another task has already taken it. (Think of the lock as a physical token object. Either the object is in a drawer, or someone has it in their hand. Only the person holding the object may access the resource.) So “take the lock” really means “wait until no one else has the lock, then take it”.

From a high-level point of view, there are two major ways to implement locks: spinlocks, and conditions. With spinlocks, taking the lock means just “spinning” (i.e. doing nothing in a loop) until noone else has the lock. With conditions, if a task attempts to take the lock but is blocked because another task holds it, the newcomer enters a wait queue; the release operation signals to any waiting task that the lock is now available.

(These explanations are not enough to let you implement a lock, because I haven't said anything about atomicity. But atomicity is not important here.)

Spinlocks are obviously wasteful: the waiting task keeps checking whether the lock is taken. So why and when is it used? Spinlocks are often very cheap to obtain in the case where the lock isn't held. This makes it attractive when the chance for the lock to be held is small. Furthermore, spinlocks are only viable if obtaining the lock is not expected to take long. So spinlocks tend to be used in situations where they will remain held for a very short time, so that most attempts are expected to succeed on the first try, and those that need a wait don't wait long.

There is a good explanation of spinlocks and other concurrency mechanisms of the Linux kernel in Linux Device Drivers, chapter 5.

Solution 5

A spinlock is a lock that operates by disabling scheduler and possibly interrupts (irqsave variant) on that particular core that the lock is acquired on. It is different from a mutex in that it disables scheduling so only your thread can run while spinlock is held. A mutex allows other higher priority threads to be scheduled in while it is held but does not allow them to simultaneously execute the protected section. Because spinlocks disable multitasking you can not take a spinlock and then call some other code that will try to acquire a mutex. Your code inside the spinlock section must never sleep (code typically sleeps when it encounters a locked mutex or empty semaphore).

Another difference with a mutex is that threads typically queue for a mutex so a mutex underneath has a queue. Whereas spinlock just ensures that no other thread will run even if it has to. Therefore, you must never hold a spinlock when calling functions outside your file that you are not sure will not sleep.

When you want to share your spinlock with an interrupt you must use irqsave variant. This will not just disable scheduler but will also disable interrupts. It makes sense right? Spinlock works by making sure nothing else will run. If you don't want an interrupt to run you disable it and proceed safely into the critical section.

On multicore machine a spinlock will actually spin waiting for another core that holds the lock to release it. This spinning only happens on multicore machines because on single core ones it can not happen (you either hold spinlock and proceed or you never run until the lock is released).

Spinlock is not wasteful where it makes sense. For very small critical sections it would be wasteful to allocate a mutex task queue compared to simply suspending the scheduler for a few microseconds that it takes to finish the important work. If you need to sleep or hold the lock across an io operation (which may sleep) then use a mutex. Certainly never lock a spinlock and then try to release it inside an interrupt. While this will work, it will be like the arduino crap of while(flagnotset); in such case use a semaphore.

Grab a spinlock when you need simple mutual exclusion for blocks of memory transactions. Grab a mutex when you want multiple threads to stop right before a mutex lock and then the highest priority thread to be chosen to continue when mutex becomes free and when you lock and release in the same thread. Grab a semaphore when you intend to post it in one thread or an interrupt and take it in another thread. It's three slightly different ways to ensure mutual exclusion and they are used for slightly different purposes.

View more solutions

Comments

[Navaneeth Sen]

What is the role of the scheduler there? Or does it have any role?

[Shawn J. Goff]

In the spin lock method, the scheduler resumes the process every ~1 second to do its task (which is simply check the existence of a file). In the inotifywait example, the scheduler only resumes the process when the child process (inotifywait) exits. Inotifywait is also sleeping; the scheduler only resumes it when the inotify event happens.

[Navaneeth Sen]

So how is this scenario handled in a single core processor system?

[Navaneeth Sen]

@Warren : A couple of doubts- I would like to know more about this Big Kernel Lock and its implications. I also dint understand the last paragraph "doubling CPU cores from 2 to 4 probably will nearly double the speed of a Linux box, but doubling it from 16 to 32 probably won't"

[Warren Young]

Re: implications of BKL: I thought I made that clear above. With only one lock in the kernel, any time two cores try to do something protected by the BKL, one core is blocked while the first finishes using its protected resource. The more fine-grained the locking, the lower the chance that this will happen, so the greater the processor utilization.

[Warren Young]

Re: doubling: I mean that there's a law of diminishing returns when adding processor cores to a computer. As the number of cores increases, so does the chance that two or more of them will need to access a resource protected by a particular lock. Increasing lock granularity reduces the chances of such collisions, but there's overhead in adding too many, too. You can easily see this in supercomputers, which often have thousands of processors these days: most workloads are inefficient on them because they can't avoid idling many processors due to shared resource contention.

[Gilles 'SO- stop being evil']

While this is an interesting explanation (+1 for that), I don't think it's effective in conveying the difference between spinlocks and other kinds of locks.

[Gilles 'SO- stop being evil']

@Sen: This is explained rather well in Linux Device Drivers.

[Warren Young]

If one wants to know the difference between a spin lock and, say, a semaphore, that's a different question. Another good but tangential question is, what is it about the Linux kernel design that makes spin locks good choices instead of something more common in userland code, like a mutex. This answer divagates plenty as is.

[Navaneeth Sen]

I would like to know more about what is it about the Linux kernel design that makes spin locks good choices instead of something more common in userland code. Shall i post it as another query?

[Warren Young]

Yes. One question per question. :)

[Navaneeth Sen]

thread keeps spinning in place till it gets the lock. Could you please tell me what is this spinning? Is it like it comes to the wait_queue and is put to execution by the Scheduler? Maybe i am trying to get into the low level, but still cant hold my doubt.

[Martin]

That bash script is a bad example of a spinlock. You are pausing the process making it go to sleep. A spinlock never sleeps. On a single core machine it just suspends the scheduler and continues (without busy wait)

[Paul Stelian]

Spinning among the 3-4 instructions in the loop, basically.

[Paul Stelian]

What would be a good way to implement other synchronization primitives? Take a spinlock, check if someone else has the actual primitive being implemented, then either use the scheduler or grant access? Could we consider the synchronized() block in Java a form of spinlock, and in properly implemented primitives just use a spinlock?

[Gilles 'SO- stop being evil']

@PaulStelian It is indeed common to implement “slow” locks this way. I don't know enough Java to answer that part, but I doubt that synchronized would be implemented by a spinlock: a synchronized block could run for a very long time. synchronized is a language construct to make locks easy to use in certain cases, not a primitive to build larger synchronization primitives.