読者です 読者をやめる 読者になる 読者になる

Boost.Lockfree ロックフリーキューの制限

C++

Boost 1.53.0時点のロックフリーキューは、要素型Tがtrivially copyable(memcpy可能な型)であることを要求します。そのため、ユーザー定義型の多くはロックフリーキューに格納できません。

#include <boost/lockfree/queue.hpp>

int main()
{
    boost::lockfree::queue<std::string> que(3); // エラー!
}
In file included from main.cpp:3:0:
boost_1_53_0/boost/lockfree/queue.hpp: In instantiation of 'class boost::lockfree::queue<std::basic_string<char> >':
main.cpp:7:41:   required from here
boost_1_53_0/boost/lockfree/queue.hpp:79:5: error: static assertion failed: (boost::has_trivial_destructor<T>::value)
boost_1_53_0/boost/lockfree/queue.hpp:83:5: error: static assertion failed: (boost::has_trivial_assign<T>::value)

これは、Boost.Lockfreeのキューの実装方法としてTagged Pointerが採用されていることによる制限です。
参照: lock-freeアルゴリズムにおけるメモリ回収 - yamasaのネタ帳


Hazard Pointerの方式を採用できればこの問題は解決するのですが、Hazard Pointerは特許が取得されていることにより、採用できないのだそうです。

as for the problem of memory reclamation: this is not a trivial issue and unfortunately the published algorithms (hazard pointers and pass-the-buck) are patented.

Re: 【Review】 Lockfree review: today is the last day

特許 US 2004/0107227 : Method for efficient implementation of dynamic lock-free data structures ...


なので、Boost.Lockfreeのロックフリーキューに非trivially copyableな型を格納したい場合、newした生ポインタをpushし、pop時にdeleteすることになります。


修正履歴:
2013/02/13 21:26 :「Boost.Lockfreeのロックフリーコンテナ」と記載していましたが、スタックの方にはtrivially copyableの制限がなかったので、「Boost.Lockfreeのロックフリーキュー」に修正しました。