自旋锁是一种在内核定义，只能在内核态下使用的同步机制。自旋锁用来保护共享数据或者资源，使得并发执行的程序或者在高优先级IRQL的对称多处理器的程序能够正确访问这些数据。分析Windows自旋锁，首先需要介绍Windows的IRQL。
1 Interrupt Request Level
(IRQL)
介绍
IRQL是Interrupt Request
Level，中断请求级别。一个由windows虚拟出来的概念，划分在windows下中断的优先级，这里中断包括了硬中断和软中断，硬中断是由硬件产
生，而软中断则是完全虚拟出来的。处理器在一个IRQL上执行线程代码。IRQL是帮助决定线程如何被中断的。在同一处理器上，线程只能被更高级别
IRQL的线程能中断。每个处理器都有自己的中断。IRQL在Windows下
IRQL有如下值：
名称
级别
解释
Software IRQL
PASSIVE_LEVEL
0
Passive release level
LOW_LEVEL
0
Lowest interrupt level
APC_LEVEL 1
APC interrupt level
DISPATCH_LEVEL
2
Dispatcher level
Hardware IRQL
from 3 to 26 for device ISR
PROFILE_LEVEL
27
timer used for profiling
CLOCK1_LEVEL
28 Interval
clock 1 level - Not used on x86
CLOCK2_LEVEL
28
Interval clock 2 level
SYNCH_LEVEL
28 synchronization
level
IPI_LEVEL
29
Interprocessor interrupt level
POWER_LEVEL
30 Power
failure level
HIGH_LEVEL
31
Highest interrupt level
Windows的自旋锁有一系列函数组成，实现在不同场景下的自旋锁机制。
本系列文章主要涉及的体系结构是X86（32位）体系结构。如不特殊注明，都是在X86（32位）体系结构下。
下面分析KeAcquireSpinLock 的实现机制
2 KeAcquireSpinLock 的实现机制
KeAcquireSpinLock 在单核处理器和多核处理器上的实现是不一样的。
在单核处理器（WindowsXP）下
hal!KfAcquireSpinLock:
mov
edx,dword ptr ds:[0FFFE0080h]
mov
dword ptr ds:[0FFFE0080h],41h
shr
edx,4
movzx
eax,byte ptr hal!HalpVectorToIRQL [edx]
ret
观察KeGetCurrentIrql的实现
hal!KeGetCurrentIrql:
mov
eax,dword ptr ds:[FFFE0080h]
shr
eax,4
movzx
eax,byte ptr hal!HalpVectorToIRQL [eax]
ret
有充足的理由说明ds:[FFFE0080h]地址处存放的是IRQL相关的数据。
KfAcquireSpinLock就是改变当前的IRQL，KfAcquireSpinLock将IRQL改到一个什么值了呢？
db hal!HalpVectorToIRQL：
00 ff ff 01 02
ff 05 06 07 08 09 0a 1b 1c 1d 1e
00 00 00 00 00
00 00 00 2a 00 00 00 c4 00 00 00
如果先调用KfAcquireSpinLock
那么ds:[0FFFE0080h]的值是0x41,再调用KeGetCurrentIrql，由以上表得到返回值是(BYTE
*)HalpVectorToIRQL[4]是2。单核处理器下，KfAcquireSpinLock的工作就是将IRQL升为DISPATCH_LEVEL。KfReleaseSpinLock就是将IRQL还原为原来的值了。
在多核处理器（Windows2003）下
KeAcquireSpinLock
通过调用KfAcquireSpinLock来实现功能
hal!KfAcquireSpinLock:
mov
eax,dword ptr fs:[00000024h]
mov
byte ptr fs:[24h],2
jmp
hal!KeAcquireSpinLockRaiseToSynch+0xe
hal!KeAcquireSpinLockRaiseToSynch:
mov
eax,dword ptr fs:[00000024h]
mov
byte ptr fs:[24h],1Bh
hal!KeAcquireSpinLockRaiseToSynch+0xe
lock bts dword ptr
[ecx],0
jb
hal!KeAcquireSpinLockRaiseToSynch+0x16
ret
hal!KeAcquireSpinLockRaiseToSynch+0x16
test dword
ptr [ecx],1
je
hal!KeAcquireSpinLockRaiseToSynch+0xe
pause
jmp
hal!KeAcquireSpinLockRaiseToSynch+0x16
KfAcquireSpinLock是不会执行到KeAcquireSpinLockRaiseToSynch的头两行代码的。
fs:[00000024h] 保存的是当前线程的IRQL，可以通过函数来证实。
hal!KeGetCurrentIrql：
mov
al,byte ptr fs:[00000024h]
ret
将KfAcquireSpinLock翻译成伪代码：
KfAcquireSpinLock(SpinLock){
KeRaiseIrql(DISPATCH_LEVEL,
OldIrql);
While(TRUE)
{
//独占处理器和相关存储空间执行下面代码
//由Lock指令实现
lastbit=SpinLock.lastbit;
SpinLock.lastbit=1;
//释放独占
if(lastbit ==1){
while(SpinLock.lastbit ==1) ;
}
else break;
}
Return
OldIrql;
}
对KfAcquireSpinLock的解释就比较容易了，首先提升IRQL到DISPATCH_LEVEL，然后一直等到SpinLock被别人释放，设置SpinLock的值为占有然后退出。
在Windows2003
多核处理器下KeReleaseSpinLock通过调用KfReleaseSpinLock来实现功能
hal!KfReleaseSpinLock:
lock and
byte ptr [ecx],0
mov
cl,dl
call
hal!KfLowerIrql
ret
释放SpinLock，将IRQL还原。
分析：
显而易见，在单核环境里实现DISPATCH_LEVEL及其以下IRQL的同步，将当前线程升级到DISPATCH_LEVEL足够了。但是在多核环境
下，每一个核都有自己的IRQL，提升IRQL来实现同步是不行的，在多核的情况下，Windows系统引入了lock指令来实现同步。
现在DDK(3790)中是这么定义的
#if defined(_X86_)
#define KeAcquireSpinLock(a,b) *(b) =
KfAcquireSpinLock(a)
#define KeReleaseSpinLock(a,b)
KfReleaseSpinLock(a,b)
#else
//
// These functions are imported for IA64, ntddk, ntifs, nthal,
ntosp, and wdm.
// They can be inlined for the system on AMD64.
//
#define KeAcquireSpinLock(SpinLock, OldIrql) /
*(OldIrql) =
KeAcquireSpinLockRaiseToDpc(SpinLock)
参考资料将在系列文章结束后列出。
3
KeAcquireSpinLockAtDpcLevel的实现机制
MSDN上说明调用KeAcquireSpinLockAtDpcLevel的程序必须运行在DISPATCH_LEVEL上。
在多核处理器（Windows2003）下
先来查看一下KeAcquireSpinLockAtDpcLevel的汇编代码
nt!KeAcquireSpinLockAtDpcLevel:
mov
ecx,dword ptr [esp+4]
nt!KeAcquireSpinLockAtDpcLevel+0x4
lock bts dword ptr
[ecx],0
jb
nt!KeAcquireSpinLockAtDpcLevel+0xe
ret
4
nt!KeAcquireSpinLockAtDpcLevel+0xe：
test dword
ptr [ecx],1
je
nt!KeAcquireSpinLockAtDpcLevel+0x4
pause
jmp
nt!KeAcquireSpinLockAtDpcLevel+0xe
将KeAcquireSpinLockAtDpcLevel翻译成伪代码：
KeAcquireSpinLockAtDpcLevel (SpinLock){
while(TRUE) {
//独占处理器和相关存储空间执行下面代码
lastbit=SpinLock.lastbit;
SpinLock.lastbit=1;
//释放独占
if(lastbit ==1){
while(SpinLock.lastbit ==1) ;
}
else
break;
}
}
对比一下KfAcquireSpinLock，KeAcquireSpinLockAtDpcLevel除了不提升IRQL到DISPATCH_LEVEL，其他都是一样的，KeAcquireSpinLockAtDpcLevel的运行环境已经在DISPATCH_LEVEL上了，确实也不要提升。
KefReleaseSpinLockFromDpcLevel的实现
nt!KefReleaseSpinLockFromDpcLevel:
lock and byte ptr [ecx],0
ret
KefReleaseSpinLockFromDpcLevel就是简单实用lock指令把Spinlock的值置成0释放。
在单核处理器（WindowsXP）下
在单核处理器下KfAcquireSpinLock所作的工作就是简单提升一下IRQL到DISPATCH_LEVEL，那么KeAcquireSpinLockAtDpcLevel已经在DISPATCH_LEVEL，还需要做什么工作呢？是不是什么工作都不需要做了？
实际上观察KeAcquireSpinLockAtDpcLevel在单核处理器下的实现，发现确实什么也没做，直接返回了。
KefReleaseSpinLockFromDpcLevel也是一样,直接返回了。
分析：
关于KeAcquireSpinLockAtDpcLevel在MSDN上有这样一段文字：
当IRQL=
DISPATCH_LEVEL时，驱动调用KeAcquireSpinLockAtDpcLevel比调用KeAcquireSpinLock
有更好的性能。当IRQL<DISPATCH_LEVEL时,驱动必须调用KeAcquireSpinLock。
其实观察具体实现，KeAcquireSpinLockAtDpcLevel
“更好的性能”体现在多核状态下少运行了两条MOV指令，单核状态下少运行了三条MOV指令和一条SHR指令，不得不感叹下Windows的惜指令如金。
4，KeAcquireSpinLockRaiseToDpc的实现机制
在MSDN上是这么说的：
调用KeAcquireSpinLockRaiseToDpc的程序必须运行在IRQL<=DISPATCH_LEVEL
上
KeAcquireSpinLockRaiseToDpc和KeAcquireSpinLock具有同样的功能，但是比KeAcquireSpinLock具有更高的效率。
下面将着重关注KeAcquireSpinLockRaiseToDpc是如何提高效率的。
写到这里我打开Windbg准备看个究竟，可是不论在nt下还是hal下怎么也找不到这个函数。
然后我使用dependency查看ntoskrnl.exe 和 hal.dll导出函数也没有看到这个函数，奇怪。
最后使用在线的MSDN找到了这样令人晕倒的一句话：
Requirements
Versions: Available in the 64-bit versions of Windows 2000 and in
later 64-bit versions of Windows. This routine is not available in
32-bit versions of Windows.
我机器上装的MSDN2003却没有这样的提示，误我！
没见我在第一篇中明确提到了吗
本系列文章主要涉及的体系结构是X86（32位）体系结构。如不特殊注明，都是在X86（32位）体系结构下。
这只是一个小插曲。
5，KeAcquireInStackQueuedSpinLock的实现机制
在单核处理器（WindowsXP）下
观察KeAcquireInStackQueuedSpinLock的实现
hal!KeAcquireInStackQueuedSpinLock:
mov
eax,dword ptr ds:[FFFE0080h]
shr
eax,4
mov
al,byte ptr hal!HalpVectorToIRQL [eax]
mov dword
ptr ds:[0FFFE0080h],41h
mov
byte ptr [edx+8],al
ret
和KeReleaseSpinLock的实现基本上一样的，只不过将原来的IRQL保存在了LockHandle里。
而KeAcquireInStackQueuedSpinLock就是将IRQL降为原来的值了。
在多核处理器（Windows2003）下
仔细比对WRK上的代码和Windbg上的汇编代码，除了一个标志位上有不同外其他实现是一样的。
本来希望对这些汇编代码做一些解释，但是解释来解释去，发现远不如直接用WRK的代码简洁明了。
以下将直接分析WRK上的实现。
下面代码直接复制于WRK
typedef struct _KSPIN_LOCK_QUEUE {
struct
_KSPIN_LOCK_QUEUE * volatile Next;
PKSPIN_LOCK
volatile Lock;
}
typedef struct _KLOCK_QUEUE_HANDLE {
KSPIN_LOCK_QUEUE LockQueue;
KIRQL
OldIrql;
}
KeAcquireInStackQueuedSpinLock (PKSPIN_LOCK
SpinLock, PKLOCK_QUEUE_HANDLE LockHandle);
{
LockHandle->LockQueue.Lock = SpinLock;
LockHandle->LockQueue.Next = NULL;
LockHandle->OldIrql =
KfRaiseIrql(DISPATCH_LEVEL);
KxAcquireQueuedSpinLock(&LockHandle->LockQueue,
SpinLock);
return;
}
KxAcquireQueuedSpinLock (PKSPIN_LOCK_QUEUE LockQueue,PKSPIN_LOCK
SpinLock )
{
PKSPIN_LOCK_QUEUE TailQueue;
TailQueue = InterlockedExchangePointer((PVOID *)SpinLock,
LockQueue);
if (TailQueue != NULL) {
KxWaitForLockOwnerShip(LockQueue, TailQueue);
}
return;
}
ULONG64 KxWaitForLockOwnerShip(PKSPIN_LOCK_QUEUE
LockQueue,PKSPIN_LOCK_QUEUE TailQueue)
{
ULONG64
SpinCount;
*((ULONG64
volatile *)&LockQueue->Lock) |=
LOCK_QUEUE_WAIT;
TailQueue->Next = LockQueue;
SpinCount =
0;
do {
__asm { rep nop }
} while
((*((ULONG64 volatile
*)&LockQueue->Lock)
& LOCK_QUEUE_WAIT) != 0);
KeMemoryBarrier();
return
SpinCount;
}
下面将分析KeAcquireInStackQueuedSpinLock如何获访问互斥的资源。
如图所示，LockHandle是在栈上建立的的数据。当线程1首次进入InStackQueuedSpinLock时，初始时*SpinLock的值为
NULL，因此TailQueue的值也为NULL。SpinLock通过InterlockedExchangePointer被置成为指向栈上的LockHandle。线程1进入被InStackQueuedSpinLock保护的资源。
当线程1还在占用状态，线程2准备获得InStackQueuedSpinLock时，由于线程1已经将SpinLock的值置成为线程1上的
LockHandle，线程2获得线程1的LockHandle，这时线程2的TailQueue指向线程1的LockHandle，不为空，线程2进入
等待状态。
线程2进入等待状态后，先将自己的lock置成等待状态，然后将线程1的LockHandle的next指针置成为指向自己的LockHandle，完成将自己栈上的节点插入链表。
同样，当其他线程准备获得InStackQueuedSpinLock时，将会在自己的栈上建立节点，并插入到线程2的节点之后。
这就是KeAcquireInStackQueuedSpinLock的名称的由来了，InStack是指在栈上建立节点，Queued就是将这些节点形成链表了。
算法KeAcquireInStackQueuedSpinLock描述为：
1， 链表的表尾保存在SpinLock中。初始值为NULL。将IRQL升级为DISPATCH_LEVEL
，
LockQueue->Lock置为SpinLock。
2， 当线程准备获得资源时，执行如下独占处理器和相关存储空间操作：
1> 保存SpinLock到TailQueue
2> 将SpinLock指向当前栈上节点
3， 如果TailQueue为空，则直接获得资源。
4， 如果TailQueue不为空，LockQueue->Lock置为LOCK_QUEUE_WAIT，
然后
TailQueue->Next置成当前节点，等待LockQueue->Lock的值不为LOCK_QUEUE_WAIT。
下面分析释放InStackQueuedSpinLock
KeReleaseInStackQueuedSpinLock (PKLOCK_QUEUE_HANDLE
LockHandle)
{
KxReleaseQueuedSpinLock(&LockHandle->LockQueue);
KeLowerIrql(LockHandle->OldIrql);
return;
}
KxReleaseQueuedSpinLock (PKSPIN_LOCK_QUEUE LockQueue)
{
PKSPIN_LOCK_QUEUE
NextQueue;
NextQueue =
ReadForWriteAccess(&LockQueue->Next);
if
(NextQueue == NULL) {
if (InterlockedCompareExchangePointer((PVOID
*)LockQueue->Lock,
NULL,
LockQueue) == LockQueue) {
return;
}
NextQueue = KxWaitForLockChainValid(LockQueue);
}
ASSERT(((ULONG64)NextQueue->Lock &
LOCK_QUEUE_WAIT) != 0);
InterlockedXor64((LONG64 volatile
*)&NextQueue->Lock,
LOCK_QUEUE_WAIT);
LockQueue->Next = NULL;
}
KxWaitForLockChainValid ( PKSPIN_LOCK_QUEUE
LockQueue)
{
PKSPIN_LOCK_QUEUE
NextQueue;
do {
KeYieldProcessor();
} while
((NextQueue = LockQueue->Next) == NULL);
return
NextQueue;
}
线程准备退出时，首先检查链表上有没有其他节点在等待，如果有节点在等待，直接将下一个节点的Lock的LOCK_QUEUE_WAIT标志位去掉，并将本节点的从链表中脱离出来。
如果没有节点在等待，这时候的操作复杂一些，因为在任何时刻都有可能有节点进入。本节点的Lock指向的是SpinLock，而SpinLock指向的是表尾节点。下面的操作作为一个原子操作完成：
1， 如果Lock指向的是当前节点LockQueue，说明在此之前没有节点插入，则将Lock即SpinLock的值还原为初始状态NULL。
2， 如果Lock指向的不是当前节点，则说明已经或者正在有节点插入。说明其他线程在此之前执行完了KeAcquireInStackQueuedSpinLock第2步。
如果是1，已经完成退出操作，直接退出。
如果是2，则等到则点插入完成即当前节点的next指向下一个节点，然后回到刚开始，将下一个节点的Lock的LOCK_QUEUE_WAIT标志位去掉，并将本节点的从链表中脱离出来。
算法KeReleaseInStackQueuedSpinLock描述为：
1， 获得下一个节点NextQueue。
2， 如果NextQueue不为空，将下一个节点的Lock的LOCK_QUEUE_WAIT标志位去掉，并将本节点的从链表中脱离出来。
3， 将IRQL降为原来的值并且退出。
4， 如果NextQueue为空，执行如下独占处理器和相关存储空间操作：
1>
Lock指向的是当前节点LockQueue，将Lock即SpinLock的值还原为初始状态NULL,转3。
2> Lock指向的不是当前节点。
5， 等待NextQueue不为空，然后转3。
分析：
在单核下，KeAcquireInStackQueuedSpinLock和KeReleaseSpinLock的实现基本上一样。
并没有性能上的提高。
在多核下。KeAcquireInStackQueuedSpinLock相对于KeReleaseSpinLock有如下不同：
1， KeAcquireInStackQueuedSpinLock每一个线程等待自己栈上的一个变量变化，
而KeReleaseSpinLock等待全局的SpinLock发生变化。
2， KeAcquireInStackQueuedSpinLock能维护一个队列，保证等待的队列先进先出。
而KeReleaseSpinLock获得资源则是随机的，与等待的先后次序无关。
关于更深层次的性能比较，期待其他人的分析了。
6，KeAcquireInStackQueuedSpinLockAtDpcLevel的实现机制
在单核(WinXP)下，KeAcquireInStackQueuedSpinLockAtDpcLevel直接返回。
在多核(Windows2003)下，KeAcquireInStackQueuedSpinLockAtDpcLevel
与KeAcquireInStackQueuedSpinLock比较除了不提升IRQL外，其他都是一样的。
7，KeAcquireInterruptSpinLock的实现机制
在单核(WinXP)下和多核(Windows2003)下，KeAcquireInterruptSpinLock的实现机制是一样的，先将IRQL升级到KINTERRUPT->
SynchronizeIrql，然后直接调用KefAcquireSpinLockAtDpcLevel。
而KeReleaseInterruptSpinLock则是先调用KefReleaseSpinLockFromDpcLevel，再将IRQL还原。
当然单核和多核下，KefAcquireSpinLockAtDpcLevel与KefReleaseSpinLockFromDpcLevel实现并不一样。
8，自旋锁性能分析
John M. Mellor-Crummey和Michael L. Scott的文章
"Algorithms for scalable synchronization on shared-memory
multiprocessors"介绍了五种自旋锁的实现算法并进行了详细的性能分析。
1,Simple test_and_set lock
2,Ticket lock
3,Anderson’s array-based queueing lock
4,Graunke and Thakkar's array-based queuing lock
5,The MCS list-based queuing lock (John M. Mellor-Crummey 和Michael
L. Scott发明)
下面是一些性能分析的截图。
对Windows 自旋锁进行分类：
Windows
自旋锁
平台(X86,32位) 自旋锁算法
-------------------------------------------------------------------------------
KeAcquireSpinLock
单核
无
多核
Simple test_and_set lock
-------------------------------------------------------------------------------
KeAcquireSpinLockAtDpcLevel
单核
无
多核
Simple test_and_set lock
-------------------------------------------------------------------------------
KeAcquireInStackQueuedSpinLock
单核
无
多核
MCS
-------------------------------------------------------------------------------
KeAcquireInStackQueuedSpinLockAtDpcLevel
单核
无
多核
MCS
-------------------------------------------------------------------------------
KeAcquireInterruptSpinLock
单核
无
多核
Simple test_and_set lock
9 参考资料
http://baike.baidu.com/view/904161.htm
http://ext2fsd.sourceforge.net/documents/irql.htm
www.cs.rice.edu/~johnmc/papers/tocs91.pdf
http://www.microsoft.com/resources/sharedsource/windowsacademic/researchkernelkit.mspx