谈一谈STM(软件事务内存)

coredump

wiki定义:http://zh.wikipedia.org/wiki/%E8 ... 1%E5%86%85%E5%AD%98
在计算机科学中，软件事务内存 (STM) 是一种 模拟数据库事务的并发控制 机制来控制在并行计算时对共享内存的访问控制。它是锁的一种替代机制。在STM中，一个事务指的是一段读、写共享内存的代码。这些读写操作在逻辑上是一个独立的单元，其中间状态对于其它的事务而言，是不可见的。

随着多核时代的到来, 更方便更有效率的并发编程成为迫切需要，Herb Shutter著名的“免费的午餐已经结束”是对软件界这一趋势的最好注脚。不过，现存的软件开发工具(语言，库，算法)显然都还没有完全准备好，对于编程语言来说，应对并发编程的普遍做法是多线程+锁的实现方式，不过这样的实现既低效丑陋又容易出错，
Andrei Alexandrescu曰：泛型编程难、编写异常安全的代码更难，但跟多线程编程比起来，它们就都成了娃娃吃奶。

锁是另多线程编程困难的主要原因，软件事务内存就是业界大牛们企图跨过锁这座大山的最新尝试。 从wiki的列表上可以看到STM的实现已经有了一大堆了，比较值得一说的有：
Intel STM Compiler Prototype Edition  用特殊的编译器对C++进行扩展以支持STM语义。
Boost.STM, 原名DracoSTM ,这个实现将会进入Boost 1.39.0的官方发布版，值得一看。

在各种编程语言中，Haskell在语言中内置了对STM的近乎完美支持，Beautiful Code这本书由专门的一章来讲解Haskell中的STM实现。
此外，还有用硬件来实现STM语义的，称为HTM,比如Sun最新的Rock处理器将正式支持事务型内存，还有软硬结合的，称为HyTM。


但是STM也并不就是能够解决一切的银弹，缺点和不足也有很多，有些是由于STM的固有缺陷，有些缺点相信随着各种实现的成熟会逐步消失，所以总体来说STM走向了解决问题的正确一步，将会逐步走出实验室,成为多核时代的主流技术。

coredump

可以看出在多处理器环境下，STM相对于Locks性能优势非常明显，单CPU下overhead有一些，尤其是线程数较多时。

coredump

TBoost.STM的实现相当精简，居然就用5个interface就解决了问题：
1. Initializes STM, always first call

1. void transaction::initialize()

复制代码

2. Initializes thread, call per thread before using tx

1. void transaction::initialize_thread()

复制代码

3. Constructs a transaction object
Executes <compound> until successful

1. atomic(<transaction name>) { <compound> } end_atom

复制代码

4. Perform tx write; returns ref of object to write

1. template <typename T> T& transaction::w(T&)

复制代码

5. Perform tx read; returns const ref of object to read

1. template <typename T> T const& transaction::r(T const&)

复制代码

coredump

一个TBoost.STM的C++代码例子：

native_trans<int> C = 1000;

int deposit_and_balance()
{
  int c = 100, bal = -1;
  atomic (t)
  {
    t.w(C) += c;
    bal = t.r(C);
  } end_atom
  return bal;
}

coredump

native_trans是用于内建基本类型的，对于类类型，需要使用transaction_object,适用于transaction_object的类必须：1. 有default和copy 构建器
2. operator=
3. 使用CRTP模式进行类声明


例子：

class str_trans : public transaction_object <str_trans> //要求3
{
  char *b_;
public:
   str_trans() : b_(0) {} //要求1
   str_trans(str_trans const &rhs) : b_(0) { cp(rhs.b_); }
   str_trans& operator=(str_trans const &rhs)//要求2
   { cp(rhs.b_); return *this; }
   void cp(char const *buf)
   {
      delete [] b_; b_ = 0;
      if (0 == buf) return;
      b_ = new char [strlen(buf)+1]; strcpy(b_, buf);
   }
   char const * buf() const { return b_ ? b_ : “”; }
   ~str_trans() { delete [] b_; }
};

coredump

transaction_object的使用和native_trans几乎一样

using namespace std;
str_trans str;

void read_str(string &s)
{
   atomic(t) {
      s = t.r(str).buf();
   } end_atom
}

void write_str(string const &s)
{
   atomic(t) {
    t.w(str).cp(s.c_str());
   } end_atom
}

coredump

TBoost.STM的高级使用,(前面说只有5个interface是骗人的,当然80%情况下前面5步足够用了)

1. 对于不可撤消操作的处理(I/O类操作)

1. transaction::make_irrevocable()

复制代码

If fails, throws exception, Otherwise, guaranteed to commit

例子：

void hello_world() {
  atomic(t) {
    write_str((string)
       "hello concurrent world");
    string s; read_str(s);
    t.make_irrevocable();
    cout << s.c_str();   //cout是不可撤消的Output操作，前面的make_irrevocable()保证了一旦出错cout这行不会被执行
  } end_atom
}

coredump

高级2. Do not use new and delete for txes!
To create memory

1. T* new_memory()T* new_memory_copy(T const &rhs)

复制代码

To destroy memory

1. delete_memory(T &rhs)

复制代码

高级3：before_retry

1. atomic(<tx>) { <compound> }before_retry { <compound> }

复制代码

作用：一旦tx第一次提交失败，会自动重试，before_retry的代码块会在tx重试前执行，一般用来做cleanning up,改变tx的优先级等。
如：

template <typename C> bool algo::move
(C &l1, C &l2, C::node_type const &v)
{
  bool r = false;
  atomic(t) {
    if (l1.lookup(v) && !l2.lookup(v))
    {
      l1.remove(v); l2.insert(v); r = true;
    }
  } before_retry { r = false; }
  return r;
}

高级4：tx不支持reference!
a bad idea

1. native_trans<int> &x = t.w(X);

复制代码

an even worse idea!

1. native_trans<int> &x = t.r(X);

复制代码

不过可以使用read_ptr和write_ptr代替：

1. boost::stm::read_ptr(transaction &t, T)boost::stm::write_ptr(transaction &t, T)

复制代码

至于不能使用reference的原因，主要是直接的reference无法处理atomic嵌套的情况，而read_ptr，write_ptr把transaction也作为参数传递过去了，这样如果嵌套使用,则可以自动检测出来。

coredump

结论：

STM很好很强大, TBoost.STM的实现也的确很优雅，不过仍然有不少很tricky的地方，特别是在处理pointer和reference的时候。

在被Boost选为候选STM库之后, TBoost.STM已经比它的前身DracoSTM 快了10倍, 可见这帮哥们干活还是挺卖力的，TBoost.STM的开发目标是2010年随着Boost 1.39一起推出Boost.STM 1.0版，如果你等不及了，可以到Boost的sandbox的svn版本仓库中下载正在开发中的Boost.STM.