yohhoyの日記(別館)

もうちょい長めの技術的メモをしていきたい日記

Boost.Contextでファイバーライブラリを実装してみた

Boost 1.50.x候補のBoost.Contextライブラリを利用して、一風変わったファイバーライブラリを作ってみたというお話です。(注意:Boost.ContextはBoost 1.49.0の正式リリースには含まれないため、svnレポジトリのtrunkからチェックアウトする必要アリ)

注意:2012年5月現在、Boost.Contextの破壊的API変更により実装コードはコンパイルできなくなっています。id:FlastさんのBoost.Contextの怒涛の変更も参照ください。

何これ?何ができるの?

一言で表現すると「単一スレッドで動作するスレッドライブラリ」です。

これだけだと白い目で見られそうなので…もうちょい説明的な表現では「C++11標準ライブラリ相当の同期プリミティブ群を提供する、ノンプリエンティブなスレッドライブラリ」となるでしょうか。さらに協調的同期プリミティブとしてのミューテックス(mutex)、条件変数(condition variable)も併せて提供します。

例えば下記コードのように、マルチスレッドプログラムと同じ構造で記述された生産者-消費者パターンが、ファイバーライブラリ上ではシングルスレッドアプリケーションとして動作します。ちなみに、このコードでfiber名前空間→std名前空間, fiberクラス→threadクラスへと単純置換すると、そのままマルチスレッドアプリケーションになります。(サンプルコード全体はhttps://gist.github.com/2342248

// 上限付きFIFOキュー
template <class T, std::size_t N>
class bound_queue {
public:
  typedef T value_type;
  bound_queue() : q_(N) {}
  void push(value_type data)
  {
    fiber::unique_lock<fiber::mutex> lk(mtx_);
    cv_pop_.wait(lk, [=]{ return !q_.full(); });
    q_.push_back(data);
    cv_push_.notify_all();
  }
  value_type pop()
  {
    fiber::unique_lock<fiber::mutex> lk(mtx_);
    cv_push_.wait(lk, [=]{ return !q_.empty(); });
    value_type result = q_.front();
    q_.pop_front();
    cv_pop_.notify_all();
    return result;
  }
private:
  boost::circular_buffer<value_type> q_;
  fiber::mutex mtx_;
  fiber::condition_variable cv_push_;
  fiber::condition_variable cv_pop_;
};
typedef bound_queue<int, 5> QueueType;

// 生産者ファイバー
void producer(QueueType& queue)
{
  for (;;) {
    int data = /*...*/;
    queue.push(data);
  }
}

// 消費者ファイバー
void consumer(QueueType& queue)
{
  for (;;) {
    int data = queue.pop();
    //...
  }
}

前提知識

Boost.Contextはコンテキスト切り替え機能を提供するライブラリです。面倒なので(またの名を説明力不足のため)ここでは“コンテキスト切り替え”の説明は行いません。次の記事/資料などを参照してください。

本ライブラリで提供する“ファイバー(Fiber)”は、コルーチン(Coroutine)/マイクロスレッド(Micro-thread)/軽量スレッド(Lightweight thread)とも呼ばれる協調的マルチタスク機構のための部品です。通常の“スレッド(Thread)”と“ファイバー”との違いは、OSが自動的にスレッドを切り替えて並行処理を実現する(プリエンティブ・マルチタスク)か、プログラマが明示的にファイバーを切り替えて協調的に並行処理を実現する(ノンプリエンプティブ・マルチタスク)と捉えると分かり易いかと。

また、C++11標準ライブラリが提供するスレッド(std::thread)や基本的な同期プリミティブ(std::mutex, std::unique_lock, std::condition_variableなど)の使い方を理解していることを前提としています。

Pros vs. Cons

このライブラリの長所は「C++11標準スレッドライブラリと同じインターフェイスを持つので、マルチスレッド動作へシームレスに移行可能」「プログラムが常に決定的な動作となるので、本物のマルチスレッドアプリに比べてデバッグが容易」あたりでしょうか?なお、“最初からマルチスレッドで良いんじゃ?”というもっともな質問への回答は持ち合わせていません。

一方で、短所は「必ずシングルスレッドで動作するため、マルチコアといったハードウェア並行性を活用できない」「Boostライブラリのsvn-trunkに依存するのでunstable」などです。

ライブラリ設計方針

ライブラリインターフェイスは、C++11標準スレッド関連<thread>, <mutex>, <condition_variable>ヘッダ提供のAPIに可能な限り似せています。ただし、C++11標準スレッドで提供されるタイムアウト系処理(std::this_thread::sleep_for関数、std::timed_mutexクラスなど)は削除しています。これは実行ファイバーの切り替えタイミングはユーザの責任であり、タイムアウト値の指定を行ったとしてもそれを守る仕組みが存在しないためです。

ファイバー間のスケジューリング方式は、単純ラウンドロビンによる「公平(fair)スケジューリング」を採ります。つまりファイバーがブロック中か否かに関わらず、スケジューラは全ファイバーに対し平等に実行機会を与えます。例えば、ロック獲得待ちでブロック中のファイバーであっても順番がくれば起動され、ロック獲得に失敗した場合は即座に次ファイバーへと実行が移ります。

ファイバーライブラリ独自機能として、ファイバーのスケジューリングポリシ変更関数を提供します。2つのポリシ:lazyモードとeagarモードが存在し、ライブラリ規定値はlazyモードとなっています。

  • lazyモード:別ファイバーへのコンテキスト切り替えを可能な限り後回しにする。
  • eagerモード:別ファイバーへのコンテキスト切り替えを可能な限り早期に行う。

スケジューリングポリシ挙動は、新しいファイバー作成時の切り替えが分かり易いかと思います。lazyモードでは新ファイバーへのコンテキスト切り替えが“同ファイバーとのjoin時”まで遅延されますが、eagerモードでは“新ファイバー作成直後”に新ファイバーへとコンテキスト切り替えます。

fiber::fiber fb(&proc);  // eagerモード:fbに切り替え
proc();
fb.join();  // lazyモード:fbに切り替え

提供機能の一覧

C++11標準スレッドライブラリとファイバーライブラリがそれぞれ提供する機能の対応関係は下記の通りです。

C++標準スレッド ファイバーライブラリ
スレッド/ファイバー std::threadクラス
std::this_thread名前空間
fiber::fiberクラス
fiber::this_fiber名前空間
ミューテックス std::mutexクラス
std::recursive_mutexクラス
fiber::mutexクラス
fiber::recursive_mutexクラス
ロック std::lock_guardクラステンプレート
std::unique_lockクラステンプレート
fiber::lock_guardクラステンプレート
fiber::unique_lockクラステンプレート
条件変数 std::condition_variableクラス fiber::condition_variableクラス
(追加機能) fiber::get_scheduling_policy関数
fiber::set_scheduling_policy関数

ポイント解説

実行ファイバーの切り替えは、スケジューリングポリシ設定に応じて下表のコンテキスト切り替えポイントで行われます。

lazyモード eagarモード
fiberコンストラクタ
fiber::join()
mutex::lock()
recursive_mutex::lock()
mutex::unlock()
recursive_mutex::unlock()
condition_variable::wait()
condition_variable::notify_one()
condition_variable::notify_all()
this_fiber::yield()

Boost.Contextライブラリによるファイバー間コンテキスト切り替え実装は、fiber::detail::scheduler::yieldメンバ関数がコアとなります…というか本質的にこの関数が全てです。実装概略は下記の通りです。

  • fiberオブジェクトとコンテキストboost::contexts::contextとを1:1対応させます。なお、プログラムに最初から1つあるファイバーは、便宜上“メインファイバー”と呼びます。
  • ファイバーは 実行状態/コンテキスト未開始状態/yieldメンバ関数内で休止状態 の何れかの状態を取ります。なお、スケジューラから見た未開始状態と休止状態の違いは、コンテキストに対して次に呼ぶべきメソッドがstartかresumeかの差異だけです。また常にただ1個のファイバーが実行状態にあり、プログラム開始直後はメインファイバーがそれに該当します。
  • コンテキスト切り替えでは必ずメインファイバーのコンテキストを経由します。すなわち、yieldメンバ関数がメインファイバー以外のコンテキストで呼び出された場合は、suspendで一旦メインファイバーへコンテキストを戻します。続いてスケジューラが決定した次ファイバーのコンテキストをstart/resumeし、コンテキスト切り替えの後にyieldメンバ関数を抜けます。ちなみに次ファイバーがメインファイバーの場合は、コンテキストのresumeを行わずにyieldメンバ関数を抜けるだけです。

ライブラリコード

ライブラリコードはBoost Software License 1.0で公開しています。動作確認はGCC 4.6.3+Boost svn-trunk rr77773@Ubuntu 11.10で行いました。[https://gist.github.com/2318086

既知の問題とか

このライブラリはコンセプト実証レベルで実装しているため、下記箇所で手抜きをしています。

  • fiberコンストラクタ引数でコピー不可かつムーブ可能な型を扱えない(std::threadはできる)
  • fiber::id型が単にuintptr_tのtypedef(std::thread::idは独立したclass)
  • C++11標準ライブラリ<future>の提供APIに未対応(std::future, std::asyncなど)