mutex 问题(二)

mutex 问题看起来如此之简单,求解起来却是如此之困难。软件的实现说到底是需要硬件的支撑,atomicity 和 sequential consistency 是两个很容易混淆的概念,开始这部分之前讨论一些这两者的关系,参考这篇 paper:简单的说来就是为一个问题实现这两个不同的 consistency model 时前者理论上更加 expensive。这篇文章之前有文章找到了 sequential consistency 的一个充分条件,这个条件也蕴含了 atomicity,于是可能产生一种错觉,似乎 atomicity 要“弱”于后者。

atomicity 也称为 linearizability,其含义指一个操作对系统来说是“即刻发生的”,具有所谓的 atomic(原子性)、linearizable(可线性化)、indivisible(不可分割性)与 uninterruptible(不可中断性)。通常这类行为或者成功或者失败。前面讨论过 sequential consistency,这两者其实前者要求更高,及 sequential consistency 要求存在的序同时也保持全局、外部的顺序的时候为 linearizability。很自然这个定义上来看 atomicity 更难以并行,其好处是之一我们可以从这个序的要求上看出来,之二是它是是 compositional 的,意味着可以将两个 linearizable 的实现组合获得的还是 linearizable 的实现,而 sequential consistency 不具有这个性质。

从这点看 Sutter 的例子似乎有点不大合适?毕竟硬件现在走的是 linearizability 的路线,软件上似乎更崇尚 sequential consistency?这个问题留到后面再想。这里我们看看大牛 Leslie Lamport 的 Bakery algorithm。

Bakery Algorithm

这个算法来自下面的例子:日常生活中经常有排队的例子,Lamport 举的是烘焙店里面很多顾客前来买各种东西,进门时领号,叫到号之后就可以去买东西了。很自然顾客就是线程,那么什么是出号的设备呢?日常生活中出号的设备是独占性的,这点本身就跟 mutex 有关了,我们只是将一般的 mutex 转换成为了对一个 int 独占性的访问。实际实现这个算法的时候可以用另外的策略:

  • 数组 entering 表示对应 thread 的 intention,数组 number 表示对应 thread 领取的号
  • 进入前需要设置 entering 对应 bit 为 true,然后为 number 对应位取号,这时遍历该数组取最大的 + 1
  • 虽然仍然可能存在两个 thread 对应的号一样,我们可以用 thread 编号(或者 id)来决定谁优先

很有意思的地方是这个算法不需要 atomicity,Dekker’s algorithm 和 Peterson’s algorithm 如果没有 atomic,很快就能看到出现的问题,但是 Bakery algorithm 不存在这个问题,可以玩玩下面的实现:

template <int N>
struct lock_manager {
  std::array<bool, N> entering ;
  std::array<int, N> number ;

  lock_manager () {
    for (int i = 0 ; i < N ; ++ i) {
      entering [i] = false ;
      number [i] = 0 ;
    }
  }

  template <int M>
  struct lock {
    lock_manager<M>& m ;
    int id ;

    lock (lock_manager<M>& lm, int i) : m (lm), id (i) {
      m.entering [id] = true ;
      m.number [id] = max () + 1 ;
      m.entering [id] = false ;
      for (int j = 0 ; j < M ; ++ j) {
        while (m.entering [j]) {}
        while (m.number [j] != 0 && (m.number[j] < m.number[id] ||
               (m.number[j] == m.number[id] && j < i))) {}
      }
    }

    inline int
    max () {
      int ma = 0 ;
      for (int i = 0 ; i < M ; ++ i) {
        if (m.number [i] > ma) ma = m.number [i] ;
      }
      return ma ;
    }

    ~lock () {
      m.number [id] = 0 ;
    }
  } ;

  lock<N>
  get (int id) {
    return lock<N> (*this, id) ;
  }
} ;

当然比较有意思的问题是为什么 Bakery algorithm 不需要 atomicity 呢?这个准备先读读 Leslie Lamport 大牛的相关著作再说 🙂

Leslie Lamport 在 Amazon 的讲座
Leslie Lamport 在 Amazon 的讲座

关于硬件的一些知识

感谢 peter 同学提供的科普文章。摘记一些要点在下面:

  • CPU 的速度与访问内存的速度差距巨大,为此 CPU 设计者使用了 cache,为每个 CPU/core 提供一个相对快速访问的存储空间,有了 cache 意味着存在 replication,这本质上跟分布式系统面临的问题类似,只是单机上我们可以使用一些硬件上的东西来提供某种 consistency model
  • cache 类似一个 hash table,但是其 hash 比较简单,通常是地址计算出来的 bit set
  • 为了使得 CPU 访问一致的数据,人们通过 cache coherence protocol 来同步 cache 里面的数据,常见的协议是 MESI 及其变种
  • MESI 对应四个状态:modified(被修改过,要求对应内存不存在其他 cache 中)、exclusive(尚未被修改,但是仅有这个 CPU 拥有 copy,对应的也是 up-to-date 的数据)、shared(可能被多个 CPU 拥有,此时可以读但不可以写) 和 invalid(表示数据非法,也就是可以看成不可用);通常 CPU 需要用个 2bit 表示这四个状态;状态之间的转移通过某种 meesage 来实现
  • 一般对 MESI 的简单实现都是没有实际价值,这是因为发生写操作往往会带来很长时间的等候:首先需要写的 CPU 需要让别的 CPU 将状态转换到 invalid,收到 response 以后才能进行实际的写,为此硬件专家使用了 store buffer(Sutter 同志也说过,modern CPU 如果没有 store buffer 就不值得买,可见这个 feature 对整体性能的影响是不可忽略的)
  • store buffer 的作用是让 CPU 需要写的时候仅仅将其操作交给 store buffer,然后继续执行下去,store buffer 在某个时刻就会完成一系列的同步行为;很明显这个简单的东西会违背 self consistency,因为如果某个 CPU 试图写其他 CPU 占有的内存,消息交给 store buffer 后,CPU 继续执行后面的指令,而如果后面的指令依赖于这个被写入的内存(尚未被更新,这个时候读取的值是错误的)就会产生问题,所以实际实现 store buffer 可能会增加 snoop 特性,即 CPU 读取数据时会从 store buffer 和 cache 两处读
  • 即便增加了 snoop,store buffer 仍然会违背 global memory ordering,导致的解决方案是 memory barrier:我们知道程序员书写两个写操作的时候,隐含的假定是如果能观察到后一个写的结果,那么前一个写的结果势必也会发生,这是一个非常符合人直觉的行为,但是由于 store buffer 的存在,这个结论可能并不正确:这是因为如果观察线程位于另一个 core,首先读取后一个写(该地址并不在 cache 内)需要向写入线程所在 core 要对应地址的值,由于该 core 从 store buffer 返回了新值的时候这个 buffer 里面的写操作可能尚未发生,所以观察线程在获取了后一个写的最新结果时,前一个写的结果依然无法观察到,这违背了 sequential consistency 的假定,往往程序员更倾向于这个 consistency model 下的 reasoning
  • 硬件 level 上很难揣度软件上这种前后依赖关系,因此往往无法通过某种手段自动的避免这种问题,因而只有通过软件的手段表示(对应也需要硬件提供某种指令来支持这种语义),这个就是 memory barrier,从硬件上来看这个 barrier 就是 CPU flush 其 store buffer 的指令,那么一种做法就是提供给程序员对应的指令(封装到函数里面)要求在合适的时候插入表达这种关系,另一种做法就是通过某种标识让编译器翻译的时候自动的插入这个指令
  • 往往 store buffer 都很小,针对连续写操作力不从心;类似的情况也发生在碰到 memory barrier 之后;开始写之前首先需要 invalidate 其他 cache 里面的数据,为了加速这个过程硬件设计者又加入了 invalidate queue,这个 queue 将 incoming 的 invalidate 消息存放,立即返回对应的 response 这样以便发起者能尽快做后面的事情,而这个 CPU 可以通过 invalidate queue 后续处理这些内存
  • invalidate queue 的存在会使得我们有更多的地方需要 memory barrier(理由与 store buffer 类似)
  • 实际 memory barrier 又有一些细分,如 read/write 的,软件上会通过 smb_mb/rmb/wmb 等表示,对应的硬件指令不同平台下各不相同
  • 实际实现的时候由于某些指令集之间的关系使得 memory barrier 的实现不可能做到最优,很多常见的平台都使用了简单粗暴的 bus 锁(x86、amd64、armv7),这也就是 Sutter talk 里面认为硬件平台往往提供了一些“过度”的指令的原因,最终软件需要的 sequential consistency 尽管得以实现,但是产生了一些不必要的代价
  • memory barrier 不是一个必需的东西,但是似乎如果有 real-time 的 requirement 似乎就不能避开,这一点有待证实

一个简单的例子:

int a = 0, b = 0 ;

// on core 0
void foo () {
  a = 1 ;
  b = 1 ;
}

// on core 1
void bar () {
  while (b == 0) ;
  assert (a == 1) ;
}

为了保证在 store buffer 的存在下这个能 work 我们得在 a = 1 之后加上 memory barrier,而 invalidate queue 的存在使得我们得在 while 之后加上 memory barrier。

另外的一些感受:硬件设计很多时候感觉是将某些代价高的操作分摊到其他的操作上避免出现较长的等待:比如写操作通过 store buffer 加速,然后将读操作修正为从 store buffer + cache,转移了一部分 cost (如果真有的话)到读上;invalude queue 的存在也是类似。

——————
That which was torn of beasts I brought not unto thee; I bare the loss of it; of my hand didst thou require it, whether stolen by day, or stolen by night.

Advertisements
mutex 问题(二)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s