Spinlock vs Semaphore / Mutex

NTDEV
1

I have a question about synchronization in kernel mode.
As I know, spinlock provided multi-processor safe manipulation for entering
critical section.
Semaphore and Mutext can also be used for synchronization purpose.
Are they multi-processor safe mechanism?

I was confused by them.
For example, if I have two dispatched function may access one shared
resource.
Could I use semaphore or mutex to synchronize the shared resource access?

What would be the case I should use spinlock if semaphore or mutex can be
used in this case for mutil-processor system?

Best Regards
Jack

2

Yes all of these are multi-processor safe. The reasons for using a spinlock
are:

  1. Very lightweight vesus the others
  2. Can be used at DISPATCH_LEVEL (or above with interrupt spinlock)

That being said spin locks do cause the processor to spin and no other
thread being scheduled. So if you are holding the lock for a long time, you
want to look at semaphores, mutexs, executive resources, and the plethora
of other mechanisms Windows provides.

–
Don Burn (MVP, Windows DKD)
Windows Filesystem and Driver Consulting
Website: http://www.windrvr.com
Blog: http://msmvps.com/blogs/WinDrvr

“Jack Huang” wrote in message news:xxxxx@ntdev…
>I have a question about synchronization in kernel mode.
> As I know, spinlock provided multi-processor safe manipulation for
> entering critical section.
> Semaphore and Mutext can also be used for synchronization purpose.
> Are they multi-processor safe mechanism?
>
> I was confused by them.
> For example, if I have two dispatched function may access one shared
> resource.
> Could I use semaphore or mutex to synchronize the shared resource access?
>
> What would be the case I should use spinlock if semaphore or mutex can be
> used in this case for mutil-processor system?
>
> Best Regards
> Jack
>
>
>
> Information from ESET NOD32 Antivirus, version of virus
> signature database 4294 (20090731)
>
> The message was checked by ESET NOD32 Antivirus.
>
> http://www.eset.com
>
>
>

Information from ESET NOD32 Antivirus, version of virus signature database 4294 (20090731)

The message was checked by ESET NOD32 Antivirus.

http://www.eset.com

3

Spin locks are lightweight and fast, and can be used above PASSIVE_LEVEL. A
mutex is heavyweight. While a spin lock “just spins”, the question is *how
long* it spins. If the goal of the spin lock is, for example, to protect a
list link/unlink style operation, you will end up spinning for something on
the order of tens on nanoseconds, whereas a scheduling operation (even if
you were locking at PASSIVE_LEVEL) is going to on the order of microseconds.
Also, because the scheduler is involved, the “latency” from releasing the
lock until the next thread can be scheduled can be in the tens of
milliseconds.

Since semaphores do not provide mutual exclusion, their usage should not
enter the discussion. They are used for a different purpose (the case of a
semaphore whose range is 0…1 is a special case, but then you end up with
details such as recursive acquisition and other differences between a
“binary semaphore” and a mutex).

All synchronization mechanisms have to be multiprocessor-safe; it wouldn’t
make sense any other way.

You cannot cause a thread running at DISPATCH_LEVEL to wait on a mutex, so
the best you can do is poll, which means you have just reinvented a
massively expensive spin lock.

Also, spin locks have the queued spin lock variant, which reduces bus
contention and guarantees FIFO processing (no thread starvation). In
general, for any short interval, spin locks would be preferred. For
synchronizing PASSIVE_LEVEL threads with lengthy delays, mutexes would be
used. A PASSIVE_LEVEL thread working with a queue will use a semaphore.
Note that if you need lengthy delays, you *cannot* use spin locks (the
nominal spin lock budget is 10us), which means you may need to create a
complex architecture so your waiting thread is waiting at PASSIVE_LEVEL.

Generally, it is not usually a good idea to have threads blocked for lengthy
periods of time unless they are your own threads. Otherwise you can consume
threads from the thread pool and potentially interfere with the file system
performance.
joe

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Jack Huang
Sent: Friday, July 31, 2009 12:44 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Spinlock vs Semaphore / Mutex

I have a question about synchronization in kernel mode.
As I know, spinlock provided multi-processor safe manipulation for entering
critical section.
Semaphore and Mutext can also be used for synchronization purpose.
Are they multi-processor safe mechanism?

I was confused by them.
For example, if I have two dispatched function may access one shared
resource.
Could I use semaphore or mutex to synchronize the shared resource access?

What would be the case I should use spinlock if semaphore or mutex can be
used in this case for mutil-processor system?

Best Regards
Jack

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

–
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

4

> For example, if I have two dispatched function may access one shared resource.

Could I use semaphore or mutex to synchronize the shared resource access?

Mutex is dispatcher-level synchronization construct - it thinks in terms of threads, rather than CPUs, but once the same thread cannot run on more than one CPU at any given moment, it is multi-processor safe as well.

Spinlock is basically different thing - it is used for synchronization between CPUs, so it has no concept of threads. Normally it is used for synchronizing access to the variables that may be accessed in atomic
context, because you cannot use dispatcher-level synch constructs in atomic context. As long as you hold a spinlock no context switches may occur on a given CPU. Therefore, you should not hold a spinlock for any more or less significant period of time - otherwise, the whole thing may result in significant performance degradation at the system level…

Anton Bassov

5

Those were three VERY interesting answers… each touched on a slightly different aspect of the issue.

Thanks for those excellent replies to what could easily have been dismissed as a “simple” question… Nice job to the three of you!

Peter
OSR

6

Please read this:

http://www.microsoft.com/whdc/driver/kernel/locks.mspx

–
Jake Oshins
Hyper-V I/O Architect
Windows Kernel Group

This post implies no warranties and confers no rights.

“Jack Huang” wrote in message news:xxxxx@ntdev…
> I have a question about synchronization in kernel mode.
> As I know, spinlock provided multi-processor safe manipulation for
> entering critical section.
> Semaphore and Mutext can also be used for synchronization purpose.
> Are they multi-processor safe mechanism?
>
> I was confused by them.
> For example, if I have two dispatched function may access one shared
> resource.
> Could I use semaphore or mutex to synchronize the shared resource access?
>
> What would be the case I should use spinlock if semaphore or mutex can be
> used in this case for mutil-processor system?
>
> Best Regards
> Jack
>
>

7

It should also be noted that if you use spin-locks any code/data you touch while holding the spin-lock (functions you call into, etc…) must reside in non-pagable memory. I don’t think it is common to use spin locks, unless you are synchronizing with the code which runs at DISPATCH or above. Another synch primitive which should be mentioned is FAST_MUTEX which is just as fast as spin-lock in the uncontended case since it tries to lock the object using interlocked operations before waiting on the kernel dispatcher object (similar to the way CriticalSection works in user mode).

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Joseph M. Newcomer
Sent: Friday, July 31, 2009 10:42 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlock vs Semaphore / Mutex

Spin locks are lightweight and fast, and can be used above PASSIVE_LEVEL. A
mutex is heavyweight. While a spin lock “just spins”, the question is *how
long* it spins. If the goal of the spin lock is, for example, to protect a
list link/unlink style operation, you will end up spinning for something on
the order of tens on nanoseconds, whereas a scheduling operation (even if
you were locking at PASSIVE_LEVEL) is going to on the order of microseconds.
Also, because the scheduler is involved, the “latency” from releasing the
lock until the next thread can be scheduled can be in the tens of
milliseconds.

Since semaphores do not provide mutual exclusion, their usage should not
enter the discussion. They are used for a different purpose (the case of a
semaphore whose range is 0…1 is a special case, but then you end up with
details such as recursive acquisition and other differences between a
“binary semaphore” and a mutex).

All synchronization mechanisms have to be multiprocessor-safe; it wouldn’t
make sense any other way.

You cannot cause a thread running at DISPATCH_LEVEL to wait on a mutex, so
the best you can do is poll, which means you have just reinvented a
massively expensive spin lock.

Also, spin locks have the queued spin lock variant, which reduces bus
contention and guarantees FIFO processing (no thread starvation). In
general, for any short interval, spin locks would be preferred. For
synchronizing PASSIVE_LEVEL threads with lengthy delays, mutexes would be
used. A PASSIVE_LEVEL thread working with a queue will use a semaphore.
Note that if you need lengthy delays, you *cannot* use spin locks (the
nominal spin lock budget is 10us), which means you may need to create a
complex architecture so your waiting thread is waiting at PASSIVE_LEVEL.

Generally, it is not usually a good idea to have threads blocked for lengthy
periods of time unless they are your own threads. Otherwise you can consume
threads from the thread pool and potentially interfere with the file system
performance.
joe

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Jack Huang
Sent: Friday, July 31, 2009 12:44 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Spinlock vs Semaphore / Mutex

I have a question about synchronization in kernel mode.
As I know, spinlock provided multi-processor safe manipulation for entering
critical section.
Semaphore and Mutext can also be used for synchronization purpose.
Are they multi-processor safe mechanism?

I was confused by them.
For example, if I have two dispatched function may access one shared
resource.
Could I use semaphore or mutex to synchronize the shared resource access?

What would be the case I should use spinlock if semaphore or mutex can be
used in this case for mutil-processor system?

Best Regards
Jack

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

–
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

8

Spin lock use is much more common than iyou think it is. All you need is one function (completion routine, dpc, maybe a dispatch routine) which runs at > passive level and the spin lock usage becomes viral throughout the code. Also, one more thing to note about a fast mutex (vs an event or mutex or semaphore) is that once it is acquired, you are raised to apc level (the others leave you at passive) and there are far fewer APIs you can call at apc.

d

Sent from my phone with no t9, all spilling mistakes are not intentional.

-----Original Message-----
From: Alex Bendetov
Sent: Friday, July 31, 2009 10:12 PM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlock vs Semaphore / Mutex

It should also be noted that if you use spin-locks any code/data you touch while holding the spin-lock (functions you call into, etc…) must reside in non-pagable memory. I don’t think it is common to use spin locks, unless you are synchronizing with the code which runs at DISPATCH or above. Another synch primitive which should be mentioned is FAST_MUTEX which is just as fast as spin-lock in the uncontended case since it tries to lock the object using interlocked operations before waiting on the kernel dispatcher object (similar to the way CriticalSection works in user mode).

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Joseph M. Newcomer
Sent: Friday, July 31, 2009 10:42 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlock vs Semaphore / Mutex

Spin locks are lightweight and fast, and can be used above PASSIVE_LEVEL. A
mutex is heavyweight. While a spin lock “just spins”, the question is how
long it spins. If the goal of the spin lock is, for example, to protect a
list link/unlink style operation, you will end up spinning for something on
the order of tens on nanoseconds, whereas a scheduling operation (even if
you were locking at PASSIVE_LEVEL) is going to on the order of microseconds.
Also, because the scheduler is involved, the “latency” from releasing the
lock until the next thread can be scheduled can be in the tens of
milliseconds.

Since semaphores do not provide mutual exclusion, their usage should not
enter the discussion. They are used for a different purpose (the case of a
semaphore whose range is 0…1 is a special case, but then you end up with
details such as recursive acquisition and other differences between a
“binary semaphore” and a mutex).

All synchronization mechanisms have to be multiprocessor-safe; it wouldn’t
make sense any other way.

You cannot cause a thread running at DISPATCH_LEVEL to wait on a mutex, so
the best you can do is poll, which means you have just reinvented a
massively expensive spin lock.

Also, spin locks have the queued spin lock variant, which reduces bus
contention and guarantees FIFO processing (no thread starvation). In
general, for any short interval, spin locks would be preferred. For
synchronizing PASSIVE_LEVEL threads with lengthy delays, mutexes would be
used. A PASSIVE_LEVEL thread working with a queue will use a semaphore.
Note that if you need lengthy delays, you cannot use spin locks (the
nominal spin lock budget is 10us), which means you may need to create a
complex architecture so your waiting thread is waiting at PASSIVE_LEVEL.

Generally, it is not usually a good idea to have threads blocked for lengthy
periods of time unless they are your own threads. Otherwise you can consume
threads from the thread pool and potentially interfere with the file system
performance.
joe

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Jack Huang
Sent: Friday, July 31, 2009 12:44 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Spinlock vs Semaphore / Mutex

I have a question about synchronization in kernel mode.
As I know, spinlock provided multi-processor safe manipulation for entering
critical section.
Semaphore and Mutext can also be used for synchronization purpose.
Are they multi-processor safe mechanism?

I was confused by them.
For example, if I have two dispatched function may access one shared
resource.
Could I use semaphore or mutex to synchronize the shared resource access?

What would be the case I should use spinlock if semaphore or mutex can be
used in this case for mutil-processor system?

Best Regards
Jack

—
NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

–
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

—
NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

—
NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

9

>(functions you call into, etc…) must reside in non-pagable memory. I don’t think it is common to use

spin locks, unless you are synchronizing with the code which runs at DISPATCH or above.

All dispatch/completion paths in the storage/volume/disk stack.

Another synch primitive which should be mentioned is FAST_MUTEX which is just as fast as spin-lock
in the uncontended case since it tries to lock the object using interlocked operations before waiting on
the kernel dispatcher object (similar to the way CriticalSection works in user mode).

Surely. The only difference is that CriticalSection is recursive, and FAST_MUTEX is not.

I would call FAST_MUTEX and spinlock 2 main kinds of locks in the Windows kernel/

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

10

>semaphore) is that once it is acquired, you are raised to apc level (the others leave you at passive)

and there are far fewer APIs you can call at apc.

Calling complex APIs under the lock (like ZwXxx) is evil anyway.

I even prefer to not call ExAllocate under a spinlock.

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

11

Thanks for all of your replies.
You did help me so much in Windows synchronization concept.
Locks.doc linked below is good to me.

Best Regards
Jack

“Jake Oshins” …
> Please read this:
>
> http://www.microsoft.com/whdc/driver/kernel/locks.mspx
>
>
> –
> Jake Oshins
> Hyper-V I/O Architect
> Windows Kernel Group
>
> This post implies no warranties and confers no rights.
>
> --------------------------------------------------------------
>
>
> “Jack Huang” wrote in message news:xxxxx@ntdev…
>> I have a question about synchronization in kernel mode.
>> As I know, spinlock provided multi-processor safe manipulation for
>> entering critical section.
>> Semaphore and Mutext can also be used for synchronization purpose.
>> Are they multi-processor safe mechanism?
>>
>> I was confused by them.
>> For example, if I have two dispatched function may access one shared
>> resource.
>> Could I use semaphore or mutex to synchronize the shared resource access?
>>
>> What would be the case I should use spinlock if semaphore or mutex can be
>> used in this case for mutil-processor system?
>>
>> Best Regards
>> Jack
>>
>>
>