Hi,
Can anyone explains how queued spinlocks are different that spinlock and
how they are more efficient that normal spinlocks.
MSDN does not have any implementation details.
Ravish
The Queued Spinlock uses a queuing mechanism (hence its name) to keep track of processors waiting on the spinlock. This is different from the ordinary spinlock, where processors simply spinning on same piece of memory. The Queued Spinlock is more efficient by avoiding this memory contention.
thtse
Date: Sat, 21 Mar 2015 19:58:32 +0530
Subject: [ntdev] Queued Spinlock versus Spinlock
From: xxxxx@gmail.com
To: xxxxx@lists.osr.com
Hi,
Can anyone explains how queued spinlocks are different that spinlock and how they are more efficient that normal spinlocks.
MSDN does not have any implementation details.
Ravish
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
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
Check http://www.osronline.com/showThread.cfm?link=236864
We had a not-so-bad discussion of this topic on this thread. In fact, IIRC,we had discussed it quite a few times in this NG, so you can check the archives…
Anton Bassov
I think the bottom line is that they aren’t “more efficient” but they might
be “more fair”.
Mark Roddy
On Sat, Mar 21, 2015 at 11:31 AM, wrote:
> Check http://www.osronline.com/showThread.cfm?link=236864
>
> We had a not-so-bad discussion of this topic on this thread. In fact,
> IIRC,we had discussed it quite a few times in this NG, so you can check
> the archives…
>
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
>
That linked thread is a classic NTDEV discussion. Not to mention it further links to one of THE greatest all-time NTDEV threads, ever… Complete with Alberto and Mr Kyler.
Ah, those were the days,
Peter
OSR
@OSRDrivers
In short, a queued spinlock provides FIFO ordering, and also eliminates multiple processors beating on the same cache line (which may cause a whole storm on the interprocessor bus and affect other processors currently not fighting for the lock). When there is little contention, it’s more costly than a regular spinlock.
[quote]
When there is little contention, it’s more costly than a regular
spinlock.
Disagree. Mr. Oshins said “more complex But no more expensive” in the uncontested case.
Peter
OSR
@OSRDrivers
Like an ERESOURCE?
Peter
OSR
@OSRDrivers
One clarification : In case of normal spin lock
since all processors spins on same memory which processor get the lock
first once the owning processor releases the lock how it is determined ??
is it random how processors(in NUMA) for those the memory is remote get a
less chance to acquire them??
On Sun, Mar 22, 2015 at 6:24 PM, wrote:
> Like an ERESOURCE?
>
> Peter
> OSR
> @OSRDrivers
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
>
Ravish Yadav wrote:
One clarification : In case of normal spin lock
since all processors spins on same memory which processor get the lock
first once the owning processor releases the lock how it is
determined ??
is it random how processors(in NUMA) for those the memory is remote
get a less chance to acquire them??
Yes, it’s random. Whichever processor checks for the lock next will get it.
In a hyperthreaded processor, you could probably predict which processor
would check next. In a multicore environment, it’s truly random.
–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.
Don’t confuse “random” with “fair”!
Yes, it’s random. No, it’s not fair. in a NUMA architecture machine, a processor that is far from the lock will be less likely to gain the lock. There have been demonstrated instances of starvation in these configurations. Hence… queued spin locks!
Peter
OSR
@OSRDrivers
Hi
Given that (non MS) drivers can only use the ‘Instack’-Queued SLocks is it imperative that the KLOCK_QUEUE_HANDLE must always be on stack, i.e. can it be in (non-paged of course) pool (heap) area, If I assure
[1] every thread/contender (i.e. every logical core) has its own pool area allocated for its lock-handle i.e. (no two cores use the same area for the lock handle)
[2] somehow the execution dynamics ensure that this per-logical-core specific lock-handle (allocated on heap) memory location is always in the (local) cache (I guess even otherwise it will be probably in cache because the core is spinning on that area anyway).
Thanks
Thanks All for very useful comments!
Ravish
On Tue, Mar 24, 2015 at 4:08 AM, wrote:
>
>
> Don’t confuse “random” with “fair”!
>
> Yes, it’s random. No, it’s not fair. in a NUMA architecture machine, a
> processor that is far from the lock will be less likely to gain the lock.
> There have been demonstrated instances of starvation in these
> configurations. Hence… queued spin locks!
>
> Peter
> OSR
> @OSRDrivers
>
>
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
>
>Disagree. Mr. Oshins said “more complex But no more expensive” in the
uncontested case.
Agree, the cost overhead (in clocks) is very marginal and way below any possible noise of cache miss penalty.
>Can anyone explains how queued spinlocks are different that spinlock
- Precisely 1 atomic operation on acquire, and precisely 1 on release
- Each CPU spins on its local var, not on a shared var
- Order guarantee - the attempters will be granted acquisition in the order of attempts, so no starvations.
MSDN does not have any implementation details.
Look at non-MS web pages. MS have not invented the queued spinlock. The idea existed before them.
–
Maxim S. Shatskih
Microsoft MVP on File System And Storage
xxxxx@storagecraft.com
http://www.storagecraft.com
> [1] every thread/contender (i.e. every logical core) has its own pool area allocated for its lock-handle
i.e. (no two cores use the same area for the lock handle)
In-stack automatically ensures this in cheapest possible way.
You need 1 handle per CPU, and the number of CPUs is now dynamic.
–
Maxim S. Shatskih
Microsoft MVP on File System And Storage
xxxxx@storagecraft.com
http://www.storagecraft.com
I think Linux always had this kind of spinlocks.
They were using +1 for shared and -LargeNumber for exclusive IIRC.
wrote in message news:xxxxx@ntdev…
> Like an ERESOURCE?
>
> Peter
> OSR
> @OSRDrivers
>
>