Linux无锁队列-内存一致性
date
slug
tags
summary
type
status
内存模型
什么是内存模型
为了优化程序运行的性能，编译器和CPU往往会引入自己的优化，比如编译器会进行指令重排，而CPU则可能在内部引入缓存，这些优化会保证程序的运行结果与原来一致，然而，却会导致其发往内存系统的指令与预设不同。
内存系统包括了缓存，比如L1 Cache，因为L1 Cache与Memory会通过缓存一致性协议保证读写顺序一致性，因此可以将其视为对用户透明。
对于单线程程序而言，这类优化并不会影响程序的正确性。然而如果多个线程之间进行协作，并且协作之间假设了程序的访存顺序，此时编译器以及CPU优化导致的乱序就会导致协作出现失败。
为了能够编写正确的多线程程序，我们需要先定义一个抽象内存模型，忽略具体的优化实现，内存模型描述了程序的访存指令最终可能以何种形式进行乱序，同时，往往编译器和CPU会提供一些工具阻止某种乱序的发生，基于该内存模型以及提供的工具，多线程程序能够通过一些技巧来保证协作正确性。
处理器内存模型
内存模型取决于编译器和处理器，不同的处理器实现往往会导致不同的内存模型。就处理器提供的内存模型而言（忽略编译器重拍行为），内存模型主要分为以下三类：
- 顺序一致性：所有操作严格按照程序原来的顺序执行
- TSO一致性（x86）：对于没有数据依赖和地址依赖的写读操作会出现乱序。
写读乱序出现的原因是因为x86架构会在处理器中引入写缓冲区，因此写指令不一定会马上发出到内存系统。
- 弱一致性：对于没有数据依赖和地址依赖的读读，读写，写读，写写都可能会出现乱序
为了使得多线程程序可以正确运行，不同的处理器提供了不同的指令（工具）来阻止乱序的发生。比如，x86提供
mfence内存屏障，对于write；mfence；read ，mfence会保证write指令发出到内存再进行read指令，阻止写读乱序。对于存在数据依赖和地址依赖的读写操作，处理器必然会保证其在单线程内执行的顺序（这是保证程序按照预期运行的前提。
然而，其可见性是否如此？
Linux内存模型
对于不同的处理器架构，不同的内存模型需要不同的指令来保证多线程程序的正确性。这对于Linux这类架构无关应用是不友好的，为了保证内核中的多线程程序可以正确地运行在各种架构中，Linux定义了自己的内存模型，并且通过宏的方式提供了一系列架构无关的工具。
在Documentation/memory-barriers.txt描述的内存模型基本可以视为一个弱一致性模型，在这个模型中，若指令之间存在以下关系，则会保证指令之间按序执行，否则，不可以假设指令的执行存在某种顺序：
- 存在依赖关系
A←D; B←A
- 存在地址重叠
A←0x00;0x00←B
在memory-barriers.txt的描述中，以上规则是针对一个CPU内，这里个人认为有点模糊，那么针对全局的可见性是否如何？即对于
A = 0, B = 1
A <- B
C <- A
其他CPU是否可能遇到A=0,C=1的情况？
结合硬件的实现，个人认为这里是不会的，因为load指令最终被发到内存系统的顺序由于依赖关系会保证其先后关系，因此C←A会在A←B之后发出，因此其他CPU不可能遇到A=0,C=1。
Linux内存屏障
针对以上的内存模型，Linux内提供了多种内存屏障工具用于干预乱序行为，以保证多线程程序的正确性。
Linux内存屏障是一种抽象概念，其表现形式以及实现会有多种方式，比如后文会看到某类内存屏障其会有多种表现形式，根据不同架构，也会有多种实现方式。
Linux主要提供6种内存屏障：
- 写屏障
写屏障会保证在屏障前的所有写操作都会在屏障之前完成
- 地址依赖屏障（目前所有处理器已经天然满足，已弃用
- 读屏障
读屏障会保证在屏障前的所有读操作都会在屏障之前完成
- 通用屏障（写+读屏障
通用屏障会保证屏障前的所有读写操作都会在屏障前完成
- acquire
acquire保证所有acquire后的操作只会在acquire后执行，acquire有多种表现形式，在调用
LOCK，smp_load_acquire，smp_cond_load_acquire时，都可以将其视为一种acquire屏障。- release
release保证所有release后的操作只会在release前执行，release有多种表现形式，在调用
UNLOCK，smp_store_release 时，都可以将其视为一种release屏障。以上的屏障具体的实现取决于不同的CPU架构，以及在实现上，其通常包括编译器屏障和处理器屏障，比如
asm volatile("" ::: "memory"); 通常作为编译器屏障防止重拍，mfence 则是CPU的内存屏障。Linux Lock-Free Queue
Linux Lock-Free Queue是一个单生产者单消费者的无锁队列，其基本的逻辑如下所示：
- 生产者在生产新的数据之前需要查看消费者位置，保证当前存在空闲位置，之后将数据存入空闲位置，最后更新生产者位置。
- 消费者需要读取生产者位置，在确定存在可消费元素后，读取数据，最后更新消费者位置。
根据以上的内存模型，指令之间存在乱序，我们需要内存屏障以保证正确性：
- (A)保证了在确认存在空闲位置之前，不会有数据存储的动作发生
- (D)保证了在更新消费者位置之后，不会存在访问数据的动作
- (B)保证了在更新生产者动作之前，所有数据都会被存入空闲位置
- (C)保证了在确定存在可消费元素之前，不会出现读取数据的行为
其中(ABCD)根据具体可能出现动作，采用了合适的屏障(read or write)，理论上全部使用通用屏障也是可行的。
然而，根据上下文的语义，这里的读写屏障可以被进一步优化为
smp_load_acquire ，smp_store_release 。使用
smp_load_acquire ，smp_store_release 的好处在于，在x86平台的TSO内存模型中，这类屏障实际是天然满足的，因此在该内存模型中，这两个操作不需要加CPU内存屏障操作，只需要加入编译器屏障防止指令重排。这也是这两个屏障最初提出的初衷。相比于读屏障和写屏障，更细粒度的屏障语义更加复杂，但同时也增加了优化空间。
Ref
- ‣
- ‣
Loading...