boost 的 lockfree

boost.lockfree 提供了几个 lockfree 的数据结构,包括先进先出的 fifo、后进先出的 stack 和循环队列 ringbuffer(前面两个是 multi-producer multi-consumer 的模型,后者是 single-producer single consumer 的模型)。首先讲几个相关的概念:

  • wait free:所有的并行操作可以在有限步内完成,因此可以为最坏情况下估计最大操作次数
  • lock free:某些并行操作可以在有限步内完成,因此理论上存在某些步骤可能无法进行下去,但是实际操作中出现的概率非常小
  • obstruction free:一个并行操作在没有别的操作干涉下可以在有限步后结束

boost.lockfree 的目标是为多线程编程提供一些分发消息的数据结构,fifo 和 stack 都是 lock free 的,而 ringbuffer 是 wait free 的。实现的原理并不是依赖 OS 提供的 locking mechanism,而是使用 CPU 提供的 atomic operation(具体来说就是 compare and swap)。与 STL 提供的 container 不同在于 lockfree 的容器都是固定大小的,以此避免 runtime 时重新分配内存。下面是个来自文档的简单例子。

#include <boost/thread/thread.hpp>
#include <boost/atomic.hpp>
#include <boost/lockfree/fifo.hpp>
#include <iostream>

boost::atomic_int producer_count (0);
boost::atomic_int consumer_count (0);
boost::atomic<bool> done (false);

boost::lockfree::fifo<int> fifo ;

const int iterations = 10000000;
const int producer_thread_count = 4;
const int consumer_thread_count = 4;

void
producer (void) {
  for (int i = 0; i != iterations; ++i) {
    int value = ++producer_count;
    while (!fifo.enqueue(value))
      ;
  }
}

void
consumer(void) {
  int value;
  while (!done) {
    while (fifo.dequeue(value))
      ++consumer_count;
  }

  while (fifo.dequeue(value))
    ++consumer_count;
}

int
main (int argc, char* argv[]) {
  using namespace std;
  cout << "boost::lockfree::fifo is ";
  if (!fifo.is_lock_free ())
    cout << "not ";
  cout << "lockfree" << endl;

  boost::thread_group producer_threads, consumer_threads;

  for (int i = 0; i != producer_thread_count; ++i)
    producer_threads.create_thread(producer);

  for (int i = 0; i != consumer_thread_count; ++i)
    consumer_threads.create_thread(consumer);

  producer_threads.join_all();
  done = true;

  consumer_threads.join_all();

  cout << "produced " << producer_count << " objects." << endl;
  cout << "consumed " << consumer_count << " objects." << endl;

  return 0 ;
}

最后说一下的是 boost.lockfree 并不是个 boost 官方的库,需要的话在这里通过 git 下载吧,文档在此。这个也是仅有头文件的,只需要把 boost 目录 copy 到 include path 里面。上面的例子由于使用了 boost.thread 需要与 libboost_thread 连接。

——————
In the selfsame day was Abraham circumcised, and Ishmael his son.

Advertisements
boost 的 lockfree

发表评论

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