I would like to know about Linux spinlocks in detail; could someone explain them to me?
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
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.
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
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.
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.
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.