CPU同步机制漫谈

张银奎 [email protected]

更快是计算机世界的一个永恒主题。要做到更快有两个方向：一是提高串行执行的速度，二是并行计算（Parallel Computing）。并行计算又可分为同一CPU内部多个流水线间的并行、同一个系统内多个CPU间的并行、和同一个网络中多个计算机系统间的并行。

当并行运行的多个任务彼此无关，互不依赖时，整个系统的性能是最高的。但在现实的并行计算中，这是不可能的。至少同一组内的多个任务之间是存在依赖关系的，它们需要交流信息，报告彼此的计算结果；调整进度，确保各个任务都有条不紊的进行；协调资源，确保共享数据的一致性和安全性和最终结果的正确性。这样便产生了并行计算中的一个基本问题，那就是同步（Synchronization）。并行计算的特征决定了同步是它的一个必然问题。

为了易于理解，我们看一个从银行账户中存款和提款的简单例子，清单1给出的是账户类CAccount的Withdraw和Deposit方法的C++代码。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

BOOL CAccount::Withdraw(double dblNumber) {          BOOL bRet=TRUE;          if(GetBalance()>=dblNumber)          {                    // Send out money now, we use sleep to simulate                    Sleep(rand());                    m_dblBalance-=dblNumber;          }          else          {                    bRet = FALSE;          }          Log(TASK_WITHDRAW,dblNumber,bRet);          return bRet; } void CAccount::Deposit(double dblNumber) {          m_dblBalance+=dblNumber;          Log(TASK_DEPOSIT,dblNumber,TRUE); }

以上方法很容易理解，参数dblNumber是要支出或存入的金额，第4行检查帐户余额是否足够本次提取，第7行执行支付操作，我们调用Sleep函数延迟一段时间来模拟这个操作，第8行修改账户余额。

图1是使用以上类的TaskSync程序的界面和一次执行记录。点击Deposit和Withdraw按钮会触发创建新的线程来调用CAccount类的Deposit和Withdraw 方法。编辑框中的数字既是存入和支出的金额，又是要创建的线程数，因为我们让每个线程都固定的存入或取出1元钱。

在编辑框中各输入10后，随机的反复点击Deposit和Withdraw按钮，持续一段时间后，我们会发现余额变成了负数。

图1 TaskSync程序

观察清单1中的代码，只有在确保余额不小于参数dblNumber时（第4行）才会执行取款动作，然后递减余额（m_dblBalance）。也就是说这个账户是不应该出现负数余额的（不可透支）。那么，是什么原因导致余额变为负数呢？以下是几种猜想：

1.          在某个（些）线程执行取款动作的过程中（第7行），其它线程又修改了余额值。尽管第4行作判断时账户中还有足够的余额，但是在执行递减操作时，其它线程（提款机）可能已经把余额递减为0了，于是再次递减便出现了负数。

2.          在某个（些）线程更新m_dblBalance变量时，也就是执行递减操作（第8行）时，其它线程又修改了它的值。清单2列出了m_dblBalance-=dblNumber语句所对应的汇编代码。可见尽管C++是一条语句，但是编译出的汇编语句还是有很多条的。第1行（清单2）是将this指针存入EAX寄存器，第2行是将m_dblBalance（this+8）从内存加载到FPU（符点处理单元）寄存器栈中，第3行是执行减法运算，ebp+8指向的是参数dblNumber，第4行是将this指针存入ECX寄存器，第5行是将计算结果存回内存中的m_dblBalance成员变量。因为第3行的减法计算是对加载在CPU寄存器中的值做减法，第5行再将这个值存回内存，那么如果在某个线程执行2、3条指令的间隙，其它线程修改了m_dblBalance，那么这个线程使用的仍然是旧的数据，而且第5行会将错误的结果写入到内存中。

3.          在32位x86系统中，m_dblBalance变量在内存中的长度是8个字节（QWORD）。这意味着存取这个变量时需要读写8个字节。如果，两个线程恰好都要读写这8个字节，那么有可能某个线程读到的内容是另一个线程写了一半的数据，或者某个线程写了8个字节的前半部分，另一个线程写了后半部分。

清单2 m_dblBalance-=dblNumber语句所对应的汇编代码

1 2 3 4 5

004013B5   mov         eax,dword ptr [ebp-4] 004013B8   fld         qword ptr [eax+8] 004013BB   fsub        qword ptr [ebp+8] 004013BE   mov         ecx,dword ptr [ebp-4] 004013C1   fstp        qword ptr [ecx+8]

可以说，以上三种猜想都是合理的。猜想1的可能性最大，因为判断条件和递减操作之间的时间较大，在此期间，余额值被其它线程修改的概率很高。猜想2也是可能的，因为在Windows这样的抢先式（preemptive）多任务操作系统中，操作系统可能在某个线程执行完清单2中的第2条指令后将其挂起，然后去执行其它线程。这意味着，因为线程切换，即使系统中只有一个普通的CPU（非Hyper Threading等），那么猜想1和猜想2所描述的情况仍然可能发生。

下面看一下猜想3，对于单CPU系统，因为CPU总是在指令边界（instruction boundary）来确认中断和进行线程切换，而且存取m_dblBalance变量都是使用一个指令来完成的，所以这种情况是不会发生的，也就是说CPU不会在一条指令还没执行完时将某个线程挂起。对于多CPU系统，是可能发生的（见下文），因为多个CPU可能并行执行清单2中的递减操作，也就是所谓的并发（concurrency）情况。

事实上，以上三种情况也是并行计算中经常遇到的三个典型问题。为了解决这些问题，操作系统通常会提供各种同步机制，供自身和应用软件使用。比如Windows操作系统提供了很多种用于线程同步的核心对象，以满足不同的需要，比如关键区（critical section），事件对象（event），互斥对象（semaphore）和spinlock等等。此外，作为计算机系统执行核心的CPU也内建了很多 同步支持。下面以IA32 CPU为例略作介绍。

首先我们介绍一下CPU一级的原子操作（atomic operations）。所谓原子操作，就是CPU会保证整个操作被完整执行，不会被打断成几个部分多次执行。例如，IA32 CPU会保证以下操作（列出的不是全部）都是原子的：

n         读写一个字节。

n         读写与16位地址边界对齐的字（WORD）。

n         读写与32位地址边界对齐的双字（DWORD）。

n         读写与64位地址边界对齐的四字（QWORD）（从奔腾开始）。

归纳一下，读写一个字节永远是安全的，读写按其长度做内存对齐的数据通常也是安全的。读写内存对齐的数据也有利于提高效率，这也是编译器在编译时会自动做内存对齐的原因。回到我们刚才讨论的猜想3，m_dblBalance是8字节长的，从调试器中可以看到它的地址是0x12fed0，这个地址可以被8整除，符合64位（二进制）对齐标准。所以如果是在奔腾及其之后的CPU上执行，那么读写m_dblBalance是安全的（不必担心不完全的读写）。如果在CAccount类的定义前加上pack(1)编译指令（compiler directive），并在m_dblBalance成员前加上一个一字节的字符变量，那么m_dblBalance的地址变成了0x12fecd，不再64位对齐了。

#pragma pack(1)

class CAccount 

{

protected:

char n;

double m_dblBalance;

…

对于没有对齐的16位，32位和64位数据，CPU是否能以原子方式读写就要视情况而定了，如果它们是位于同一个cache line中的，那么P6系列及其后的IA32 CPU仍会保证原子读写。如果是分散在多个cache line中的，那么奔腾4和至强（Xeon）CPU仍有可能支持其原子读写，但是访问这样的未对齐数据会影响系统的性能。

下面我们再来看一下总线锁定。为了保证某些关键的内存操作不被打断，IA32 CPU设计了所谓的总线锁定机制。当位于前端总线上的某个CPU需要执行关键操作时，它可以设置（assert） 它的#LOCK信号（管脚）。当一个CPU输出了#LOCK信号，其它CPU的总线使用请求便会暂时堵塞，直到发出#LOCK信号的CPU完成操作并撤销#LOCK信号。例如，CPU在执行以下操作时，会使用总线锁定机制：

n         设置TSS（任务状态段）的Busy标志。设置Busy标志，是任务切换的一个关键步骤，使用锁定机制可以防止多个CPU都切换到某个任务。

n         更新段描述符。

n         更新页目录和页表表项。

n         确认（acknowledge）中断。

除了以上默认的操作外，软件也可以通过在指令前增加LOCK前缀来显式的（explicitly）强制使用总线锁定。例如，可以在以下指令前增加LOCK前缀：

n         位测试和修改指令BTS、BTR和BTC。

n         数据交换指令，如XCHG、XADD、CMPEXCHG和CMPEXCHG8B。

n         以下单操作符算术或逻辑指令：INC、DEC、NOT和NEG。

n         以下双操作符算术或逻辑指令：ADD、ADC、SUB、SBB、AND、OR和XOR。

Windows操作系统所提供的用于同步访问共享变量的Interlocked Variable Access API就是使用LOCK方法实现的。例如，以下就是InterlockedIncrement API的汇编代码：

kernel32!InterlockedIncrement:

7c809766 8b4c2404        mov     ecx,dword ptr [esp+4]

7c80976a b801000000      mov     eax,1

7c80976f f00fc101        lock xadd dword ptr [ecx],eax

7c809773 40              inc     eax

7c809774 c20400          ret     4

可以看到，XADD指令前被加上了LOCK前缀。类似的InterlockedExchange API是使用带有LOCK前缀的cmpxchg指令。以下是kernel32.dll和ntdll.dll输出的所有Interlocked API。

0:001> x kernel32!Interlocked*

7c80978e kernel32!InterlockedExchange = <no type information>

7c8097b6 kernel32!InterlockedExchangeAdd = <no type information>

7c80977a kernel32!InterlockedDecrement = <no type information>

7c8097a2 kernel32!InterlockedCompareExchange = <no type information>

7c809766 kernel32!InterlockedIncrement = <no type information>

0:001> x ntdll!Interlocked*

7c902f55 ntdll!InterlockedPushListSList = <no type information>

7c902f06 ntdll!InterlockedPopEntrySList = <no type information>

7c902f2f ntdll!InterlockedPushEntrySList = <no type information>

除了前面的三种猜想，还有一种可能导致数据不同步，那就是因为处理器的乱序执行（out-of-order execution）和内部缓存（cache）而导致的数据不一致。为了发挥CPU内多条执行流水线（execution pipeline）的效率，CPU可能把一段代码分成几段同时放到几个流水线中执行；另外，为了减少存取内存的次数，少占用前端总线，处理器会对某些写操作进行缓存。比如，一个函数先向地址A写入1，而后又写为2，…….，那么CPU可以延迟中间步骤中的各次写操作，只需要把最终的结果更新到内存，这就是所谓的写合并（Write Combining）。但如果系统中有多个处理器，那么另一个处理器就有可能使用过时的数据。为了解决诸如此类的问题，IA32 CPU配备了SFENSE 、LFENCE和MFENCE三条指令，分别代表Store Fence（写屏障）、Load Fence（读屏障）和Memory Fence。SFENCE用来保证该指令之前（程序顺序）的写操作一定早于它之后的所有写操作而落实完成（complete）、公之于众（通知其它处理器和写入内存）。换句话来说，SFENCE指令之前的写操作是不可能穿越SFENCE而早于其后的写操作而完成的。类似的，LFENCE是用来强制读操作的顺序的，MFENCE可以同时强制读写操作的顺序。因为这三条指令的作用都是为了显式定义内存存取顺序，所以它们又被称为内存定序（memory ordering）指令。

因为SFENCE指令是Pentium III CPU引入的，而LFENCE和MFENCE是奔腾4和至强引入的，所以这几条指令在Windows XP或之前的系统中还较少使用。

DDK for Windows Server 2003定义了KeMemoryBarrier API，在3790版本DDK的ntddk.h中可以看到其x86实现如下：

FORCEINLINE VOID KeMemoryBarrier ( VOID )

{

    LONG Barrier;

    __asm {  xchg Barrier, eax  }

}

可见使用的是自动锁定的XCHG指令。而在支持Vista的5744及更高版本的DDK中，其定义为：

FORCEINLINE VOID KeMemoryBarrier ( VOID )

{

    FastFence();

    LFENCE_ACQUIRE();

    return;

}

其中FastFence被定义为编译器的intrinsics（内建函数）：

#define FastFence __faststorefence

所谓intrinsics，就是定义在编译器内部的函数片断，很类似于扩展关键字，当编译器看到程序调用这些函数时，会自动产生合适的代码，也有些intrinsics只是以函数调用的形式向编译器传送信息，并不产生代码，如KeMemoryBarrierWithoutFence便是告诉编译器调整内存操作顺序时不能跨越这个位置。类似的定义还有：

#define LoadFence _mm_lfence

#define MemoryFence _mm_mfence

#define StoreFence _mm_sfence

在最新的Vista SDK（SDK 6.0）的头文件中也包含以上定义，只不过用户态的API名字叫MemoryBarrier()。可见最新的Windows DDK和SDK都已经提供了充分的内存定序支持。

本文结合一个简单的例子讨论了多任务系统中的同步问题，重点介绍了原子操作，总线锁定和内存定序这三种实现同步的重要机制。更多内容请阅读参考文献中所列出的资源。

参考文献：

1, IA-32 Intel (C) Architecture Developer’s Manual Volume 2& 3 Intel Corporation

2, Compiler Intrinsics MSDN

3, Multiprocessor Considerations for Kernel-Mode Drivers Microsoft Corporation

4, Memory Barriers Wrap-up Steve Dispensa