Why are spin locks good choices in Linux Kernel Design instead of something more common in userland code, such as semaphore or mutex?

Question

I understand that Spinlocks are real waste in Linux Kernel Design.

I would like to know why is it like spin locks are good choices in Linux Kernel Design instead of something more common in userland code, such as semaphore or mutex?

Solution 1

The choice between a spinlock and another construct which causes the caller to block and relinquish control of a cpu is to a large extent governed by the time it takes to perform a context switch (save registers/state in the locking thread and restore registers/state in another thread). The time it takes and also the cache cost of doing this can be significant.

If a spinlock is being used to protect access to hardware registers or similar where any other thread that is accessing is only going to take a matter of milliseconds or less before it releases the lock then it is a much better use of cpu time to spin waiting rather than to context switch and carry on.

Solution 2

As the question implies in saying that spinlocks are a "waste", spinlocks should be held only briefly.

Spinlocks are not the only way to synchronize multiple threads. Mutexes/semaphores are also used in the Linux kernel, as are other synchronization primitives (e.g. waitqueues, events).

However the kernel has to deal with cases that userspace never sees, a common one being interrupt handlers. Interrupt handlers can not be rescheduled on Linux, but often do have to use some synchronization primitive (e.g. to add a work item to a linked list that some other thread will process further). Since interrupt handlers are not able to sleep, they can't use mutexes, waitqueues, etc. That pretty much leaves spinlocks. If a thread needs to synchronize access with an interrupt handler, then it must also use the same spinlock.

Spinlocks are not necessarily a waste. They are optimized for the non-contention/non-waiting case and can be taken and released very quickly. In that case they are faster and involve less overhead than other synchronization primitives.

Solution 3

Others have answered. I shall summarize the cases where you would use spinlock and rules to use spinlock.

1. When spinlock is used ?

Ans: In the following situations.

1. The thread that holds the lock is not allowed to sleep.
2. The thread that is waiting for a lock does not sleep, but spins in a tight loop.

When properly used, spinlock can give higher performance than semaphore. Ex: Intrrrupt handler.

2. What are the rules to use spinlocks?

Ans:

Rule - 1: Any code that holds the spinlock, can not relinquish the processor for any reason except to service interrupts ( sometimes not even then). So code holding spinlock can not sleep.

Reason: suppose your driver holding spinlock goes to sleep. Ex: calls function copy_from_user() or copy_to_user(), or kernel preemption kicks in so higher priority process pushed your code aside. Effectively the process relinquishes the CPU holding spinlock.

Now we do not know when the code will release the lock. If some other thread tries to obtain the same lock, it would spin for very long time. In the worst case it would result in deedlock.

Kernel preemption case is handled by the spinlock code itself. Anytime kernel code holds a spinlock, preemption is disabled on the relevant processor. Even uniprocessor system must disable the preemption in this way.

Rule - 2: Disable interrupts on the local CPU, while the spinlock is held.

Reason: Support your driver take a spinlock that control access to the device and then issues an interrupt. This causes the interrupt handler to run. Now the interrupt handler also needs the lock to access the device. If the interrupt handler runs on the same processor, it will start spinning. The driver code also can not run to release the lock. SO the processor will spin for ever.

Rule - 3: Spinlocks must be held for the minimum time possible.

Reason: Long lock hold times also keeps the current processor from scheduling, meaning a higher priority process may have to wait to get the CPU.

So it impacts kernel latency (time a process may have to wait to be scheduled). Typically spinlocks should be held for the time duration, less than that CPU takes to do a contex switch between threads.

Rule -4: if you have semaphores and spinlocks both to be taken. Then take semaphore first and then spinlock.

Comments

[Shawn J. Goff]

Spinlocks are not always a waste in kernel code. This was explained very well by @HandyGandy in your previous question.

[Navaneeth Sen]

@Shawn : But i would like to make it a separate question, where i could get more clearer answers.

[Gilles 'SO- stop being evil']

Although the question you're asking here is not identical to your previous question, it has been answered by several people on the previous thread. And again, you should read chapter 5 of Linux Device Drivers, which explains this.

[Navaneeth Sen]

@Gilles : Sure.. I will do that.. But I prefer understanding the concepts via discussion rather than reading and absorbing the books.. :-)

[David Cary]

If the blocked caller doesn't context switch, how is it possible for that other thread to release the lock?

[invot]

In the kernel the spinlock can only be held by another CPU, not another thread. Hence you can wait until the other CPU releases the lock.