Coordination Data Structures – SpinLock
This is an article in a series of blog entries describing a set of new Coordination Data Structures (CDS) introduced in the June 2008 CTP of the Parallel Extensions for .NET Framework .
Waiting on locks usually result in a thread context switch and associated kernel transition which at times can be considered costly. On a multi-processor machine, often it might be more efficient to busy wait for a short period of time instead of paying the cost of performing an expensive context switch and a possible transition to kernel mode.
One approach to busy waiting is to wait in a loop repeatedly checking until the lock becomes available. These types of locks are called spin-locks.
System.Threading.SpinLock provides a mutual exclusion lock primitive where a thread trying to acquire the lock waits in a loop repeatedly checking until the lock becomes available.
When acquiring a spin-lock, it uses the CompareExchange interlocked operation to ensure that the owner of the lock is assigned in a thread-safe manner (this implementation detail is subject to change):
if(Interlocked.CompareExchange(ref _owner, newOwner, owner) == owner && ...)
Failing to become the owner of the lock, other threads will wait using a SpinWait until the lock is released (pseudo code):
public void Enter()
{
SpinWait sw = new SpinWait();
...
while (true)
{
if (!IsOwnerSet())
{
// set the owner - atomic
if (SetOwner())
{
// this thread is the owner so return
return;
}
}
// spin wait once
sw.SpinOnce();
}
...
}
One point to mention here is the effect of a spin-lock on a single-processor machine. On these systems, the spin-lock will hamper the performance by adding an unnecessary delay into the whole process. It will not result in a deadlock because after executing its quantum, the spinning thread is context-switched or pre-empted by another thread, however the time spent looping has not been productive.
Due to this behaviour, the System.Threading.SpinLock primitive ensures we always yield (switch threads) on single-processor machines instead of using busy waits.
Unlike Monitor, SpinLock publicly offers a set of reliable enter methods for acquiring a lock (i.e. ReliableEnter and TryReliableEnter). You should probably never use the unreliable enter methods because in the case of any asynchronous exceptions such as ThreadAbortException and OutOfMemoryException, you may end up with an orphaned lock that is never released. This is particularly true in ASP.NET since it uses aborts very aggressively.
As a side-note, you may wonder how we achieve this reliability. As it happens, the default CLR host postpones async exceptions inside a finally block until the end of the block. Therefore any part of the code that could result in an orphaned lock can be included inside a finally block: try { } finally { // take the lock in here // ... }Please note that another host could choose to escalate thread aborts to rude thread aborts, which can interrupt finally blocks. |
Closer investigating of the SpinLock.Exit method reveals an overload that takes a Boolean. If this Boolean is set to true, SpinLock flushes the write buffers associated with the lock in order to ensure that all processors are immediately made aware that the lock is now available. This is more expensive but will prevent a situation where one processor is given an unfair advantage to reacquire the lock:
SpinLock sharedLock = new SpinLock();
while (true)
{
sharedLock.Enter();
sharedLock.Exit();
// very little between Exit and retry Enter;
// possibly no other processor would see the lock available!
}
There are a few more things to remember when using the SpinLock:
1- When using the default constructor, the thread that owns the lock can enter the same lock and effectively cause a deadlock:
SpinLock l = new SpinLock();
l.Enter(); // non-blocking call
l.Enter(); // blocking call
2- When using the default constructor, any thread can release the lock (This is not a recommended practice and should be avoided in normal circumstances):
SpinLock l = new SpinLock();
l.Enter();
ThreadPool.QueueUserWorkItem(delegate
{
l.Exit();
});
3- In the current implementation, you can change the above behaviour. Simply set the isThreadOwnerTrackingEnabled parameter to true when creating a new instance of SpinLock:
Setting isThreadOwnerTrackingEnabled to true changes the behaviour of the lock by:
- Prohibiting the owner thread from trying to enter the same lock – throws a LockRecursionException; and,
- Ensuring the Exit method is only called by the owner thread – a SynchronizationLockException is thrown otherwise
Something else that’s worth mentioning is that SpinLock is a struct, and as such, you need to be careful about access patterns. If you accidentally make a copy of the struct, you’ll be copying by value meaning that you will be using a replica rather than the original lock. For example in the code below, both the main thread and the ThreadPool thread would successfully enter the lock. The morale of the story is that ideally these are not passed around, and instead they are used as local variables or member fields:
SpinLock sl = new SpinLock();
ThreadPool.QueueUserWorkItem(state =>
{
SpinLock theLock = (SpinLock)state;
theLock.Enter();
}, sl);
sl.Enter();
(Thanks to Stephen Toub, Joe Duffy and Ed Essey for their input and support)
Comments
Anonymous
June 02, 2008
PingBack from http://mdavey.wordpress.com/2008/06/02/coordination-data-structures/Anonymous
June 02, 2008
YES!! Finally a built-in SpinLock! :) Will this class also have a method that takes an Action so we don't have to worry about proper lock usage? I.e., so we can just do myLock.Use(() => something()); ?Anonymous
June 02, 2008
Michael, what an excellent idea! I have forwarded your comment to the Parallel Extensions team and should let you know of the outcome. Cheers and keep up the good feedback, PedramAnonymous
July 21, 2008
Nice article. Thanks! A few (very minor) typos: ... Perdam said: already sorted thanksAnonymous
February 02, 2010
Concise and complete. Thanks for the article. Micheal just to mention, Parallel task library is intended for the purpose you are mentioning. Probably you have already taken a look at it.