[其他] 多线程无锁同步

参考：​​https://docs.microsoft.com/zh-cn/windows/win32/dxtecharts/lockless-programming?redirectedfrom=MSDN​​

小结：

1）Volatile 无法保证无锁同步；

2）windows下锁的是通过 memory barrier 实现的，掌握了内存屏障的使用便掌握了无锁同步；

3）DirectX提供了LockFreePipe，此管道只接受 “一个生产者，一个消费者” 模型；

4）Windows下，MemoryBarrier 提供了一个硬件内存屏障，使用此屏障可以防止CPU和编译器进行乱序执行；

5）Windows下，InterlockedIncrement 提供了一个绝对原子自增 32位变量的手段；64位变量可使用64位版本 InterlockedIncrement64

6）如果操作共享资源不会太耗时的话(比如被锁包裹的代码端就几条指令)，可以考虑使用带自旋锁的Critical Section (InitializeCriticalSectionAndSpinCount)，自旋锁可以让线程在指定的指令周期范围(注意这里是指令周期，因此时间会非常短)内独占CPU一段时间，然后在这段时间内反复检查是否可以获得锁（这也从侧面说明此方法不适用只有一个CPU核心的场景，而此函数也明确了在单CPU核心场景下不适用，毕竟如果就一个CPU核心又被独占的话，其他线程将无法得到执行），这样可以提高加锁速度。自旋锁的计数值是需要手工指定的，如果过大则会导致线程长时间独占cpu（很危险，会导致程序无响应，不过一般都是几千个指令周期，换算成时间可以忽略不计，参考上下文切换的指令周期不会超过1W），如果过小则无法达到效果，具体取值参照 InitializeCriticalSectionAndSpinCount 。

7）Windows下，可使用线程独享堆来解决多线程从同一块内存池中申请/释放内存时需要加锁的的问题，这是一种无锁同步策略。过多的线程共享同一个资源毕竟造成糟糕的竞争场景，如果能够将资源细分则可按照资源相关性安排线程组，这是业务层面的优化，恰巧Windows 提供了 线程独享堆 来帮助完成这种优化。

ps：几种同步手段的效率

• ​​MemoryBarrier​​ was measured as taking 20-90 cycles.
• ​​InterlockedIncrement​​ was measured as taking 36-90 cycles.
• Acquiring or releasing a critical section was measured as taking 40-100 cycles.
• Acquiring or releasing a mutex was measured as taking about 750-2500 cycles.

Critical Section 的内部组成：

msdn：Acquiring or releasing a critical section consists of a memory barrier, an InterlockedXxx operation, and some extra checking to handle recursion and to fall back to a mutex, if necessary. You should be wary of implementing your own critical section, because spinning in a loop waiting for a lock to be free, without falling back to a mutex, can waste considerable performance. 

Critiacal Section 内部自带递归锁机制，这样可以防止因为当前线程对同一个Critical Section重复加锁导致死锁。

Recommendations：

• Use locks when possible because they are easier to use correctly.
• Avoid locking too frequently, so that locking costs do not become significant.
• Avoid holding locks for too long, in order to avoid long stalls.
• Use lockless programming when appropriate, but be sure that the gains justify the complexity.
• Use lockless programming or spin locks in situations where other locks are prohibited, such as when sharing data between deferred procedure calls and normal code.
• Only use standard lockless programming algorithms that have been proven to be correct.
• When doing lockless programming, be sure to use volatile flag variables and memory barrier instructions as needed.
• When usingInterlockedXxxon Xbox 360, use theAcquireandReleasevariants.

解读：

• 尽可能使用锁，因为锁是绝对安全的；
• 不要频繁地加锁；
• 不要过长时间持有锁；(这条和上一条有点冲突，需要自己平衡)
• 如果使用无锁同步，要衡量带来的代码复杂性是否值得带来的性能提升；
• 有些场景下必须明确 锁 是禁止的，这个时候就必须使用无锁同步 或者 自旋锁，比如在延迟过程调用 和 正常代码 之间共享数据 的场景。
• 尽量使用系统提供的无锁同步组件，尽量不要自己造轮子；
• 在进行无锁编程时，在必要的时候一定要使用 volatile 关键字 和 内存屏障；
• InterlockedXxx在Xbox 360上要配合Acquire 和Release。

对于InitializeCriticalSectionAndSpinCount具体描述：

实际上对 CRITICAL_SECTION 的操作非常轻量，为什么还要加上旋转锁的动作呢？其实这个函数在单cpu的电脑上是不起作用的，只有当电脑上存在不止一个cpu，或者一个cpu但多核的时候，才管用。

如果临界区用来保护的操作耗时非常短暂，比如就是保护一个reference counter，或者某一个flag，那么几个时钟周期以后就会离开临界区。可是当这个thread还没有离开临界区之前，另外一个thread试图进入此临界区——这种情况只会发生在多核或者smp的系统上——发现无法进入，于是这个thread会进入睡眠，然后会发生一次上下文切换。我们知道 context switch是一个比较耗时的操作，据说需要数千个时钟周期，那么其实我们只要再等多几个时钟周期就能够进入临界区，现在却多了数千个时钟周期的开销，真是是可忍孰不可忍。