Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I would like to know about spinlocks in detail?
Could someone explain that to me?

share|improve this question
add comment

4 Answers

up vote 17 down vote accepted

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.

share|improve this answer
    
@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" –  Sen Dec 22 '10 at 17:40
2  
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 Dec 22 '10 at 18:01
2  
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. –  Warren Young Dec 22 '10 at 18:07
    
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 Dec 22 '10 at 20:55
    
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. –  Warren Young Dec 23 '10 at 1:53
show 2 more comments

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
share|improve this answer
    
What is the role of the scheduler there? Or does it have any role? –  Sen Dec 22 '10 at 14:16
    
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. –  Shawn J. Goff Dec 22 '10 at 14:32
    
So how is this scenario handled in a single core processor system? –  Sen Dec 22 '10 at 17:35
    
@Sen: This is explained rather well in Linux Device Drivers. –  Gilles Dec 22 '10 at 20:57
add comment

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.

share|improve this answer
add comment

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 wakle it up when some event happens.

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

Now let us for the moment assume that on the 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 forth 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 in the example you make a for loop run eg 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 then the time it takes to "try and block". It is efficient when the typical time to hold a lock is much smaller then the time to 'try and block".

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

share|improve this answer
    
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. –  Sen Dec 23 '10 at 14:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.