文档章节

无锁数据结构(基础篇):原子性、原子性原语

oschina_00
 oschina_00
发布于 2017/03/22 14:57
字数 5089
阅读 35
收藏 1

无锁数据结构基于两方面——原子性操作以及内存访问控制方法。本文中我话题主要涉及原子性和原子性原语。

 

在开始之前,我对大家表示感谢,谢谢你们对初识无锁数据结构的热爱。看到大家对无锁话题很感兴趣,我感到很开心。我计划依据学术概念将此做成一个系列,从基础到算法,同时以文本的形式展示 libcds 中的代码实现。但有些读者希望避开漫谈,尽快展示这些代码,以及如何利用这些库。我同意其中的一些观点。毕竟,不是所有的人既想知晓 boost 内部构造,也想知道如何应用。

 

因此,我将系列文章分了三部分:基础篇、机制篇、番外篇,每篇文章涉及其中之一。

 

  • 在基础篇,我会介绍底层的知识,甚至现代CPU构造。

  • 在机制篇,我会介绍无锁领域有趣的算法和方法——这一部分更像是无锁数据结构的理论实现。Libcds会是一个无尽的 C++ 代码来源。

  • 在番外篇,大都是关于 libcds 实现实践为主题的文章,编程方法、建议和常见问题;对读者的提问、评价、提议做出反馈。

 

本文不会涉及太多 C++ 编程,甚至不会涉及太多无锁知识;(尽管没有原子性,无锁算法难以实现。)主要是现代处理器的原子性原语实现,利用这些基本类型时可能遇到的问题。

 

原子性是两种底层概念中的前一种。

 

原子性操作可以简单地分为读写(read and write)、原子性交换操作(read-modify-write,RMW)两部分。原子操作可认为是一个不可分的操作;要么发生,要么没发生,我们看不到任何执行的中间过程,不存在部分结果(partial effects)。简单的读写操作甚至不具有原子性,例如,没有内存对齐的数据,该数据的读取不具有原子性。在X86架构的计算机中,这样的读操作会导致内部回避。这样,处理器读取数据就被分成了好几部分。在其它诸如Sparc、Intel Itanium架构中,这样的读操作会导致段错误,这些操作要能被拦截并处理,而原子性操作不存在这样的问题。在现代处理器中,原子性的读写操作仅仅作用于对齐后的完整类型(整数和指针);而现代编译器是volatile基本类型正确对齐的保障。如果你想4到8个比特大小的数据结构具有原子性,那你就应该谨慎行事,借助编译器指令确保其正确对齐。每种编译器都有其独一无二的数据、类型对齐方法。顺便说一下,libcds 库支持一组备用类型和宏指令,当你声明对齐数据时,它们会隐藏编译器依赖的部分。

 

Compare-and-swap

 

即便竭尽全力,设计一个仅仅使用读写的无锁容器算法依然是困难重重(我不清楚针对线程随机数的数据结构)。这就是为什么处理器架构开发人员采用 RMW 操作的原因。RMW可以原子性地执行对齐内存单元读操作和针对它的写操作:compare-and-swap (CAS)、fetch-and-add (FAA)、test-and-set (TAS) 等等。在学术圈,compare-and-swap (CAS)被认为是最基本的一种操作。伪代码如下:

 

bool CAS( int * pAddr, int nExpected, int nNew )

atomically {

    if ( *pAddr == nExpected ) {

         *pAddr = nNew ;

         return true ;

    }

    else

        return false ;

}

 

从字面意思上看,如果pAddr地址中的当前变量值等于预期的 nExpected,那么将 nNew 的值赋给此变量,并返回true;否则返回false,变量值不变。所有执行过程都是原子性的、不可分的,不会产生任何可见的部分结果。借助于CAS,其它的 RMW 操作都可以估值。如下的 fetch-and-add 是这样的:

 

int FAA( int * pAddr, int nIncr )

{

     int ncur ;

     do {

          ncur = *pAddr ;

     } while ( !CAS( pAddr, ncur, ncur + nIncr ) ;

     return ncur ;

}

 

CAS 操作的学术性类型在实践中并非那么得心应手。CAS 失败后,我们时常想知道内存单元中的当前值是多少。这时可以考虑另一个种CAS (所谓的 valued CAS,依然是原子性执行):

 

int CAS( int * pAddr, int nExpected, int nNew )

atomically {

      if ( *pAddr == nExpected ) {

           *pAddr = nNew ;

           return nExpected ;

       }

       else

            return *pAddr

}

 

C++11中的 compare_exchange函数包含了两种衍生类型(严格地说,C++11没有此类函数,它们是 ompare_exchange_strong 和 compare_exchange_weak,这些我稍后会告知大家):

 

bool compare_exchange( int volatile * pAddr, int& nExpected, int nNew );

 

参数nExpected通过引用传值,并且包含pAddr地址的预期变量值。在输出端,返回变化之前的值。(译者注,其实就是返回pAddr的旧地址。假如函数地址中存在值 nExpected,返回true,加入失败了则返回false(nExpected 会包含地址 pAddr 的当前变量值)。multipurpose CAS 操作构建涵盖了学术 CAS定义的两种衍生类型。但在实际应用中,compare_exchange 会出现一些错误,你需要知道 nExpected 参数是传引用,它是可以改变的,这一点是不能接受的。

 

但借助 compare_exchange 可以实现 fetch-and-add 基本类型,代码可以写成下面这样:

 

int FAA( int * pAddr, int nIncr )

{

     int ncur = *pAddr;

     do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ;

     return ncur ;

}

 

ABA问题

 

CAS 基本类型适合多种方式。不过在应用过程中,可能发生一个严重的问题,就是所谓的 ABA 问题。为了描述这个问题,我们需要考虑一种 CAS 操作应用的典型模式:

 

int nCur = *pAddr ;

while (true) {

    int nNew = calculating new value

    if ( compare_exchange( pAddr, nCur, nNew ))

        break;

}

 

事实上,我们一直在循环中,直到CAS执行才跳出循环。在读取 pAddr 地址中的当前变量值和计算新值 nNew,这个在 pAddr 地址中可被其它线程改变的变量之间,循环是必须的。

 

 

ABA 问题可以用下面的方式加以描述。假设线程A从共享内存单元读取A值,与此同时,该内存单元指针指向某些数据;接着线程Y将内存单元的值改为B,接着再改回 A,但此时指针指向了另一些数据。但线程 A 通过 CAS 基本类型试图更改内存单元值时,指针和前面读取的 A 值比较是成功的,CAS 结果也正确。但此时 A 指向完全不一样的数据。结果,线程就打破了内部对象连接(internal object connections),最终导致失败。

 

下面是一个无锁栈的实现,重现了ABA 问题 [Mic04]:

 

// Shared variables

static NodeType * Top = NULL; // Initially null

 

Push(NodeType * node) {

            do {

/*Push1*/          NodeType * t = Top;

/*Push2*/          node->Next = t;

/*Push3*/   } while ( !CAS(&Top,t,node) );

}

 

NodeType * Pop() {

          Node * next ;

          do {

/*Pop1*/        NodeType * t = Top;

/*Pop2*/        if ( t == null )

/*Pop3*/             return null;

/*Pop4*/        next = t->Next;

/*Pop5*/   } while ( !CAS(&Top,t,next) );

/*Pop6*/   return t;

}

 

下面一系列活动导致栈结构遭受破坏(需要注意的是,此序列不是引起 ABA 问题的唯一方式)。

 

   
Thread X Thread Y
Calls Pop().
Line Pop4 is performed,
variables values: t == A
next == A->next
 
  NodeType * pTop = Pop()
pTop == top of the stack, i.e. A
Pop()
Push( pTop )
Now the top of the stack is A again
Note, that A->next has changed
Pop5 line is being performed.
CAS is successful, but the field Top->next
is assigned with another value,
which doesn’t exist in the stack,
as Y thread has pushed A and A->next out,
of a stack and the local variable next
has the old value of A->next
 
 

 

ABA 问题是所有基于 CAS 基本类型的无锁容器的一个巨大灾难。它会在多线程代码中出现,当且仅当元素 A 从某个容器中被删除,接着存入另一个元素 B,然后再改为元素A。即便其它线程使该指针指向某一元素,该元素可能正在被删除。即使该线程物理删除了A,接着调用new方法创建了一个新的元素,也不能保证 allocator 返回A的地址。此问题在超过两个线程的场景中经常出现。鉴于此,我们可以讨论 ABCBA 问题、ABABA 问题等等。

 

为了处理 ABA 问题,你应该物理删除(延迟内存单元再分配,或者安全内存回收)该元素,并且是在不存在竞争性线程局部,或全局指向待删除元素的情况下进行。

 

因此,无锁数据结构中元素删除包含两个步骤:

 

  • 第一步,将该元素逐出无锁容器中;

  • 第二步(延迟),不存在任何连接的情况下,物理移除该元素。

 

我会在接下来的某篇文章中详细介绍延迟删除的不同策略。

 

Load-Linked / Store-Conditional

 

我猜测,因为 CAS 中出现的ABA问题,促使处理器开发人员寻找另外一种不受 ABA 问题影响的 RMW 操作。于是找到了load-linked、store-conditional (LL/SC) 这样的操作对。这样的操作极其简单,伪代码如下:

 

word LL( word * pAddr ) {

      return *pAddr ;

}

 

bool SC( word * pAddr, word New ) {

      if ( data in pAddr has not been changed since the LL call) {

           *pAddr = New ;

           return true ;

      }

      else

         return false ;

}

 

LL/SC对以括号运算符的形式运行,Load-linked(LL) 运算仅仅返回 pAddr 地址的当前变量值。如果 pAddr 中的数据在读取之后没有变化,那么 Store-conditional(SC) )操作会将LL读取 pAddr 地址的数据存储起来。这种变化之下,任何 pAddr 引用的缓存行修改都是明确无误的。为了实现 LL/SC 对,程序员不得不更改缓存结构。简而言之,每个缓存行必须含有额外的比特状态值(status bit)。一旦LL执行读运算,就会关联此比特值。任何的缓存行一旦有写入,此比特值就会被重置;在存储之前,SC操作会检查此比特值是否针对特定的缓存行。如果比特值为1,意味着缓存行没有任何改变,pAddr 地址中的值会变更为新值,SC操作成功。否则本操作就会失败,pAddr 地址中的值不会变更为新值。

 

CAS通过LL/SC对得以实现,具体如下:

 

bool CAS( word * pAddr, word nExpected, word nNew ) {

   if ( LL( pAddr ) == nExpected )

      return SC( pAddr, nNew ) ;

   return false ;

}

 

注意,尽管代码中存在多个步骤,不过它确实执行原子性的 CAS。目标内存单元内容要么不变,要么发生原子性变化。框架中实现的 LL/SC 对,仅仅支持 CAS 基本类型是可能的,但不仅限于此种类型。在此,我不打算做进一步讨论。如果感兴趣,可以参考引文[Mic04]。

 

现代处理器架构分为两大部分。第一部分支持计算机代码中的 CAS 基本类型;第二部分是LL/SC 对。CAS 在X86、Intel Itanium、Sparc框架中有实现。基本类型第一次出现在IBM系统370基本类型中;而PowerPC、MIPS、Alpha、ARM架构中的 LL/SC 对, 最早出现在DEC中。倘若 LL/SC 基本类型在现代架构中没有完美实现,那它就什么都不是。比如,采用不同的地址无法调用嵌入的 LL/SC ,连接标签存在错误遗弃的可能。

 

从C++的角度看,C++并没有考虑 LL/SC 对,仅仅描述了原子性原语 compare_exchange (CAS),以及由此衍生出来的原子性原语——fetch_add、fetch_sub、exchange等等。这个标准意味着通过 LL/SC 可以很容易地实现 CAS;而通过 CAS 对 LL 的向后兼容实现绝对没有那么简单。因此,为了不增加 C++ 库开发人员的难度,标准委员会仅仅引入了C++ compare_exchange。这足以用于无锁算法实现。

 

伪共享(False sharing)

 

现代处理器中,缓存行的长度为64-128字节,在新的模型中有进一步增加的趋势。主存储和缓存数据交换在 L 字节大小的 L 块中进行。即使缓存行中的一个字节发生变化,所有行都被视为无效,必需和主存进行同步。这些由多处理器、多核架构中缓存一致性协议负责管理。

 

 

假设不同的共享数据(相邻地址的区域)存入同一缓存行,从处理的角度看,某个数据改变都将导致同一缓存行中的其它数据无效。这种场景叫做伪共享。对 LL/SC 基本类型而言,错误共享具有破坏性。这些基本类型的执行依赖于缓存行。加载连接(LL)操作连接缓存行,而存储状态(SC))操作在写之前,会检查本行中的连接标志是否被重置。如果标志被重置,写就无法执行,SC返回 false。考虑到缓存行的长度 L 相当长,那么任何缓存行的变更,即和目标数据不一致,都会导致SC 基本类型返回 false 。结果产生一个活锁现象:在此场景下,就算多核处理器满负载运行,依然无用。

 

为了处理错误共享,每个共享变量必须完全处理缓存行。通常借用填充(padding)来处理。缓存的物理结构影响所有的操作,不仅仅是 LL/SC,也包含CAS。在一些研究中,采用一种特殊的方式创建数据结构,该方式有考虑缓存结构(主要是缓存行长度)。一旦数据结构被恰当地构建,性能就会有极大的提升。

 

struct Foo {

       int volatile nShared1;

       char   _padding1[64];     // padding for cache line=64 byte

       int volatile nShared2;

       char   _padding2[64];     // padding for cache line=64 byte

};

 

CAS衍生类型

 

同样,我乐意介绍两种更有用的基本类型:double-word CAS (dwCAS) 和 double CAS (DCAS)。

 

Double-word CAS 和通用 CAS 相似,不同的是前者运行在双倍大小的内存单元中:32位体系结构是64比特,64位体系结构是128比特(要求至少96比特)。有鉴于此架构提供 LL/SC 而非CAS,LL/SC 应该运行在 double-word 之上。我了解的情况是仅有 X86 支持 dwCAS。那么为什么 dwCAS 如此有用呢?借助它可以组织一种 ABA 问题的解决方案——tagged pointers。此方案依赖于每种相关的共享 tagged pointer 整数。tagged pointer 可以通过以下结构加以描述:

 

template <typename T>

struct tagged_pointer {

      T *       ptr ;

      uintptr_t tag ;

 

    tagged_pointer()

      : ptr( new T )

      , tag( 1 )

    {}

};

 

为了支持原子性,本类型的变量必须与 double-word 对齐:32位架构是8字节,64位架构是16字节。tag 包含 “版本号” 数据,ptr 指向此数据。我会在接下来的某篇文章中详尽介绍 tagged pointers,集中介绍安全内存回收和安全内存回收。目前仅讨论内存,一旦涉及 T-type 数据(以及其对应的tagged_pointer),都不应该物理删除,而是移入到一个 free—list 中(对每个T-type进行隔离)。未来随着tag增长,数据得以分布式存储。ABA问题解决方案:现实中,此指针式很复杂的,tag 包含一个版本号(分布式位置编号)。如果 tagged_pointer 指针类型和 dwCAS 参数相同,但 tag 的值不同,那么 dwCAS 不会成功执行。

 

第二种原子性原语——double CAS (DCAS) ,是纯理论,没有在任何现代处理器架构中实现。DCAS 伪代码如下:

 

bool DCAS( int * pAddr1, int nExpected1, int nNew1,

           int * pAddr2, int nExpected2, int nNew2 )

atomically {

    if ( *pAddr1 == nExpected1 && *pAddr2 == nExpected2 ) {

         *pAddr1 = nNew1 ;

         *pAddr2 = nNew2 ;

         return true ;

    }

    else

         return false

}

 

DCAS 运行子两个随机排序内存单元上。若当前值与预期值一致,可改变这两个内存单元的值。

 

为何此基本类型如此有意思呢?因为它容易构建一个无锁双链表(deque)。数据结构是许多有趣算法的基础。许多学术性工作关注的数据结构,都基于 DCAS。尽管这个基本类型在硬件中还没有实现,依然有一些工作(比如[Fra03]- 最流行的一种)描述了基于常规 CAS 的 DCAS 构建(针对任意多个 pAddr1…pAddrN 地址的 multi-CAS )算法。

 

性能

 

那么原子性原语性能如何?

 

现代处理器是如此的复杂、难于预测,以至于程序员对计算机指令常常难以适从。特别是原子性指令,其工作机制涉及内部同步、处理器总线信号等等。许多工作正在试着测试处理器指令长度。而我所提及的测试来自[McKen05]。在这篇文章中,作者比较了原子性增长(atomic increment)和 CAS 基本类型长度和nop(no-operation)长度。比如Intel Xeon 3.06 hHz 处理器(2005 model)原子性增长长度为400 nop,CAS 长度 850-1000 nop。IBM Power4 1.45 hHz 处理器原子性增长长度为180 nop, CAS长度为250 nop。测试时间有些久远,处理器架构有了一些不小的进步,不过我猜还是在同一数量级上。

 

正如你所看到的那样,原子性原语是相当复杂的。所以不加取舍,任何场景下都用它是相当不利的。例如,二进制树搜索算法采用 CAS 读取当前树的节点,我不看好此类算法。毫无意义,每一代Intel核心架构,其CAS都会变得更快。显然,Intel付出很多努力去改进微型架构。

 

Volatile和原子性

 

C++中有一个神秘的关键字Volatile。很多时候,Volatile被认为与原子性以及校准(regulation)有关。其实这是不对的,当然存在这样的认识是有历史原因的。Volatile仅仅是防止编译器将值缓存入寄存器(编译器优化、寄存器越多,编译器在其中缓存的数据也越多)。读取Volatile变量意味着永远从内存中读取,Volatile变量的写是直接写入内存中。倘若并发地改变Volatile数据,需要注意这一点。

 

实际上我们并没有这么做,主要是缺乏内存栅栏。某些语言如Java、C#,volatile被赋予一个神奇的状态值来提供校准。不过C++11中并没有这么做。volatile 并没有任何特殊的校准,现在我们知道恰当的校准对原子性来说是必须的。

 

因此,在C++11兼容的编译器没有必要为原子性变量提供 volatile。不过在以往的编译器中,采用volatile还是很有必要的,如果你想自己实现原子性。在下面的声明中:

 

class atomic_int {

    int m_nAtomic;

  //….

};

 

编译器有权优化 m_nAtomic 调用(尽管是间接调用)。因此,时常在此声明一个int volatile m_nAtomic是很有用的。

 

libcds

 

那么我们能从 libcds 库得到什么?我们已经在x86、amd64、 Intel Itanium и Sparc架构中,以C++11的方式实现了原子性原语。倘若编译器不支持C++11, libcds 可以采用自己的原子性实现。构建无锁数据结构,除去常规的原子性写读,最主要的基本类型就是CAS,而DwCAS用的很少。截止目前,libcds库还没有DCAS和multi-CAS的实现,但未来这些都很有可能出现。很多研究表明,唯一的制约因素是,实现DCAS 算法[Fra03]太困难了。尽管如此,我已经提到个别高效的准则在无锁的世界已经存在。目前效率低下的是硬件部分,相信随后的日子针对不同的硬件和任务,这些都会变得极其高效。

 

接下来的基础篇文章,我会详尽介绍内存序列化和内存栅栏。

 

本文引用:

 

[Cha05] Dean Chandler Reduce False Sharing in .NET, 2005, Intel Corporation

 

[Fra03] Keir Fraser Practical Lock Freedom, 2004; technical report is based on a dissertation submitted September 2003 by K.Fraser for the degree of Doctor of Philosophy to the University of Cambridge, King’s College

 

[McKen05] Paul McKenney, Thomas Hart, Jonathan Walpole Practical Concerns for Scalable Synchronization

 

[Mic04] Maged Michael ABA Prevention using single-word instruction, IBM Research Report, 2004

来源: 伯乐在线 - 乔永琪 

英文出处:khizmax

本文转载自:来源: 伯乐在线 - 乔永琪 

oschina_00
粉丝 5
博文 101
码字总数 0
作品 0
廊坊
私信 提问
无锁数据结构(基础篇):内存模型

本文由伯乐在线 -乔永琪 翻译,蒋生武 校稿。未经许可,禁止转载! 英文出处: khizmax。欢迎加入 翻译组。 假设在前文中大家已窥探了处理器的内部结构。为了并行代码的正确执行,我们需提示...

伯乐在线
2016/06/17
0
0
求你了,再问你Java内存模型的时候别再给我讲堆栈方法区了…

GitHub 4.1k Star 的Java工程师成神之路 ,不来了解一下吗? GitHub 4.1k Star 的Java工程师成神之路 ,真的不来了解一下吗? GitHub 4.1k Star 的Java工程师成神之路 ,真的确定不来了解一下吗...

Hollis
07/02
0
0
并发三:J.U.C---CAS与原子变量

CAS CAS(Compare-And-Swap)是CPU的原子指令,中文翻译成比较交换,汇编指令为CMPXCHG。CAS操作包含三个操作数内存值V、预期原值A和新值B,当且仅当预期原值A和内存值V相同时,将内存值V修改为...

wangjie2016
2017/06/19
0
0
Java并发问题--乐观锁与悲观锁以及乐观锁的一种实现方式-CAS

首先介绍一些乐观锁与悲观锁: 悲观锁:总是假设最坏的情况,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人想拿这个数据就会阻塞直到它拿到锁。传统的关系型...

Java架构
2018/07/11
0
0
尝试Java加锁新思路:原子变量和非阻塞同步算法

进年以来,并发算法领域的重点都围绕在非拥塞算法,该种算法依赖底层硬件对于原子性指令的支持,避免使用锁来维护数据一致性和多线程安全。非拥塞算法虽然在设计上更为复杂,但是拥有更好的可...

登高且赋
2017/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS苹果应用IPA一键签名工具及重签教程

开心签名工具,是一款跨平台ios签名和重签名工具。 同时支持在windows、linux、mac运行,数据同步,方便使用及管理! 开心重签名工具官网 功能特点 1、支持图形界面及命令行重签(部署到服务...

tintong
6分钟前
2
0
2.4G有源卡核心芯片供应商

有源2.4G RFID的防盗标签,在与无源标签相比较,通信距离远,通信时效高。我司的SI24R2E这颗芯片专门为2.4G有源标签而设计,具有低功耗,发送距离远,厂商设计简单等优势;广泛应用于现在城市...

文刀石
11分钟前
2
0
设置Ubuntu16.04启动为命令行界面

1. 修改/etc/default/grub文件,将GRUB_CMDLINE_LINUX_DEFAULT设置成”quiet splash 3” 2. 使用命令update-grub使得在/boot下重新生成GRUB2配置文件。 3. 重启...

JosiahMg
12分钟前
2
0
C++基础知识点

计算机语言 计算机不能理解高级语言,只能理解机器语言,必须要将高级语言翻译成机器语言,翻译的方式有两种,一种是编译,一种是解释 解释型语言,在运行程序时进行翻译,每个语句在执行时逐...

大瑞清_liurq
18分钟前
2
0
EFCore 多条数据更新不能同时savechanges()的解决方法

1 在ModelContext定义下增加var transaction = ctx.Database.BeginTransaction(); 1.2 在最后一个SaveChanges()后增加transaction.Commit(); 3 在finally的if (sMsgCode != "")分支中增加tra......

_Somuns
22分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部