mutex 问题(一)

所谓 mutex 问题就是 mutual exclusion 问题,几个 process/thread 为了进入 critical region 而避免 race condition 导致的问题时需要解决这个问题。与 distributed 问题相比较这个问题里面允许有 shared memory,这里我们看看几个常见的解决这个问题的算法(参看这个部分这个评论):

Dekker’s Algorithm

作为最早解决 mutex 问题的算法,尽管不是最好,但仍然提供了理论上的指导意义:

  • 用一个 flag[2] 标定意图,线程开始进入 critical region 时,通过这个数组表现自己的意图
  • 用一个 turn 表示轮回,即当前应该哪个线程可以进入 critical region
  • 进 入 critical region 的基本步骤为:设置自己的 flag 表达意图,检查 turn 直到不指向其他人为止。检查包括如果没轮到自己,先取消自己的 intention(将对应 flag 取消掉),然后 busy waiting 直到 turn 指向自己,此后重新表达自己的 intention(设置对应的 flag)。检查过程包在循环里。
  • 离开的基本步骤为:将 turn 指向对方,取消自己的 flag

值 得注意的是该算法只在 flag/turn 均为 atomic 类型(即满足 sequential consistensy)的情况下才能 work,我们知道现代 CPU 存在 cache,因此一个线程对 turn/flag 的修改可能不能反映到另一个 core 上的线程里,这就会导致问题,下面是一个简单的实现:

#include <atomic>

struct lock_manager {
  std::atomic_bool flag [2] ;
  std::atomic_int turn ;

  lock_manager () {
    flag[0] = false ; flag[1] = false ;
    turn = 0 ;
  }

  struct lock {
    lock_manager& manager ;
    int id ;

    lock (lock_manager& m, int i) : manager (m), id (i) {
      int other = (i == 0 ? 1 : 0) ;
      m.flag [id] = true ;
      while (m.flag [other] == true) {
        if (m.turn != id) {
          m.flag [id] = false ;
          while (m.turn != id) {
            // busy wait
          }
          m.flag [id] = true ;
        }
      }
    }

    ~lock () {
      manager.turn = (id == 0 ? 1 : 0) ;
      manager.flag [id] = false ;
    }
  } ;

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

下面是一个测试的代码

#include <iostream>
#include <thread>
#include <chrono>

void
foo (lock_manager& m, int id) {
  std::chrono::milliseconds t (1) ;
  for (int i = 0 ; i < 50; ++ i) {
    auto lk = m.get (id) ;
    std::cout << "hello world from thread "
              << std::this_thread::get_id () << "\n" ;
    std::this_thread::sleep_for (t) ;
  }
}

int
main (int argc, char* argv[]) {
  lock_manager m ;
  std::thread t1 (foo, std::ref(m), 0) ;
  std::thread t2 (foo, std::ref(m), 1) ;
  t1.join () ;
  t2.join () ;

  return 0 ;
}

如果没有 atomic 锁就会失效,比如产生如下的输出

hello world from thread hello world from thread 140054655059712
140054646667008

而正确的实现不会出现重叠行。

Peterson’s Algorithm

觉得 Peterson’s algorithm 和 Dekker’s algorithm 有点像,前者可以推广到多个线程问题上,对应又称为 Filter Algorithm,核心想法与 Dekker 的不大一样,在 N 个 threads 同时访问时,我们使用 level 数组记录对应 thread 当前的级别,用 waiting 数组记录在对应 level 上等候的 thread,

  • 每个 thread 都从 level 0 开始一直走到 level N – 2
  • 在第 l 个 level,如果多个线程同时写 waiting,最后 waiting[l] 的值是最后写入那个线程的,它将被 block 在这个 level,(因为后面的 thread 一定会写入自己 level 更大的 level)
  • 在 l + 1 个 level 我们就只有 N – l 个线程重复以上过程,这样到第 N – 1 个 level 时,我们 block 了 N – 1 个线程,最后那个线程结束了这个循环,进入了 critical region
  • 如果同时参与的线程数不足 N 个,当最后一个线程设置了 waiting 后不存在其他 level 高于自己的值,于是跳出 block 继续设置更高的 level 直到结束
  • 线程退出 critical region 后重置 level,这样其他等候的线程就可以被 unblock
template <int N>
struct lock_manager {
  std::array<std::atomic_int, N> level ;
  std::array<std::atomic_int, N-1> waiting ;

  lock_manager () {
    for (int i = 0 ; i < N ; ++ i) level [i] = -1 ;
    for (int i = 0 ; i < N - 1 ; ++ i) waiting [i] = -1 ;
  }

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

    lock (lock_manager<M>& lm, int i) : m (lm), id (i) {
      for (int l = 0 ; l < M - 1; ++ l) {
        m.level [id] = l ;
        m.waiting [l] = i ;
        while (m.waiting[l] == i && exist (l)) {}
      }
    }

    inline bool
    exist (int l) {
      for (int i = 0 ; i < M ; ++ i) {
        if (i == id) continue ;
        if (m.level [i] > l) return true ;
      }
      return false ;
    }

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

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

小结

即 便是如此简单的 Dekker’s Algorithm 也非常难写得尽善尽美,最终的实现依靠了 atomic,这也是硬件上提供的一套保证 sequential consistency 的概念,等价于 Java 里面的 volatile 关键字。想起 Sutter 大牛的 talk,继续叹服一下。今天 mentor 碰到另外位做 distributed system 的大牛,两人就类似的东西稍微说了两句我已经跟不上他们的思路了,都是程序员差别还是老大了。做系统总归还有很多可以学习的。

——————
Now Rachel had taken the images, and put them in the camel’s furniture, and sat upon them. And Laban searched all the tent, but found them not.

Advertisements
mutex 问题(一)

一个有关“mutex 问题(一)”的想法

    1. zt 说:

      话说俺说人牛并不意味着俺“崇拜”人,我评估这个人牛当然是个主观的东西,但是我不认为我对这些人的评估“过分”了,就说那位 distributed system 方面的大牛,作为 distinguished engineer,AWS 巨多产品的核心抑或有他贡献的代码或者设计时受他的影响,我有幸听过几个他给的相关的 talk,分析和设计都非常 impressive,不管什么公司里面估计你也找不到几个啊

      1. t.k. 说:

        去崇拜毛吧,新中国很多决定都是受他的影响,我有幸听过他的文革运动,规模和影响都非常impressive,不管什么国家这样的老大你也找不到几个啊

      2. hxtang 说:

        “牛”不就一表示赞许某方面能力的称呼,至于非要跟崇拜划等号么。
        承认别人某方面比自己强,至少多个学习的动力,比如lz就觉得系统还是有很多东西需要学的,有什么不好。要是反过来知道点东西就觉得别人都不过如此了,不知道还能从哪里学东西。

      3. t.k. 说:

        我承认我这些言论有我偏见之处,但归根结底因为我看到太多同胞的博客上种种牛人被提及,对比其他国家的,这种思维惯势尤其明显,大家缺乏务实真诚的品质。若能启发各位,就不枉我在这里的乱扯。其实我观咱们和其他国家的思维差距,就在于批判思维。忘大家以后如遇佩服的人放在心底勉励自己,尽量不要把对个人的钦佩之情表在书面,让后人感觉不可超越、不可怀疑。

      4. zt 说:

        t.k. 同志既然这么崇拜毛,连文革都要各种赞许,看来不大分得清楚是非啊

        将称赞和崇拜,尤其是和盲目崇拜混淆,见人称赞他人就扣帽子,言必称拯救国人,同志怀着圣人的心,有没有圣人的品呢?

  1. lcn 说:

    I think all the problem of your “跟不上他们的思路了” is about the levels of abstraction. Different algorithms are actually handling different assumption/implementation of the hardware. You know the hardware, then you know the algorithms; you abstract the hardware, then the algorithms for the lower level don’t matter anymore. Don’t try to know everything, only invest on the level of abstraction that interests you the most.

  2. t.k. 说:

    Because you only care about software, because you want to stand on a “high” level, you think it is all about algorithm, unfortunately, you cannot even ensure atomicity when you only use “algorithm” (i.e. Dekker’s Algorithm). What makes things worse? You want to explain how to achieve atomicity in your blog whereas you do not even know the basic knowledge and do not care about the under level. In fact, these thing can be done in just a few lines of assembly code, instead of generating a lot of shit by a c++ compiler. BTW. If you truly want to be learned, stay away from idolatry.

    1. zt 说:

      这是一个 CAS 的典型例子,也就是 C++11 现在加入 atomic 的原因

      硬件上通过特殊的指令集实现锁可以对一个主机上单进程多线程提供便利,兴许多进程也能有类似的概念,但是做到 distributed system 里面怎么“锁”就会有更多不同的策略实现不同需求的锁。

      不过 Bakery algorithm 似乎是不用 CAS 的… http://en.wikipedia.org/wiki/Bakery_algorithm

    2. zt 说:

      另外,上锁这个事情肯定不是一条 CAS 实现的,跟具体的体系结构也有关系

      x86 的指令集这方面的不是特别到位的,ARMv8 和 IA-64 这方面好一些

      1. t.k. 说:

        无论是CAS、还是test&set、还是最常见的LL and SC,都是设计出来为了保证两个instr之间的原子性,他们之间都可以等效替换。并且,他们是最基础的,也就是说他们之间随便挑一个都能实现barrier(通过计数),barrier在他们的层次之上。实际上,现代很多锁的硬件实现根本没有锁bus,而是在cache协议(MESI, MESI, MOESI)的基础上实现的。另外,store buffer/ reorder buffer也显然并没有破坏global memory ordering,锁为什么出现,是因为多线程,不是因为单个processor的乱序执行。reorder buffer只是破坏了单个线程里的顺序。全局的顺序(global memory ordering)也没有单一的定义(本来他们就不是一个线程的,你怎么能规定指令谁在谁的前面??显然要具体程序具体分析),学术上根据Memory Consistency Models来定义不同松紧程度的global memory ordering。实际上,全局顺序问题的出现,完全是因为多线程的出现加上需要共享变量。为什么有多线程?因为单核的潜力和功耗已经做到极致了,只能通过Multiprocessor,也就是当今CPU发展的发力点。

  3. zt 说:

    MESI 实际根本就不能在多线程下 work 的好吧
    http://en.m.wikipedia.org/wiki/MESI_protocol
    最终还是要靠 membar,似乎我了解的x86最常见的就是full fence锁bus,AMD的不熟悉

    另外参考这里的讨论
    http://stackoverflow.com/questions/2972389/why-is-compareandswap-instruction-considered-expensive

    至于其他的部分,你的显然对我来说并不显然,而你解释正确的地方,你不说我也知道(分界线在实际上),还是用你批判国人的热情上点干货吧,欢迎言之有物的评论

发表评论

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